# Question
Title: Algorithm to solve Turing's "Halting problem"
> "Alan Turing proved in 1936 that a general algorithm to solve the halting problem for *all* possible program-input pairs cannot exist"

Can I find a general algorithm to solve the halting problem for *some* possible program input pairs?

Can I find a programming language (or languages), where I for every kind of program in this language, it can decide if the program terminates or run forever?

# Answer
> 27 votes
> Can I find a general algorithm to solve the halting problem for some possible program input pairs?

Yes, sure. For example you could write an algorithm that returns "Yes, it terminates" for any program which contains neither loops nor recursion and "No, it does not terminate" for any program that contains a `while(true)` loop that will definitely be reached and doesn't contain a break statement, and "Dunno" for everything else.

> Can I find a programming language (or languages), where I for every kind of program in this language, it can decide if the program terminates or run forever?

Not if that language is Turing-complete, no.

However there are non-Turing complete languages like for example Coq, Agda or Microsoft Dafny for which the Halting Problem is decidable (and in fact is decided by their respective type systems, making them total languages (i.e. a program that might not terminate will not compile)).

# Answer
> 3 votes
I think all the answers here completely and utterly miss the point. The answer to the question is: assuming the program is intended to halt, then yes you *had better* be able to show it stops. If you cannot show it stops easily then the program should be considered very badly written and rejected by Quality Control as such.

Whether you can actually write a suitable machine algorithm depends on the input programming language and how ambitious you are. It is a reasonable design goal for a programming language to make it easily possible to prove termination.

If the language is C++ you probably can't write the tool, indeed it is unlikely you'd ever get the parser going, let alone prove termination. For a better structured language, you should at be able to generate a proof, or at least do so with certain assumptions: in the latter case the tool should output these assumptions. A similar approach would be to include termination assertions in the language and use them in complex situations where the tool would trust the assertions.

The bottom line is that no one seems to understand that proof a program halts is indeed possible because (good) programmers intending to write such halting programs always do so intentionally and with a mental picture of why they terminate and act correctly: such code is deliberately written so it is clear that they halt and are correct and if a reasonable algorithm cannot prove this, possibly with some hints, then the program should be rejected.

The point: programmers don't write arbitrary programs, so the thesis of the halting theorem isn't satisfied and the conclusion doesn't apply.

# Answer
> 3 votes
excellent and (prob unintentionally deep) question. there are indeed halting-detecting programs that can succeed on limited sets of inputs. its an active area of research. it has very strong ties to (automated) theorem proving areas.

however computer science does not appear to have an exact term for "programs" that "sometimes" succeed. the word "algorithm" is usually reserved for programs that always halt.

the concept seems to be distinctly different than *probabilistic algorithms* where CS theorists insist there be some known or computable probability on their succeeding.

there is a term *semialgorithms* that is used sometimes but its apparently a synonym for recursively enumerable or noncomputable.

so for purposes here, call them *quasialgorithms*. the concept is different than decidable vs undecidable.

one might say that one cannot compare quasialgorithms. but in fact there seems to be a natural hierarchy (a partial ordering) of these quasialgorithms. suppose a quasialgorithm $A$ can detect halting of some limited set of input programs say $X$. another one $B$ can detect halting of a set $Y$. if $X \subset Y$ ie $X$ is *proper* subset of $Y$ then $B$ is "more powerful" than $A$.

in CS this "quasi algorithm hierarchy" seems to be studied mostly only informally so far.

it shows up in busy beaver research\[1\] and the PCP problem\[2\]. in fact a DNA based computing attack on PCP can be seen as a quasialgorithm.\[3\] and its seen in other areas already noted such as theorem proving\[4\].

\[1\] New millenium attack on the busy beaver problem

\[2\] Tackling Posts correspondence problem by Zhao (v2?)

\[3\] Using DNA to solve the Bounded Post Correspondence Problem by Kari et al

\[4\] proving program termination by Cook et al, Comm. of the ACM

(so this is actually a very deep question that defn deserves to be on TCS.SE imho... maybe someone can re-ask it there in a way such that it fits & stays)

# Answer
> 2 votes
As long as the programming language in question is sufficiently complex (i.e. if it is Turing complete), then there are always programs in the language which no program can prove to terminate.

~~Since all but the most primitive languages are Turing complete (it only takes something like variables and conditionals), you could really only build very small toy languages for which you could solve the halting problem.~~

*Edit:* In light of the comments, let me be more explicit: Any language that you might design for which you could solve the halting problem would necessarily have to be Turing-incomplete. This rules out any language that contains a suitable set of basic ingredients (e.g. "variables, conditionals and jumps", or as @sepp2k says, a generic "while"-loop).

Apparently there exist several practical "simple" languages like that (e.g. theorem solvers such as Coq and Agda). If those satisfy your notion of a "programming language", you might investigate whether they satisfy some sort of completeness, or whether the halting problem is solvable for them.

# Answer
> 2 votes
Consider some formal theory $T$. Consider TMs augmented with proofs in $T$ that they halt/do not halt. Then we can decide whether a given TM-proof pair is halting by verifying the proof. (The examples given in sepp2k's answer are special cases).

This is quite trivial. If we take the union of any c.e. subset of halting TMs and any c.e. subset of non-halting TMs, the result will be set of TMs for which the halting problem is decidable (run both machines in parallel, if the first one accept the TM halts, if the second one accepts then the machine does not halt). However this will not lead to much interesting languages.

The reason is simple: in practice, we usually don't care if a program halts on one particular input but when if it halts on set of inputs, and in that case we have a universal quantifier which cannot be verified as soon as programs are expressive enough. How expressive? A very small amount of expressiveness is sufficient (e.g. $\mathsf{ALogTime}$). As soon as the programs are powerful enough to express if a given string $c$ is a halting computation of a Turing machine $M$ on a blank input (a completely syntactic problem that can be solved quite easily) then the halting problem for those programs becomes undecidable.

# Answer
> 1 votes
Yes you can, but I doubt it will be useful. You'd probably have to do it be case analysis and then you'd only be able to look for the most obvious cases. For example, you could grep a file for the code `while(true){}`. If the file has that code it will never terminate^. More generally you could say that a program with no loop or recursion will always terminate and there are several cases you could do that could guarantee that a program will or will not terminate, but for even a mid-size program this would be very difficult and in many cases would not be able to give you an answer.

**tl;dr:** Yes, but you won't be able to have it be useful for most useful programs.

---

^ Yes, technically if that code is not on the code-path or there are other threads it could still terminate, but I'm making a general point here.

---
Tags: computability, formal-methods, halting-problem, software-verification
---


# Question
Title: Recursive complexity with change of variable
I face a problem with computing a complexity. I have this equality : $P(u) = (\sqrt{u}+1)P(\sqrt{u}) + \theta(\sqrt{u})$

And I want to prove that $P(u) = O(u)$

This is how I process :

I put $m = \lg\lg u \implies P(u) = P(2^{2^{m}}) = (2^{2^{m-1}}+1)P(2^{2^{m-1}}) + \theta(2^{2^{m-1}})$

Now, I consider $S(m)$ that is : $S(m) = P(2^{2^{m}}) = mS(m-1) + \theta(m-1)$

And here I have a problem. I obtain a factorial complexity and I don't know how to integrate $\lg$ to prove the equality $P(u) = O(u)$

Some advice ?

# Answer
> 4 votes
Following your suggestion, let $S(m) = P(2^{2^m})$, and let's forget about the $+1$ in the recurrence. Then $$ \begin{align\*} S(m) &= 2^{2^{m-1}}S(m-1) + \Theta(2^{2^{m-1}}) \\ &= \Theta(2^{2^{m-1}} + 2^{2^{m-1}+2^{m-2}}) + 2^{2^{m-1}+2^{m-2}} S(m-2) \\ &= \cdots \\ &= \Theta(2^{2^{m-1}} + 2^{2^{m-1}+2^{m-2}} + \cdots + 2^{2^{m-1}+\cdots+1}) \\ &= %\Theta(2^{2^m-1}(1+2^{-1}+2^{-1-2}+\cdots+2^{-1-2-\cdots-2^{m-2}})) \\ &= \Theta(2^{2^m}(2^{-1}+2^{-2}+\cdots+2^{-2^{m-1}})) = \Theta(2^{2^m}). \end{align\*} $$

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Time complexity of an enumeration of SUBSET SUM instances
An instance of the **SUBSET SUM** problem (given $y$ and $A = \\{x\_1,...,x\_n\\}$ is there a non-empty subset of $A$ whose sum is $y$) can be represented on a one-tape Turing Machine with a list of comma separated numbers in binary format. If $\Sigma = \\{0,1,\\#\\}$ a reasonable format could be:

$( 1 \\; (0|1)^\* \\; \\#)^\* \\#$

Where the first required argument is the value $y$ and $\\#\\#$ encodes the end of the input. For example:

```
 1  0  0  #  1  0  #  1  #  #
^^^^^^^^     ^^^^     ^
   y          x1     x2
Instance: y=4, A={2,1}

```

I would like to enumerate the SUBSET SUM instances.

> **Question**: What is the (best) time complexity that can be achieved by a Turing Machine $TM\_{Enum}$ that on input $m$ (which can be represented on the tape with a string of size $\log m + 1$) - outputs the $m$-th SUBSET SUM instance in the above format?

**EDIT**:

Yuval's answer is fine, this is only a longer explanation.

Without loss of generality we set that $y \> 0$ and $0 \< x\_1 \leq x\_2 \leq ... \leq x\_n$, $n \geq 0$

And we can represent an instance of subset sum using this encoding:

$y \\# x\_1\\# d\_2\\# ...\\# d\_{n} \\#\\#$ where $d\_i \geq 1, x\_i = x\_{i-1} + d\_i - 1 \\; , i \geq 2$

Using a binary representation for $y,x\_1, d\_2, d\_3, ...$ we have the following representation:

$1 \\; ((0|1)^\* \\# 1)^\* \\; \\#\\#$

Equivalent to $1 \\; (0|1|\\#1)^\* \\; \\#\\#$. There is always a leading 1 and a trailing ## so we can consider only the $(0|1|\\#1)^\*$ part.

So the decoder TM on input $m$ in binary format should:

* output the leading 1
* convert $m$ to base 3 mapping digit 2 to $\\#1$
* when outputing the i-th intermediate $\\#$ calculate $x\_i = d\_i + x\_{i-1}-1$
* output the trailing $\\#\\#$

No duplicate instances are generated.

# Answer
> 3 votes
SUBSET-SUM instances can be encoded in base 3. We have codes for $0,1,\\#$. Some codings are invalid, but in that case we can just immediately output $\\#\\#$ (or $\\#$, if we have just written $\\#$). Every SUBSET-SUM problem has infinitely many encodings, I hope that's not a problem.

If the input has length $\ell$, then (assuming the tape alphabet has at least 4 symbols) we can do the conversion in time $O(\ell^2)$. I don't know whether this is the "best" time complexity achievable.

Edit: Here is a better encoding. We still have only three input codes, $0,1,\\#$. The output string always starts with $1$ and ends with $\\#\\#$. Further, $\\#$ is output as $\\#1$. Now each output string is generated once, though several output strings could correspond to the same instance.

As an example, your instance is encoded by "00#0#".

---
Tags: algorithms, formal-languages, turing-machines, enumeration
---


# Question
Title: What helpful solution does the Halting Problem give to computing?
What problem does the halting problem solve in computing, whether theoretical or practical?

It is very easy to debug code which loops forever, just signal the debugger to break if the program is running for too long? What purpose / good is the halting problem? Why was Turing praised for it?

# Answer
> 15 votes
The halting problem is an example of a problem that a computer cannot solve. On the face of it, it might seem that computers can do anything, given enough resources and time. However, Turing showed that this intuition is false. Later on this was made more tangible by showing that a computer cannot decide whether a given Diophantine equation has solutions in the positive integers.

This is similar to Gödel's incompleteness theorem, which shows that the axiomatic method doesn't provide an answer to all possible questions. In fact, no finite list of axioms is enough to determine the truth of every statement regarding the natural numbers. Later on, a natural example emerged in the realm of set theory, namely the continuum hypothesis.

# Answer
> 7 votes
Just an extended (informal) comment.

As explained in Yuval's answer the halting problem is not computable.

But even if you were able to connect a Turing machine to a black-box (*oracle*) that solves it (i.e. the Turing machine sends a program $M$ and an input $x$ to the black-box and receives an answer whether $m$ halts on $x$ or not), you'll soon be in trouble again because the device *TM+HALT black-box* \- a "hypercomputer" - cannot solve the "*hyper-halting problem*" for devices of its kind: i.e. given an hypercomputer program $H$ and an input $x$, an hypercomputer cannot decide if $H$ halts on $x$.

You can continue adding more black-boxes but *the halting-problem will always be with you* :-) (see Wikipedia for references about the Arithmetic Hierarchy)

---
Tags: computability, terminology, halting-problem
---


title: Left-Factoring a grammar into LL(1)

text:
# Question
Title: Left-Factoring a grammar into LL(1)
I have a homework assignment where I need to convert a grammar into LL(1). I've already removed the left recursion, but I'm having trouble doing left-factoring. All of the examples I've found are simple, and look something like this:

`A -> aX | aY`
becomes:
`A -> aZ`
`Z -> X | Y`

I understand that. However, my grammar looks more like this:

```
X -> aE | IXE | (X)E
E -> IE | BXE | ϵ
I -> ++ | --
B -> + | - | ϵ

```

I'm not sure how to apply the simpler example to this. I've been trying for at least a couple of hours and I've lost track of all of the things I've tried. Generally, my attempts have looked something like this:

```
X  -> X' | IXE
X' -> aE | (X)E
E  -> IE | BIX'E | BX'E | ϵ

```

And I then try to convert the E rules into ones having only one production starting with + or -:

```
X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> IE | B'IX'E | IX'E | B'X'E | X'E | ϵ

```

And then...

```
X  -> X' | IXE
X' -> aE | (X)E
B' -> + | -
E  -> +P | -M | ϵ
P  -> +E | IX'E | +X'E | X'E
M  -> -E | IX'E | -X'E | X'E

```

And so on. But I continually end up with a lot of extra nonterminals, and some very long productions / chains of productions, without actually having left-factored it. I'm not sure how to approach this - I can't seem to eliminate *some* nonterminal having multiple productions starting with a + and with a -.

# Answer
Let's have a look at your grammar:

$\qquad \begin{align} X &\to aE \mid IXE \mid (X)E \\ E &\to IE \mid BXE \mid \varepsilon \\ I &\to \text{++} \mid \text{--} \\ B &\to \text{+} \mid \text{-} \mid \varepsilon \end{align}$

Note that $X$ does not need left-factoring: all rules have disjoint FIRST sets¹. If you want to make this obvious, you can drop $I$ and inline it:

$\qquad \begin{align} X &\to aE \mid \text{++}XE \mid \text{--}XE \mid (X)E \\ E &\to \text{++}E \mid \text{--}E \mid BXE \mid \varepsilon \\ B &\to \text{+} \mid \text{-} \mid \varepsilon \end{align}$

Similarly, we can inline $B$:

$\qquad \begin{align} X &\to aE \mid \text{++}XE \mid \text{--}XE \mid (X)E \\ E &\to \text{++}E \mid \text{--}E \mid \text{+}XE \mid \text{-}XE \mid XE \mid \varepsilon \end{align}$

Now we see that we actually have to do left-factoring on $E$: we have obvious conflicts, and we get additional conflicts via $XE$. So, let's inline $X$ once at $XE$:

$\qquad \begin{align} X &\to aE \mid \text{++}XE \mid \text{--}XE \mid (X)E \\ E &\to \text{++}E \mid \text{--}E \mid \text{+}XE \mid \text{-}XE \mid aEE \mid \text{++}XEE \mid \text{--}XEE \mid (X)EE \mid \varepsilon \end{align}$

And now we can left-factor as easily as in your example:

$\qquad \begin{align} X &\to aE \mid \text{++}XE \mid \text{--}XE \mid (X)E \\ E &\to \text{+}P \mid \text{-}M \mid aEE \mid (X)EE \mid \varepsilon \\ P &\to \text{+}E \mid XE \mid \text{+}XEE \\ M &\to \text{-}E \mid XE \mid \text{-}XEE \end{align}$

By now we can see that we are not getting anywhere: by factoring away $\text{+}$ or $\text{-}$ from the alternatives, we dig up another $X$ which again has both $\text{+}$ and $\text{-}$ in its FIRST set.

So let's have a look at your language. Via

$\qquad \displaystyle X \Rightarrow aE \Rightarrow^\* aI^n E \Rightarrow aI^nBXE$

and

$\qquad \displaystyle X \Rightarrow aE \Rightarrow^\* aI^n E \Rightarrow aI^nIE$

you have *arbitrarily long* prefixes of the form $+^+$ which *end differently*, semantic-wise: an LL(1) parser can not decide whether any given (next) $\text{+}$ belongs to a *pair* -- which would mean choosing alternative $IE$ -- or comes alone -- which would mean choosing $BXE$.

In consequence, it doesn't look like your *language* can be expressed by *any* LL(1) grammar, so trying to convert yours into one is futile.

It's even worse: as $BXE \Rightarrow BIXEE \Rightarrow^\* BI^n X E^n E$, you can not decide to chose $BXE$ with *any* finite look-ahead. This is not a formal proof, but it strongly suggests that your language is not even LL.

If you think about what you are doing -- mixing Polish notation with unary operators -- it is not very surprising that parsing should be hard. Basically, you have to count from the left *and* from the right to identify even a single $B$-$\text{+}$ in a long chain of $\text{+}$. If I think of multiple $B$-$\text{+}$ in a chain, I'm not even sure the language (with two *semantically different* but syntactically equal $\text{+}$) can be parsed deterministically (without backtracking) at all.

---

1. That would be the sets of terminals that can come first in derivations of a non-terminal/rule alternative.
> 13 votes

---
Tags: formal-languages, formal-grammars, parsers, left-recursion
---


title: Math for TCS major

text:
# Question
Title: Math for TCS major
I'm looking for a major in Theoretical Computer Science; specifically, I'm interested on complexity theory and probabilistic automata theory. As I'm graduating in one year, what advanced courses in math (like Galois theory or Harmonic analysis, for example) do you think would be useful to take over the next two semesters? Why?

# Answer
> 2 votes
*(A summary of the comments to the questions)*

pretty much any area of mathematics could be important in TCS, so you should do the best to strengthen your math background. Any tool you learn is a gain, and may be employed in some TCS (sub-)field.

This question was also answered in other SE, and very informative details can be found in:

1. what-kind-of-mathematical-background-is-needed-for-complexity-theory
2. Examples of “Unrelated” Mathematics Playing a Fundamental Role in TCS?
3. What math courses should I take to prepare for a CS masters or PhD?

---
Tags: complexity-theory, automata, education
---


title: An Alternative Hanoi Tower problem

text:
# Question
Title: An Alternative Hanoi Tower problem
We got tower $T\_1$ with $n$ odd disks (1,3,5,...) and tower $T\_2$ with $n$ even disks (2,4,6,...). Now we want to move all $2n$ disks to tower $T\_3$. If $T(p,q)$ is a recurrence relation of minimum number of moves we make to move $p$ disks from $T\_1$ and $q$ disks from $T\_2$ to $T\_3$, we must find $T(n,n)$.

If anyone has any idea, please share.

# Answer
> 5 votes
Let $T\_n$ be the the column of disks $1:2:…:n$.

Let's start by the end:

* $(T\_n)()()$ is the final configuration. The only mean to get there is by moving the disk $n-1$ on the stack $(n)$, so the remaining $T\_{n-2}$ should be on another stick. So we should get to:
* $(n)(n-1)(T\_{n-2})$ in $2^{n-2}$ steps: first move the $n-1$ disk then use $2^{n-2}-1$ steps with Hanoi maneuvers to move the $T\_{n-2}$. This again is accessible from
* $(n-2:n)(T\_{n-3}:n-1)()$ in $2^{n-3}$ steps, which again is reachable from
* $(n-4:n-2:n)(n-3:n-1)(T\_{n-5})$ in $2^{n-5}$ steps, from
* $(T\_{n-6}:n-4:n-2:n)(n-5:n-3:n-1)()$ in $2^{n-6}$ steps...

At the end we get $2^{n-2}+2^{n-3}+2^{n-5}+2^{n-6}+… +2^{n-3i+1}+2^{n-3i}+…+c$.

Which is about $3(8^{n/3-1}+8^{n/3-2}+…)= \frac378^{n/3}$ modulo some constant depending on the remaining modulo $6$ of $n$. Testing in practice to determine the constant gives the exact formula for $n$ disks which happens to be surprisingly simple:

$$ \left\lfloor \frac37 2^n \right\rfloor \enspace .$$

For $n∈\\{1,2,3,4,5,6,7,8\\}$ we get $\\{0,1,3,6,13,27,54,109\\}$ (the first five terms verified by hand) which happens to be OEIS's sequence A033129 which confirms that this is the fastest way.

---
Tags: algorithms, recurrence-relation, board-games, towers-of-hanoi
---


# Question
Title: Relation between problems and algorithms
From Wikipedia

> **a computational problem** is understood to be a task that is in principle amenable to being solved by a computer (i.e. the problem can be stated by a set of mathematical instructions). Informally, a computational problem consists of **problem instances** and **solutions** to these problem instances. For example, primality testing is the problem of determining whether a given number is prime or not. The instances of this problem are natural numbers, and the solution to an instance is yes or no based on whether the number is prime or not.
>
> ... A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to **analyzing the amount of resources needed by a particular algorithm to solve a problem**, whereas the latter asks a more general question about **all possible algorithms that could be used to solve the same problem**.

So a problem can be solved by multiple algorithms.

I was wondering if an algorithm can solve different problems, or can only solve one problem? Note that I distinguish a problem and its instances as in the quote.

# Answer
I think the question is more philosophical than scientific, and indeed, as @raphael mentioned, the problem is in the definition of a "Problem".

Algorithm, in the simplest way, is a function (a mapping). It gets an input (instance) $in \in I$ and gives an output $out \in O$. For any instance $in$ there is only a single output $out=\mathsf{ALG}(in)$. Therefore, the algorithm solves only a single problem — that is, it defines only a single mapping from $I$ to $O$.

True, if you have two problems (mappings), $P\_1 : I\_1 \to O\_1$ and $P\_2: I\_2 \to O\_2$ we can construct a "single" algorithm that solves "both". It gets as an input the pair $(in,type)$. If $type=1$ it returns $P\_1(in)$ and otherwise it returns $P\_2(in)$.

But again, this fancy algorithm can be seen as solving a **single** problem from the domain $(I\_1\cup I\_2) \times \\{1,2\\}$ into $O\_1 \cup O\_2$.
> 4 votes

# Answer
I think this can be answered in a fairly trivial way.

I could easily introduce a tag into the description of a problem and make my algorithm branch on that tag and then call more specific algorithms to solve the actual problem, thereby making an algorithm that solves more than one problem.

For instance, I can tag the input with $1$ if it is an instance of SUBSET-SUM and with a $2$ if it is an instance of HAMILTONIAN-PATH. Then the first step of my algorithm inspects the tag, and runs an algorithm for solving SUBSET-SUM if the tag is a $1$ or runs an algorithm for solving HAMILTONIAN-PATH if the tag is a $2$.
> 2 votes

# Answer
You can, for example, reduce problem A to a problem B, and then apply the classic algorithm for solving B to A. Therefore I'd say, you can apply algorithms to different problems.
> 1 votes

---
Tags: algorithms, complexity-theory, terminology
---


# Question
Title: Meaning of complexity of a computational problem
If I understand correctly, the complexity of solving a computational problem is defined in terms of which instance $I$ of the problem, what size $n$ of the problem instance, and what algorithm $A$ for solving the problem instance.

Is the complexity of the problem at a given size $n$ of the problem instance defined as $$ \min\_A \max\_{I\in \\{\text{instances of size }n\\}} \text{complexity}(A,I,n)? $$ Note that the solution to the above optimization $A^\*(n)$ and $I^\*(n)$ are both functions of instance size $n$.

Or is the complexity of the problem defined for some same algorithm for all the problem instances and all sizes of the problem instances?

Or is the complexity of the problem defined for some same instance for all the algorithms that solve the problem and all the problem instance sizes?

# Answer
You are missing one thing, namely that the optimal algorithm and worst instance are not simply functions of the instance size. Also, I am not sure that minimising/maximising algorithm and instance independently of each other is doing the right thing.

The complexity of a problem is the *complexity of an optimal algorithm solving the problem* in the chosen machine model. It's as simple as that, but of course we have to define what "optimal algorithm solving the problem" means. Note that we *have* to fix the machine model (in particular what to count, see below), as complexities can differ between models.

First, "solving the problem" is clear: for all inputs (that are instances of the problem), the algorithm should give the correct answer, i.e. terminate and produce the correct result, or don't terminate. Let's denote the set of all algorithms that solve problem $P$ with $\newcommand{\Alg}\[1\]{\mathsf{Alg}\_{#1}}\Alg{P}$.

Second, what is the "complexity" of an algorithm? There are many ways to investigate runtime; complexity theory has defaulted to *worst-case* time and *Landau classes*. Formally, we define the (worst-case) runtime function of some algorithm $A$ to be

$\qquad \displaystyle T\_A(n) = \max \\{ T\_A(x) \mid x \in I\_P, |x|= n \\}$

where $I\_P$ is the set of instances of the problem $P$ (which $A$ solves) and $T\_A(x)$¹ is the runtime of $A$ on input $x$² (in clock cycles, state transitions, whatever fits your machine model). Now, the complexity of $A$ is the *asymptotic growth* of $T\_A$. For example, if $T\_A(n) = 17n^2 - 5n + 13$, we would say "The complexity of $A$ is $\Theta(n^2)$".

Finally, an *optimal* algorithm (for $P$) is an algorithm with *minimal* complexity (among all algorithms in $\Alg{P}$)³.

---

1. We abuse notation here: depending on its parameter, $T\_A$ means different things. It is usually done this way, though, and we don't need the runtime on individual inputs later on.
2. Let's assume for the moment that we deal only with deterministic algorithms. Otherwise, there may be many different runtimes for a given input. In that case, we would choose the runtime of the longest computation; see here for reasons why.
3. Note that Landau-$O$ implies a partial order on functions: $f \leq g \iff \exists c \in \mathbb{N}.\\,\limsup\limits\_{n \to \infty} \frac{f(n)}{g(n)} \leq c$.
> 6 votes

---
Tags: complexity-theory, terminology
---


# Question
Title: When generating a PDA from a CFG do I have a receiving state?
Thw Wikipedia article on Pushdown automata doesn't explain what the receiving state is for the generated PDA it just states that there is but one state.

# Answer
Assuming that you mean accept state when you say receiving state, the construction given in the wikipedia article has one accept state, being the only state in the machine. It accepts when you reach the end of the input with an empty stack. However, the construction used there requires a slight abuse of notation, as you need the starting symbol from the grammar to be pushed to begin with, and you have to be able to push more than one symbol at a time. This isn't so bad, but a more detailed construction makes the conversion more obvious.

The basic approach is to simulate the CFG using the PDA, informally it reads symbols off the stack, if it's a nonterminal, it replaces it with its production, if it's a terminal, it matches it off the input. The input alphabet for the PDA is the same as the CFG, the stack alphabet is the input alphabet plus the set of nonterminals in the CFG and the end of stack symbol.

The basic backbone of the PDA is: Where $\\$$ is the special end of stack symbol, and $S$ is the start symbol of the grammar.

The "production rules" transition represents a bunch of loops that simulate each production of the grammar. Given a production $X \rightarrow \chi\_{1}\ldots\chi\_{n}$ where the $\chi\_{i}$'s are either terminals or nonterminals, we add a loop starting and ending at $q\_{3}$ that looks like: Note that I've opened the loop, and the first and last state are the same.

The last past is the "terminal rules" loop, which represent a bunch of loops (one for each terminal symbol), that match terminals pushed onto the stack by the productions to terminals in the input:

So hopefully you can see how the simulation works, the PDA literally walks through the steps of the CFG, sticking terminals and nonterminals on the stack, replacing nonterminals with their productions, and matching terminals off the input. Then it can only reach the accept state if you can match the entire input (and hence there must be some series of grammar rules that get you there).
> 7 votes

# Answer
There are several equivalent PDA models:

1. In one model, "By accepting state", the PDA accepts if at the end of processing the input, the automaton is in an accepting state.
2. In another model, "By empty stack", the PDA accepts if at the end of processing the input, the stack is empty (regardless of the state the PDA ends at)
3. Although the two above models are enough, sometimes people combine them to a model that accepts "By stack and state", in which the PDA accepts only if at the end of the computation, the automaton is at an accepting state, and the stack is empty.

The construction you mentioned in your question (the one that appears on the Wiki page) has only one state. Clearly, this means we cannot be in the first model (otherwise, the PDA will always accept either $\Sigma^\*$ or $\emptyset$, because there's only one state which is either final or not). Therefore, the model implied in the wiki page is "by emptying the stack". (or "By state and stack", assuming the single-state is accepting)

Indeed, the PDA uses the grammar to non-deterministically derive the input word on the stack, and at the same time, on the fly, checks that the input and the derived word on the stack are equal (popping form the stack any checked letter). If the non-deterministic process derived exactly the input word, this process succeeds, and at the end of the computation the stack will be empty and the PDA will accept (Alternatively, there *exists* a computation path that will accept—the one in which the input word is derived on the stack). On the other hand, if the input word cannot be generated by the grammar, then no computation path can generate the input word on the stack, and the computation (any computation path) is bound to reject.
> 4 votes

---
Tags: terminology, automata, pushdown-automata
---


# Question
Title: What is the difference between a module in a monolithic kernel and a server in a microkernel?
I´m not exactly sure what kind of impact these two things have on kernel design. Are servers more flexible because of running in user space, for instance, and does adding a module require a new build of a kernel?

# Answer
Basically, a `module` runs at the same memory space than the kernel and a `server` runs in a different one.

Although a `module` can surely be added/removed on-the-fly (linux kernel does that), any misbehavior caused by it may affect the entire system, whether in the micro-kernel architecture, only the `server` gets compromised.
> 4 votes

---
Tags: operating-systems, os-kernel
---


# Question
Title: Ambiguous grammar? Could the grammar be parsed by SLR parser?
I got one grammar:

```
re2: re1 $

re1: expr == expr | expr != expr | expr < expr | expr <= expr | expr >= expr | expr > expr | expr

expr: expr + term | expr - term | term

term: term * factor | term / factor | factor

factor: (expr) | num | id

num: (0|1|2|3|4|5|6|7|8|9)num | ε

id: (a|b|....|z|A|B|....|Z|)id | ε

Here are the FOLLOW sets:

FOLLOW(r2) = {}
FOLLOW(r1) = {$}
FOLLOW(expr) = {=,!,<,>,+,-,)}
FOLLOW(term) = FOLLOW(factor) = FOLLOW (id) = FOLLOW (num) = {=,!,<,>,+,-,),*,/}

```

Now this grammar clearly got reduce-reduce conflict from num: ε and id: ε because FOLLOW(num) ∩ FOLLOW(id) != empty set

Now let's say I fix the grammar by doing the following (I assume it is mistake in the grammar because (ε == ε) makes no sense):

```
num: (0|1|2|3|4|5|6|7|8|9)num | (0|1|2|3|4|5|6|7|8|9)
id: (a|b|....|z|A|B|....|Z|)id | (a|b|....|z|A|B|....|Z|)

```

Now my question is, is this grammar SLR i.e can it be parsed by SLR parser? I know by building the parser I can find out but on exam I can not make the whole parser and then determine (I would lose lot of time).

# Answer
> 1 votes
Your grammar indeed is ambiguous as it currently is, but not because the follow sets of two nonterminals have common elements. The ambiguity I see is that both re2 -\> re1 -\> expr -\> term -\> factor -\> num -\> ε and re2 -\> re1 -\> expr -\> term -\> factor -\> id -\> ε derive the empty word. If you require that num and id are both nonempty, then your grammar is SLR(1) (unless you do weird things to make num and id nonempty).

As an example where your 'follow test' does not work is the following:

```
S -> A c
S -> B c
A -> a
B -> b

```

The follow sets of A and B both contain c, but the grammar is SLR(1).

Unfortunately, the only three options I know to test whether a grammar is SLR(1) all have downsides: generating the table and doing the polynomial time test both take quite some time for an exam, and the third method, visual inspection of the grammar, is not very accurate. Finally, 'quickly' writing down the LR(0) automaton (by omitting the items in the states of the automaton) is possible but requires a lot of practice and is still somewhat inaccurate.

---
Tags: formal-languages, formal-grammars, compilers, parsing
---


# Question
Title: Is there any way to distinguish between LL(k) and LR(k) grammar?
I am recently studying about Compilers designing. I came to know about two types of grammar one is LL grammar and other is LR grammar.

We also know the facts that every LL grammar is LR that is LL grammar is a proper subset of LR grammar. First one is used in top-down parsing and the second one is used in bottom-up parsing.

But is there any way to so that we can say that a given grammar is LL or LR?

# Answer
We have to check only that a grammar is LL or not because every LL grammar is LR that is LL is proper subset of LR. So if a grammar is LL then it must be LR but every LR is not LL.

A grammar G is in LL iff whenever A-\>C|D , the following condition should hold:

1. First(C) and First(D) are disjoint sets.
2. If empty is in First(D) the First(C) and Follow(A) are disjoint sets likewise empty is in First(C).
> 3 votes

# Answer
$LL(k)$ and $LR(k)$ grammars are nice not just because they can be parsed efficiently, but also because we can check if a grammar is $LL(k)$ or $LR(k)$, and because we can generate tables for them (parse tables are used to parse input strings). Note that for these two classes, having the parse table immediately allows you to check whether the grammars are in the classes, because this is so if and only if the tables contain no errors. Also, yes, there are classes of grammars which we can parse efficiently if we have a parse table, but for which we cannot generate the table if it exists.

Any textbook on parsing methods will teach you how to generate the tables for $LL(1)$ methods and possibly also for $LR(1)$ (though $SLR(1)$ is more common). Textbooks such as Parsing Theory by Sippu and Soisalon-Soininen also treat the parse table generation for $LL(k)$ and $LR(k)$ grammars.

Unfortunately, for really weird grammars, the parse tables for $LL(k)$ and $LR(k)$ (though not for $LL(1)$) can blow up and become huge; they will do this even for normal grammars if $k$ is high enough. There are tests available that can check whether a grammar is $LL(k)$ or $LR(k)$ or not that run in polynomial time (table generation is exponential). For details, read the textbook above. Note that in a lot of cases, the table is reasonably sized, so the test is not needed.

If you don't want to try values of $k$ to see if your program works, but instead want to have your computer figure out whether there exists a value of $k$ such that your grammar is $LL(k)$ or $LR(k)$, you are unfortunately out of luck, as this is undecidable. If your grammar is $LR(k)$ for some $k$ though, you *can* decide whether your grammar is $LL(c)$ for some $c$, possibly different from $k$ (see here for details).
> 12 votes

---
Tags: formal-grammars, compilers, parsers, lr-k, ll-k
---


# Question
Title: What are current approaches to auto-parallelisation?
I am looking for answers which provide short overview of models and current state of research for auto-parallelisation of sequential code.

# Answer
Automatic parallelization in the most general terms is extracting a dependency graph from the execution sequence of the program and executing distinct paths in this graph in parallel with synchronization introduced at the nodes of the graph where the paths merge.

Our ability to extract the dependency information varies depending on the programming language used. Functional languages have no side effects that makes it easier to parallelize. It is more difficult with imperative languages. Several programming languages were proposed where parallelism may be implicit. Such as array programming languages.

Autoparallelization of inherently sequential programs like programs written in C or FORTRAN attracts significant practical interest. One classical reference work on the subject is Michael Wolfe's "*Optimizing Supercompilers for Supercomputers*" based on his 1982 PhD thesis \[1\].

One of the key areas of the work is parallelizing multidimensional loops. Observe that loop indices are often used in linear combinations inside loops (e.g. for a $N\times N$ matrix $a$ in a C language program `a[I][J]` is a reference to an element that lies at position `a + I * N + J`). Therefore dependencies between iterations can be expressed as linear equations. Thus the ability to solve systems of linear equations efficiently is important for autoparallelizing compilers.

In an important general case finding depdendencies between operators in a loop requires finding all solutions of a system of linear equations in integers. There exists no polynomial algorithm for finding a solution of such a system of equations, therefore approximate tests are employed, that can detect independence. An important class of tests are derived from Banerjee Inequality.

The essense of the method is as follows. Let $x$ and $y$ be vectors of unknowns of dimension $d$, and $\textrm{A}$, $\textrm{B}$ be some linear operators. For loop dependencies the values of indices usually have upper and lower bounds. Suppose $m\_i \leq x\_i,y\_i \leq M\_i$.

To test if a system of linear equations $\textrm{A}x - \textrm{B}y = c$ has a solution we find the upper bounds $UB\_j$ and lower bounds $LB\_j$ of $\textrm{A}x - \textrm{B}y$ for all possible values of $x$ and $y$, $m\_i \leq x\_i,y\_i \leq M\_i$ and test if $c$ lies within the bounds. If it does not, then there is no solution, and two memory references are independent, hence can be executed in parallel. This test is incomplete, but can be efficiently computed.

Different data-dependence heuristics are compared on real and synthetic benchmarks \[2\]. A recent overview of data-dependence analysis techniques can be found in the publications from the UCSD Kremlin project \[3\].

1. *M. Wolfe*, Optimizing Supercompilers for Supercomputers, 1989
2. *K. Psarris, K. Kyriakopoulos*, An Experimental Evaluation of Data Dependence Analysis Techniques, IEEE Transactions on Parallel and Distributed Systems, March 2004 (vol. 15 no. 3), pp. 196-213
3. *S. Garcia, D. Jeon, C. Louie, M.B. Taylor*, Kremlin: Rebooting and Rethinking gprof for the Multicore Age, PLDI'2011
> 3 votes

---
Tags: reference-request, compilers, parallel-computing, code-generation
---


# Question
Title: Expected gain of a game of chance with differently-priced tokens
Foo and Bar are playing a game of strategy. At the start of the game, there are $N$ apples, placed in a row (in straight line). The apples are numbered from $1$ to $N$. Each apple has a particular price value.

The price of $i$th apple is $p\_i$.

In this game, the players Foo and bar make an alternative move.

In each move, the player does the following:

* If there is more than one apple left, the player tosses an unbiased coin. If the outcome is head, the player takes the first apple among the apples that are currently present in a row in a straight line.
* If there is a single apple left, te player takes it.

The goal here is to calculate the expected total price value that Foo will get if Foo plays first.

```
Example 1:
N=5
Apple price val:
5 2 3 1 5

Answer is : 11.00

Example 2:
N=6
7 8 2 3 7 8

Answer : 21.250

Example 3:
N=3
1 4 9

First           Second      Third          Foo Total Val
Foo gets 1  Bar gets 4  Foo gets 9          10
Foo gets 1  Bar gets 9  Foo gets 4          5
Foo gets 9  Bar gets 1  Foo gets 4          13
Foo gets 9  Bar gets 4  Foo gets 1          10

probability 0.5 • 0.5 = 0.25.
Expected value (Foo)= (0.25 *10 )+ (0.25 *5) + (0.25*13)+ (0.25*10) = 9.500

```

I wrote the following code:

```
#include<iostream>
using namespace std;
double calculate(int start,int end,int num,int current);
int arr[2010];
int main()
{
    int T;
    scanf("%d",&T);
    for(int t=0;t<T;t++)
    {
        int N;
        scanf("%d",&N);
        for(int i=0;i<N;i++)
        {
            scanf("%d",&arr[i]);
        }
        printf("%.3lf\n",calculate(0,N-1,N/2+N%2,0));
    }

    return 0;
}
double calculate(int start,int end,int num,int current)
{
    if(num==current)
        return 0;
    double  value=0;
    value=.5*arr[start]+.5*arr[end]+.5*calculate(start+1,end,num,current+1)+.5*calculate(start,end-1,num,current+1);
    return value;
}

```

But the above code is quite slow. The constraints are: price of apples $p\_i \le 1000$; $1 \le N \le 2000$; there are 500 test cases. How can I solve this more efficiently?

# Answer
They probably meant you to solve it using dynamic programming. Since I'm guessing this is an exercise, I won't say anything more on this front. Also, your program is incorrect: it doesn't consider the actions of Bar.

The game is not really a *game of strategy*, since there are no choices involved, only chance. In order to compute the expected value that Foo gets, it is enough to compute the probability that Foo takes each particular item. Let $p\_{a,b}$ be the probability that Foo takes an item which is the $a$th from the left, $b$th from the right ($a,b \geq 0$, total number of elements is $a+b+1$). Then $$ \begin{align\*} p(0,0) &= 1, \\ p(0,1) &= 1/2, \\ p(1,0) &= 1/2, \\ p(1,1) &= 1/2, \\ p(0,b+2) &= 1/2 + p(0,b)/4, \\ p(a+2,0) &= 1/2 + p(a,0)/4, \\ p(1,b+2) &= p(0,b+1)/2 + p(1,b)/4, \\ p(a+2,1) &= p(a+1,0)/2 + p(a,1)/4, \\ p(a+2,b+2) &= (p(a+2,b)+2p(a+1,b+1)+p(a,b+2))/4. \end{align\*} $$ You could precompute the requisite values for $a+b+1 \leq 2000$ and then your program will be blazingly fast.

It turns out that for fixed $c$, $p(c,n-c)$ tends to a limit $p\_c = 1/2(1 + (-1)^c/3^{c+1})$. To see why, note first that $p\_0$ is the ability that if you and a friend alternate tossing fair coins, yours will come up HEAD first. There are many ways to see that $p\_0 = 2/3$. Next, we have the formula $p\_{c+1} = p\_0 (1-p\_c) + (1-p\_0) p\_c$ (exercise), from which the formula for $p\_c$ follows by induction.
> 4 votes

---
Tags: algorithms, game-theory
---


# Question
Title: Why are decision problems commonly used in complexity theory?
From Wikipedia:

> The type of computational problem: **The most commonly used problems are decision problems**. However, complexity classes can be defined based on function problems, counting problems, optimization problems, promise problems, etc.

I also saw the definitions of NP-complete, NP-hard, NP, ..., are defined for decision problems only. I wonder why that is the case?

Is it because any other problem can be equivalently converted to a decision problem?

# Answer
> 11 votes
Oftentimes decision problems are used because they allow a precise and simple definition of the problem and, as stated, many other problems can be converted to an equivalent decision problem.

Other types of problems are also considered in complexity theory, for instance Function Problems and Search Problems.

# Answer
> 5 votes
there are probably many different ways to answer this question however one key element is historical precedent. the disproof of the existence of an algorithm for the halting problem in 1936 by Turing uses the halting problem as a decision problem. this was in turn based on (and resolved negatively) Hilberts Entscheidungsproblem (1928) that asked for a systematic method of determining the truth or falsity of any well formed mathematical statement ie also a decision problem.

this in turn has some similarity to Hilberts 10th problem dating to 1900 that asks for the solution of integer Diophantine equations (many of his 23 frontier/pivotal research problems were stated as decision problems). yet note the Entscheidungsproblem even rooted in a much earlier concept of Leibniz as wikipedia states:

> The origin of the Entscheidungsproblem goes back to Gottfried Leibniz, who in the seventeenth century, after having constructed a successful mechanical calculating machine, dreamt of building a machine that could manipulate symbols in order to determine the truth values of mathematical statements.

also note that Diophantine equations date to the Greeks who were some of the 1st to consider, study, and emphasize the importance of mathematical proof. there are at least two important problems from number theory, still unresolved with much modern research, due to the Greeks: existence of infinite twin primes, and existence of odd perfect numbers.

note some "decision problems" (ie in the form of searching for proofs to open math conjectures) literally took *hundreds of years* to resolve eg Fermats Last Theorem, over 3.5 centuries, also in number theory.

so decision problems are very old, but even while simply stated can be *extremely hard*, and are essentially rooted in the question "is this statement true or false" relative to existence of proof(s). at the heart its a core mathematical concept. moreover it keeps reappearing in modern places in a fundamental and reminiscent way such as the P vs NP question (~1971) where the NP class can be defined/framed in terms of halting of an NP machine and solution of the satisfiability problem in P time.

---
Tags: complexity-theory, terminology
---


# Question
Title: How do I write a proof using induction on the length of the input string?
In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however when strings come into play I get real tripped up. I'd really appreciate it if someone would go through the process of making such a proof step by step.

Here's an example problem (Exercise 2.2.10 from Hopcroft and Ullman 3rd Edition):

> Consider the DFA with the following transition table:
>
> ```
>         0    1
>        ________
> -> A |  A    B
>   *B |  B    A
>
> ```
>
> Informally describe the language accepted by this DFA, and prove by induction on the length of an input string that your description is correct.

This is an answered problem in the book, so I'm not looking for someone to do my homework. I just need someone to explain it to me straight.

**Book's Answer:** (taken from here)

> The automaton tells whether the number of 1's seen is even (state A) or odd (state B), accepting in the latter case. It is an easy induction on |w| to show that dh(A,w) = A if and only if w has an even number of 1's. Basis: |w| = 0. Then w, the empty string surely has an even number of 1's, namely zero 1's, and δ-hat(A,w) = A.
>
> Induction: Assume the statement for strings shorter than w. Then w = za, where a is either 0 or 1.
>
> * **Case 1:** a = 0. If w has an even number of 1's, so does z. By the inductive hypothesis, δ-hat(A,z) = A. The transitions of the DFA tell us δ-hat(A,w) = A. If w has an odd number of 1's, then so does z. By the inductive hypothesis, δ-hat(A,z) = B, and the transitions of the DFA tell us δ-hat(A,w) = B. Thus, in this case, δ-hat(A,w) = A if and only if w has an even number of 1's.
> * **Case 2:** a = 1. If w has an even number of 1's, then z has an odd number of 1's. By the inductive hypothesis, δ-hat(A,z) = B. The transitions of the DFA tell us δ-hat(A,w) = A. If w has an odd number of 1's, then z has an even number of 1's. By the inductive hypothesis, δ-hat(A,z) = A, and the transitions of the DFA tell us δ-hat(A,w) = B. Thus, in this case as well, δ-hat(A,w) = A if and only if w has an even number of 1's.

I understand how to prove things like $\sum\_{i=0}^{n}i = \frac{n(n+1)}{2}$ using induction. I'm just confused by how this works with building strings. I'm confused by the bolded parts. I don't understand how they are come up with/how it actually proves what is accepted/how it is inductive.

δ-hat is the extended transition function, by the way.

# Answer
As it is unclear where your problem lies, I'll start at the very beginning.

Mathematical induction works like the game of Chinese whispers (in the ideal case, i.e. all communication is lossless) or (perfectly set up) dominoes: you start somewhere and show that your every next step does not break anything, assuming nothing has been broken till then.

More formally, every induction proof consists of three basic elements:

* Induction **anchor**, also **base case**: you show for small cases¹ that the claim holds.
* Induction **hypothesis**: you *assume* that the claim holds for a certain subset of the set you want to prove something about.
* Inductive **step**: Using the hypothesis, you show that the claim holds for more elements.

Of course, the step has to be tuned such that it covers the whole base set (in the limit).

Important note: people who are confident of their induction skills often gloss over the anchor and leave the hypothesis implicit. While this is fine when presenting your work to an expert audience (e.g. a paper), this is *not* recommended when doing proofs yourself, especially as a beginner. Write down everything.

---

Consider a simple example over $(\mathbb{N},\leq)$; we want to show that $\sum\_{i=0}^{n} i = \frac{n(n+1)}{2}$ holds for all $n \in \mathbb{N}$.

* **Anchor**: For $n=0$, $\sum\_{i=0}^{n} i = 0 = \frac{n(n+1)}{2}$ clearly holds.
* **Hypothesis**: Assume that $\sum\_{i=0}^{k} i = \frac{k(k+1)}{2}$ holds for an arbitrary, but fixed² $n \in \mathbb{N}$.
* **Step**: For $n+1$, compute the sum:

$\qquad \displaystyle \sum\_{i=0}^{n+1} i = (n+1) + \sum\_{i=0}^{n} i \overset{\text{IH}}{=} n+1 + \frac{n(n+1)}{2} = \frac{(n+2)(n+1)}{2}$

So the identity holds for $n+1$. (We note that we only needed a tiny part of the hypothesis, namely for $k=n$. That often happens.)

The inductive principle now assures us that the claim indeed holds: we have directly shown it for $0$. The step says, if it holds for $0$, it also holds for $1$; if it holds for $1$, it also holds for $2$; and so on.

---

Let's have a look at another example, this time on $(2^\mathbb{N}, \subseteq)$. The claim we want to prove is: for every finite subset $A$ of $\mathbb{N}$, the size of the power set $2^A$ of $A$ is $2^{|A|}$³. We perform our induction over $(\mathbb{N}, \leq)$, again, namely over the size of subsets $A$.

* **Anchor:** Consider the (only) set of size $0$, the empty set. Clearly, $2^\emptyset = \\{\emptyset\\}$ and therefore $|2^\emptyset| = 1 = 2^0$ as claimed.
* **Hypothesis:** Assume that for all sets $A \subseteq \mathbb{N}$ with $|A| \leq n$ with some arbitrary, but fixed $n \in \mathbb{N}$, we have $|2^A| = 2^{|A|}$.
* **Step:** Let $B \subseteq \mathbb{N}$ arbitrary⁴ of size $n+1$, and let $b \in B$ arbitrary (such $b$ exists as $n+1 \> 0$). Now the hypothesis applies to $B \setminus \\{b\\}$ and thus $|2^{B \setminus \\{b\\}}| = 2^n$. Since

$\qquad \displaystyle 2^B = 2^{B \setminus \\{b\\}} \cup \\{ A \cup \\{b\\}\mid A \in 2^{B \setminus \\{b\\}} \\}$,

we have indeed that $|2^{B}| = 2 \cdot |2^{B \setminus \\{b\\}}| = 2 \cdot 2^n = 2^{n+1}$ as claimed.

Again, by induction the claim is proven.

---

Now, for your problem can use a common trick: **strengthening the statement**. If you formulate your claim as "the automaton accepts all words with an odd number of ones", you get an induction hypothesis like "among all words of length $n$, exactly those with an odd number of ones are accepted by the automaton". This won't lead you anywhere since we don't know anything about how many ones are contained in which part of a given (accepted) word; the hypothesis does not apply on whatever you cut away of your arbitrarily selected word.

Therefore, you want to formulate a stronger claim: "The automaton is in state $B$ if and only if the consumed part of the input contained an odd number of ones", and show this one. Note that it implies the former claim.

* **Anchor**: After processing the only string of length zero, $\varepsilon$, the automaton is clearly in state $A$ as claimed.
* **Hypothesis**: Assume that claim holds for input fragments of length up to $n$ which is chosen arbitrarily, but fixed.
* **Step**: Consider an arbitrary word $w \in \\{0,1\\}^{n+1}$. There are two cases.
    1. $w$ contains an even number of ones. There are two cases for the last symbol.
        1. $w\_n = 0$: In this case, $w' = w\_1 \dots w\_{n-1}$ contains an even number of ones. By induction hypothesis, the automaton is in state $A$ after consuming $w'$. Consuming $w\_n = 0$ causes the automaton to stay in state $A$, as claimed.
        2. $w\_n = 1$: In this case, $w' = w\_1 \dots w\_{n-1}$ contains an odd number of ones. By induction hypothesis, the automaton is in state $B$ after consuming $w'$. Consuming $w\_n = 1$ causes the automaton to switch to state $A$, as claimed.
    2. $w$ contains an odd number of ones. Similar to case 1.

The principle of induction implies that the claim indeed holds.

---

1. You perform induction along some partial order; the anchor needs to cover all minimal elements, and sometimes more (depending on the statement).
2. The "arbitrary, but fixed" is essential! We can not change $n$ in the step and treat it as if it were a fixed number, but we can also not assume anything about it.
3. Denoting the power set with $2^A$ may seem weird. It is rooted in the observation that the power set is equivalent to the set of all functions from $A$ to ${0,1}$, which is denoted thus.
4. Choosing $B$ arbitrary is essential for covering the whole space. One may be tempted to say, "Take any such $A$ and add an element that was not there before.". In this case, that would do the same, but it can be easy to get wrong in more complicated settings (e.g. adding nodes to graphs). Always take an arbitrary larger object and then cut it apart to apply the hypothesis on its parts; never assemble the larger object from smaller which are covere by the hypothesis.
> 17 votes

---
Tags: automata, finite-automata, proof-techniques, reference-question, induction
---


# Question
Title: What piece am I missing to turn this idea into a programming language?
I've been doing some reading (I'll name drop along the way) and have selected a few scattered ideas that I think could be cobbled together into a nifty esoteric programming language. But I'm having some difficulty assembling the parts.

Kleene's Theorem states: Any Regular Set can be recognized by some Finite-State Machine (Minsky 4.3).

Minsky's Theorem 3.5: Every Finite-State machine is equivalent to, and can be "simulated by", some neural net.

"There is a natural way to represent any forest as a binary tree." (Knuth, v1, 333).

And according to Bentley (Programming Pearls, p.126) a binary tree can be encoded as a flat array.

So I'm imagining an array of bit-fields (say 4 bits so it can easily be worked with in hexadecimal). Each field indicates a type of automaton, and the positions of the array encode (via an intermediary binary tree representation) a forest which approximates (? missing piece ?) the power of a graph.

I'm somewhat bewildered by the possibilities of automaton sets to try, and of course the fun Universal Automata require three inputs (I worked up an algorithm inspired by Bentley to encode a ternary tree implicitly in a flat array, but it feels like the wrong direction). So I'd appreciate any side-bar guidance on that. Current best idea: the normal set: and or xor not nand nor, with remaining bits used for threshold weights on the inputs.

So the big piece I'm missing is a formalism for applying one of these nibble-strings to a datum. Any ideas or related research I should look into?

---

*Edit:* My theoretical support suggests that the type of computations will probably be limited to RL acceptors (and maybe generators, but I haven't thought that through).

So, I tried to find an example to flesh this out. The C `int isdigit(int c)` function performs a logical computation on (in effect) a bit-string. Assuming ASCII, where the valid digits are `0x30 0x31 0x32 0x33 0x34 0x35 0x36 0x37 0x38 0x39`, so bit 7 must be off, bit 6 must be off, bit 5 must be on, and bit 4 must be on: these giving us the 0x30 prefix; then bit 3 must be off (0-7) or if bit 3 is on, bit 2 must be off and bit 1 must be off (suppressing A-F), and don't care about bit 0 (allowing 8 and 9). If you represent the input *c* as a bit-array (`c[0]`..`c[7]`), this becomes

```
~c[7] & (~c[6] & (c[5] & (c[4] & (~c[3] | (~c[2] & ~c[1])))))

```

Arranging the operators into a tree (colon (:) represents a wire since pipe (|) is logical or),

```
c[7]  6   5   4   3   2   1   0
 ~    ~   :   :   ~   ~   ~   :
    &     :   :   :     &
       &      :      |
           &        :
                &

```

My thought based on this is to insert "input lead" tokens into the tree which receive the values of the input bit assigned in a left-to-right manner. And I also need a *ground* or *sink* to explicitly ignore certain inputs (like c\[0\] above).

This leads me to make NOT (~) a binary operator which negates the left input and simply absorbs right input. And in the course of trying this, I also realized the necessity for a ZERO token to build masks (and to provide dummy input for NOTs).

So the new set is: &(and) |(or) ^(xor) ~(not x, sink y) 0(zero) I(input)

So the tree becomes (flipping up for down)

```
                 ^
           &           &
       &       |      I 0
     &   I  ~     &
   &   I   I 0  ~   ~
 ~   ~         I 0 I 0
I 0 I 0
=   =  = = =   =   =  =
7   6  5 4 3   2   1  0

```

Which encodes into the array (skipping the "forest\<=\>tree" part, "\_" represents a blank)

```
_ ^ & & & | I 0 & I ~ & _ _ _ _ & I _ _ I 0 ~ ~ _
  _ _ _ _ _ _ _ ~ ~ _ _ _ _ _ _ _ _ _ _ I 0 I 0 _
  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ I 0 I 0

```

The tree-\>array encoding always put the root in array(1) so with zero-indexed array, there's a convenient blank at the beginning that could be used for linkage, I think.

With only 6 operators, I suppose it could be encoded in octal.

By packing a forest of trees, we could represent a chain of acceptors each applied on the next input depending on the result of the previous.

# Answer
This sounds more like the makings of a computational model rather than a programming language, as such, perhaps in the same way that the quantum computation can form the basis of a programming language such as the quantum lambda calculus.

Ask yourself:

* What kinds of computation are you trying to perform?
* How can these computations be composed?
* How can the results of these computations be stored? How can they be used in subsequent computations?
* How can I represent this syntactically?
* Does my chosen syntax have a clear denotational meaning? Or clear operational meaning?
* Do my syntactic constructs compose nicely? Are they sufficiently orthogonal and free from arbitrary constraints?
* Can I modularise computations in my language?
* What forms of abstraction does my language offer?

There are a number of places you could use as a starting point:

* The imperative language WHILE --- a simple language with variables, assignment, sequencing, if statements, and while statements. Maybe later add procedures.
* The lambda calculus.
* Combinatorial logic. Programs consist of combinators which are plugged together. No variables.
* Something like Prolog or Datalog.

Or you could be completely wild and ignore these and see how far you get (which could result in something interesting).
> 12 votes

# Answer
From the point of view of filling-out the machine model, the three criteria of Turing Completeness (Böhm-Jacopini theorem) appear useful.

* Sequence
* Selection
* Iteration or Recursion

It's clearly #3 that's missing at present, the fanciful "linkage" mentioned above.

---

*Edit: This doesn't really help dig me out of the hole with this question, but ...*

I was reading an old book on digital computer fundamentals and found this very nice representation of all possible functions of two binary inputs:

```
x y  F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16
0 0   0  1  0  1  0  1  0  1  0   1   0   1   0   1   0   1
0 1   0  0  1  1  0  0  1  1  0   0   1   1   0   0   1   1
1 0   0  0  0  0  1  1  1  1  0   0   0   0   1   1   1   1
1 1   0  0  0  0  0  0  0  0  1   1   1   1   1   1   1   1

 C =  0  1  2  3  4  5  6  7  8   9   A   B   C   D   E   F
(function code)

```

So take the function F *n*, store *n* as C = *n - 1*, and the Universal Binary Function is: C *x,y* = ( C \>\> ( 2 * x + y ) & 1 ). And it fits in one hex digit!

---

*Edit:* There's another piece missing from the above: representing a neural-net as a forest.

---

Combining the above Universal Binary Function table with the isdigit(c) example from the question gives

```
[0] used for "size"
 8
                      [1] tree root
                       8                       8 = X & Y (AND)

          [2]                     [3]          7 = ~(X & Y) (NAND)
           8                       7
                                               1 = ~(X | Y) (NOR)
     [4]        [5]         [6]         [7]
      1          8           7           C     C = X  (ignore Y)

   [8]  [9]  [10]  [11]  [12]  [13]  [14]  [15]
    c7   c6   c5    c4    c3    c2    c1    c0

```

Where each function is applied to its two children, and the 8 input values propagate upward toward the root, collapsing into the yielded value.

So, the (1 bit) isdigit(8bit c) function encodes into this array (with the argument row omitted).

```
8:8 8 7 1 8 7 C [. . . . . . . .]

```

---

For building data-types, I'm inspired by this brief description of the types in Konrad Zuse's *Plankalkül*,

> Binary n-bit numbers in the Plankalkül were represented by type `S1.n`. Another special type was used for *floating-binary* numbers, namely,
>
> > SΔ1 = (S1.3, S1.7, S1.22).
>
> The first three-bit component here was for signs and special markers‐‐ indicating, for example, whether the number was real or imaginary or zero; the second was for a seven-bit exponent in two's complement notation; and the final 22 bits represented the 23-bit fraction part of a normalized number, with the redundant leading-'1' bit suppressed. -- Knuth, "The Early Development of Programming Languages" in *Selected Papers on Computer Languages*, p. 10.
> 6 votes

# Answer
Ahh, the ever persistent question of how to design a language. For years I never had a good solid answer to that until I fond Cognitive dimensions of notations.

The author list out various dimensions, think orthogonal properties, which should be considered when designing a language. I wish I had found this decades ago.

Enjoy.
> 5 votes

---
Tags: programming-languages, finite-automata, arrays, neural-networks, machine-models
---


title: Complexity of optimized bubblesort

text:
# Question
Title: Complexity of optimized bubblesort
What is the runtime complexity of the following implementation of Bubblesort (for integers)?

```
    #define SWAP(a,b)   { int t; t=a; a=b; b=t; }

    void bubble( int a[], int n )
    /* Pre-condition: a contains n items to be sorted */
    {
       int i, j;
      /* Make n passes through the array */
      for(i=0;i<n-1;i++)
      {
     /* From the first element to the end
       of the unsorted section */
        for(j=1;j<(n-i);j++)
        {
        /* If adjacent items are out of order, swap them */
       if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);
       }
    }
}

```

# Answer
> 6 votes
The first iteration will do will do $n-1$ comparisons, the next $n-2$, the second $n-3$ and so on. In total $n-1$ iterations are done.

Hence, you need to find the sum of $(n-1)+(n-2) + ... + 1$ which is $((n-1)^2+n-1)/2$ which still is $O(n^2)$. So the optimization does not improve the asymptotic running time.

Note that I edited your algorithm slightly: the outer loop is only iterated $n-1$ times. This is because for each iteration, one more element is put into the right place. Hence after $n-1$ iterations, $n-1$ elements will be in the right place and so element $n$ must also be in the right place.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, sorting
---


# Question
Title: Numeral systems other than unary used in nature or in animal and human behaviours
Representing numeric values using positional notation is one of the milestones in the history of arithmetic. Babylons used a base 60 system, Maya a base 20 system; base 10 system became "the standard" used by modern civilizations; digital computers use the Binary numeral system, ....

But if we look at nature, we found that life itself "heavily rely" on an alphabet of 4 symbols: the DNA has four (chemical) bases: adenine, cytosine, guanine and thymine (A, C, G, T) that are used to store the "instructions and information" to generate and drive the parts of a living organism.

> But on a higher level, are there *"natural algorithms"* (algorithms found in natural processes, in animal behaviours or in everyday human behaviours) that take advantages of "numeral systems" other than the unary representation.

To be more precise I would like to know whether or not natural processes or living creatures make use of a finite, discrete alphabet of "symbols" and use them in a manner similar to a positional notation: the symbols are placed together and used as a whole to represent "something" (an action, an information, an object, ...) among many other possibilites ... a sort of "index" in an exponential number of possibilites.

Another (obvious) non numeric example is the human language where (in general) a combination of finite number of sounds ("alphabet") are combined to form the words.

# Answer
> 3 votes
There is at least one example where a string of symbols from an alphabet is also used: proteins.

Proteins consist of chains of 20 different amino acids (usually, in some cases, it's 21 or 22) and the sequence of amino acids determines what given protein does.

This example is closely related to the DNA example you gave, because each amino acid in a protein is encoded by a triplet of bases in DNA.

For more information, see the article *Genetic code* on Wikipedia.

# Answer
> 2 votes
The Aufbau principle, which controls the electron configuration of atoms, is an example of a "positional" notation. Electrons (more or less) fill shells in some fixed order, and the outer shell determines the chemical properties of the atom.

---
Tags: integers, notation, numeral-representations
---


# Question
Title: How to make a parse tree for the following propositional logic formula?
I have a formula $ \neg((q \implies \neg q) \vee p \vee (\neg q \implies (r \wedge p))) $.

As it contains 3 subformulas between the $\vee$'s, how can i put it into a parse tree, as a parse tree contains 2 branches from each node.

# Answer
> 8 votes
As it is, your formula is ambiguous; it is not clear which pair of parentheses to insert in order to get a binary tree. Both

$\qquad \displaystyle \varphi\_1 \lor (\varphi\_2 \lor \varphi\_3)$

and

$\qquad \displaystyle (\varphi\_1 \lor \varphi\_2) \lor \varphi\_3$

are feasible. Luckily for you, $\lor$ is associative, so you can choose either one:

<sup>\[source\]</sup>

For the purposes of parsing, you would either require formulae to be completely parenthesised, or specify operators to be left- (or right-) associative. Operator precedences would be the next thing to look into, in order to disambiguate formulae like

$\qquad \displaystyle a \land b \lor c$.

---
Tags: formal-languages, logic, binary-trees, parsing
---


# Question
Title: Determining whether a CFG is $LL(k)$ for any $k$?
In Knuth's original paper on $LR(k)$ grammars, he proved that the decision problem "Given a CFG $G$, is there a $k$ such that $G$ is an $LR(k)$ grammar?" is undecidable.

Is there a similar result showing that it is undecidable whether a given CFG is an $LL(k)$ grammar for some choice of $k$? Or is this problem known to be decidable?

# Answer
This is undecidable. It is theorem 11 in Properties of deterministic top down grammars by Rosenkrantz and Stearns. Theorem 12 in the same paper however states that the problem becomes decidable if the grammar is known to be $LR(k')$ for some (possibly different) $k'$.
> 5 votes

---
Tags: formal-languages, computability, formal-grammars, context-free, parsing
---


# Question
Title: What's wrong with this LL grammar? (very short)
```
S --> Ta | b | Sc
T --> Tc | λ

```

This isn't an LL grammar but I need it to be so I can do a parse table. The problem is that no matter how much I try I never manage to do make it an LL grammar. Can someone please help by making it a LL grammar? It isn't that big and I'm very confused.

# Answer
First note that $T = c^\*$ (using regular expression syntax). We can therefore rewrite your grammar to:

```
S --> c*a | b | Sc

```

Rewriting even further, we can say that $S = (c^\*a | b)c^\*$, so $S$ is regular. It is not hard to come up with a grammar for this language:

```
S --> T a T | b T
T --> c T | λ

```

More generally, when trying to rewrite grammars to $LL$ form, one first removes left recursion using standard techniques (for instance here). Then one tries to remove any conflicts that are left, for which no general techniques are known - just try to figure out what the conflict means, and try to solve it accordingly.
> 3 votes

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


title: Non-linear grammars

text:
# Question
Title: Non-linear grammars
I look for information about grammars which can be described by a non-linear equation such as a quadratic equation:

$\qquad \displaystyle G \to G G a \mid b$

or

$\qquad \displaystyle G \to G G \mid y G z \mid z G y \mid \varepsilon$

While there is lots of material about linear grammars, their connection with regular languages etc. "quadratic grammars" ( a term, which doesn't even seem to exist ) are only mentioned when an author presents some counterexamples for a parsing algorithm in order to show its limitations.

Is there an autonomous treatment of grammars which can be described by general polynomial equations?

# Answer
> 3 votes
I'm going to attempt to answer your question, risking the possibility I have misunderstood you.

If we restrict context-free grammars to only a single nonterminal per rule, then the resulting class of grammars are exactly the linear grammars (by definition). However, if we allow more than one nonterminal per rule, then we are back at all context-free grammars.

This can quite easily be seen by considering the Chomsky normal form, in which any rule contains either exactly one terminal, two nonterminals or the empty string (in this last case the left hand side is further constrained to be the starting symbol). Any context-free language is described by some context-free grammar in Chomsky normal form, so we are back at the full range of languages.

I don't know about the case if you make the restriction to just one nonterminal.

---
Tags: reference-request, formal-grammars
---


title: Meaning of the adjacency matrix product

text:
# Question
Title: Meaning of the adjacency matrix product
Let $A$ be an adjacency matrix of a directed graph. What's the meaning of the $(i,j)-$entry of the matrix $((A^T)^{7} \cdot (A^{7}))$ ?

My initial interpretation is that $(i,j)$ of this matrix is zero whenever nodes $i$ and $j$ have no 7-length in-coming paths from a common source. Is that right? Any attention is appreciated!

# Answer
> 7 votes
This is answered on Math.SE; see also MathWorld.

Briefly,the $(i,j)$-th entry in $A^n$ gives the number of directed walks from vertex $i$ to $j$ that have length $n$. Also, given another adjacency matrix $B$, this entry in the product $(AB)$ gives the number of directed walks from vertex $i$ to $j$ , that walk first along an edge of the first graph and then along an edge of the second.Putting these two together would give you an interpretation to the product of 7th powers in your question.

---
Tags: algorithms, graphs
---


# Question
Title: Is an oracle ever useful if you can't control the input instances?
Let's say $F$ is an oracle for a problem in $\mathbb{NP}$, but I cannot call this oracle with any input instance. Instead, whenever I call $F$ I get returned a random instance and solution. Thus, I know that $F$ is in fact capable of solving arbitrary $\mathbb{NP}$-hard problems, I just can't specify which one I want it to solve.

Is it possible to use such an oracle to solve an $\mathbb{NP}$-complete problem faster? My gut says no because the naive use of the oracle still requires $O(2^n)$ time by calling the oracle enough to check every solution. I just can't think of a way to prove this.

# Answer
> 8 votes
As Xodarap pointed out, if you require your algorithm with the “random oracle” to *always* output the correct answer, then the random oracle is useless. The problem becomes more interesting if we allow small probability of error (where the probability is with respect to the random instance chosen by the oracle).

In addition, as Vor pointed out in comments on the question, it is meaningless to say “random instance” without specifying a probability distribution. One of the reasonable assumptions to make here is that this random instance is chosen uniformly at random from the set of all strings of length *p*(*n*), where *n* is the input length and *p* is some fixed polynomial. We could make other, weaker, assumptions on the probability distribution.

Here we will make the assumption quite general, and will show that existence of a randomized polynomial-time algorithm with a “random oracle” for NP-complete problems has a surprising consequence even under this weak assumption.

Let’s drop the requirement that the “random oracle” will solve a problem in NP (on a randomly chosen instance). Now the “random oracle” can be any predetermined probability distribution over polynomial-length strings, and every time it is asked, it emits a string according to this probability distribution. The only requirement is that this probability distribution depends only on the input length. Note that your model is indeed a special case of this model. In your model, the probability distribution is required to have the following form: it first chooses a uniformly random instance *y* from a set depending on the input length, and then returns a pair (*y*, *g*(*y*)), where *g*: {0, 1}\*→{0, 1} is the characteristic function of some decision problem in NP. Now we allow *any* probability distribution, as long as the distribution is determined by the input length alone.

An “oracle” of this general form is called a *randomized advice*. The class of decision problems which can be decided by a randomized polynomial-time algorithm with a randomized advice (with bounded two-sided error) is called BPP/rpoly, and it is known that this class is equal to P/poly. (The inclusion BPP/rpoly⊆P/poly can be proved in the same way as a well-known inclusion BPP⊆P/poly. For a proof of the latter, see e.g. Theorem 6.3 of Goldreich \[Gol08\].)

This means that if an NP-complete problem can be solved in your model, then NP⊆P/poly. However, it is known that NP⊆P/poly implies that the polynomial hierarchy collapses to the second level \[KW98, Cai07\]. Most complexity theorists consider a collapse of the polynomial hierarchy as a big surprise. If we believe that the polynomial hierarchy does not collapse, then NP-complete problems cannot be solved efficiently with the “random oracle” in your sense.

## References

\[Cai07\] Jin-Yi Cai. S2p ⊆ ZPPNP. *Journal of Computer and System Sciences*, 73(1):25–35, Feb. 2007. DOI: 10.1016/j.jcss.2003.07.015.

\[Gol08\] Oded Goldreich. *Computational Complexity: A Conceptual Perspective*. Cambridge University Press, 2008.

\[KW98\] Johannes Köbler and Osamu Watanabe. New collapse consequences of NP having small circuits. *SIAM Journal on Computing*, 28(1):311–324, 1998. DOI: 10.1137/S0097539795296206.

# Answer
> 0 votes
Let's specifically think about everyone's favorite NP-complete problem: 3SAT.

It's possible (albeit unlikely) that each time you call your oracle it gives you an assignment for the same instance. Specifically, each time it could give you an assignment for the trivial sentence:

$$(x\vee x \vee x)\wedge(x\vee x\vee x)\dots$$

But you already know the assignment for this. So your Oracle can't be useful.

More formally, if we call your oracle $A$, then $P^A\not=NP$ (assuming $P\not=NP$...)

---
Tags: complexity-theory, np-complete
---


# Question
Title: Dijkstra to favor solution with smallest number of edges if several paths have same weight
You can modify any graph $G$ so that Dijkstra's finds the solution with the minimal number of edges thusly:

Multiply every edge weight with a number $a$, then add $1$ to the weight to penalize each additional edge in the solution, i.e.

$w'(u,v)=a\*w(u,v)+1$

This does not work for all values of $a$; $a$ needs to be at least $x$ for this to work. If $a$ is not this minimum number, it might not choose the shortest path. How do I find this minimum value $x$?

Ps. This was done recreationally, I'm done with homework long ago.

# Answer
> 5 votes
Given a graph $G = (V,E,w)$, we define $G'=(V,E,w')$ with $w'(e) = aw(e) + 1$ where $a = |E| + \varepsilon$ for some $\varepsilon \geq 0$ as proposed in the comments of the question.

> **Lemma**
> Let $P$ a path in $G$ with cost $C$, i.e. $w(P)=C$. Then, $P$ has cost $aC + |P|$ in $G'$, i.e. $w'(P) = aC + |P|$.

The lemma follows directly from the definition of $w'$.

Call the result of Dijkstra on $G'$ $P$, which is a shortest path in $G'$. Assume $P$ was not a shortest path with fewest edges (among all shortest paths) in $G$. This can happen in one of two ways.

1. $P$ is not a shortest path in $G$.
Then, there is a path $P'$ with $w(P') \< w(P)$. As $|P|,|P'| \leq |E| \leq a$, this implies that also $w'(P') \< w'(P)$ with above lemma¹. This contradicts that $P$ was chosen as shortest path in $G'$.
2. $P$ is a shortest path but there is a shortest path with fewer edges.
Then, there is another shortest path $P'$ -- i.e. $w(P) = w(P')$ -- with $|P'| \< |P|$. This implies that $w'(P') \< w'(P)$ by above lemma, which again contradicts that $P$ is a shortest path in $G'$.

As both cases have led to a contradiction, $P$ is indeed a shortest path with fewest edges in $G$.

---

That covers one half of the proposition. What about $a \< |E|$, i.e. $a = |E| - \varepsilon$ with $\varepsilon \in (0,|E|)$?

---

1. Actually, we also need that $a$ or all weights in $G$ are integers. Otherwise, $w(P') \< w(P)$ does not cause the weights in $G'$ to be at least $|E|$ apart. This is not a restriction, though; we can always scale $w$ with a constant factor so that all weights are integer, assuming we start with rational weights.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Finding paths with smallest maximum edge weight
I need to find the easiest cost path between two vertices of a graph. Easiest here means the path with the smallest maximum-weigth edge.

In the above graph, the easiest path from 1 to 2 is:

```
1 > 3 > 4 > 2

```

Because the maximum edge weight is only 2. On the other hand, the shortest path `1 -> 2` has maximum weight 4.

So it's an MST problem. I am thinking I will use Kruskal's algorithm to build the tree, but I'm not sure how exactly. I will know the edges but how do I "reconstruct" the path? For example, given vertices `3` and `2`, how do I know to go left (top) of right in the tree? Or do I try both ways?

# Answer
You're right; it's essentially a MST problem. First build the minimum spanning tree, then use breadth-first or depth-first search to find the unique path in the tree between the two vertices.
> 5 votes

---
Tags: algorithms, graphs, shortest-path
---


title: Flow of control? or Control of flow?

text:
# Question
Title: Flow of control? or Control of flow?
In most PL textbooks (even in language specifications) statments like **if, while, for, break** are categorized as *flow of control* statements.
However, it is not consistent; i.e. sometimes the same text uses *control-flow statement* (note the dash), or *control flow statment*, I read sentences that says *control flows...*

I understand those statements *control the flow of execution*, hence *control of flow*. But many texts (even wikipedia) says otherwise, implying *control is something that flows in a program*

What is the formal, language-agnostic definition of this concept in CS, if any?

# Answer
I am not sure what you mean by "language-agnostic definition of this concept in CS"; such notions are rarely (if ever) rigorously defined. Someone uses them first, others pick them up and eventually they become standard vocabulary. That's ho we get conflicting notation all the time.

In this case, I don't see an either-or. Both makes sense, depending of how you look at it. The semantics of the language control the flow of execution, i.e. determine which statement is executed next. But as this control -- once it is implemented in a processor -- only looks at the current statement, it flows along, that is control flows.
> 2 votes

---
Tags: terminology, programming-languages
---


# Question
Title: Dynamic programming with large number of subproblems
Dynamic programming with large number of subproblems. So I'm trying to solve this problem from Interview Street:

> **Grid Walking** (Score 50 points)
> You are situated in an $N$-dimensional grid at position $(x\_1,x\_2,\dots,x\_N)$. The dimensions of the grid are $(D\_1,D\_2,\dots,D\_N$). In one step, you can walk one step ahead or behind in any one of the $N$ dimensions. (So there are always $2N$ possible different moves). In how many ways can you take $M$ steps such that you do not leave the grid at any point? You leave the grid if for any $x\_i$, either $x\_i \leq 0$ or $x\_i \> D\_i$.

My first try was this memoized recursive solution:

```
def number_of_ways(steps, starting_point):
    global n, dimensions, mem
    #print steps, starting_point
    if (steps, tuple(starting_point)) in mem:
        return mem[(steps, tuple(starting_point))]
    val = 0
    if steps == 0:
        val = 1
    else:
        for i in range(0, n):
            tuple_copy = starting_point[:]
            tuple_copy[i] += 1
            if tuple_copy[i] <= dimensions[i]:
                val += number_of_ways(steps - 1, tuple_copy)
            tuple_copy = starting_point[:]
            tuple_copy[i] -= 1
            if tuple_copy[i] > 0:
                val += number_of_ways(steps - 1, tuple_copy)
    mem[(steps, tuple(starting_point))] = val
    return val

```

Big surprise: it fails for a large number of steps and/or dimensions due to a lack of memory.

So the next step is to improve my solution by using dynamic programming. But before starting, I'm seeing a major problem with the approach. The argument `starting_point` is an $n$-tuple, where $n$ is as large as $10$. So in fact, the function could be `number_of_ways(steps, x1, x2, x3, ... x10)` with $1 \leq x\_i \leq 100$.

The dynamic programming problems I've seen in textbooks almost all have twp variables, so that only a two-dimensional matrix is needed. In this case, a ten-dimensional matrix would be needed. So $100^{10}$ cells in total.

With 2-D matrixes in dynamic programming, usually only the previous row of calculations is needed for the next calculation, hence reducing the spatial complexity from $mn$ to $\min(m,n)$. I'm not sure how I would do the same in this case. Visualizing a table isn't feasible, so the answer would have to come directly from the recursion above.

**UPDATE**

Using Peter Shor's suggestions, and making some minor corrections, notably the need to keep track of position in the $W(i, t\_i)$ function, and rather than only splitting dimensions into two sets A and B, doing the splitting recursively, effectively using a divide-and-conquer method, until a base case is reached where only one dimension is in the set.

I came up with the following implementation, which passed all tests below the maximum execution time:

```
def ways(di, offset, steps):
    global mem, dimensions
    if steps in mem[di] and offset in mem[di][steps]:
        return mem[di][steps][offset]
    val = 0
    if steps == 0:
        val = 1
    else:
        if offset - 1 >= 1:
            val += ways(di, offset - 1, steps - 1)
        if offset + 1 <= dimensions[di]:
            val += ways(di, offset + 1, steps - 1)
    mem[di][steps][offset] = val
    return val

def set_ways(left, right, steps):
    # must create t1, t2, t3 .. ti for steps
    global mem_set, mem, starting_point
    #print left, right
    #sleep(2)
    if (left, right) in mem_set and steps in mem_set[(left, right)]:
        return mem_set[(left, right)][steps]
    if right - left == 1:
        #print 'getting steps for', left, steps, starting_point[left]
        #print 'got ', mem[left][steps][starting_point[left]], 'steps'
        return mem[left][steps][starting_point[left]]
        #return ways(left, starting_point[left], steps)
    val = 0
    split_point =  left + (right - left) / 2
    for i in xrange(steps + 1):
        t1 = i
        t2 = steps - i
        mix_factor = fact[steps] / (fact[t1] * fact[t2])
        #print "mix_factor = %d, dimension: %d - %d steps, dimension %d - %d steps" % (mix_factor, left, t1, split_point, t2)
        val += mix_factor * set_ways(left, split_point, t1) * set_ways(split_point, right, t2)
    mem_set[(left, right)][steps] = val
    return val

import sys
from time import sleep, time

fact = {}
fact[0] = 1
start = time()
accum = 1
for k in xrange(1, 300+1):
    accum *= k
    fact[k] = accum
#print 'fact_time', time() - start

data = sys.stdin.readlines()
num_tests = int(data.pop(0))
for ignore in xrange(0, num_tests):
    n_and_steps = data.pop(0)
    n, steps = map(lambda x: int(x), n_and_steps.split())
    starting_point = map(lambda x: int(x), data.pop(0).split())
    dimensions = map(lambda x: int(x), data.pop(0).split())
    mem = {}
    for di in xrange(n):
        mem[di] = {}
        for i in xrange(steps + 1):
            mem[di][i] = {}
            ways(di, starting_point[di], i)
    start = time()
    #print 'mem vector is done'
    mem_set = {}
    for i in xrange(n + 1):
        for j in xrange(n + 1):
            mem_set[(i, j)] = {}
    answer = set_ways(0, n, steps)
    #print answer
    print answer % 1000000007
    #print time() - start

```

# Answer
> 14 votes
The different dimensions are **independent**. What you can do is compute, for each dimension *j*, how many different walks there are in just that dimension which take $t$ steps. Let us call that number $W(j,t)$. From your question, you already know how to compute these numbers with dynamic programming.

Now, it's easy to count the number of walks that take $t\_i$ steps in dimension $i$. You have $N \choose t\_1,t\_2, \ldots, t\_M$ ways of interspersing dimensions so that the total number of steps taken in dimension $i$ is $t\_i$, and for each of these ways you have $\Pi\_1^N W(i,t\_i)$ walks. Sum over these to get $$ \sum\_{t\_1+t\_2+\ldots+t\_N=M}{M \choose t\_1,t\_2,\ldots,t\_N}\ \Pi\_{i=1}^N W(i,t\_i). $$ Now, the memory is under control, since you only need to remember the values $W(j,t)$. The time grows superpolynomially for large $N$, but most computers have a lot more time than memory.

You can do even better. Recursively divide the dimensions into two subsets, $A$ and $B$, and compute how many walks there are using just the dimensions in subset $A$, and just those in $B$. Call these numbers $W\_A(t)$ and $W\_B(t)$, respectively. You get the total number of walks by

$$ \sum\_{t\_1 + t\_2 = M} {M \choose t\_1} \\, W\_A(t\_1) W\_B(t\_2). $$

# Answer
> 4 votes
Let's extract a formula for $\newcommand{\now}{\operatorname{now}}\now(s,x\_1,\dots,x\_n)$ from your code (for an inner cell, that is ignoring border cases):

$\qquad \begin{align} \now(s,x\_1,\dots,x\_n) = \phantom{+} &\sum\_{i=0}^n \now(s-1,x\_1,\dots,x\_{i-1},x\_i + 1, x\_{i+1},\dots,x\_n) \\ \+ &\sum\_{i=0}^n\now(s-1,x\_1,\dots,x\_{i-1},x\_i - 1, x\_{i+1},\dots,x\_n) \end{align}$

Here are some ideas.

* We see that once you have computed all values for $s=k$, you can drop all computed values for $s\<k$.
* For a fixed $s$, you should compute the table entries in lexicographic order (just because it's simple). Then, note that every cell only needs such cells inside a "radius of one", that is no coordinate can be farther away than one. Therefore, once your iteration hits $x\_1=i$, you can drop all values for $x\_1\leq i-2$. If that is not enough, do the same for $x\_2$ -- for fixed $x\_1=i$, drop values with $x\_1 = i$ and $x\_2 \leq j-2$ when $x\_2=j$ is reached -- and so on.
* Note that "so there are always $2N$ possible different moves" holds only in the middle of the grid, that is if $x\_i - M \> 0$ and $x\_i + M \< D\_i$ for all $i$. But that also means that the answer is easy in the middle: it's just $(2N)^M$. If you had a working dynamic programming recurrence, that alone would allow you shave away most of the table (if $M\ll N$).
* Another thing to note is that you don't have to compute the whole table; most values will be filled with $0$ anyway (if $M\ll N$). You can restrict yourself to the (hyper)cube of edge-length $2M$ around $x$ (note that it will be dented because of paths leaving the grid).

That should be sufficient to keep memory usage quite low.

---
Tags: algorithms, efficiency, dynamic-programming
---


# Question
Title: The path between any two nodes in cyclic directed graph
G{V, E} is directed, **cyclic**, weighted graph. What is the algorithm of finding all paths between any given two nodes?
Can you suggest any good reading?

# Answer
If the graph happens to be a DAG, then you can found the number of paths from any vertex to any other vertex using linear algebra. Let $A$ be the adjacency matrix of the graph. Compute $$ B = \sum\_{k=0}^{n-1} A^k. $$ Then $B\_{ij}$ is the number of paths (of length at most $n-1$) between vertex $i$ and vertex $j$. This also works for weighted graphs, in which case the weight of each path is the product of the weights on the edges.

It is easy to construct examples where there are exponentially many paths. For example, let the vertices be $x\_0,\ldots,x\_n,y\_1,\ldots,y\_n,z\_1,\ldots,z\_n$, and the edges be $(x\_i,y\_{i+1}),(x\_i,z\_{i+1}),(y\_i,x\_i),(z\_i,x\_i)$. The number of paths from $x\_0$ to $x\_n$ is $2^n$.

If the graph is not a DAG, then there can be infinitely many paths from a vertex to another, since any given cycle can be taken an unbounded number of times. In this case it makes sense to ask for the number of *simple* paths from one vertex to another. In the weighted version (with weights of polynomial length), we expect this to be difficult, since HAM-PATH can be solved this way.
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: Simple paths with halt in between in directed graphs
I have two problems related to paths in a directed graph. Let $G=(V,E)$ be a directed graph with source $s \in V$ and target $t \in V$. Let $v \in V \setminus \\{s,t\\}$ be another vertex in $G$.

1. Find a simple directed path¹ from $s$ to $t$ through $v$.
2. Find a simple directed path from $s$ to $t$ that goes through two fixed edges in $G$.

I do not know if there are polynomial time algorithms for them. Does anyone have solutions or references for them?

---

1. A simple directed path does not allow any vertex to appear more than once.

# Answer
As Tsuyoshi Ito notes, the first problem can be solved using network flow. This was described in detail in cstheory.
> 3 votes

---
Tags: algorithms, graphs
---


title: Target-Value Search (& II)

text:
# Question
Title: Target-Value Search (& II)
\[*previously appearing in cstheory, it was closed there and introduced here instead*\]

Given an edge-weighted graph $G=(V,E)$ the problem of finding the shortest path is known to be in P ---and indeed a simple approach would be Dijkstra's algorithm which can solve this problem in $O(V^2)$. A similar problem is to find the maximum path in $G$ from a source node to a target node and this can be solved with Integer Programming so that, as far as I know, this is not known to be in P.

Now, the problem of finding a path in $G$ such that it deviates the minimum from a given target value (typically larger than the optimal distance but less than the maximum distance that separates the source and target nodes) has been conjectured to be in EXPTIME (see section "Conventions" of A depth-first approach to target-value search in the proceedings of SoCS 2009). In particular, this paper addresses this particular problem for directed acyclic graphs (DAGs). A previous work is Heuristic Search for Target-Value Path Problem. There is event a US Patent of this algorithm US 2011/0004625.

I've been searching for related problems in other fields of Computer Science and Mathematics and strikingly, I have found none though this problem is clearly relevant in practice ---there are tons of opportunities to look for a specific target value instead of the minimum or the maximum path.

Do you know related problems to this or additional bibliographical references to this problem? Any information on this problem including studies of their complexity would be very welcome

**Note**: as already pointed out by Jeffe in cstheory, proving this problem to be in EXPTIME is trivial and the authors probably meant EXPTIME-complete.

# Answer
> 4 votes
*What follows is taken from Tsuyoshi Ito's comment.*

In the case of DAG, all paths can be enumerated in polynomial space and therefore the problem cannot be EXPTIME-complete unless PSPACE=EXPTIME. The natural decision version (given a DAG G, its vertices s and t, and numbers x and y, decide whether there is a path from s to t whose length is between x and y) is in NP.

---
Tags: algorithms, complexity-theory, reference-request, search-algorithms
---