# Question
Title: Why are there so many programming languages?
I'm pretty fluent in C/C++, and can make my way around the various scripting languages (awk/sed/perl). I've started using python a lot more because it combines some of the nifty aspects of C++ with the scripting capabilities of awk/sed/perl.

But why are there so many different programming languages ? I'm guessing all these languages can do the same things, so why not just stick to one language and use that for programming computers ? In particular, is there any reason I *should* know a functional language as a computer programmer ?

Some related reading:

# Answer
> 127 votes
Programming languages evolve and are improved with time (innovation).

People take ideas from different languages and combine them into new languages. Some features are improved (inheritance mechanisms, type systems), some are added (garbage collection, exception handling), some are removed (`goto` statements, low-level pointer manipulations).

Programmers start using a language in a particular way that is not supported by any language constructs. Language designers identify such usage patterns and introduce new abstractions/language constructs to support such usage patterns. There were no procedures in assembly language. No classes in C. No exception handling in (early) C++. No safe way of loading new modules in early languages (easy in Java). No built-in threads (easy-peasy in Java).

Researchers think about alternative ways of expressing computations. This led to Lisp and the functional language branch of the language tree, Prolog and the logic programming branch, Erlang and other actor-based programming models, among others.

Over time, language designers/researchers come to better understand all of these constructs, and how they interact, and design languages to include many of the popular constructs, all designed to work seamlessly together. This results in wonderful languages such as Scala, which has objects and classes (expressed using traits instead of single or multiple inheritance), functional programming features, algebraic data types integrated nicely with the class system and pattern matching, and actor-based concurrency.

Researchers who believe in static type systems strive to improve their expressiveness, allowing things such as typed generic classes in Java (and all of the wonderful things in Haskell), so that a programmer gets more guarantees before running a program that things are not going to go wrong. Static type systems often impose a large burden on the programmer (typing in the types), so research has gone into alleviating that burden. Languages such as Haskell and ML allow the programmer to omit all of the type annotations (unless they are doing something tricky). Scala allows the programmer to omit the types within the body of methods, to simplify the programmer's job. The compiler infers all the missing types and informs the programmer of possible errors.

Finally, some languages are designed to support particular domains. Examples include SQL, R, Makefiles, the Graphviz input language, Mathmatica, LaTeX. Integrating what these languages' functionalities into general purpose languages (directly) would be quite cumbersome. These languages are based on abstractions specific to their particular domain.

Without evolution in programming language design, we'd all still be using assembly language or C++.

As for *knowing a functional programming language*: functional languages allow you to express computations differently, often more concisely than using other programming languages. Consider about the difference between C++ and Python and multiply it by 4. More seriously, as already mentioned in another answer, functional programming gives you a different way of thinking about problems. This applies to all other paradigms; some a better suited to some problems, and some are not. This is why multi-paradigm languages are becoming more popular: you can use constructs from a different paradigm if you need to, without changing language, and, more challengingly, you can mix paradigms within one piece of software.

# Answer
> 75 votes
tldr: There is no silver bullet language.

I hope they won't sue me, but here is a pic from one of the Stanford presentations.

When you decide to pick a language, you can pick **only 2 of these 3 features**.

And that is why people are sad and want to invent a superlanguage that will cover all 3 of them.

Actually, there is a huge list of requirements (some of them you can see in other answers) but they just add details to the core features. Additionally, there are historical and political reasons to prefer one language over another.

Combinations of such factors yield a new language.

(*And I've heard that every good programmer should make their own new language ;)*)

# Answer
> 29 votes
The world is filled with things that have many different variations: word processors, cars, home designs, beverages, candy, pens, shovels, etc. The reasons why we have so many can be boiled down to a few principles:

* Someone thinks they can improve on existing products
* A different design is necessitated by local considerations (think: homes on stilts vs. homes on concrete slabs)
* A new category of product fills a need where none existed before

Walk into any office supply store and look at the "writing instrument" section -- there are hundreds of varieties of pens. They all do roughly the same thing: deliver ink to a writing surface. But each pen you see displayed for sale is there because one of the three reasons above.

* Cartridge fountain pens are an improvement on dipped fountain pens, which are themselves an improvement on feather quills.
* NASA needed a pen that could write in the absence of gravity, so the pressurized rollerball pen was invented.
* The very first pen itself may well have been a pointed stick dipped in tar or blood; prior to that people were scraping rocks together or smearing pigments on walls with fur. (Just a guess.)

The evolution of pens will continue since no one product fits the needs of every user. Some pens are cheap and disposable, some are expensive and built of high-quality materials; some use gels, some use ink, some use pigments; some have twist-off caps, some don't have caps at all; wide barrels, narrow barrels, round barrels, square barrels; short, long; red, white, black, blue. Etc, etc.

But enough about pens.

Our current myriad of programming languages can be traced back to the very first ones: the numeric machine codes for early computers back in the 1940s. Primitive, hard to use, and laborious to enter into the computer, but they did the job. It wasn't long after that programmers assigned mnemonic words (such as ADD, CALL, LOAD) to the machine codes, giving birth to the class of languages called "assembly languages."

Different processor architectures called for different mnemonic codes, depending on the specific features of the underlying machines. Taking these differences into account meant inventing different assembly languages.

(Perhaps by now you can see where this is going...)

Programmers looked at their assembly languages programs and saw patterns: the same sequences of instructions would be used to form loops, conditionals, variable assignment, function calls, and so forth. Thus, the procedural programming languages were born. These languages encapsulated groups of instructions under umbrella terms such as "if", "while", "let", etc.

Out of a mathematical analysis of computer programming came the functional languages -- a whole new way of looking at computation. Not better, not worse, just different.

And then there's object-oriented, statically typed, dynamically typed, late binding, early binding, low memory usage, high memory usage, parallelizable, languages for specific uses, and on and on.

Ultimately, we have different programming languages because we *want* different programming languages. Every language designer has their own ideas about how their "dream" language will look and operate. Diversity is a *good* thing.

# Answer
> 20 votes
Functional programming languages are usually based on the different (but equivalent in power) model of computation: lambda-calculus. There are some untyped (has Python-like typing) languages such as LISP, Scheme (used in widely recognizable Structure and Interpretation of Computer Programs book/course) and statically-typed languages like Haskell, ML, F#.

SICP is what got me into functional programming, but other people recommend this paper by John Hughes and this interview with him.

Functional programming is now being push by Microsoft, for example, who have included F# (their functional language for .NET) in VS2010 and 11; they also employ some Haskell developers in MSR, IIRC.

Note, that there are also some non-lambda-calculus functional programming languages, such as Refal, which is based on pattern matching and rewriting.

Because the level of abstraction in functional languages is different, your attitude to solving problems changes, when you use functional programming techniques. Some say that it can make you a better programmer in general.

# Answer
> 19 votes
> In particular, is there any reason I should know a functional language as a computer programmer ?

Yes. Because haskell changed the way I think. It might change the way you think too.

**Story:** I used to think that I can learn **any** programming language in a day. One day I started Haskell. I finished everything that came before monads in half a day. Now its been a year since that day and I am still hopelessly stuck at Monads.

**Read:**

1. Languages and thought wiki
2. Notation as a tool for thought by Kenneth E. Iversion, Turing Award lecture

> But why are there so many different programming languages ?

Notation is tool for thought. We need different tailor made notations to deal with different thoughts comfortably. So we create new languages.

Also, read. ;-)

# Answer
> 14 votes
There hardly could be a programmer who hasn't at some point in time become frustrated by the constraints of the language they were using and decided to scratch his itch. Thus a new language - or dialect of an existing one - is born.

Abadi and Cardelli in "A Theory of Objects" develop a whole family of programming languages from object-oriented foundations. They prove that functional programming is a special case of OO but not the converse.

Inventing something new is fun, that is why people are more likely to create yet another language than contribute to making an existing one better. Of course, there are custodians of languages who don't welcome changes to their vision. Best example being the chasm between Common Lisp and Scheme supporters.

# Answer
> 14 votes
Why are there so many countries in the world? Wouldn't it be easier if we just had 5 or 6 superpowers, or even one universal kingdom of the Earth? It is easy to argue why it would not be better --- for a start, competition different countries may lead to progress, and from the point of view of democracy, human rights, etc., many countries may be better than one --- but this does not explain, *why* we have many countries. It only explains *why many countries would be better*.

Similarly, you can ask, why so many different human languages? Polish, Arabic, Mandarin... Wouldn't it be easier if there were just one language? You could argue either way, but those would be reasons as to why it would be better if life were one way or the other. It wouldn't explain the *causes* behind there being so many different human languages.

The thing is, there are many people on the planet, and we are all doing our thing, we all have our opinions, we all want to be in charge and have our own country or programming language, and we often think that we know better than others, or at least don't bother to understand what others have to offer.

Read this very enlightening blog post, Why so many Python web frameworks? Apparently, there are about **50** web frameworks in Python. This is just ridiculous; there is absolutely no sensible rational reason for that. But the author of the post answers: there are so many Python web frameworks **because it is so easy to create one**. You don't need a rational reason for there being more python web frameworks or more programming languages. People will go on creating new ones because they don't know what is already available, or because they hope they can make money, or just because creating new things is fun!

Let me describe a personal example. About 10 years ago I was writing some C++ code for a Finnish company. You know, in Finland they have those huge trucks that, well, travel long-distance and deliver a lot of stuff from one place to the other. I am sure, there are such trucks in America as well. So a typical problem is to make sure that all the 24 or so tires are fine. Of course, there is time-tested technology: pressure and temperature can be monitored, and drastic changes would indicate that something went wrong. Of course, all of this technology is proprietary, patented, with all the implications. (Remember: patents are supposed to promote innovation!) So this Finnish company wanted to detect the state of the tires by... sound. The idea was to install microphones to listen to the sound coming from all the tires and to do some kind of signal processing magic on those sounds in order to see if one of the tires had a problem of some kind, and I was doing a prototype of this madness. (They even had a dedicated lab for recording sample sounds; once they sent me an impressive video record of a particular occasion when they managed to explode a sample tire after subjecting it to 5 or 10 tons of pressure and heating it up to some ridiculous temperature.) Clearly, again, there was not a particular rational reason for this development, except that it was fun and some people wanted to make money. So also understand that there are so many reasons as to why somebody would start developing a new programming language. There is no need or even possibility to learn all of them.

Of course, all of this only applies if you believe in evolution. If you believe in some form of intelligent design, that God has also created all of the programming languages, then you would have to find a purpose behind this multitude. Perhaps God wanted to promote competition between different programming languages so that the art of software development would reach its highest possible state.

In conclusion, there are many people, many countries, many programming languages. This is just the nature of life! Let's be grateful for that: this just means that the field of programming/computer science is very much alive and flourishing.

# Answer
> 13 votes
Since others have already given good answers for this question, I will just quote Alan Perlis.

> Beware of the turing tar pit, in which everything is possible but nothing of interest is easy.

Also, http://weblog.raganwald.com/2004/10/beware-of-turing-tar-pit.html, is a good read.

# Answer
> 10 votes
*Why are there so many different programming languages?*

Because there are choices to be made:

* Mode of specification: Imperative vs. functional
* Typing: Statically typed vs. dynamically typed
* Order of evaluation: call-by-value vs. call-by-name
* Modularity: class-based vs. abstract data type-based
* Execution model: sequential vs. concurrent

Fortunately, the last two are inessential dichotomies, i.e., one could put both the choices into a single programming language. But, the first three dichotomies give rise to 8 combinations. So, even in an ideal world, there would be at least 8 programming languages. When you drill down, there would be further nuanced design choices within particular paradigms. For instance, if one decides to do a class-based statically typed language, there are different ways of designing the type system. There is not yet a canonical way of doing it. If one decides to do a concurrent programming language, there are various ways of representing concurrency: semaphores, conditional critical regions, monitors, message-passing (synchronous vs. asynchronous). Within synchronous message-passing, there are two major paradigms determined by how nondeterministic choice is captured (as represented by CCS and CSP).

Part of the research we do in programming language theory is devoted to resolving these dichotomies. For instance, I worked on resolving the dichotomy between imperative and functional programming in a paper called "Assignments for applicative languages" and our method has now been adopted by Haskell, making it both a functional and imperative language. That doesn't mean that the dichotomy is fully resolved. A Haskell programmer is still faced with the choice of whether to solve his problem functionally or imperatively. Luca Cardelli worked on resolving static vs. dynamic typing dichotomy. Paul Levy worked on resolving the call-by-value vs. call-by-name dichotomy. Not all of these results have yet been implemented in real-life programming languages.

---

*If all these languages can do the same things, why not just stick to one language and use that for programming computers?*

Because for a programmer in the real world, it is not enough to just do something. It also matters how it is done. When it is done properly, the problem domain is represented faithfully in the program, modularity of the problem is retained, and the programs become easy to understand, modify and maintain. All these things affect the **cost** of program development and maintenance. They also affect the reliability and security of the software.

For instance, many people use a program called "Quicken" for financial accounts. The original program was developed in some in-house version of Visual Basic, and it was quite good. However, it has been hard to extend it and maintain it. Over the years, as the company attempted to extend it for newer features, the program became increasingly buggy with millions of dissatisfied customers everywhere. They will probably benefit from re-engineering the software in a strongly typed object-oriented programming language.

---

*In particular, is there any reason I should know a functional language as a computer programmer ?*

Historically, "functional programming" was invented by Godel, Kleene and Church following the standard mathematical practice, and "imperative programming" was invented by Turing to pin down the notion of mechanical computation. Before Turing, there is no evidence of mathematics ever having analysed imperative programming ideas. (While all traditional mathematical algorithms were expressed in an "imperative style," their essential content was still functional.) So, imperative programming is very very new to human civilization, and its mathematics is still not very well understood. The No. 1 reason why everybody should know some functional programming is to understand how programming can be mathematical. (I am not admitting that imperative programming is non-mathematical, which is what functional programmers would have you believe. But I would agree that, with the present state of art, we don't yet know how to do imperative programming mathematically. Many of us are working on precisely that problem.)

# Answer
> 1 votes
You might look at it as evolution.

In the beginning, computers were programmed purely with binary codes. After that mnemonics were introduced and assembly languages were introduced, mostly depending heavily on the CPU used.

After that higher level (3th level) languages was introduced (Pascal, C, ADA, Cobol), some very generic (like C), some more suitable for data handling (Cobol), some for calculations (Fortran).

After that 4th level languages arose, like logic languages (like Prolog). The most generic languages are successors of third level languages; some of them are Java, C#.

We also see languages specific for internet/web, like ASP.NET, PHP.

And languages for a specific domain (DSL), which mostly work together with a generic language.

Then there are languages for kids to learn programming, like LOGO.

Also languages for fastly writing code, like Python, Ruby etc, languages for handling XML (XSLT).

And I probably have forgotten a lot of languages and even categories of languages.

# Answer
> 1 votes
other answers are good, will add a few new angles. as DC writes languages *evolve* just like real human languages! and they borrow concepts and syntax from each other again like real human languages. in other words theres also a fairly real study of etymology of computer languages.

this also means theres been a long history and timeline which mainly started around the 1930s with lambda calculus.

there is a strong interplay/synergy/symbiosis between theory and application with programming languages. new applications are invented which leads to new theories and vice versa. a programming language is in many ways *a bridge between theory and application*.

an interesting case study from history is Fortran. it is not well known but earlier versions of Fortran (mostly before Fortran77) had an ambiguous grammar. this means that the same command could be *legitimately* "interpreted"/compiled different ways by the compiler because there were multiple valid "interpretations" (this is not the same technical sense of "interpreted" languages).

so the theory about formal grammars was being developed around the time that Fortran was invented, and it was a small crisis when the issue of language ambiguity was discovered. Fortan syntax was reformulated to avoid this ambiguity and later languages had more sensitivity to grammar ambiguity in their design. OOP is also a very important/foremost example of a theoretical concept/advance in programming languages that "impacts" or "ripples" into many existing languages, transforming them.

other case studies are the invention of new technologies. for example the invention of the relational database has had huge impact on computer languages eg with SQL and computer language interfaces to it (eg for example in java, "JDBC"). likewise the world wide web with even more massive impact. there seemed to be an explosion of languages timed right around the dotcom boom which largely coincided with the early growth of the WWW and might be compared with evolutionary explosions.

there also does seem to be a long trend of rise in new programming languages in conjunction with the massive exponentially increasing processing power of Moores law which some think may be slowing.

current longrange trends in programming languages seems to be toward Big Data and Parallelization eg with MapReduce. there is also a current interest in closures.

another key aspect of languages is that they represent *increasing levels of abstraction*. they build on lower-level abstractions to create higher level abstractions (similar to a pyramid). in this way the progress of computer language evolution is probably endless and we can be relatively sure important new ones will continue to be invented long into the future. this is probably analogous to a similar concept in psychology called chunking—roughly stated, building higher level mental concepts out of lower-level building blocks.

anyone who has studied many computer languages must admit that a herd mentality can be observed whereby some aspects of them turn out to be overhyped fads, ie not so critical as advocated, or even die out (in use) over time! some of the core ideas/changes remain but the (over-)hype fades. in this sense programming languages also fall in and out of *fashion*. two cases in my opinion from the last half-decade that *are indeed useful* but were overhyped:

increasingly a self-similarity can be observed across many major languages such that they all tend to be converging toward implementing many similar features in their own way, ie as with product comparison charts that "check off" many features in a grid.

# Answer
> -5 votes
They weren't, it's just a marketing gimmick-- if you make the language kinda sorta look like "C", then that lowers the apparent barrier to entry.

Some that have no C influence at all: SQL, Pascal, Delphi, FORTRAN, COBOL, Ada, PowerBuilder, HyperTalk, Lisp, Simula, FOCAL, BASIC, PL/I, Algol, Algol-68, SNOBOL, Modula, Visual BASIC, Tutor, logo, Forth, DIBOL, Helix, AppleScript, Python, Erlang, Ruby, Pick, English, RPG, PL/SQL, ASP, Prolog, SmallTalk, Perl, bash, Wand BASIC, REXX, DOS batch language.

Those that kinda LOOK like C, but have very little in common with it: JavaScript, Java, C#, (arguably) Objective-C.

It's all marketing, Java, C++, and JavaScript kinda looks like C, but could hardly be more different under the covers.

---
Tags: programming-languages
---


title: Need to give a CFG for this language?

text:
# Question
Title: Need to give a CFG for this language?
I have the language:

$$ L = \\{0^m1^n \mid 0 ≤ m ≤ n\text{ or }0 ≤ n ≤ 2m\\}. $$

My goal is to give an equivalent context-free grammar for this language, but I am unsure if I am going about it the right way. So far this is what I've come up with:

$$ \begin{align\*} &S \to A \mid X \\ &A \to 0A1 \mid A1 \mid \varepsilon \\ &X \to 00A1 \mid 00A \mid \varepsilon \end{align\*} $$ Is this anywhere close?

# Answer
> 0 votes
Yes it is pretty close but a little far, correct solution will be (if you go about writing grammar methodically)

$S \rightarrow A \ | \ B$
$A \rightarrow 0A1\ |\ A1 \ |\ \epsilon$
$B \rightarrow 0B11\ |\ 0B \ |\ \epsilon$

Otherwise, if you go by logic, condition $0 \leq m \leq n$ OR $0 \leq n \leq 2m$ is true for every non-negative integer pair $m$ and $n$ (because $m \leq n$ OR $n \leq m$ translates to $m \leq n$ OR $n \leq m \leq 2m$, which is always true). Hence your language is really $\\{0^m1^n\ |\ m\geq 0, n\geq 0\\}$ and the grammar is:

$S \rightarrow 0S \ | \ S1 \ | \ \epsilon$

---
Tags: formal-languages, context-free
---


title: Addition recursively

text:
# Question
Title: Addition recursively
How would you recursively add numbers? Just in terms of pseudocode how would one approach such a problem in the most efficient run time

# Answer
> 2 votes
As a simple rule of recursion, any function can be computed using a recursive routine if : 1. The function can be expressed in its own form. 2. There exists a termination step, the point at which f(x) is known for a particular ‘x’.

Therefore to write a recursive program for addition of 2 numbers, we have to express addition in a recursive form using the above 2 rules : 1. add(m,n) = add(m,n-1)+1 (recursive defination of addition). 2. if n=0, return m (termination step). Using these 2 rules, the recursive program of addition can be coded very easily as shown :

add(int m,int n) { if(n==0) return m; y=add(m,n-1)+1; return y; }

---
Tags: algorithms, arithmetic
---


# Question
Title: How to correctly define the ratio of an approximation algorithm?
For a maximization problem $P$, I know that an $\gamma$-approximation algorithm for $P$ produces a solution $S$ that is $|OPT|\ge |S| \ge \gamma\cdot|OPT|$ for $\gamma \<1$ and $OPT$ the optimal solution for $P$.

Is there an alternative definition?

For example, can we say that an $\gamma$-approximation algorithm for $P$ produces a solution $S$ that is $|S| \le \gamma\cdot|OPT|\le |OPT|$ for $\gamma\<1$.

# Answer
> 4 votes
No, your definition isn't very useful. A $\gamma$-approximation algorithm is an algorithm that produces a solution which is not too bad compared to the optimal solution. In contrast, under your definition you are guaranteed to produce a solution which is somewhat worse than the optimal one.

Let's take as an example the maximum clique problem. Here is a $\gamma$-approximation algorithm for maximum clique under your definition: output an empty clique. This works for *any* $\gamma \< 1$.

I suspect that what you intended to capture was that $\gamma$ is the "tight" approximation ratio of the algorithm. That is, you want $\gamma$ to be the supremal $\gamma$ such that the solution $S$ produced by the algorithm always satisfied $|S| \geq \gamma |OPT|$.

I just gave one definition of the tight approximation ratio, but here is another (equivalent) one. We say that $\gamma$ is the tight approximation ratio of the algorithm if the algorithm is a $\gamma$ approximation (under the usual definition), and for every $\epsilon \> 0$ there is an instance on which the solution satisfies $|S| \leq (\gamma + \epsilon)|OPT|$. It's important here to include both parts of the definition.

---
Tags: algorithms, terminology, approximation
---


title: Converting a language to a PDA?

text:
# Question
Title: Converting a language to a PDA?
I am trying to convert the follow language

$$L = \\{0^m1^n \ | \ 0 \le m \le n \le 2m\\}$$

We have an exam in 2 days and the professor didn't teach us much about PDA's. They will be on the test though and I am freaking out because I have no idea how to do them. Could anyone give me a hint or get me started on this example?

# Answer
> 1 votes
If you've seen nondeterministic PDAs then this is a fairly easy construction. The key idea here is that for every string in your language, each $0$ must be matched with either a single $1$ or two $1$s, so when reading the input, nondeterministically place one or two markers on the stack for each $0$ seen. Then, for every $1$ seen, pop a marker off the stack and accept if the stack is empty after processing all the characters in the string. If the input is in your language, there will be at least one sequence of moves that will leave you in the final state, which is all you need.

---
Tags: formal-languages, regular-languages, context-free, pushdown-automata
---


# Question
Title: Proving a language is neither Recursively Enumerable nor co-Recursively Enumerable
$$L = \\{ \langle M \rangle \mid \text{\\(M\\) is a Turing Machine and \\(|L(M)| = 1\\)} \\}$$

I have to prove that this is not R.E. and not co-R.E.

I know how to approach these kind of problems. For $\check L = \\{ \langle M \rangle \mid \text{\\(M\\) is a Turing Machine and \\(|L(M)| \le 1\\)} \\}$, Here a simple reduction from complement of HP would do the trick. (Make a TM $M'$ which on input $w$ runs $M$ on $x$ and accepts if $M$ accepts $x$. If $\langle M,x \rangle$ belongs to complement of HP then $x$ would not be accepted and hence $M'$ would reject everything thereby satisfying the $\le 1$ property. Also in case $\langle M,x \rangle$ doesn't belong to complement of HP, $M'$ would accept everything and hence would be $\gt 1$. Thus we know that the complement of HP is reducible to $\check L$. Hence $\check L$ is not RE.)

But in the main problem I don't have an inequality and I am stuck with how to approach such problems. I would face the same problem while proving $L'$ (complement of $L$) as not RE for proving $L$ as not co RE.

# Answer
> 1 votes
One way to solve this problem is by showing there do not exist Turing machines that accept $L\_3$ or $\overline L$. But probably that is simply restating the question.

$L\_u$, the universal language, is non-recursive but RE language. If we reduce $L\_u \leq\_M L$ then $L$ cannot be co-RE. If we reduce $L\_u \leq\_M \overline{L}$ then $L$ cannot be RE.

Let us first do the reduction $L\_u \leq\_M L$.

We shall reduce $\langle M,w\rangle$ to a Turing machine $M'$ as follows: $M'$ rejects all inputs other than $w$. If the input is $w$ then it runs as Turing Machine $M$ on $w$. This gives us $\langle M,w\rangle \in L\_u$ iff $M' = f(\langle M,w\rangle) \in L$.

Hence $L\_u \leq\_M L$. Therefore $L$ cannot be co-RE. Otherwise $L\_u$ will become recursive.

Next we do the reduction $L\_u \leq\_M \overline L$.

We shall reduce $\langle M,w\rangle$ to a Turing machine $M''$ as follows: Let $w'$ be a string other than $w$. $M''$ rejects all inputs other than $w$ and $w'$. If the input in $w'$ then $M''$ accepts the input. If the input is $w$ then it runs as Turing Machine $M$ on $w$. This gives us $\langle M,w\rangle \in L\_u$ iff $M''= f(\langle M,w\rangle) \not\in L$, that is, $\langle M,w\rangle \in L\_u$ iff $M'' \in \overline L$.

Hence $L\_u \leq\_M \overline{L}$. Therefore $L$ cannot be RE. Otherwise $L\_u$ will become recursive.

If we combine the results, $L$ is neither RE nor co-RE.

---
Tags: turing-machines, proof-techniques, undecidability
---


title: Rank athletes by weighted criteria

text:
# Question
Title: Rank athletes by weighted criteria
I have a structure. that consist of the following:

```
Athlete A         Athlete  B     Athlete C
speed=10          speed=12       speed=6
endurance=60      endurance=59   endurance=64

```

I would like to rank the strength of those three Athletes based on their speed and endurance. I would like to give a slightly greater weight (0.6) to the endurance. Is there any algorithm that have a good complexity to solve this problem?

# Answer
> I would like to rank the strength of those three Athletes based on their speed and endurance.

There is an infinite number of ways of doing that. The two *lexicographic orders* and *weighted sums* are only a few examples.

What do you *really* want?

> I would like to give a slightly greater weight (0.6) to the endurance.

This suggests that you want (linear) weighted sums. If that is to make sense, you need to *normalize* your values to a shared scale. You don't give units or ranges, so I'll have to guess.

Normalizing with the maximum values in the sample and assuming that values $0$ are possible, a weighted sum that gives weight $p \in \[0,1\]$ to endurance and $1-p$ to speed looks like this:

$\qquad\displaystyle w(a) = p \cdot \frac{\operatorname{end}(a)}{64} + (1-p) \cdot \frac{\operatorname{speed}(a)}{12}$.

Implementing this is so straight-forward that it's barely worth being called "algorithm"; you'll certainly find nothing in a textbook that lays out the details for your. Just code it down.
> 4 votes

---
Tags: algorithms, sorting
---


# Question
Title: Reduction variation for the q-coloring problem
I'm trying to prove that $q$-COL $\leq^P\_m q$-COL$\_{2q-1}$, where $q$-COL$\_{2q-1}$ is the restriction of the q-coloring problem to graphs of maximum degree $2q-1$. Now, it seems fairly obvious "if you can color a graph of any maximum degree with $q$ colours, then you can colour a graph of maximum degree $2q-1$ with $q$ colours", the second is a subset of the first. Am I correct this far?

Assuming the previous assumption is correct, I need to find a function or mapping from $G$ to $G'$. It would seem that I need to pick a vertex $v \in G$, and $v' \in G'$ and colour $v'$ the same as $v$, then follow the pattern of $v$, for up to $2q-1$ connections, and then leave the rest alone.

In my head this works, but I'm fully new in reductions and would appreciate your input about this. I'd also appreciate any pointers on how to formalise it. Thank you!

# Answer
> 2 votes
When proving that $q\text{-}\textsf{COL} \leq\_m^P q\text{-}\textsf{COL}\_{2q-1}$, what you are really showing is that checking whether a graph with maximal degree $2q-1$ is $q$-colorable isn't any *easier* than checking whether an arbitrary graph is $q$-colorable. Why is this an interesting statement? Since if we replace $2q-1$ with a small enough number, then checking whether a graph is $q$-colorable *does* become easier. For example, any graph with maximal degree $q-1$ is $q$-colorable, so checking whether such a graph is $q$-colorable is easy, whereas checking whether an arbitrary graph is $q$-colorable is NP-hard for all $q \geq 3$.

How do you show that $q\text{-}\textsf{COL} \leq\_m^P q\text{-}\textsf{COL}\_{2q-1}$? You need to transform a given graph $G$ to a graph $H$ with maximum degree $2q-1$ such that $H$ is $q$-colorable iff $G$ is $q$-colorable. The most natural way of doing this is by splitting high-degree vertices. I'll illustrate how to do it for the case $q=2$ (which in reality isn't so interesting — why?), and will let you generalize the construction. Once you do that, you'll also see where $2q-1$ is coming from.

Suppose therefore that $q = 2$. First of all, we number the neighbors of all vertices. For each edge $(v,w)$, there are numbers $i,j$ such that $w$ is the $i$th neighbor of $v$, and $v$ is the $j$th neighbor of $w$. Now, we replace each vertex $v$ of degree $d$ with a path $v\_0,\ldots,v\_{2d}$, and connect $v\_{2i}$ and $w\_{2j}$ if $w$ is the $i$th neighbor of $v$ and $v$ is the $j$th neighbor of $w$. Note that all vertices now have degree at most 3. The construction works basically since the vertices $v\_0,v\_2,\ldots,v\_{2d}$ all get the same color — I'll let you work out the details.

---
Tags: complexity-theory, graphs, reductions
---


# Question
Title: Proving preservation under substitution System F Omega
I am going over the proofs for the simply typed lambda calculus in the book "Types and Programming languages" by Benjamin Pierce. I am trying to find inspiration for the similar proofs for System F Omega. When I was going over the preservation under substitution proof for the simply typed lambda calculus I was a bit puzzled.

The hypothesis of the proof is:

> If $\Gamma ,x:S \vdash t:T $ and $\Gamma \vdash s:S$ then $\Gamma \vdash \[x \mapsto s\]t : T$

So far I understand the proof quite well, but for the case $T-Abs$ I'm a bit lost. The rule is shown below.

$$ \dfrac{\Gamma ,x:T\_1 \vdash t\_2 : T\_2} {\Gamma \vdash \lambda x:T\_1 . t\_2 : T\_1 \rightarrow T\_2} $$

To prove the hypothesis for this case we use the previously proven lemmas weakening and permutation.

We assume that in this proof $x \neq y$ and $y \notin FV(s)$.

First we list the givens:

1. $t = \lambda y:T\_2 . t\_1$
2. $ T = T\_1 \rightarrow T\_2$
3. The first subderivation: $\Gamma ,x:S,y:T\_2 \vdash t\_1 : T\_2$
4. The second subderivation: $\Gamma \vdash s:S$ by hypothesis.

**Step 1** The first step we take is using permutation on the first sub-derivation, yielding: $\Gamma ,y:T\_2,x:S \vdash t\_1 : T\_2$. The reason why this happens is a bit unclear to me. I am assuming that the actual order of the extensions of $\Gamma$ matter for the third step.

**Step 2** The second step, which is the one that is unclear to me, is applying weakening to the second sub-derivation: changing $\Gamma \vdash s:S$ into $\Gamma ,y:T\_2\vdash s:S$. The reason that I find this odd is that this new form of the sub-derivation is not used anywhere in the proof.

**Step 3**: By the induction of our hypothesis we know that $\Gamma ,x:S,y:T\_2 \vdash t\_1 : T\_2$ implies $\Gamma ,y:T\_2 \vdash \[x \mapsto s\]t\_1 : T\_2$. And since we know that, we can apply the $T-Abs$ rule. Since that is what it basically says. We wrap the given sub-derivation in a lambda and we have to remove the $y:T\_2$ from the context because it is now introduced by the abstraction we constructed:

$$\Gamma \vdash \lambda y:T\_2 . \[x \mapsto s\]t\_1 : T\_1 \rightarrow T\_2$$

And finally we can move the substitution outside because we assumed that $x \neq y$ and $y \notin FV(s)$.

$$\Gamma \vdash \[x \mapsto s\]\lambda y:T\_2 . t\_1 : T\_1 \rightarrow T\_2$$

And this is exactly what we had to prove.

The problem I have with the second sub-derivation is that we nowhere in the prove actually used it. We never relied on that fact. Any input would be highly appreciated.

# Answer
> 6 votes
Throughout $y$ should have type $T\_1$ instead of $T\_2$.

Let us be more careful about step 3. We are going to apply the following induction hypothesis:

> If $\Gamma, y : T\_1, x : S \vdash t\_1 : T\_2$ and $\Gamma, y : T\_1 \vdash s : S$ then $\Gamma, y : T\_1 \vdash \[x \mapsto s\] t\_1 : T\_2$.

After that we will use abstraction to get $\Gamma \vdash (\lambda y : T\_1 . \[x \mapsto s\] t\_1) : T\_2$, and finish the proof by observing that $(\lambda y : T\_1 . \[x \mapsto s\] t\_1) = \[x \mapsto s\](\lambda y : T\_1 . t\_1)$.

So let us make sure that the induction hypothesis is applicable:

1. First we need $\Gamma, y : T\_1, x : S \vdash t\_1 : T\_2$: because $\Gamma, x : S \vdash (\lambda y : T\_1 . t\_1) : T\_1 \to T\_2$ by inversion we obtain $\Gamma, x : S, y : T\_1 \vdash t\_1 : T\_2$ and then we use exchange to get $\Gamma, y : T\_1, x : S \vdash t\_1 : T\_2$. This is your step 1. (The exchange is valid because types are non-dependent in this argument.)
2. Second, we need $\Gamma, y : T\_1 \vdash s : S$: we already have $\Gamma \vdash s : S$. By weakening we obtain $\Gamma, y : T\_1 \vdash s : S$, this is your step 2.

**Supplemental:** It seems unclear how induction works. To perform a proof by induction we need to specify what the induction is *on*. In this case the induction is on the derivation of $\Gamma, x : S \vdash t : T$. Thus, we have to look at all the possible cases of deriving $\Gamma, x : S \vdash t : T$. Each inference rule gives us one case, and we've just discussed the case of $\lambda$-abstraction. Each case has its own induction hypotheses, one for each premise of the rule.

Let me give you a simpler example. Suppose we only had the following typing rules:

1. Variables: $$\frac{(x : T) \in \Gamma}{\Gamma \vdash x : T}$$
2. Pairs: $$\frac{\Gamma \vdash e\_1 : T\_1 \qquad \Gamma \vdash e\_2 : T\_2}{\Gamma \vdash (e\_1, e\_2) : T\_1 \times T\_2}$$
3. First projection: $$\frac{\Gamma \vdash e : T\_1 \times T\_2}{\Gamma \vdash \mathsf{fst}\\,e : T\_1}$$

A derivation is a finite tree built from these rules (if you are not clear about that, you should first understand what a derivation is). Suppose we want to show that every derivable judgement has some given property $\phi$. To prove this by induction on the derivation, we need to show three things:

1. Variable case: if $(x : T) \in \Gamma$ then $\Gamma \vdash x : T$ has property $\phi$.
2. Pair case: if $\Gamma \vdash e\_1 : T\_1$ has property $\phi$ and $\Gamma \vdash e\_2 : T\_2$ has property $\phi$ then $\Gamma \vdash (e\_1, e\_2) : T\_1 \times T\_2$ has property $\phi$.
3. First projection case: if $\Gamma \vdash e : T\_1 \times T\_2$ has property $\phi$ then $\Gamma \vdash \mathsf{fst}\\, e : T\_1$ has property $\phi$.

The first case has no induction hypothesis, it is a base case. This is so because the corresponding inference rule has no premises (only the side condition $(x : T) \in \Gamma$). The second case has *two* induction hypotheses, namely that $\Gamma \vdash e\_1 : T\_1$ has property $\phi$ and that $\Gamma \vdash e\_2 : T\_2$ has property $\phi$. This is so because the corresponding inference rules has these two premises. The third case has one induction hypothesis, and you should be able to see why that is if you understood what I am saying.

---
Tags: type-theory, type-checking, types-and-programming-languages
---


# Question
Title: How do I get and/or verify a formal Grammar for a given formal Language?
I was given the Language $L=\left \\{ a^nb^na^nb^n |n\epsilon \mathbb{N} \right \\}$ and I'm supposed to find a Grammar that generates that Language. After some trying and fiddling I found one that I think works. The question is how do I verify it? On paper it looks fine, but are there some tools check this for me? Also are there easier methods than trying out by hand or brute force?

The Grammar I found is as follows:

$S\rightarrow aB\_{1}A\_{2}B\_{2}|aB\_{1}PA\_{2}B\_{2}$

$P\rightarrow A\_{1}B\_{1}A\_{2}B\_{2}|A\_{1}B\_{1}PA\_{2}B\_{2}$

$B\_{1}A\_{1}\rightarrow X\_{A1}A\_{1}$

$X\_{A1}A\_{1}\rightarrow X\_{A1}X\_{B1}$

$X\_{A1}X\_{B1}\rightarrow A\_{1}X\_{B1}$

$A\_{1}X\_{B1}\rightarrow A\_{1}B\_{1}$

$B\_{2}A\_{2}\rightarrow X\_{A2}A\_{2}$

$X\_{A2}A\_{2}\rightarrow X\_{A2}X\_{B2}$

$X\_{A2}X\_{B2}\rightarrow A\_{2}X\_{B2}$

$A\_{2}X\_{B2}\rightarrow A\_{2}B\_{2}$

$aA\_{1}\rightarrow aa$

$aB\_{1}\rightarrow ab$

$bB\_{1}\rightarrow bb$

$bA\_{2}\rightarrow ba$

$aA\_{2}\rightarrow aa$

$aB\_{2}\rightarrow ab$

$bB\_{2}\rightarrow bb$

# Answer
You don't really need the various $X$ nonterminals, just use rules $B\_iA\_i\to A\_iB\_i$ instead.

For correctness, use induction to show (1) that you can reach $aB\_1(A\_1B\_1)^k(A\_2B\_2)^{k+1}$, and from there $a^{k+1}b^{k+1}a^{k+1}b^{k+1}$, for all $k\ge 0$, and (2) that all generated words have the required form. For the second part, try to find some auxiliary conditions (e.g. numbers of $A\_i,B\_j$ match; if a factor $B\_1A\_1$ is not rewritten to $A\_1B\_1$ before the $B\_i$ is replaced by $b$, the derivation gets stuck; etc).
> 2 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Invertible function that randomizes order
I am looking for an invertible discrete function $f:\\{0,1,2,\dots,n-1\\} \to \\{0,1,2,\dots,n-1\\}$ for some given integer $n$. I want $f(0),f(1),\dots,f(n-1)$ to return all the integers in range $\[0..n)$ exactly once, but in a "messy", random-seeming arrangement. I anticipate that $n$ will be not bigger than $2^{30}$.

I thought about finding a generator for the group `<Zn,*>`, but I'm not sure if it would work for any given $n$ (would it?). Any other ideas?

# Answer
> 0 votes
Well, What i do isnt for encryption and i was looking for something quick and simple, what i did was finding the highest prime p that is smaller than n and a generator g in the group `<Z_p,*>` , and used the following f :

```
f(i) = (g^i)modp - 1 if i<n, i otherwise.

```

I know that the last n-p images are in order but oh well...

# Answer
> 4 votes
You are looking for a pseudorandom permutation on the set $\\{0,1,2,\dots,n-1\\}$. In cryptography, this has been studied under the (counter-intuitive) name "format-preserving encryption". There are a number of constructions you could use for your purposes.

There's a bunch of research literature on the problem, with different schemes that are optimized for different values of $n$. You can also find some summaries on Cryptography.SE.

I recommend you start by reading the question and the answers at Lazily computing a random permutation of the positive integers and Encrypting a 180-bit plaintext into a 180 bit ciphertext with a 128-bit block cipher and What are the examples of the easily computable "wild" permutations?.

---
Tags: algorithms, discrete-mathematics, cryptography, permutations, randomness
---


# Question
Title: Are there sorting algorithms that take advantage of a metric space?
We know comparison sorting algorithms use the ternary information (lt, eq, gt) garnered from a single comparison to make decisions about what to do next. Is there any research into using a *metric*? That is, if we compare $x$ and $y$ and we not only know that $y \> x$ but we also know the value $y - x$. Presumably if $y - x$ were a very large number we could heuristically separate them from each other, or move $y$ closer to end of the array, or move $x$ closer to the beginning. Could you make fewer than $O(n \lg n)$ comparisons in this way?

This is not a very precise idea (and credit goes to my friend Ian who brought it up out of the blue one day), but I Googled around for a little bit and I was unable to find anything to help me narrow the question.

# Answer
For the searching problem (rather than sorting), your idea sounds like interpolation search. Binary search uses only the binary result of the comparison (less than or not), and runs in $O(\lg n)$ time. Interpolation search also uses information about how close the values were, and heuristically runs in $O(\lg \lg n)$ time in the average case. Thus, that's an example where using the extra information can speed up search (at least heuristically).
> 3 votes

# Answer
It's possible to sort $n$ integers in $o(n\log n)$ time (the exact complexity might depend on the model). Wikipedia has a very thorough page on the topic.
> 1 votes

---
Tags: algorithms, sorting
---


# Question
Title: Sorting algorithm that moves element to a 2-dimensional array
I had an idea for a sorting algorithm wich is very fast, but can (potentially) use a lot of memory. I'm not a Computer Science student/graduate, only a self-taught programmer so I don't know how to evaluate it's viability. Also, I would like to know if it has already been documented and under what name.

Algorithm:

* Get an unsorted array
* Iterate through it, and find the highest and lowest value stored in it
* Determine "range" (highest - lowest)
* Make a 2 dimensional array `presorted`,
in which the first dimension's size is "range" + 1
* For each element in array "unsorted"
    + Add the current element into presorted\[current\_element\_value - lowest\]
* Make array "sorted", and add each element of `presorted`'s second dimension, ignoring the empty first dimensions.
* return the sorted array

An example using said algorithm would be the following:

```
unsorted[] = {5, 8, 2, 4, 6, 8, 2, 0, 4, 5, 6, 3, 3, 2, 1}

After iterating through it once, we get:
lowest: 0
highest: 8

range = highest - lowest = 8

Make 2 dimensional array presorted,
 consisting of range+1 arrays:

presorted[0] = {}
presorted[1] = {}
presorted[2] = {}
presorted[3] = {}
presorted[4] = {}
presorted[5] = {}
presorted[6] = {}
presorted[7] = {}
presorted[8] = {}

Next we add the elements, first element of unsorted is 5.
 5 - lowest (0) is 5

presorted[0] = {}
presorted[1] = {}
presorted[2] = {}
presorted[3] = {}
presorted[4] = {}
presorted[5] = {5}
presorted[6] = {}
presorted[7] = {}
presorted[8] = {}

After doing this which each element:

presorted[0] = {0}
presorted[1] = {1}
presorted[2] = {2, 2, 2}
presorted[3] = {3, 3}
presorted[4] = {4, 4}
presorted[5] = {5, 5}
presorted[6] = {6, 6}
presorted[7] = {}
presorted[8] = {8, 8}

Now, we simply create an empty array called "sorted",
 to which we add all the elements
 of non-empty arrays in presorted:

sorted = {0, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 8, 8}

```

This is the C++ source code for it

```
std::vector<int> Sort(std::vector<int> &unsorted)
{
   int min = unsorted[0];
   int max = unsorted[0];

   int range;

   std::vector<int> sorted;

   for (int i = 0; i < unsorted.size(); i++)
   {
      if (unsorted[i] > max)
         max = unsorted[i];
      if (unsorted[i] < min)
         min = unsorted[i];
   }

   range = max - min;
   std::vector<std::vector<int>> presorted(range+1);

   for (int i = 0; i < unsorted.size(); i++)
       presorted[unsorted[i] - min].push_back(unsorted[i]);

   for (int i = 0; i < presorted.size(); i++)
   {
       if (!presorted[i].empty())
       {
           for (int k = 0; k < presorted[i].size(); k++)
               sorted.push_back(presorted[i][k]);
       }
   }

    return sorted;
}

```

Is this algorithm viable?

I think it could be used in certain scenarios (when range is not too big) and it has the advantage that you can determine if it's appropriate to use it with simply iterating once through the unsorted list.

I'll do some tests and report back.

# Answer
What you have come up with is a sligthly less memory efficient version of counting sort.

This algorithm works in $\mathcal{O}(n + range)$ time where $n$ is the number of elements in the vector $unsorted$ and $max$ and $min$ are as defined in your program.

Your implementation uses $\mathcal{O}(n + range)$ memory. You can make it more memory efficient by just keeping track of how many times the same number in the vector 'unsorted' occurs rather than maintaining a vector with repeated instances of the same element i.e.

```
vector<int> presorted(range+1);
for(int i = 0; i < unsorted.size(); i++)
     presorted[unsorted[i] - min]++

```

It will now use only $\mathcal{O}(range)$ memory.

Yes you are correct, this method might potentially use up a lot of memory if the difference between the smallest and largest elements of the vector is too great.

For those who are not fluent in C++:

1. OP is finding the smallest and largest elements of the unsorted array $max$ and $min$ respectively.
2. He is initializing an array of size $max - min$ and creating an empty linked list in each position of the array (in this code it is the vector of vector of integers $presorted$).
3. Then each element of $unsorted$ is added as a new node in the linked list at $presorted\[unsorted\[i\] - min\]$. In a random access computational model this operation will take $\mathcal{O}(1)$ time and hence each element of $unsorted$ is added to its appropriate bucket in constant time.
4. Then he is just iterating in the array of linked lists and compressing it to the final array $sorted$ which is the final output.
> 5 votes

---
Tags: algorithms, sorting, arrays
---


# Question
Title: Test cases for graph embeddability problem
Suppose that I have a polynomial-time algorithm to solve the graph embeddability problem.

$k$-embeddability problem :
Given an edge-weighted and undirected graph $G = (V,E)$, can we assign coordinates to each $v \in V$ in $k$-dimensions such that Euclidean distance between $u,v \in V$ is equal to the weight of the edge $\\{u,v\\}$?

And, suppose that I want to check if I have settled **P** vs. **NP**. The algorithm has 100% success rate when tested with random graphs.

However, I might be *lucky* while generating random data. Is there any finite set of test cases, such that if an algorithm solves each of them, that implies the algorithm is able to solve graph-embedding problem for all possible problem instances?

(I've already verified that the algorithm runs in polynomial time; now I just want to verify whether the algorithm is correct.)

# Answer
No finite set of test cases can prove correctness of an algorithm, if we have no information about the form or structure of the algorithm and if the set of possible inputs is infinite.

For any finite set of test cases you might have in mind, I can come up with an algorithm that works correctly on all of those test cases, but is incorrect (works incorrectly on another input, or on infinitely many inputs). For instance, if your test cases are the inputs $t\_1,\dots,t\_k$, and the correct answers are $y\_1,\dots,y\_k$, then my algorithm can be:

Algorithm FooledYou(x):
1. If $x=t\_i$ for some $i$, then output $y\_i$. Otherwise, output 42.

This algorithm has polynomial time and works correctly on those $k$ test cases, but is not a correct solution to the problem.

This is a fundamental limitation of using testing to check program correctness. Testing cannot prove a program is correct; it can only prove the program is incorrect.

---

Now, suppose you want to test your program in practice. Here is a heuristic that will likely be effective. You link to a paper that shows that 1-embeddability is strongly NP-complete, by showing a polynomial-time reduction from 3SAT to 1-embeddability. There are standard ways of generating hard instances of 3SAT. So, use that polynomial-time reduction to convert them into (hard) instances of 1-embeddability, and test whether your algorithm gives a correct answer and solves the corresponding 3SAT problem. Odds are, this will reveal a problem of some sort somewhere.

For instance, one standard way to generate hard 3SAT instances is by using the reduction from Factoring to 3SAT: generate a random 2048-bit RSA modulus (product of two 1024-bit primes), then ask what its factors are. For more details, see Fast Reduction from RSA to SAT and Generating 3SAT circuit for Integer factorization example.
> 4 votes

---
Tags: np-hard, software-testing
---


title: 8-bit floating-point representation

text:
# Question
Title: 8-bit floating-point representation
I'm studying about representing fractional numbers as floating-point values. It is going to be an 8-bit representation. Somewhere in the text, it is said that:

> "We use the first bit to represent the sign (1 for negative, 0 for positive), the next four bits for the sum of 7 and the actual exponent (we add 7 to allow for negative exponents), and the last three bits for the mantissa's fractional part"

Now the question is: Why "7" -and not another value- must be added to the actual exponent ?

# Answer
With 4 bits you can represent 16 different values: 0,1,...,15. If you want to allow negative exponents it makes sense to take (approximately) half of the possible values to mean a negative exponent. By adding 7 to the exponent you map the values -7,-6,...,0,1,...,8 to the representable range. You might also want to look up two's complement.
> 3 votes

---
Tags: floating-point, numeral-representations
---


# Question
Title: See that P$^{NP}_{||} = P^{NP}_{O(\log n)}$
I'm trying to prove that P$^{NP}\_{||} =$ P$^{NP}\_{O(\log n)}$ where $n$ is the length of the input.

So, to see that polynomially many non-adaptive queries to a problem in NP can do as much as logarithmically many adaptive ones.

I know I need to see both inclusions, and have worked out the "easy" one: P$^{NP}\_{||} \supseteq$ P$^{NP}\_{O(\log n)}$ by arranging all the logarithmically many possibilities in a long deterministic one, and then use the fact that it's still polynomial (from known time complexity properties).

Now, I bang my head on a wall when I try to do the other one. I'm not even sure of where to start. I would very much appreciate your input on this problem, and besides the problem advice on where I could read examples on similar problems to get a better hang on them.

# Answer
Please refer the theorem 7, in On Truth-Table Reducibility to SAT and the Difference Hierarchy over NP and On Truth-Table Reducibility to SAT by Samuel R. Buss. The problem you mentioned is the original result by Buss. Hemachandra proved one of the inclusions in his PhD thesis.
> 2 votes

---
Tags: complexity-theory, time-complexity, np
---


# Question
Title: is little-o notation correct after being powered by a number?
I just wanted an example in which the equation given below is **not** correct.

$f(n) = o(g(n)) \Leftrightarrow 2^{f(n)} = o(2^{g(n)})$

# Answer
> 3 votes
Trivially: $f(n) = 0, g(n) = 1$. Then $lim\_{n \to \infty} f(n)/g(n) = lim\_{n \to \infty} 0 / 1 = 0$ and $lim\_{n \to \infty} 2^{f(n)}/2^{g(n)} = lim\_{n \to \infty} 1 / 2 \neq 0$. You may want to think if less trivial cases exist.

# Answer
> 2 votes
Hint: $2^{f(n)} = o(2^{g(n)})$ does not always imply $f(n)=o(g(n))$.

For any monotonically increasing $f(n) = g(n)/c$, $c \> 1$, $f(n) = \Theta(g(n)) \neq o(g(n))$ but $2^{g(n)} = 2^{cf(n)}$ and therefore $2^{f(n)} = o(2^{cf(n)})$.

In particular, the proposition fails for $f(n) = n$ and $g(n)=2n$.

# Answer
> 0 votes
If you want asymptotically positive functions check $f(n)={1 \over n}$ and $g(n)=2$

---
Tags: complexity-theory
---


# Question
Title: Complexity for minimum subset sum of size n-k
Disclaimer: Not a HW.

Given $n$ sorted positive floating point numbers, and one has to find the minimum subset sum of size $n-k$. What would be the most efficient way? I can figure out using Brute force becomes $O(n^{n-k})$

# Answer
Since all floating points are positive, we can conclude that we should greedily pick the smallest $n-k$ floating point numbers for the smallest sum. This can be proven by the exchange argument that any solution that does not follow the greedy strategy can be improved by making swaps accodring to the greedy strategy.

Since the list is already sorted, the complexity will be $\mathcal{O}(n-k)$
> 0 votes

---
Tags: algorithms, asymptotics
---


# Question
Title: Does the memory get unallocated when program exits?
I have been trying to manipulate pointers just for the sake of studying. I have had some problems with some programs I wrote where I had memory leak.

### Does this memory stay allocated even when the program returns?

* If yes how to deallocate it?
* If no why, isn't all saved in heap so only the one who has that heap pointer can deallocate? Or does the operating system pull some magic tricks?

# Answer
When you run your program its memory allocations take the form of page allocation requests to the operating system. When your program terminates, the operating system notices and returns all the allocated pages to the list of free pages, which can then be used by other processes. It does not matter if your program leaks memory (other than potentially using more memory as a result), because ultimately the operating system will reclaim everything.
> 2 votes

---
Tags: memory-management
---


# Question
Title: $O(n \log n)$ algorithm for disjoint segment visibility problem
Consider we have $n$ disjoint segments and a point $P$ which is not on any segment. I want to find an $O(n \log n)$ algorithm to check which segments are visible from $P$. A segment is visible from $P$ if it has a point which is visible from $P$.

My idea is to use a sweep half-line with one end-point on $P$, sort points clock-wise by degree and start from an end-point on the nearest visible segment (which I don't know how to find), rotate and detect one visible and some possible invisible segments at a time. All I can think of is $O(n^2)$ so far. Can anyone suggest an $O(n \log n)$ algorithm.

# Answer
W.o.l.g. we could assume $P$ is the origin point $(0,0)$.

1. List the endpoints of all segments, represent them in polar coordinate $(\theta,\rho) \in \[0,2\pi) \times \[0,\infty)$ and sort them by their degree.
2. Imagine there is an ray from $P$ pointing to the right, we sweep it for one round (by gradually changing its direction $\alpha$ from 0 to $2\pi$). Let $R(\alpha)$ denotes the ray from $P$ to direction $\alpha$. We wonder what's the segments $R(\alpha)$ hits, and what's their order on $R(\alpha)$.
3. Find out all segments hit $R(0)$, and sort them by their order on $R(0)$. Store them in a balanced binary search tree (e.g. red-black tree).
4. Iterate over the points we found (and sorted) in step 1: Each point $(\theta,\rho)$ indicates a segment would start/stop hitting the ray $R(\alpha)$ when $\alpha$ increase to $\theta$. Update the binary search tree accordingly.
5. The elements that once be the smallest one in the binary search tree are the segments visible from $P$.

It's easy to check that the runtime of above algorithm is $O(n \log n)$.
> 3 votes

# Answer
We can do a radial line sweep to solve the problem -

Sort the end points of the line segments w.r.t. the angle the line joining $P$ and the endpoint $Q$ make, break ties w.r.t. distance from $P$. Now when we sweep radially (in the clockwise direction) maintain two types of events 'open' and 'close' which correspond to opening and closing some new line segment. Keep track of how many line segments are 'active' at any given time ('active' means that we have encountered the end point which corresponds to the 'open' event of the line segment but we haven't encountered the other endpoint in the sweep yet). If at any point of time we have exactly one 'active' line segment, then this segment is visible from $P$.

We should be careful that when we start the sweep, we should always start at some 'open' event.

There will be $2n$ such events and keeping track of the number of active segments can be done in constant time per segment (via a hash table or logarithmuc time by using a balanced BST). Hence the dominating step in then algorithm is sorting which takes $\mathcal{O}(n)$ time as required.

As with all computational geometry problems, there might be some corner cases that I have overlooked but the general idea that if at some point of time during the radial line sweep, if we have exactly one active line segment, then it is visible from $P$ is the crux to solve this problem.
> 1 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Big O relationship between $n^{10\log n}$ and $(\log n)^n$
I need help with a home task with computer science. the problem is: compare the two complexity functions: $F(n) = n^{10\log n}$ and $G(n) = (\log n)^n$. Which is $O(\ )$ of the other? Which is $\Omega(\ )$ of the other?

# Answer
> 1 votes
$F(n) = n^{10\log{n}}$ and $G(n) = (\log{n})^n$

The crux of the solution is to take $\log$ on both sides of both functions to get $$F'(n) = \log{F(n)} = 10\log^2{n}$$ $$G'(n) = \log{G(n)} = n\log\log{n}$$ $$\exists c,N \\, s.t. \ \log^2n \le c\*n\log\log n \ \ \forall n \> N$$

I'll leave the proof of the above statement to you as an exercise. Thus we can now conclude that

$$\implies F'(n) = \mathcal{O}(G'(n))$$ $$\implies e^{F'(n)} = \mathcal{O}(e^{G'(n)}) $$ $$\implies F(n) = \mathcal{O}(G(n))$$

This is due to the fact that $\log(x)$ is a monotonically increasing function. This should be sufficient for you to proceed further for $\Omega$.

# Answer
> 1 votes
\[Note: this probably should be a comment, but it's too long and I don't like comments that need to be split over multiple entries.\]

You need to be a bit careful with these arguments, since it's not always the case that $$\log f(n)\in O(\log g(n))\Longrightarrow f(n)\in O(g(n))$$ Consider, for example, $f(n)=3^n, g(n)=2^n$. We obviously have $\log 3^n\in O(\log 2^n)$, since $n\log3\in O(n\log 2)$, but we can't conclude from that that $3^n\in O(2^n)$.

See here for a further discussion. By the way, in this particular case, Banach Tarski's answer was correct.

# Answer
> 0 votes
You can also solve this problem by rewriting $n^{10 \log(n)} = e^{10 \log^2(n)}$.

Now, in $(\log(n))^n$, both the base and the exponent grow asymptotically faster.

This is not completely rigorous, but can at least help to give the idea for which function is the $O$ of which function.

---
Tags: asymptotics, landau-notation
---


# Question
Title: Generating general term of union of two countably infinite sets
I have two sets whose general terms are given as: $$ \begin{align\*} A &= \\{2⋅n \mid n ∊ ℤ\\} \\ B &= \\{2⋅n + 1 \mid n ∊ ℤ\\} \end{align\*} $$ I want to find the union of these two sets and return the common term of the set, something like $\\{n \mid n ∊ ℤ\\}$.

I have the following questions:

* Given that I can't store the entire sets, what are some efficient ways of merging these two sets?
* How can I find the common term of any given sequence?
* What would be some other approaches to solve this problem?

I would really appreciate if someone can share some relevant literature or an algorithm for this question.

Note that the members of the sets need not be integers – they can be rationals too.

# Answer
In functional programming languages, there is a technique called lazy evaluation, to deal with infinite sets. In lazy evaluation, the sets are used as generators, and the elements of the set are only generated when they are needed.

We can even have lazy operations on lazy data: like lazy union, lazy intersection, and the like, particularly if the lazy generation spits out elements in some order. Particularly, lazy union is very efficient. Lazy intersection and lazy minus are problematic in cases such as yours.
> 2 votes

# Answer
You need to take a step back or two, because there is a huge gap between the example you posted and the extremely broad problem you describe.

The number of sets of integers is uncountable. So it's impossible to represent them all. The number of representable sets is finite. That's a gap already.

If you stick to the sets that are the image of a computable function, i.e. the sets of the form $\\{f(n) \mid n \in \mathbb{N}\\}$ where $f : \mathbb{N} \to \mathbb{N}$ is computable, then you have exactly the recursively enumerable sets. That's still too large to do anything, because any nontrivial property of these sets is undecidable: if a property $P$ is such that $P(A\_1) \iff P(A\_2)$ when $A\_1$ and $A\_2$ are representations of the same set, then $P$ is undecidable unless it's one of the two properties “always true” or “always false”. This is a variation on Rice's theorem.

(Note: it's customary to work on the natural integers, so I'm using $\mathbb{N}$. But going to $\mathbb{Z}$ or $\mathbb{Q}$ is just a matter of a simple reencoding.)

In particular, a key property to do useful things with just about anything is to test whether the result of two computations represent the same mathematical object. That is, equality of representations: if you have two representations, do they represent the same set? For functions, this is decidable only for some very “small” classes (and there is no maximal class). The situation is similar for their images.

There are three basic approaches you can take:

* Decide that sometimes your system will not spot that two objects represent the same set, and you can live with that. Then you can be very liberal in what inputs you accept, but there will be many inputs for which your system will not produce any useful results. You need to be careful about your simplification procedures, as it may be difficult to ensure that they terminate, let alone terminate in a reasonable time.
* Restrict your inputs to a “small” class of set representations for which equality is decidable. For example, if your sets are all images of linear functions with integer coefficients, then their equality is fairly easy to decide, and it is fairly easy to obtain canonical representations. But if you allow multiplication, you've lost the game.
* An intermediate stance: get human assistance. When your system needs to prove something and the built-in rules aren't enough, ask a human to decide one way or the other. If you want to ensure that the results are correct (as opposed to trusting the human), you enter the realm of proof assistants.

Which approach to take, as well as which class of sets to target, depends very heavily on the problem you want to solve. Once you've decided that, you can start thinking about problems such as simplifying representations and making calculations such as unions and intersections.
> 2 votes

---
Tags: algorithms, sets
---


# Question
Title: Approximating all independent sets of size k in a graph
Given an undirected graph, I need an algorithm that outputs all the independent sets of size \>= k (constant) in the graph. I know the problem is NPC, and I do not want to use the exponential brute-force solution. What I am looking for is to hear about the best solutions currently known to this problem. If someone can refer me to some known polynomial approximation algorithms that achieve good results, that would be very helpful.

# Answer
> 1 votes
In general, the maximum independent set problem cannot be approximated to within a constant factor in polynomial time unless $P = NP$. You can do better, however, if you restrict yourself to special graph classes. For example, in interval graphs, the maximum independent set problem can be solved in polynomial time. As another example, in planar graphs, the maximum independent set problem can be approximated to within any ratio $r \< 1$ in polynomial time.

There is a lot more information provided here: https://cstheory.stackexchange.com/questions/2503/maximal-classes-for-which-largest-independent-set-can-be-found-in-polynomial-tim http://www.graphclasses.org/classes/problem\_Independent\_set.html

If you're interested in actual implementations, the Wikipedia page has a few references: https://en.wikipedia.org/wiki/Independent\_set\_(graph\_theory)#Software\_for\_searching\_maximum\_independent\_set

---
Tags: complexity-theory, graphs
---


# Question
Title: Why Does the Deterministic Selection Algorithm Run in $O(n)$ and not $O(n\log n)$?
Here is pseudocode for the algorithm:

```
select(L,k)
{
if (L has 10 or fewer elements)
{
    sort L
    return the element in the kth position
}

partition L into subsets S[i] of five elements each
    (there will be n/5 subsets total).

for (i = 1 to n/5) do
    x[i] = select(S[i],3)

M = select({x[i]}, n/10)

partition L into L1<M, L2=M, L3>M
if (k <= length(L1))
    return select(L1,k)
else if (k > length(L1)+length(L2))
    return select(L3,k-length(L1)-length(L2))
else return M
}

```

Here is some analysis of the algorithm: http://www.ics.uci.edu/~eppstein/161/960130.html

The analysis suggests to use the recurrence relation $T(n) \leq \frac{12n}{5} + T(\frac{n}5) + T(\frac{7n}{10})$. Solving this we get linear work for a call. But aren't there log many recursive calls? So that would be $n\log n$.

Put another way, conceptually this algorithm seems like it could be described as "for each call, cut the search area kind of like binary search, but not guaranteed to cut the search area by as much as binary search, and add a linear time partition". Binary search runs in $O(\log(n))$, so adding a linear search per call would make it $O(n\log(n))$.

What am I not understanding about the linked analysis?

# Answer
Consider the following series

$S = n + \lceil n/2 \rceil + \lceil n/4 \rceil + ... + 1$

There are $\lceil \log\_2 n \rceil + 1$ terms but the sum is less than $2^{\lceil \log\_2 n \rceil+1} \< 4n$ always.

Similarly, in your algorithm even though you have $\log n$ recursions, each recursion successively does a fraction of work. Hence the total work done in linear in $n$, rather than $\Theta(n \log n)$ as the naive analysis suggests, just similar to the sum of the series above. '

Also note that $T(n)$ is $O(n)$ as well as $O(n\log n)$. This is because $O(n\log n)$ is also an upper bound to $T(n)$ and therefore it is incorrect to say, for example, "Why is $T(n)$ not $O(n\log n)$?".
> 3 votes

---
Tags: algorithm-analysis, runtime-analysis, recursion, selection-problem
---


# Question
Title: What happens if we add denormalized number and normalized number?
Denormalized numbers can represent numbers smaller than 2^(-1022) whereas normalized number cannot. So I'm curious what happens if we add denormalized number and normalized number. Actually, I have tried some tests and it seems that the computer converts denormalized number to 0. Is my thought correct?

# Answer
The result depends on the difference between the normal and denormal numbers you are adding. $1 + \[denormal\]$ is rounded to $1$.

But if the range difference between your numbers is inferior to $2^{52}$ for doubles, or $2^{23}$ for singles, you will get a real addition. There is nothing special about denormals here : $1 + 2^{-200}$ is rounded to $1$ as well.

To implement a floating point adder (as hardware or software), you shift right the smaller number to equalize the exponents before doing an integer addition to the aligned mantissas. If the range difference is too large, the smaller number is entirely shifted out.
> 2 votes

---
Tags: floating-point, number-formats
---


title: A problem similar to bin packing

text:
# Question
Title: A problem similar to bin packing
Let's say we have $n$ items of size $si\_i$ and $m$ containers, each has a capacity $sc\_i$. **Every container can have at most one item at a time**, provided its size is less than or equal its capacity.

Now we add time axis to this problem, because otherwise it would be trivial. Every item $i$ starts to exist at time $t\_{i1}$ and ceases to exists at $t\_{i2}$. You could visualize this with Gant diagram. There are no limitations of how many items may exist simultaneously, or anything like that. All we know that every item has its birth and death time. Also $t\_{i1}, t\_{i2} \in \\{0,1,2,...,59\\}$ and $t\_{i2}\>t\_{i1}$. **These are all constraints** on $t\_{i1}$ and $t\_{i2}$

How to assign containers to all items, assuming the solution exists? The naive approach is to assign the smallest possible container to every item, but the order does matter:

If the are two avaliable containers $c\_1$ and $c\_2$ of capacity $sc\_1=10$ and $sc\_2=12$, if $c\_1$ is assigned to the 1st item (because it's the smallest available container), and $c\_2$ to the 2nd item (again, the smallest available container), the 3rd item won't have any available container. However if you assign the smallest container to 2nd and then 1st item, there will also be a container of capacity $12$ for the 3rd item, because it won't be blocked by the 2nd item.

Does this problem as a name already? And is there any simple algorithm to solve it, except brute force?

# Answer
> 2 votes
Your problem belongs to the family of problems known as *fixed interval scheduling*. For a recent survey, see Kovalyov et al. A classical paper of Arkin and Silverberg solves the problem when all sizes or capacities are the same, and shows that if you generalize the notion of size then the problem of deciding whether all jobs (i.e., items) can be scheduled (i.e., stored) is NP-complete, though it has an $O(n^{k+1})$ solution, where $n$ is the number of jobs and $k$ is the number of machines (i.e., containers).

Your problem is easier than the NP-complete variant considered by Arkin and Silverberg:

1. Your constraints on which jobs can be scheduled on which machines are not arbitrary – they depend on the notion of size.
2. Your timeframe is short.
3. You are guaranteed a solution. (Though this doesn't usually make the problem any easier.)

The literature on the problem is probably vast, so perhaps someone already considered your particular variant.

---
Tags: algorithms
---


# Question
Title: Some basic help about Artificial Neural Networks
Firstly, I'd like to state that I do not have any basis to the Neural Networks and I'd like you to recommend me very simple and understandable resources.

While I have a home assignment for a short time, I would like to ask you for help for the following question.

> Within the context of Artificial Neural Networks;
>
> How is the solution / representation of **AND, OR, XOR** problems?

I can find some articles about **XOR** problem from google, but I cannot find any about **AND, OR** problems. I think and / or is special words for google and so I cannot find articles.

Thank you.

# Answer
> 0 votes
You are asking two question: a literature question, and a concrete question. I will only answer your concrete question. Single artificial neurons compute linear threshold functions $$f(x\_1,\ldots,x\_n) = \begin{cases} 1 & \text{ if} \sum\_i w\_i x\_i \geq \theta, \\ 0 & \text{ otherwise}. \end{cases}$$ See if you can represent AND and OR in this form.

---
Tags: neural-networks
---


# Question
Title: What is the approximation ratio of this randomized algorithm for finding matchings?
I would like to analyze the following algorithm in terms of its approximation ratio.

Here is the algorithm:

```
Input: A positive number T and two disjoint sets of nodes V={v1,...,vn} and W={w1,...,wn}.
Output: A matching S.
1: O = [] # An empty array.
2: for t = 1 to T do
3:     Create a set E of edges from V to W randomly
4:     A = LA(G) # G is the bipartite graph G=(V U W, E) and LA is
                 # an algorithm that takes as input a bipartite graph
                 # and outputs a matching A.
5:     O[t] = A # Put the matching A in the t-th element of O.
6: end for
7: S = max(O) # S is the maximum cardinality matching in O.
8: return S

```

In the algorithm above, called BA, there is a call to another algorithm LA, on line 4. We know that LA is a constant factor approximation algorithm for an NP-hard problem $\Pi$. An instance of $\Pi$ is a bipartite graph and we would like to return a maximum matching that respects some constraints. Therefore, LA will return a matching of size no less than a constant factor times the size of the optimal matching.

Note that BA is trying to solve another NP-hard problem $\Pi\_1$ that has an instance of two sets and we would like to return a maximum matching between these two sets that respects the same constraints as for $\Pi$. The only difference between $\Pi$ and $\Pi\_1$ is that $\Pi$ has as input a bipartite graph (nodes and edges) whereas $\Pi\_1$ has as input a set of nodes only.

**I am not trying to hide the constraints. I still cannot write them explicitly in a readable way**. I will give some examples to clarify the problem.

* Say, for problem $\Pi$, we are given the following graph (it is represented by set of edges):

`Instance of II = { {1, 3}, {2, 2}, {3, 1}, {4, 4} }`

In this special instance, say, the optimal solution is

`OPT of II = { {1, 3}, {2, 2}, {4, 4} }`

Hence edge `{3, 1}` cannot exist in the solution because of the constraints. If we apply `LA` to this instance we could have selected, say

`A = { {1, 3}, {2, 2} }`

Therefore, the algorithm failed to select the edge `{4, 4}`.
* Now, for problem $\Pi\_1$, we are given the following two sets:

`Instance of II1 = (V = { 1, 2, 3, 4 } and W = { 1, 2, 3, 4 })`

In this special instance, say, the optimal solution is (brute-force on all possible edges between V and W and apply the optimal algorithm for $\Pi$)

`OPT of II1 = { {1, 4}, {2, 3}, {3, 1}, {4, 2} }`

Hence, since we do not have the set of edges initially, the optimal solution for $\Pi\_1$ is to select 4 edges unlike 3 edges for $\Pi$. In fact, it is clear that `|OPT of II| <= |OPT of II1|`.

Now, at iteration `t=1`, if we apply `BA` to this instance we could get, say

`formed edges in line 3 of BA = { {1, 2}, {2, 2}, {3, 4}, {4, 3} }`.

Now we apply `LA` to this instance and we could obtain `A = { {1, 2}, {4, 3} }`

We continue until `t=T`, and then select the maximum cardinality set `A` obtained, which is `S` in line 7 of `BA`.

Knowing that LA is $O(1)$-approximation algorithm for $\Pi$, can I say that BA is an approximation algorithm for $\Pi\_1$?

I think I can say that BA is something like $O(1+\frac{1}{T})$-approximation algorithm for $\Pi\_1$ because as $T\to\infty$ and the 3rd line of BA is generated uniformly random, the solution produced by BA is no less than a constant factor times the optimal solution.

The pseudo-code is also given in more clearer way here:

# Answer
Suppose that the only feasible solution are single edges and $\\{(1,1),(2,2),\ldots,(n,n)\\}$. The optimal solution thus has value $n$. On the other hand, the optimal solution on a random bipartite graph is $1$ with probability $1-2^{-n}$. Thus algorithm BA would have to take $T=\Omega(2^n)$ in order to guarantee a constant approximation ratio, even though algorithm LA always outputs the optimal solution.
> 4 votes

---
Tags: algorithms, algorithm-analysis, approximation, randomized-algorithms
---


# Question
Title: What are the differences between propositional logic and temporal logic?
I am currently studying temporal logic and find it much similar to propositional logic. However, temporal logic seems to be slightly more specific because it encapsulates more precise meaning symbols, like `until, eventually, next` etc.. My question is are there other major differences with temporal logic and propositional logic? And can everything expressed in propositional logic be expressed in temporal logic too and vice versa? Perhaps, why would one use one over the other or vice versa?

# Answer
An *interpretation* in propositional logic consists of assigning a truth value to every variable. In contrast an interpretation of, say, LTL consists of assigning a truth value to every variable **at each point in time**. So the *domain of discourse* is different. Propositional logic is about variables having a definite truth value, whereas LTL is about variables having a truth value depending on time.

Everything that can be expressed in propositional logic can also be expressed in LTL, by just always referring to the truth value at time zero. We say that propositional logic is *interpretable* in LTL. The converse isn't true – you can't express temporal concepts in propositional logic. You use temporal logic when you need to express temporal concepts. In situations where you don't need to express temporal concepts, you use propositional logic.

The language of set theory is rich enough to encompass both propositional logic (and its extension, predicate logic) and temporal logic. However, the language of set theory might be too expressive for your comfort at times (for example, it may be hard to process algorithmically), which is why we are interested in propositional logic and temporal logic.
> 4 votes

---
Tags: propositional-logic, temporal-logic
---


# Question
Title: Indexing into a pattern database - Korf's Optimal Rubik's Cube solution
As a fun project, I've been working on a C# implementation of Richard Korf's - Finding Optimal Solutions to Rubik's Cube Using Pattern Databases.

https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

I actually have it working, I'm just trying to improve my solution.

One thing that Korf glazes over in his paper is how he stores and indexes into the pattern databases. Ideally, I think we want to use an instance of a rubik's cube to generate an index into an array.

My question is about the best way to generate this index.

My solution is to generate a minimal perfect hash. This involves keeping ALL of the cubes in memory until I have discovered the entire pattern database then generating a minimal perfect hash based off of that. The MPH takes a couple hours to run depending on the pattern database size, but I only need to do it once since I save it to disk. In the end, I can throw away the cubes themselves storing only the MPH. That way I can take a randomized rubik's cube, apply the pattern, then look up the array index in the MPH to get an estimated solution length.

I believe Korf and Shultz describe a better way to determine the cube's index in their 2005 paper called "Large Scale Breadth-First Search"

https://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

This paper describes an algorithm to generate an index based off of the lexicographical ordering of a permutation. Basically you can take the permutation {1, 2, 3} and figure that it is the smallest with an index of 0. {1, 3, 2} is next up with an index of 1 and so on.

I feel like I should be able to apply this algorithm to a rubik's cube to get its index within a pattern database, but I'm having a hard time figuring out how it would work in practice.

The corners only pattern database for instance contains all rubik's cubes that have had their edge stickers taken off. There are exactly 88,179,840 cubes in this set. Any corner cubie on a rubiks cube can be in one of 24 different states. The state of the 8th corner cubie can be calculated based on the other 7 so cubes in the corners only pattern database each have 7 values between 0 and 23

e.g. {0, 3, 6, 9, 12, 15, 18, 21} defines the "solved" cube with all edge stickers removed.

if I rotate the front face 90 degrees the permutation might be: {0, 3, 11, 23, 12, 15, 8, 20}

Is there a way to get an index out of these sort of permutations?

# Answer
You don't explain what the numbers from 0 to 23 mean, but according to this answer, you can represent the state of the corners using eight pairs $(p\_i,o\_i)$, where $(p\_0,\ldots,p\_7)$ is a permutation of $(0,\ldots,7)$, $o\_i \in \\{0,1,2\\}$, and $o\_7$ (say) is determined by $o\_0,\ldots,o\_6$. In total, this gives $8! \cdot 3^7 = 88179840$ degrees of freedom. Assuming that you can decompose your $\\{0,\ldots,23\\}$ to pairs $(p\_i,o\_i)$, you can easily convert a position to an index by encoding separately the permutation $(p\_0,\ldots,p\_7)$ (which the AAAI paper explains how to do) and the values $o\_0,\ldots,o\_6$, which you can encode in base 3. Putting the two values together in the obvious way (for example, $3^7p + o$ or $8!o + p$), we get an index.
> 6 votes

---
Tags: algorithms, permutations
---


# Question
Title: Why do floating point additions sometimes produce equal results?
I have tried two sentences on my computer :

```
2 + 10^(-18) == 2
2^(-55) + 2^(-57) == 2^(-55)

```

My computer gives TRUE and FALSE respectively. Why does the computer give two different results? Shouldn't the computer give the same output?

# Answer
Floating point numbers have limited accuracy. They are stored in the following way: $\pm 1.x\_0\ldots x\_{n-1} \times 2^y$ (here $x\_0,\ldots,x\_{n-1}$ are binary digits) for an appropriate $n$; the value of the exponent $y$ is also bounded. The value of $n$ and the bounds on $y$ depend on the exact type of the floating point number.

When you add $2$ and $10^{-18}$, the answer is rounded to $2$ since the contribution of $10^{-18}$ is too small to store in the number (i.e., $n$ is too small). When you add $2^{-55}$ and $2^{-57}$ there is no such problem: this is stored as $1.01 \times 2^{-55}$.

For more, check out one of the multitudinous resources on floating point numbers.
> 3 votes

---
Tags: arithmetic, floating-point, number-formats, numerical-algorithms
---


title: perspective transformation of a grid

text:
# Question
Title: perspective transformation of a grid
A **perspective transformation** of a point is defined as follows:

$ x' = \frac{M\_{11}x + M\_{12}y +M\_{13}}{M\_{31}x + M\_{32}y +M\_{33}} $

$ y' = \frac{M\_{21}x + M\_{22}y +M\_{23}}{M\_{31}x + M\_{32}y +M\_{33}} $

Now, say I wish to transform a **uniform** grid (blue) and obtain the transformed grid (green), as illustrated below.

My intuition tells me that the largest transformed tile (on the green grid) will be either in the top left, top right, bottom left or bottom right corners i.e. in one of the extreme corners.

Is there a (not necessarily formal) way to prove this?

# Answer
We can apply a linear transformation to get into the situation $$ \begin{align\*} x' &= \frac{x+C}{Ax+By+1} \\ y' &= \frac{y+D}{Ax+By+1} \end{align\*} $$ The Jacobian of the mapping $$ J = \begin{vmatrix} \frac{\partial x'}{\partial x} & \frac{\partial x'}{\partial y} \\ \frac{\partial y'}{\partial x} & \frac{\partial y'}{\partial y} \end{vmatrix} $$ is the infinitesimal area element of the mapping. That is, it is the area of an epsilonic rectangle around the image of a point $(x,y)$. In our case, the Jacobian turns out to be $$ J(x,y) = \frac{1-AC-BD}{(Ax+By+1)^3}. $$ This function is either increasing or decreasing in each of the inputs $x,y$, and so after the initial affine transformation, one of the corner rectangles has the maximal area (and same for the minimal area). The linear transformation might change the sense of the axes, but otherwise only affects the area by a constant factor.
> 1 votes

---
Tags: computational-geometry, image-processing
---


# Question
Title: Given Q constraints find the number of binary arrays of N elements
You have to find the number of arrays having N binary elements (0/1), that satisfy the Q given constraints. The constraints are of the form Li Ri Bi. Where if Bi is 0, then it means that the sum of the elements of the sub array between Li and Ri is even. If Bi is 1, it means that the sub array has odd sum.

Eg. N is 4 Q is 2. The constraints are 1 3 0 and 3 3 1. Then the answer is 4, the arrays are {1,0,1,1} {1,0,1,0} {0,1,1,0} {0,1,1,1}.

I am looking for a solution of complexity O((N+Q)log(N+Q)) or better.

# Answer
> 0 votes
Hint: You are looking for the number of solutions $(x\_1,\ldots,x\_N)$ over $\mathbb{Z}\_2$ (the field with two elements) of the system of equations $$ x\_{L\_1} + \cdots + x\_{R\_1} = B\_1 \\ \ldots\ldots\ldots\ldots\ldots\ldots\ldots \\ x\_{L\_Q} + \cdots + x\_{R\_Q} = B\_Q $$ Use linear algebra.

---
Tags: algorithms, combinatorics
---


title: OCR Computing Question

text:
# Question
Title: OCR Computing Question
I was asked the below question in a test at school last week and I thought the answer given was incorrect.

You had to give a file format from the options for the below statement:

A file created in software that most users will not have available

You had two options, PDF or DOCX. I answered DOCX but apparently the answer was PDF, what do you think?

# Answer
> 1 votes
This looks like an advertisement for Microsoft...

The intention was that while DOCX can be created using the rather expensive but commonly available Microsoft Word, PDF is created by Adobe Acrobat (not the free Reader!) which is not commonly available. However, there are many other ways to create PDFs, and nowadays you can print to PDF even on Windows, which is roughly as commonly available as Microsoft Word.

In conclusion, it's an oversight by the question setters, who appear to be parroting material which has been influenced by Microsoft for obvious commercial purposes.

---
Tags: ocr
---


# Question
Title: Find which bundles can be demanded together
This question comes from economics. There is a market $M$ that contains $m$ items. There is a *value function* $v:2^M\to \mathbb{R}$, that assigns a monetary value to each "bundle" (- subset of $M$). The function is given by $2^m$ values - a value per bundle.

A *price-vector* $p$ is a vector that assigns to each item $x\in M$ a non-negative price $p\_x$. Given a price-vector, the *net utility* of a bundle is its value minus its price, i.e:

$$ u(X) = v(X) - \sum\_{x\in X}p\_x$$

A bundle is called *demanded* if its net-utility is maximal - no bundle has larger net-utility.

A pair of bundles is called a *demand-pair* if there exists a price-vector such that both of these bundles are demanded (i.e, they have the same net-utility and it is maximal).

**I am looking for an algorithm that receives the valuation $v$ and finds all demand-pairs**.

For example, suppose there are $m=2$ items and the valuation function is:

$v(\emptyset)=0$, $v(\\{x\\})=2$, $v(\\{y\\})=3$, $v(\\{x,y\\})=4$.

Then:

* $\\{y\\}$ and $\\{x,y\\}$ are demand-pairs, because when $p\_x=1,p\_y=0$, both these bundles have net-utility 3, which is maximal.
* $\\{\emptyset\\}$ and $\\{x,y\\}$ are not demand-pairs, because if they have the same net-utility, then this utility must be 0. Then, necessarily $p\_x+p\_y=5$; but then either $p\_x\<2$ or $p\_y\<3$; but then either $\\{x\\}$ or $\\{y\\}$ (or both) have a net-utility of more than 0, so $\emptyset$ is not demanded.

# Answer
This can be solved in polynomial time, by solving $2^{2m}$ linear programs. (That might look exponential, but is polynomial in the size of the input, as the input size is $2^m$.)

Given a pair of bundles, you can check whether it is a demand-pair using linear programming; see below. So, you can apply this to all candidate pairs.

Suppose we have two bundles, $X,Y$, and we want to know if they are a demand-pair. Introduce a variable $p\_x$ for each $x \in M$. It's easy to write a linear equality that expresses that $X,Y$ have the same net-utility: $u(X)=u(Y)$. Also, it's easy to write linear inequalities to express that no other bundle has higher net-utility: $u(X) \ge u(Z)$ for all other bundles $Z$. Each of those is a linear (in)equality on the variables $p\_x$. We also have the inequalities $p\_x \ge 0$. Now use linear programming to test whether all of those inequalities are simultaneously satisfiable; if they are, there exists a price-vector where $X,Y$ are simultaneously demanded.

As an optimization, note that $X,Y$ are a demand-pair for market $M$ iff they are a demand-pair for market $X \cup Y$: without loss of generality you can set the price of every item in $(X \cup Y) \setminus M$ to $+\infty$. Also, without loss of generality you can set the price of every item in $X \cap Y$ to 0. Consequently, $X,Y$ is a demand-pair for market $M$ iff $X'=X \setminus Y$ and $Y'=Y \setminus X$ are a demand-pair for market $X' \cup Y'$. This will make each linear program smaller and more efficient to solve. It also means that you only need to test pairs that have no common intersection, so it suffices to test at most $3^m$ pairs $X',Y'$.
> 2 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: In context-free grammar (CFG), what is the importance of doing both leftmost and rightmost derivations?
I am a beginner learning theoretical computer science. While learning about CFG, I found that doing both leftmost and rightmost derivations gave me the same parse tree.

So, my question is: Why is it necessary to do both of them? What are we trying to really prove by doing them?

# Answer
For one particular parse tree there are many possible derivations, depending on the order in which the expansions are done. In a sense, a parse tree represent all of the derivations you'd consider "the same" (as you state). It is easy to see that for a given derivation tree there is exactly one leftmost and one rightmost derivation, which in a sense also represent the set of the derivations you'd deem "the same".

For applications, you are interested in the parse tree as a representation of some underlying structure that has a specific meaning. For example, the parse tree of an expression describes the order in which operations are to be performed. If some string has several parse trees, there is no single meaning (the grammar is *ambiguous*), that is clearly useless.

Reconstructing a (hopefully the only) parse tree for a string is *parsing*, different parsing methods reconstruct leftmost or rightmost derivations.
> 9 votes

# Answer
The only practical reason derivations are important is that you want to **invert** them ("parsing"), and when doing so this affects the capabilities and efficiency of the resulting parsing algorithm.

Look up *"non-canonical parsers"* to get an idea of what this means.
> 5 votes

---
Tags: context-free, formal-grammars
---


# Question
Title: Reduce knapsack to problem with {0,1}-Matrix
I'm looking for a problem, where i can reduce the knapsack feasibility problem:

$$a^Tx=b,\ \textbf{with} \ a\in \mathbb{N}^n,b \in \mathbb{N}, x \in \\{0,1\\}^n$$

to a problem, where i have a matrix with only {0,1} entries. What would be a suitable problem, where there is easy reduction?

# Answer
> 0 votes
I think you want to prove the Knapsack Feasibility problem NP-complete by reducing an NP-complete problem to it. If that is what you want to do, then following will suffice:

PARTITION $\leq\_P$ KS\_FEASIBILITY

Let the PARTITION instance be $S = \\{a\_i\ |\ 1 \leq i \leq n\\}$, with weights $w(a\_i) \in N$ and total weight $B = \Sigma\_n w(a\_i)$.

We can reduce partition to KS\_Feasibility as:

$\[w(a\_1) w(a\_2)...w(a\_n)\] \begin{bmatrix} x\_1\\x\_2\\\...\\x\_n\end{bmatrix} = B/2$, $x\_i \in \\{0,1\\}$ for $1 \leq i \leq n$.

Then PARTITION has a solution iff KS\_FEASIBILITY has a solution.

Thus KS\_FEASIBILITY is NP-complete.

---
Tags: complexity-theory, np-complete, reductions, np-hard, decision-problem
---


title: Express product in ILP

text:
# Question
Title: Express product in ILP
Suppose I have a mixed integer-linear program (MILP) with variables $x,y,z$, where $y$ is a 0-or-1 variable, and I want to impose the constraint $z=xy$. This is not expressible in a MILP directly. Is there a way to express this using linear inequalities, by adding some new variables (possibly variables restricted to integers)?

To put it another way: I want to express the constraint $(z=0 \land y=0) \lor (z=x \land y=1)$, in a situation where I already know $y$ is constrained to be either 0 or 1.

# Answer
It depends on $x$ being bounded or not.

Suppose that $x$ is bounded as $x\in\[0,x\_{\mathrm{max}}\]$. Then, the constraint $z=xy$ can be written as: $$ \begin{cases} z\leq x\_{\mathrm{max}} y,\\ z\leq x,\\ z\geq x-(1-y)x\_{\mathrm{max}},\\ z\geq 0. \end{cases} $$

You easily see that:

* if $y=0$, then $z=0$; and
* if $y=1$, then $z=x$.
> 2 votes

---
Tags: linear-programming, integer-programming
---


# Question
Title: Does the Kolmogorov complexity of a program $p$ generating a string $x$ equal the complexity of $x$ up to constant?
If $U$ is a universal prefix Turing machine, $U(p)=x$ for some program $p$ and string $x$, is it true that $K(x)=K(p)+O(1)$, with $K$ being the prefix Kolmogorov complexity?

# Answer
> 1 votes
I guess, I have found the answer myself: no.

Let $q$ be a shortest program that generates $x$: $K(x)=l(q)$. It is enough to concatenate any incompressible string $s$ not sharing information with $q$ and setting $p=\bar{q}s$. Let $m$ be the number of a Turing machine $T\_m$ in the standard enumeration, that takes $p$, executes $q$ and discards $s$. Then, $U(\langle m,p\rangle)=T\_m(p)=x$. However, $K(p)\ge l(q)+l(s)+O(1)\>l(q)=K(x)$. We thus have constructed a $p$ that contradicts the claim.

---
Tags: turing-machines, kolmogorov-complexity
---