title: Decidability of Machines

text:
# Question
Title: Decidability of Machines
I cannot understand decidability really well. I have been reading from books and internet, but I am little bit confused. According to the book (as I understood), we can decide on decidability of a problem by constructing Turing Machines. Let us say that we want to decide whether an NFA is a decidable language. First, we need to construct a Turing Machine that accepts if the run on w in NFA ends in accept state, otherwise Turing Machine rejects. According to this definition, I can construct any Turing Machine that can decide every NFA. As a result, I can say that every NFA that can be constructed is decidable. Is this true ?

Additionally, I realized that we cannot decide whether two Context Free Grammars produce same languages. However, we can decide whether two NFA produce same language. Therefore, can we conclude that as our machines get complicated, some of the problems get harder to decide ?

I mean lets take an example. Let us say that there is an NFA that accepts some string w whose length is a composite number. I think that this is a decidable problem.

As you can see that I am little bit confused with these concepts. It will be a lot better for me to go over an example, because it is difficult for me to understand only from conceptual explanations.

# Answer
> As a result, I can say that every NFA that can be constructed is decidable. Is this true?

Yes. An NFA can be converted to a deterministic finite automaton, and that can simply be run to decide the output.

> However, is it possible to find a Turing Machine that can accept w whose length is composite number?

Yes, this is possible. It follows from the fact that it can be done in any old Turing-complete programming language, hence also on a TM.

> Is it possible to construct a CFG that accepts this w?

I doubt it. Maybe there is a proof, but I do not see it right away.

Most problems you'll encounter in practice are decidable, because you can come up with an algorithm to decide the answer. If you want an example of an undecidable problem, have a look at this list on Wikipedia.
> 5 votes

---
Tags: computability, automata, finite-automata, turing-machines
---


title: Is this grammar ambiguous?

text:
# Question
Title: Is this grammar ambiguous?
I have the grammar:

$\qquad \begin{align} S &\to S = P \mid S \neq P \mid P \\ P &\to NUM \end{align}$

This grammar suffers from left recursion. To eliminate left recursion, I got:

$\qquad \begin{align} S &\to PS' \\ S' &\to\\, = PS' \mid\\, \neq PS' \mid \varepsilon \\ P &\to NUM \end{align}$

However when constructing the LL(1) parsing table, it turns out the grammar is ambiguous. Is there a way to disambiguate the grammar without changing the generated language, or did I make a mistake somewhere?

This is my work so far:

```
Non-terminal Nullable First            Follow
S            False    NUM              $
    S'           True     !=, ==, epsilon  $
P            False    NUM              $, ==, !=

Parse Table
     !=       ==    NUM      $
S                   ->PS'
S'  ->!=PS'  ->==PS'        ->epsilon
P                   ->NUM

```

# Answer
We can consider $NUM$ and therewith $P$ a terminal symbol. Furthermore, $S$ does only occur once in every derivation. Therefore, if there is any ambiguity, it has to stem from

$\qquad \displaystyle S' \to\\, = PS' \mid\\, \neq PS' \mid \varepsilon$

Now, that fragment is a right-regular grammar with only one non-terminal whose right-hand sides do not share any prefixes. So clearly every term has only derivation, given by its length and permutation of $=$ and $\neq$.

In total, your grammar is unambiguous. Above observations also suggest that the grammar can be parsed in one pass from left to right with one token lookahead (distinguish $=$ and $\neq$). In fact, the grammar is basically a deterministic (no shared prefixes) and right-regular (replace all $P$ with $NUM$) grammar, so it's certainly an LL(1) grammar.

So I suggest you revisit the construction of the parsing table (your favorite textbook or Wikipedia) -- you must have made a mistake.
> 1 votes

---
Tags: formal-grammars, parsers, ambiguity
---


# Question
Title: Can truth tables be used in non-boolean algebra to derive functions?
There are obvious analogs (pardon the pun) between Boolean algebra and algebra. They have similar laws, operators and properties. I can't figure out why Karnaugh Maps and sum of products, which are used to derive a Boolean function from a truth table, doesn't have an equivalent in algebra. Perhaps it does, but I haven't seen it.

My only explanation is that if it were possible, you could theoretically find a function for any arbitrary series of numbers (0, 2, 4, 6, 8 f(n)=2n). Thus, you could solve a ton of very difficult problems. I'm not necessarily looking for a formal proof but an explanation.

Right now, I am having fleeting ideas that it has something to do with infinite outputs and inputs, something to do with place values, or true or false equivalents in algebra. There's something here that's difficult to put my finger on.

# Answer
> 4 votes
There are two possible ways to define a non-boolean algebra.

1. Stick with $\mathbb{F}\_2 = \\{0,1\\}$ but choose base operations other than $\\{\land, \lor, \lnot\\}$.
2. Change the base set entirely.

For the whole concept of simplification to word similarly to boolean algebra, we need two binary operations with associativity, commutativity and distributivity. Fields are the natural choice and, I think, the only one. Commutative rings *might* work but I suspect you get into trouble composing functions in a regular way if you don't have multiplicative inverse elements.

Infinite fields do not make sense here -- you can not draw an infinite table. So finite fields remain, of which there is exactly one per size (up to isomorphy).

So let us, for example, consider $\mathbb{Z}/5$ (the smallest field over $\mathbb{Z}$ with more than two elements and interesting inverses). Now try and formulate a function in a way that looks like a boolean function provided by Karnaugh maps, that is in additive (disjunctive) or multiplicative (conjunctive) normal form. We get to the core question:

> What is the complement of a given element in a non-binary algebra?

The simple logic "if it's not one it's the other" does not work here. Note that the boolean complement does not correspond to the additive nor the multiplicative inverse, so there no hope there. So let's try and define a "complement"; say $\overline{a} = a + 1$ (which contains the boolean complement as special case). We note with unease that this new complement is not symmetric. I expect symmetry to be of essence; reading off from the Karnaugh map seems to rely on it.

So there is no way to get there with an odd number of elements; let's pick one with an even number (so we can pair elements for a complement relation). Now things become messy and I'll stop. After all, Wikipedia says that (emphasis mine)

> the solution can be found by eliminating extra variables within groups *using the axioms of boolean algebra*

which *characterise* boolean algebra. Therefore -- provided that *all* axioms are needed for Karnaugh maps to work -- the concept does not work for non-boolean algebras.

---
Tags: algorithms, computability, logic
---


# Question
Title: How to random-generate a graph with Pareto-Lognormal degree nodes?
I have read that the degree of nodes in a "knowledge" graph of people roughly follows a power law distribution, and more exactly can be approximated with a Pareto-Lognormal distribution.

Where can I find a kind of algorithm that will produce a random graph with this distribution?

See for example the paper Revisiting Degree Distribution Models for Social Graph Analysis (page 4, equation 1) for a mathematical description (distribution function) of the kind of distribution I'm interested in.

# Answer
To generate a graph from a prescribed degree sequence (regardless of the degree sequence), one can use an algorithm by Blitzstein and Diaconis:

Unfortunately their algorithm is potentially $O(n^2 \bar{d})$, for $n$ vertices with average degree $\bar{d}$, so this might not be fast enough depending on the size of your graph and the application involved.

Molloy and Reed introduced the "Erased Configuration Model" which pairs vertices based on a degree sequence chosen proportional to the remaining free slots.

A paper by Britton, Deijfen and Martin-Lof show that the Erased Configuration Model asymptotically approaches the prescribed degree distribution chosen. While not guaranteeing the exact degree sequence input, I would recommend the erased configuration model for its simplicity and speed.

Briefly, the erased configuration model graph generation algorithm creates "hooks" for each vertex, where the number of hooks for each vertex is initially given by the degree sequence. Going from the vertex with the most hooks first, another hook is chosen uniformly at random from the pool still unattached. A connection is made for this pairing. Once the pool of hooks is exhausted, self loops are removed and multi-edges are collapsed into one.

Since self loops are allowed and multi-edges collapsed, the resulting degree sequence could potentially be different than the input sequence, so this method is not exact. If exactness is preferred, the algorithm by Blitzstein and Diaconus can be used at a higher computational cost. Note that the algorithm of Blitzstein and Diaconus checks whether a prescribed degree sequence is feasible (or "graphical" in their parlance), so degree sequences might need to be regenerated should they not be realizable.

Degree sequences can be chosen under any distribution you want. In your case, you would want to choose them based on a Pareto-Lognormal distribution.

I would also like to briefly note that generating graphs with prescribed degree sequences that follow a particular distribution, the Pareto-Lognormal distribution say, might not generate the type of "knowledge" graphs you want. The degree distribution is just a profile of a graph and says nothing about other features which might be present in the original graph ensemble you would be trying to model. As Raphael points out in the comments, Wikipedia's page on scale-free networks is a good starting point for some review.
> 3 votes

---
Tags: algorithms, graphs, probability-theory, randomness
---


# Question
Title: Proof that a language involving $gcd$ is not context-free
How would you prove that the following language is not context-free?

$$ L= \\{a^n b^m |\\, gcd(n,m)=1 \\}$$

I suspect the solution uses the pumping lemma, but I'm not sure how to apply it.

# Answer
> 4 votes
Let $p$ be the pumping length guaranteed by the pumping lemma (for context free languages). Then we choose $m \neq n$ such that $m,n \geq p$ and are both prime. Then clearly $s = a^{n}b^{m} \in L$.

By the pumping lemma we can divide $s$ such that $s=uvxyz$ and

1. $|vxy| \leq p$
2. $|vy| \geq 0$
3. $s' = uv^{i}xy^{i}z \in L$ for all $i \in \mathbb{N}$

For this language we get three similar cases, and one trivial case. The trivial case is where either $v$ or $y$ contains both $a$'s and $b$'s, in which case $s'$ doesn't have the correct ordering, and thus $s'\notin L$.

The nontrivial cases:

1. $v$ and $y$ are both strings of $a$'s, then when we pump $s$ we get $s' = a^{n+ik}b^{n}$ where $k\geq 1$. Then $s' \in L$ if $gcd(n+ik,m)=1$, however the modular equation $n+ik\equiv 0 (m)$ has the solution $i \equiv nk^{-1} (m)$, and as $m$ is prime we are guaranteed that $k^{-1}$ exists. Therefore any element of the residue class $i \equiv nk^{-1} (m)$ would give us $gcd(n+ik,m) \> 1$. Ergo $s' \notin L$.
Short version: we can pump the string so that $n+ik$ is a multiple of $m$ for any $k$ with $1 \leq k \leq p \< m,n$ (which is what we set up at the start).
2. $v$ and $y$ are both strings of $b$'s, but this case is just the symmetric case to case 1, so we derive a contradiction in this case too.
3. $v = a^{k}$ and $y = b^{h}$ for some $k$ and $h$ with $1 \leq k+h \leq p$. Then when we pump we get $s' = a^{n+ik}b^{m+ih}$. Now $s' \in L$ if $n+ik \equiv m+ih (m)$ has no solution, but as I'm sure you can see from here, rearranging just gives $n+i(k+h)\equiv 0(m)$, and as before this has solution $i \equiv n(k+h)^{-1}(m)$. So again we derive a contradiction.

Thus there is at least one string in $L$ that cannot be divided as per the pumping lemma and still have all pumping results remain in $L$. Therefore $L$ is not context free. $Q.E.D$
Some additional notes: of course there is an infinite number of strings which can't be pumped, and it's not actually necessary for $m$ and $n$ to be prime, it just simplifies that argument, as we don't have to fiddle around with a prime decomposition - though if you did want to, you just pick one of the prime factors and do the same (or even all of them if you want).

# Answer
> 0 votes
Trick: A language is not **Context free language** if it has same Comaprision more then one times For Instance :**L = {a^nb^c^n|n\>0}** as you know this is not context free why:? as you can see number of b shuld be same as the number of a "This is first Comarision" and after that again number of c shuld be same of the number of b or number of previous a.Here 2 stack is needed to remember for equal number of occurance of a and b.so this is not "pda" because you know pda has only one stack...

```
Another Beautifull Example: L={a^nb^na^mb^m|m,n >0} Tell me weather this language is CFL or not.

```

Again Here Look for number of Comparision between same Entity: Here Number of b shuld be same as number of a...In case of `a^nb^n...`Here only one comarision between **"n"** now move to the a^mb^m Again here number of b depend up on number of a, where number of doesn't depend on any one so between a and b for power m only one comparision is going on that's why it is `L={a^nb^na^mb^m|m,n >0}` is `CFL`

```
Ex: L = {a^nb^ma^nb^m | m>n>0} Tell me weather It's CFL or not By seeing number of comaprision Answer: Yes This is CFL

```

Now Lets move to your Questions:

> L= {a^n,b^m | gcd(n,m)=1}

Here we are restricted to choose value of n and m...so that it's gcd always come 1.... Find Comarision Here:

```
 What Will be the value of m,n ???
 It's depend upon condition that whenever you will choose value of m, or n it shuld be either > and equal to m in case of value selection for m or same for value selection for m (This is first comarision between m and n or reverse for selecting value)  Now think

```

Another comaprision : GCD of m, n shuld be 1 (This is another comarision for m, n) so here two comarision is present show it is not CFL.

```
 And Acrding to pumping Lemma Theorem:
    1)Select any string belongs to L
    2)devide it in xYz part make sure that Y shuld not have o length.
    3)Take any value of "i" acrding  to your wish.
    4)make x(Y)^iz and check weather it's belong to L if not then it will prove that it is not regular. i>and equal to 1.

```

Think: Can you construct a PDA For this, Condition you have one one Stack...Defenately You will come to conclusion ...If you still didn't get my point I will write more for you....

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


# Question
Title: Finding a minimal containing rectangle from a given set of rectangles
The problem is as follows:

Given a finite set of rectangles ($S\subset\mathbb{R}\times\mathbb{R}$), build a data structure that will support the following operations:

* Check, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and returns true iff there is a rectangle $c\in S$ so that $r\_x \leq c\_x$ and $r\_y \leq c\_y$.
* Get, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and returns the minimal member of $S$ (that is, a member with a minimal area - $c\_x c\_y$) that contains $r$ (i.e., $r\_x \leq c\_x$ and $r\_y \leq c\_y$).
* Insert, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and adds it to $S$.
* Remove, receives a rectangle $r\in\mathbb{R}\times\mathbb{R}$, and removes it from $S$.

The four procedures have to be efficient, measuring efficiency by $m$ and $n$, where $m$ is the number of different widths in $S$ and $n$ is the number of different heights in $S$.

Space efficiency has to be no worse than $O(mn)$ (that is, linear to the number of elements in $S$).

# Answer
> 2 votes
Check, insert, and remove can be accomplished by a data structure for dynamically maintaining 2D maxima (this 2011 paper by Brodal and Tsakalidis presents a history of the problem including their new algorithm). I have no idea how to do get.

---
Tags: algorithms, data-structures, computational-geometry
---


# Question
Title: From in-order representation to binary tree
Is there a way to reconstruct a binary tree just from its in-order representation?

I've searched the internet, but I could only find solutions for reconstructing a binary tree from inorder and preorder representations, but none for only inorder.

# Answer
> 6 votes
The in-order traversal is not unique. The above trees have the same sequence 1,2,3,4,5. (They are isomorphic, but I assumed you consider ordered binary trees.)

---
Tags: algorithms, graphs, binary-trees
---


title: Sums of Landau terms revisited

text:
# Question
Title: Sums of Landau terms revisited
I asked a (seed) question about sums of Landau terms before, trying to gauge the dangers of abusing asymptotics notation in arithmetics, with mixed success.

Now, over here our recurrence guru JeffE does essentially this:

$\qquad \displaystyle \sum\_{i=1}^n \Theta\left(\frac{1}{i}\right) = \Theta(H\_n)$

While the end result is correct, I think this is wrong. Why? If we add in all the existence of constants implied (only the upper bound), we have

$\qquad \displaystyle \sum\_{i=1}^n c\_i \cdot \frac{1}{i} \leq c \cdot H\_n$.

Now how do we compute $c$ from $c\_1, \dots, c\_n$? The answer is, I believe, that we can not: $c$ has to bound for all $n$ but we get *more* $c\_i$ as $n$ grows. We don't know anything about them; $c\_i$ may very well depend on $i$, so we can not assume a bound: a finite $c$ may not exist.

In addition, there is this subtle issue of which variable goes to infinity on the left-hand side -- $i$ or $n$? Both? If $n$ (for the sake of compatibility), what is the meaning of $\Theta(1/i)$, knowing that $1 \leq i \leq n$? Does it not only mean $\Theta(1)$? If so, we can't bound the sum better than $\Theta(n)$.

So, where does that leave us? It it a blatant mistake? A subtle one? Or is it just the usual abuse of notation and we should not look at $=$ signs like this one out of context? Can we formulate a (rigorously) correct rule to evalutate (certain) sums of Landau terms?

I think that the main question is: what is $i$? If we consider it constant (as it *is* inside the scope of the sum) we can easily build counterexamples. If it is not constant, I have no idea how to read it.

# Answer
I think I nailed the problem down. In essence: using Landau terms decouples the variable of the summand function from the sum's running variable. We still (want to) read them as identical, though, therefore the confusion.

To develop it formally, what does

$\qquad \displaystyle S\_n \in \sum\_{i=1}^n \Theta(f(i)) \qquad \qquad\qquad (1)$

really mean? Now I assume that these $\Theta$ let $i$ -- not $n$ -- to infinity; if we let $n \to \infty$, every such sum evaluates to $\Theta(n)$ (if the summands are independent of $n$ and therefore constant) which is clearly wrong. Here is a first giveaway that we to crude things: $i$ is bound (and constant) inside the sum, but we still let it go to infinity?

Translating $(1)$ (for the upper bound, the lower bound works similarly), we get

$\qquad \displaystyle \exists f\_1, \dots, f\_n \in \Theta(f).\ S\_n \leq \sum\_{i=1}^n f\_i(i)$

Now it is clear that the sum-$i$ and parameter-$i$ are decoupled: we can easily define the $f\_i$ so that they use $i$ as a constant. In the example from the question, we can define $f\_i(j) = i \cdot \frac{1}{j} \in \Theta(1/j)$ and have

$\qquad \displaystyle \sum\_{i=0}^n f\_i(i) "=" \sum\_{i=0}^n \Theta(1/j) = \sum\_{i=0}^n \Theta(1/i)$

but the original sum clearly does not evaluate to something in $\Theta(H\_n) = \Theta(\log n)$. Now exchanging $j$ for $i$ -- which is only a renaming -- in the $\Theta$ may feel strange because $i$ is not independent of $n$ resp. the sum, but if we object to that *now*, we should never have used $i$ inside the $\Theta$ in the first place (as that holds the same strangeness).

Note that we did not even exploit that the $f\_i$ may also depend on $n$.

To conclude, the proposed identity is bogus. We can, of course, agree on conventions on how to read such sums as abbreviation of rigorous calculation. However, such conventions will be incompatible with the definition of Landau terms (together with the normal abuse of them), impossible to understand correctly without context and misleading (for beginners) at least -- but that is ultimately a matter of taste (and ruthlessness?).

It occurred to me that we can also write *exactly* what we mean and still make use of the convenience of Landau terms. We *know* that all summands come from one common function, implying that the asymptotic bounds use the same constants. This is lost when we put the $\Theta$ into the sum. So let us *not* put it in there and write

$\qquad \displaystyle \sum\_{i=1}^n \frac{2i - 1}{i(i+1)} \in \Theta\left(\sum\_{i=1}^n \frac{1}{i}\right) = \Theta(H\_n)$

instead. Putting the $\Theta$ outside of the sum results in

* a mathematically correct statement and
* a simple term *inside* the $\Theta$ we can easily deal with (which is what we want here, right?).

So it seems to me that this is both a correct *and* a useful way of writing the matter down, and should therefore be preferred over using Landau symbols *inside* the sum when we mean them *outside* of it.
> 1 votes

# Answer
Looks right to me in the following convention:

$S\_n = \sum\_{k=1}^{n} \Theta(1/k)$ is convenient notation for

> There is an $f(x) \in \Theta(1/x)$ (as $x \to \infty$) such that
>
> $S\_n = \sum\_{k=1}^{n} f(k)$.

Thus the $c\_i$ (or with the notation in this answer $c\_k$) you get, are not really dependent on $k$.

Under this interpretation, it is indeed true that $S\_n = \Theta(H\_n)$.

In fact, in Jeff's answer, he shows that $T(k+1) = f(k) + T(k)$ where $f \in \Theta(1/k)$, so it is consistent with the above interpretation.

The confusion seems to be arising from mentally "unrolling" the $\sum$ and presuming different functions for each occurrence of $\Theta$...
> 5 votes

# Answer
If each $c\_i$ is a constant, then there is some $c\_{max}$ such that $\forall c\_i: c\_i\leq c\_{max}$. So clearly $$\sum c\_i f(i) \leq \sum c\_{max} f(i) = c\_{max} \sum f(i) = O\left(\sum f(i)\right)$$ Same idea for little o.

I think the problem here is that $1/i\not=\Theta(1)$. It's $o(1/n)$ (since there is no $\epsilon$ such that $\forall i: 1/i\>\epsilon$), so the overall sum will be $no(1/n)=o(1)$. And each term is $O(1)$, meaning the overall sum is $O(n)$. So no tight bounds can be found from this method.

I think your questions are:

1. Is bounding $\sum\_i^n f(i)$ by doing the little o of each term and the big o of each term then multiplying by $n$ acceptable? (Answer: Yes)
2. Is there a better method? (Answer: Not that I know of.)

Hopefully someone else can answer #2 more clearly.

EDIT: Looking over your question again, I think you are asking

> $\sum\_i^n \Theta(f(n)) = \Theta(nf(n))$ ?

To which the answer is yes. In this case though, each term is not $\Theta$ of anything, so that approach falls apart.

EDIT 2: You say "consider $c\_i=i$, then there is no $c\_{max}$". Unequivocally true. If you say that $c\_i$ is a non-constant function of $i$, then it is, by definition, non-constant.

Note that if you define it this way, then $c\_i i$ is not $\Theta(i)$, it's $\Theta(i^2)$. Indeed, if you define "constant" to mean "any function of $i$", then any two functions of $i$ differ by a "constant"!

Perhaps this is an easier way to think of it: we have the sequence $1,\frac{1}{2},\dots,\frac{1}{n}$. What's the smallest term in this sequence? Well, it will depend on $n$. So we can't consider the terms as constant.

(Computer scientists are often more familiar with big-O, so it might be more intuitive to ask if $1,\dots,n$ has a constant largest term.)

To provide your proof: let $f(i\_{min})$ be the smallest value of $f(i)$ in the range $1,\dots,n$. Then $$\sum\_i^n f(i) \geq \sum\_i^n f(i\_{min}) = n f(i\_{min}) = n o(f(n))$$

An analogous proof can be made for the upper bound.

Lastly, you write that $H\_n = o(n)$ and as proof give that $H\_n = \Theta(\log n)$. This is in fact a counter-proof: if $H\_n$ is "bigger" than $n$, then it can't be "smaller" than $\log n$, which is what's required for it to be $\Theta(\log n)$. So it can't be $o(n)$.
> -1 votes

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


# Question
Title: Reason for global update steps in the push-relabel algorithm
I know why and how the push relabel algorithm works for solving the max-flow problem. But why is a global update step required?

# Answer
> 3 votes
Global relabeling is not required; it's an optimization. In the push-relabel paper, Goldberg and Tarjan describe a parallel version not amenable to such an update. The kind of performance problem global relabeling addresses is when two nodes u and v with surplus and residual arcs to one another become disconnected from the sink in the residual graph. The local relabeling rule can only increase u's label to one more than v's, and vice versa, so surplus is pushed back and forth and the labels slowly count up until the maximum of n is reached. Now imagine if this happens to a dense subgraph with many nodes.

By alternating m steps of push/relabel with global updates, the running time at worst goes up by a constant factor but in practice typically goes down, by a lot. The best implementations of push-relabel use gap relabeling as well as global relabeling. Both heuristics are described, with some experiments, by Cherkassky and Goldberg.

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Tighter analysis of modified Borůvka's algorithm
Borůvka's algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$.

The pseudo-code is:

```
MST T = empty tree
Begin with each vertex as a component
While number of components > 1
    For each component c
       let e = minimum edge out of component c
       if e is not in T
           add e to T  //merging the two components connected by e

```

We call each iteration of the outer loop a round. In each round, the inner loop cuts the number of components at least in half. Therefore there are at most $O(\log n)$ rounds. In each round, the inner loop looks at each edge at most twice (once from each component). Therefore the running time is at most $O(m \log n)$.

Now suppose after each round, we remove all the edges which only connect vertices within the same component and also remove duplicate edges between components, so that the inner loop only looks at some number of edges m' \< m which are the minimum weight edges which connect two previously disconnected components.

**How does this optimization affect the running time?**

If we somehow knew that in each round, it would cut the number of edges in half, then the running time would be significantly improved: $T(m) = T(m /2) + O(m) = O(m)$.

However, while the optimization will dramatically reduce the number of edges examined, (only 1 edge by the final round, and at most # of components choose 2 in general), it's not clear how/if we can use this fact to tighten the analysis of the run-time.

# Answer
> 5 votes
It is possible to craft test cases for general graphs where your Borůvka's step wouldn't halve the number of edges in each step, even though it halves the number of vertices. An interesting note is that the optimization that you suggest works for planar graphs. This is because for planar graphs $|E| \leq 3\*|V|-6 $ i,e $|E| = O(|V|)$. And in general it leads to a speed up for the class of minor closed families of graphs.

**Reference:**

* Masters thesis, Claude Anderson (on page 100 the worst case input for Borůvka's algorithm is described). \[link\]
* "Two linear time algorithms for MST on minor closed graph classes". Archivum mathematicum 40 (3): 315–320, 2004. \[link\]

---
Tags: algorithms, algorithm-analysis, spanning-trees
---


# Question
Title: An edge that connects more than two nodes in a graph?
Is there a way to create a single edge on a graph that connects 3 or more nodes? For example, let's say that the probability of Y occurring after X is 0.1, and the probability of Z occurring after Y is 0.001, but the probability of Z occurring after *both* X and Y occur is 0.95. If the probabilities are assigned to each edge as weights, how can I make this happen?

$$X \_\overrightarrow{0.1} Y$$

$$Y \_\overrightarrow{0.001} Z$$

$$\overrightarrow{X \underrightarrow{} Y \underrightarrow{0.95}} Z$$

# Answer
> 9 votes
When edges connect more than two nodes, you don't have a graph, you have a hypergraph. More precisely, since transitions are oriented (you're starting from a digraph) and there are probability on each transition, you have a weighted hyperdigraph. I'm not sure having this term will help you that much: as data structures go, this isn't that much of a classic.

Transitions with multiple origins rather remind me of Petri nets. If your probabilities are rational numbers and there are no loops, you can scale them to integers. Otherwise you would need to reach for probabilistic Petri nets, I think.

# Answer
> 5 votes
Based on your above comments with @Gilles, what you describe is just a higher order markov model. For example an $n$th order markov model, is a model which assumes

$$ P(x\_t | x\_{t-1}, x\_{t-2}, \ldots x\_1) = P(x\_t | x\_{t-1}, x\_{t-2}, \ldots x\_{t-n}).$$

If $n$ is not fixed you have a variable order markv model.

---
Tags: algorithms, graphs, probabilistic-algorithms, weighted-graphs
---


# Question
Title: Where can I find the data of the computer experiments in the book "Neural Networks and Learning Machines"?
The book "Neural Networks and Learning Machines" by Simon Haykin has many computer experiments to which many exercises are related. But there seems to be no data for these experiments available online. Where can I find them?

# Answer
The MATLAB files for the book are accessible here.

I'm not familiar with the text, but there are `.mat` files in the zip named

> c.mat
>
> sig\_lorenz\_full.mat

which probably contain the data. There are also a handful of TIFF files (images) from which he draws the other data.
> 3 votes

---
Tags: reference-request, data-sets
---


title: Greedy choice and matroids (greedoids)

text:
# Question
Title: Greedy choice and matroids (greedoids)
As I was going through the material about the greedy approach, I came to know that a knowledge on matroids (greedoids) will help me approaching the problem properly. After reading about matroids I have roughly understood what matroids are. But how do you use the concept of a matroid for solving a given optimisation problem?

Take, for example, the activity selection problem. What are the steps to use matroid theory for solving the problem?

# Answer
The connection is that if a you can represent the structure underlying your optimisation problem as matroid, you can use the canonical greedy algorithm to optimise the sum of any positive weight function. If your optimisation goal fits this paradigm, you can solve your problem with the greedy approach.

### Example

Consider the minimum spanning tree problem with positive edge weights¹. We will show that there is a matroid corresponding to that problem, implying that it can be solved greedily, that is by the canonical greedy algorithm on said matroid.

Let $G = (V,E,c)$ be an undirected graph with $c : E \to \mathbb{R}\_+$ the edge-cost function. Then, $(E,I)$ with

$\qquad \displaystyle I = \\{F \subseteq E \mid (V|\_F, F) \text{ is a forest}\\}$²

is a matroid. Thus, we can find the element of $I$ maximising the sum of edge weights $c'(e) = (\max\_{e \in E}c(e)) - c(e)$. This happens to be a minimum spanning tree. Note that the canonical greedy algorithm is called Kruskal's algorithm in this context for historical reasons.

### Proofs

1. To show: $(E,I)$ is a matroid. We have to verify three properties:

* $\emptyset \in I$ -- the empty graph is a forest.
    * If $F \in I$, every subset of $F$ is in $I$ -- given an arbitrary forest, *removing* edges can not introduce cycles. Therefore, every subgraph of a forest is a forest.
    * For every $F\_1,F\_2 \in I$, $|F\_1| \> |F\_2|$ implies that there is $e \in F\_1 \setminus F\_2$ so that $F\_2 \cup \\{e\\} \in I$ -- consider an arbitrary forest $F\_1$ and a smaller one $F\_2$. Assume there is no such $e$. That means that all edges in $F\_1$ lie in cuts induced by edges in $F\_2$³. As there are only $|F\_2|$ such cuts, at least one pair of edges in $F\_1$ shares a cut; this contradicts that $F\_1$ is a forest.
2. To show: any element $F^\*$ with maximum weight in $I$ is a minimum spanning tree of $G$. First of all, it is clear $F^\*$ has maximum weight according to $c'$, so by definition of $c'$, it also has *minimum* weight according to $c$. Now all we have to show is that it is a spanning tree: if it was not, it would not be maximal in the sense that we could still add edges (with positive weight), contradicting maximum weight.

---

1. We can deal with negative edge weights by adding the minimum weight plus one to all weights.
2. A forest is a disjoint union of trees.
3. A graph contains a cycle if and only if there is a cut with more than one edge.
> 6 votes

---
Tags: algorithms, graphs, greedy-algorithms, matroids
---


# Question
Title: Showing $A-B$ is a CFL where $A$ is a CFL and $B$ is finite
> Show that if $A$ is a context-free language and $B$ is finite, then $A - B$ is a context-free language.

I'm just not sure how to use their properties to formally show this. Thanks for all the help in advance.

# Answer
> 6 votes
Hint: If $A$ is context-free and $R$ is regular then $A \cap R$ is context-free.

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


# Question
Title: Brute force Delaunay triangulation algorithm complexity
In the book "Computational Geometry: Algorithms and Applications" by Mark de Berg et al., there is a very simple brute force algorithm for computing Delaunay triangulations. The algorithm uses the notion of *illegal edges* -- edges that may not appear in a valid Delaunay triangulation and have to be replaced by some other edges. On each step, the algorithm just finds these illegal edges and performs required displacements (called *edge flips*) till there are no illegal edges.

> Algorithm **LegalTriangulation**($T$)
>
> *Input*. Some triangulation $T$ of a point set $P$.
> *Output*. A legal triangulation of $P$.
>
> **while** $T$ contains an illegal edge $p\_ip\_j$
> **do**
> $\quad$ Let $p\_i p\_j p\_k$ and $p\_i p\_j p\_l$ be the two triangles adjacent to $p\_ip\_j$.
> $\quad$ Remove $p\_ip\_j$ from $T$, and add $p\_kp\_l$ instead.
> **return** $T$.

I've heard that this algorithm runs in $O(n^2)$ time in worst case; however, it is not clear to me whether this statement is correct or not. If yes, how can one prove this upper bound?

# Answer
> 8 votes
A Delaunay triangulation can be considered as the lower convex hull of the 2d point set lifted to the paraboloid. Thus, if you take your 2d point set and assign to every point $(x\_i,y\_i)$ a $z$-coordinate $z\_i=x\_i^2+y\_1^2$, then the projection of the lower convex hull into the $xy$-plane gives you the Delaunay triangulation.

Using this perspective, what does it mean for an edge $(p\_i,p\_j)$ to be illegal? First of all, for every triangulation $T$ we can use the parabolic map to get a 3d (triangulated) surface that projects down to $T$. Of course, this surface is not necessarily convex, if it would be convex, $T$ would be the Delaunay triangulation. Simply speaking, the edge $(p\_i,p\_j)$ is an obstruction for the convexity of the surface, a *concave* edge. When flipping this edge we change the situation on the lifted surface only locally. So lets look at the 4 points $p\_i,p\_j,p\_k,p\_l$. In 3d they form a tetrahedron, that projects down to quadrilateral. Since the two triangles $p\_ip\_jp\_k$ and $p\_ip\_jp\_l$ define the the concave edge $(p\_i,p\_j)$, the triangles $p\_kp\_lp\_i$ and $p\_kp\_lp\_j$ define the a convex edge $(p\_l,p\_k)$. Therefore, flipping an illegal edge corresponds to replacing a concave edge by a convex edge in the lifting. Notice that this flips might turn other convex edges to concave edges.

*Remark: The image is not geometrically correct and should only be considered as a sketch.*

Let $T'$ be the triangulation after the flip. The lifted surface of $T'$ "contains" the surface of $T$. By this I mean that if you watch the two surfaces from the $xy$ plane you see only triangles from the surface of $T'$ (or triangles that are in both surfaces). You could also say that the surface of $T'$ encloses more volume. Also, the edge $(p\_i,p\_j)$ lies now "behind" the lifted surface induced by $T'$ when watching from the $xy$ plane.

During the flip sequence we get a sequence of surfaces with strictly increasing volume. Thus, the edge $(p\_i,p\_j)$ lies "behind" all these surfaces. Hence, it can never reappear during the flipping process. Since there are only $n$ choose 2 possible edges, we have at most $O(n^2)$ flips.

---
Tags: algorithms, time-complexity, algorithm-analysis, computational-geometry, runtime-analysis
---


# Question
Title: Is SAT in P if there are exponentially many clauses in the number of variables?
I define a *long CNF* to contain at least $2^\frac{n}{2}$ clauses, where $n$ is the number of its variables. Let $\text{Long-SAT}=\\{\phi: \phi$ is a satisfiable long CNF formula$\\}$.

I'd like to know why $\text{Long-SAT} \in P$. First I thought it is $\text{NPC}$ since I can do a polynomial-time reduction from $\text{SAT}$ to $\text{Long-SAT}$, no?

But maybe I can reduce $\text{2-SAT}$ to $\text{Long-SAT}$? How do I do that?

# Answer
> 12 votes
Unless I'm missing something, it's trivially in **P** as the length of the formula is exponential in the number of variables. Hence all $2^{n}$ truth assignments can be generated and checked in polynomial time in the length of the formula.

# Answer
> 7 votes
In this case, the answer is trivial as Luke points out. However, as you seem to have come up with the definition yourself, note this.

For SAT, so-called phase transitions regarding the ratio of variable count to clause count have been observed \[1,2\]. If it is small, instances are easy, and hard if it is large. There seems to be a more or less sharp transition from easy to hard. This seems to be an active area of research. cstheory.SE has some more on this phenomenon.

So, if you adjust your definition of "long" to *polynomial* blowup, you might indeed get an non-trivially easy class -- that is, in P -- just because you have much more clauses than variables.

---

1. The SAT Phase Transition by I. P. Gent (1994)
2. Determining computational complexity from characteristic 'phase transitions' by R. Monasson, R. Zecchina et al. (1999)

---
Tags: complexity-theory, np-complete, reductions, satisfiability, polynomial-time
---


# Question
Title: Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space
We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): \Leftrightarrow i \geq 0$. We don't know in advance how many elements of $S$ satisfy the predicate $P$, but we would like to sample or choose an element uniformly at random from $S' = \\{ i \mid i \in S \wedge P(i) \\}$.

The naive approach is to scan $S$ and for example record all the integers or indices for which $P$ holds, then choose one of them uniformly at random. The downside is that in the worst-case, we need $|S|$ space.

For large sets or in say a streaming environment the naive approach is not acceptable. Is there an in-place algorithm for the problem?

# Answer
The following approach is often referred to as reservoir sampling. Start scanning the set $S$ and maintain an index $j$ to the set. The first element you encounter satisfying the predicate, set $j$ to it with probability $1/1$. Update your choice for $j$ when you encounter the second such element with probability $1/2$. When you encounter the $k$th element satisfying the predicate, set $j$ to it with probability $1/k$.

The algorithm works in $\Theta(n)$ time and in constant space. For correctness, it should be shown that every item has an equal probability of being chosen and that the events they are sampled are independent. The second claim of independency is obvious: our decisions are not based on whether we have previously sampled items. The first claim (equal likelihood) can be proven quite easily with induction.

For details, see J. S. Vitter, Random Sampling With a Reservoir, algorithm R. For a more compact presentation, see for example these slides.
> 5 votes

---
Tags: algorithms, randomized-algorithms, streaming-algorithm, in-place
---


# Question
Title: Can top SAT-solvers factor easy numbers?
Modern SAT-solvers are very good at solving many real-world examples of SAT instances. However, we know how to generate hard ones: for instance use a reduction from factoring to SAT and give the RSA numbers as input.

This raises the question: what if I take an easy example of factoring. Instead of taking two large primes on $n/2$ bits, what if I take a prime $p$ on $\log n$ bits and a prime q on $n/\log n$ bits, let $N = pq$ and the encode $\mathrm{FACTOR}(N)$ as a SAT instance. $N$ would be an easy number to factor by brute-force search or sieve methods since one of the factors in so small; does a modern SAT-solver with some standard reduction from factoring to SAT also pick up on this structure?

**Can top SAT-solvers factor $N = pq$ where $|p| = \log n$ quickly?**

# Answer
> 10 votes
There are other much simpler instances which we provably know that the current algorithms cannot solve in sub-exponential time. These algorithms are incapable of counting (almost all of them are improvements of DPLL which correspond to Resolution propositional proof system).

Unfortunately such examples are unsatisfiable instances. The question about finding natural satisfiable hard instances for these algorithms is an interesting research problem (Russell Impagliazzo mentioned this during the proof complexity workshop last year at Banff). There are satisfiable instances that we provably know the algorithms fail badly if there is any such instance, but they are not very natural (they are based on formulas expressing the soundness of algorithms).

Regarding factoring, if the size of numbers are small (e.g. logarithmic as in your case, i.e. the numbers are given in unary), then theoretically there is no result that says there cannot be solved by current algorithms, and in fact we can write simple polynomial time algorithms that factor these numbers. So whether a particular SAT solver program can solve them might depend on the particular algorithm.

---
Tags: complexity-theory, satisfiability, sat-solvers, factoring
---


# Question
Title: What is the average height of a binary tree?
Is there any formal definition about the average height of a binary tree?

I have a tutorial question about finding the average height of a binary tree using the following two methods:

1. The natural solution might be to take the average length of all possible paths from the root to a leaf, that is

$\qquad \displaystyle \operatorname{avh}\_1(T) = \frac{1}{\text{# leaves in } T} \cdot \sum\_{v \text{ leaf of } T} \operatorname{depth}(v)$.
2. Another option is to define it recursively, that is the average height for a node is the average over the average heights of the subtrees plus one, that is

$\qquad \displaystyle \operatorname{avh}\_2(N(l,r)) = \frac{\operatorname{avh}\_2(l) + \operatorname{avh}\_2(r)}{2} + 1$

with $\operatorname{avh}\_2(l) = 1$ for leafs $l$ and $\operatorname{avh}\_2(\\\_) = 0$ for empty slots.

Based on my current understanding, for example the average height of the tree $T$

```
    1
   / \
  2   3
 /
4

```

is $\operatorname{avh}\_2(T) = 1.25$ by the second method, that is using recursion.

However, I still don't quite understand how to do the first one. $\operatorname{avh}\_1(T) = (1+2)/2=1.5$ is not correct.

# Answer
> 3 votes
There is no reason to believe that both definitions describe the same measure. You can write $\operatorname{avh}\_1$ recursively, too:

$\qquad \displaystyle \operatorname{avh}\_1(N(l,r)) = \frac{\operatorname{lv}(l)(\operatorname{avh\_1}(l) + 1) + \operatorname{lv}(r)(\operatorname{avh\_1}(r) + 1)}{\operatorname{lv}(l) + \operatorname{lv}(r)}$

with $\operatorname{avh}\_1(l) = 0$ for leaves $l$. If you don't believe that this is the same, unfold the definition of $\operatorname{avh}\_1$ on the right hand side, or perform an induction proof.

Now we see that $\operatorname{avh}\_1$ works quite differently from $\operatorname{avh}\_2$. While $\operatorname{avh}\_2$ weighs the recursive heights of a nodes children *equally* (adding and dividing by two), $\operatorname{avh}\_1$ weighs them according to the number of leaves they contain. So they are the same (modulo the anchor) for leaf-balanced trees, that is balanced in the sense that sibling trees have equally many leaves. If you simplify the recursive form of $\operatorname{avh}\_1$ with $\operatorname{lv}(l) = \operatorname{lv}(r)$ this is immediately apparent. On unbalanced trees, however, they are different.

Your calculations are indeed correct (given your definition); note that the example tree is not leaf-balanced.

# Answer
> 2 votes
**Edit:** Jeffe makes a good point in his comment above. You should probably read "correct vs incorrect" in the following answer as "convenient/consistent vs inconsistent".

It seems to be that your second calculation is incorrect. Let the height of a subtree with a single node (i.e. a leaf) be 0. Then the height of the subtree root at:

* height at 4 is 0
* height at 3 is 0
* height at 2 is average height at 3 + 1 = 0 + 1 = 1
* height at 1 is average of heights at 2 and 3 = (0 + 1)/2 + 1 = 1.5

I think you are doing the first calculation correctly, and 1.5 is the right answer.

---
Tags: graphs, terminology, combinatorics, binary-trees
---


# Question
Title: A polynomial reduction from any NP-complete problem to bounded PCP
Text books everywhere assume that the *Bounded* Post Correspondence Problem is NP-complete (no more than $N$ indexes allowed with repetitions). However, nowhere is one shown a simple (as in, something that an undergrad can understand) polynomial time reduction from another NP-complete problem.

However every reduction I can think of is exponential (by $N$ or by the size of the series) in run-time. Perhaps it can be shown that it is reducible to SAT?

# Answer
> 12 votes
As is often the case with NP-reductions, it makes sense to look for similar problems. In particular, it is hard to encode global conditions such has "have seen some nodes" into PCP (with polynomially many tiles) which contraindicates graph problems, packing problems would require us to encode unary numbers in PCP (creating exponentially large instance), and so on. Therefore, a string problem with only local restrictions can be expected to work best.

Consider the decision version of the shortest common supersequence problem:

> Given two strings $a,b \in \Sigma^+$ with $|a|=n$ and $|b|=m$ and $k \in \mathbb{N}$, decide whether there is a string $c \in \Sigma^+$ with $|c| \leq k$ such that $a$ and $b$ are subsequences of $c$.

The idea is to let PCP build supersequences of $a$ and $b$ from left to right, encoding in the tiles' overlaps at which position we are in $a$ and $b$, respectively. It will use one tile per symbol in $c$, so $k$ corresponds to the BPCP's bound: if we can solve this PCP with $\leq k$ tiles, you can read off the common supersequence of equal length, and vice versa.

The construction of the tiles is a bit tedious, but quite clear. Note that we will not create tiles that do not forward $a$ or $b$; such can never be part of a *shortest* common supersequence, so they are superfluous. They can easily be added without breaking the properties of the reduction.

The numbers in the overlaps are encoded in binary, but using symbols outside of $\Sigma$ and padding them to a common length $\log \max(m,n)$. Thus we ensure that the tiles are used as the graphics suggest (tetris), that is characters and index-encoding overlaps do not mix (PCP does not prevent this per se). We need:

* **Starting tiles:** $c$ can start with $a\_1$, $b\_1$ or both if they are equal.
* **Intermediate tiles:** $c$ can proceed with the next symbol in $a$, in $b$ or both if they are equal.
* **Terminating tiles:** $c$ ends with the last symbol of $a$ (if the last one of $b$ has been seen already), similar for $b$, or with the last symbol of both.

These are the tile schematics. Note that the intermediate tiles have to be instantiated for all pairs $(i,j) \in \[n\]\times \[m\]$. As mentioned above, create the tiles without $\*$ only if the respective characters in $a$ and $b$ match.

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

The $\*$ are symbolic for "don't care"; in the actual tiles, the other symbol will have to be copied there. Note that the number of tiles is in $\Theta(mn)$ and each tile has length $4\log \max(m,n) + 1$, so the constructed BPCP instance (over alphabet $\Sigma \cup \\{0,1\\}$ plus separation symbols) has polynomial size. Furthermore, the construction of every tile is clearly possible in polynomial time. Therefore, the proposed reduction is indeed a valid polynomial transformation which reduces the NP-complete shortest common supersequence problem to BPCP.

# Answer
> 9 votes
I think that you can prove that BPCP is NP-complete by using a reduction similar to the one used to prove its undecidability. We will directly prove that BPCP is NP-complete by showing how to reduce any problem in NP to it in polynomial time.

The standard reduction used to prove that PCP is undecidable (sketched out here) works by building a series of tiles such that there is a PCP solution iff there is an accepting computation of a given TM $M$ on a string $w$. The number of tiles created in this reduction is polynomially large - specifically, the number of dominoes constructed is some function of the size of the tape alphabet and number of states in the TM. The only domino whose size may be large is the initial domino, which has $w$ written on it. If we generalize this reduction from working on deterministic TMs to working on nondeterministic TMs, then this introduces at most some constant number of dominoes, since the number of transitions is finite. Consequently, we can construct the standard set of dominoes for the normal undecidability reduction in polynomial time.

Given this, we can reduce any NP problem to BPCP as follows - given any NP problem, it has some polynomial-time NTM $M$ that runs in time $p(n)$. We can then reduce this problem to BPCP in polynomial time as follows - construct the standard set of dominoes from $M$, then ask whether there is a solution that uses $f(p(n))$ dominoes, where $f$ is some polynomial function that expresses the number of dominoes necessary for the solution to exist (this is probably something like $n^2$, and is certainly not exponential). Then, using the same proof you use to show that PCP is undecidable, you can prove that there is a solution to this BPCP instance that uses at most $f(p(n))$ tiles iff the original NTM $M$ accepts $m$ within $p(n)$ steps. Consequently, we have a polynomial-time reduction from every problem in NP to BPCP, so BPCP is NP-hard.

(We should also show that BPCP is in NP, but that's easy; just nondeterministically guess which dominoes to put in order, then deterministically verify it).

Hope this helps!

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


# Question
Title: Are regular languages closed under sort (Parikh image)?
Assume $L$ is a regular language over an ordered alphabet. Is the language built by taking every word in $L$ and sorting it always a regular language?

# Answer
No. Counterexample: assuming $a \< b$, we have $(ab)^\ast \xrightarrow{\\;\\;\text{sorted}\\;\\;} \\{ a^n b^n \\;|\\; n \geqslant 0 \\}$, which cannot be expressed by a regular expression, by the pumping lemma for regular languages.
> 17 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: Message receipt verification in a cluster
At my current project I had a network problem come up for which I could not find a solution. In a peer-to-peer network I needed to send an action to all peers, and each peer was to act on it only if it could verify that all other peers would also act on it.

That is, given a network of peers $P = { P\_1, ..., P\_n }$. We wish to send, from some source peer $P\_s$ a message to all other peers. This message contains an action which must be performed. The peer should perform this action if and only if every other peer will perform the action. That is, it performs the action if it can verify that all other peers will also have receipt of the action and can perform the same verification.

The problem is subject to these conditions:

1. There is no implicit message delivery guarantee: if $P\_x$ sends a message to $P\_y$ there is no way for $P\_x$ to know if $P\_y$ gets the message. (Of course $P\_y$ can send a receipt, but that receipt is subject to the same constraint)
2. Additional messages with any payload may be created.
3. There is no total ordering on the messages received by peers. Messages can arrive in a different time-order than which they were sent. This time-order may be unique per peer. *Two messages sent in order from $P\_x$ to $P\_y$ are very unlikely to arrive out of order.*
4. Messages can arrive at any point in the future (so not only are they not ordered, they can be indefintely delayed). A message cannot inherently be detected as lost. *Most messages will be delivered quickly, or truly lost.*
5. Each peer has a synchronized clock. It is accurate enough in the domain of scheduling an action and to approximately measure transmission delays. It is however not accurate enough to establish a total ordering on messages using timestamps.

I was not able to find a solution. I'm interested in a *guarantee* and not simply a high probability of being correct (which can be done simply be repeatedly sending confirmations from peer to peer and rejections upon any likely loss.) My stumbling block is the inability to verify that any particular message actually arrived. So even if $P\_x$ determines there is an erorr, there is no guaranteed way to tell the other peers about it.

A negative confirmation is also acceptable. I have a suspicion that a guarantee cannot actually be achieved, only an arbitrarily high probability.

# Answer
Your suspicion is correct: under these conditions, there is no way to guarantee a solution. Yours is a consensus problem, and there is a general result that states the **impossibility of consensus** in an asynchronous network with failures. This result is sometimes known as FLP after its authors (Fischer, Lynch and Paterson) \[FLP\].

The original consensus states roughly this (see \[FLP\] or \[L96\] or \[T00\]): suppose you have $N$ processes with $N \ge 3$. The processes can communicate by sending asynchronous messages: there is no notion of real time, messages can take arbitrarily long in transit. Furthermore, a process may fail (it stops emitting messages). Define a *configuration* as an assignment of boolean values (0 or 1) to each process, and *consensus* as a configuration in which all non-failed processes have the same value. Each process may change its assigned value based deterministically on the messages it has received; the collection of algorithms executing on each process defines a distributed algorithm. The FLP result states that there is no algorithm that can reach a consensus from an arbitrary initial configuration, such that there is always at least one process that keeps its initial value. (In other words, the only solutions are the trivial one where all processes pick the same value.)

In your case, the failures are in transmissions rather than in processes, but this only makes the situation more difficult: you can simulate a process failure by losing all the messages to and from that process.

The FLP result implies that there is no distributed algorithm that will always (given sufficiently many received messages) lead to either all processes deciding on taking the action, or no process taking the action, unless they are all primed to act or all primed not to act.

Having clocks does not help: they are part of the local algorithm. They would help if you could put a bound on the message travel times: timeouts in transmissions are the usual way of solving consensus in practice.

### Bibliography

\[FLP\] Michael J. Fischer and Nancy A. Lynch and Michael S. Paterson. "Impossibility of distributed consensus with one faulty process". April 1985. Journal of the ACM 32 (2). DOI:10.1145/3149.214121

\[L96\] Nancy Lynch. *Distributed Algorithms*. Elsevier, 1996. 1-55860-348-4. http://groups.csail.mit.edu/tds/distalgs.html

\[T00\] Gerard Tel. *Introduction to Distributed Algorithms*. 2nd ed. Cambridge University Press, 2000. 0521794838.
> 4 votes

# Answer
Informally, the problem is similar to Sicilian reasoning. Any given agent can only act if

* it got the original message,
* it knows that everybody else got the message,
* it knows that everybody else knows it got the message,

and so on. In your model, there is no tool to break this dilemma: all communication is explicit and therefore prone to loss. In addition, agents have not way to decide whether another (known) agent is still there.
> 3 votes

---
Tags: algorithms, distributed-systems, computer-networks, fault-tolerance
---


# Question
Title: Does this regular expression equal this automata?
I just came across an exercise which is to find a regular expression for the following automata, such that the regular expression and the automata generate the same language.

One solution presents the following expression:

$\qquad \displaystyle r\_A = a^+b^+(c\mid ca^\*b^+)^\*$

However, can this be true? I think not, because the all words created from the regular expression will have at least one $b$ in it, whereas the automata accepts words without $b$, such as $aaa$.

What is your opinion?

# Answer
In general, you can decide equivalence of regular expression and finite automaton using standard algorithms:

* Construct an NFA from the regular expression,
* Determinise and minimise both automata,
* Check for equality (up to isomorphism).

These algorithms and proof that the minimal DFA of any regular language is unique (up to isomorphism) can be found in introductory textbooks.

If the underlying task is to "read off" a regular expression from an automaton, don't guess & proof but rather build the expression algorithmically to save time.
> 2 votes

---
Tags: regular-languages, automata, finite-automata, regular-expressions
---


# Question
Title: How to call something that can be either a terminal or a nonterminal?
I had written a compiler compiler a few years ago and I'm now cleaning it up, improving it, and turning it into C.

I came across a terminology problem however that I remember in the past I couldn't solve it either.

Imagine an LL(k) stack. In this stack, you may have terminals, that are expected to be matched with the next token, or non-terminals that would expand based on the next token. In either case, there is a string in the stack.

The word I am looking for, is a term that means either a terminal or non-terminal. Wikipedia was of no help.

To clarify a bit more, imagine a grammar with $t = \\{a \mid a \text{ terminal}\\}$ and $T = \\{A \mid A \text{ non-terminal}\\}$. If you have a set $X = \\{x | x \in t \vee x \in T\\}$, how would you refer to an element of $X$? "Grammar symbol"? "Grammar element"? "Terminal or non-terminal symbol"?

I am in particular looking for a name as short and to the point as possible, since this will end up becoming a variable name!

# Answer
> 7 votes
The long forms "terminal symbol" and "nonterminal symbol" suggest that you are dealing first and foremost with "symbols"; "terminal" and "non-terminal" are qualifiying attributes that specify a symbol's role in the grammar. A symbol that can be either one of terminal and non-terminal is, almost by virtue of logics, just an arbitrary symbol.

Therefore, "symbol" seems to be the natural choice. I am pretty sure it is the term usually used, too, but such statements are hard to validate.

If you want to stress that a given symbol can be either kind (in text), you can always use "arbitrary symbol (of grammar $G$)", or define $X \subseteq t \cup T$ explicitly. In source code, I'd just use "symbol".

---
Tags: terminology, formal-grammars, compilers
---


# Question
Title: Determining the particular number in $O(n)$ time and space (worst case)
$\newcommand\ldotd{\mathinner{..}}$Given that $A\[1\ldotd n\]$ are integers such that $0\le A\[k\]\le m$ for all $1\le k\le n$, and the occurrence of each number except a particular number in $A\[1\ldotd n\]$ is an odd number. Try to find the number whose occurrence is an even number.

There is an $\Theta(n\log n)$ algorithm: we sort $A\[1\ldotd n\]$ into $B\[1\ldotd n\]$, and break $B\[1\ldotd n\]$ into many pieces, whose elements' value are the same, therefore we can count the occurrence of each element.

I want to find a worst-case-$O(n)$-time-and-$O(n)$-space algorithm.

Supposing that $m=\Omega(n^{1+\epsilon})$ and $\epsilon\>0$, therefore radix sort is not acceptable. $\DeclareMathOperator{\xor}{xor}$ Binary bitwise operations are acceptable, for example, $A\[1\]\xor A\[2\]$.

# Answer
> 2 votes
Here is an idea for a simple algorithm; just count all occurrences!

1. Find $m = \max A$. -- time $\Theta(n)$
2. "Allocate" array $C\[0..m\]$. -- time $O(1)$¹
3. Iterate over $A$ and increase $C\[x\]$ by one whenever you find $A\[\\\_\]=x$. If $C\[x\]$ was $0$, add $x$ to a linear list $L$. -- time $\Theta(n)$
4. Iterate over $L$ and find the element $x\_e$ with $C\[x\_e\]$ even. -- time $O(n)$.
5. Return $x\_e$.

All in all, this gives you a linear-time algorithm which may use (in the sense of allocating) lots of memory. Note that being able to random-access $C$ in constant time independently of $m$ is crucial here.

An additional $O(n)$ bound on space is more difficult with this approach; I don't know of any dictionary data-structure that offers $O(1)$ time lookup. You can use hash-tables for which here are implementations with $O(1 + k/n)$ *expected* lookup time ($n$ the table's size, $k$ the number of stored elements) so you can get arbitrarily good with linear space -- in expectation. If all values in $A$ map to the same hash value, you are screwed.

---

1. On a RAM, this is implicitly done; all we need is the start position and maybe the end position.

# Answer
> 0 votes
An almost trivial solution - which uses however $\Theta(n)$ space - is to use a hash map. Recall that a hash map has amortized runtime $\mathcal{O}(1)$ for adding and looking up elements.

Hence, we can use the following algorithm:

1. Allocate a hash map $H$. Iterate over $A$. For each element $i \in A$, increase the number of occurences seen, i.e. $H(i)++$.
2. Iterate through the key set of the hash map, and check which of the keys has an even count of occurences.

Now this is a simple algorithm which doesn't really use any large trick, but sometimes even this suffices. If not, you might want to specifiy what space restrictions you impose.

---
Tags: algorithms, search-algorithms
---


# Question
Title: Does there exist a priority queue with $O(1)$ extracts?
There are a great many data structures that implement the priority-queue interface:

* Insert: insert an element into the structure
* Get-Min: return the smallest element in the structure
* Extract-Min: remove the smallest element in the structure

Common data structures implementing this interface are (min)heaps.

Usually, the (amortized) running times of these operations are:

* Insert: $\mathcal{O}(1)$ (sometimes $\mathcal{O}(\log n)$)
* Get-Min: $\mathcal{O}(1)$
* Extract-Min: $\mathcal{O}(\log n)$

The Fibonacci heap achieves these running times for example. Now, my question is the following:

> Is there a data structure with the following (amortized) running times?

* Insert: $\mathcal{O}(\log n)$
* Get-Min: $\mathcal{O}(1)$
* Extract-Min: $\mathcal{O}(1)$

If we can construct such a structure in $\mathcal{O}(n)$ time given sorted input, then we can for instance find line intersections on pre-sorted inputs with $o\left(\frac{n}{\log n}\right)$ intersections strictly faster than if we use the 'usual' priority queues.

# Answer
> 27 votes
Our idea is to use threaded splay trees. Other than the Wikipedia article we will thread the trees so that every node has a pointer `next` to its successor in the in-order traversal; we also hold a pointer `start` to the smallest element in the tree.

It is easy to see that extracting the smallest element is possible in (worst case) time $\mathcal{O}(1)$: just follow the `start` pointer, remove the minimum and change the pointer to the minimum's `next`. The minimum can never have a left child; if it has a right child, we put it in the minimum's place in the tree. We do *not* perform the splay operation splay trees usually would do.
The result is a search tree that is still reasonably balanced: because we only remove nodes on the left flank, we know that when the number of nodes (in an affected subtree) drops to about half the original number because of deletions, the (sub)tree's height is reduced by one.

Insertions are possible in $\mathcal{O}(\log n)$ amortised time; the zig-zag (and what not) operations will here also rebalance the tree nicely.

*This is a rough sketch at best. Credits go to F. Weinberg who puzzled over the question with me and our advisor M. Nebel who mentioned splay trees, about the only tree variant we had not tried.*

# Answer
> 22 votes
* Insert: $\mathcal{O}(\log n)$
* Get-Min: $\mathcal{O}(1)$
* Extract-Min: $\mathcal{O}(1)$

### Amortized Time

Simple implementations of a priority queue (e.g. any balanced BST, or the standard binary min-heap) can achieve these (amortized) running times by simply charging the cost of Extract-Min to insert, and maintaining a pointer to the minimum element. For example, you could have a potential function that is $cn \log n$. Then inserting a new element increases potential by $O(\log n)$, and so the amortized cost of insert is still $O(\log n)$, but Extract-Min() decreases the potential by $\Omega(\log n)$, and so the amortized cost is only $O(1)$.

### Worst-Case

You can use an existing data structure in the literature: finger-search trees, and simply maintain a pointer to the minimum element. See this survey for an overview, and the 1988 paper by Levcopoulos and Overmars for an implementable version that meets your needs.

# Answer
> 16 votes
2-4 trees have amortized $O(1)$ modifications at known locations. That is to say, if you have a pointer to some location in the tree, you can remove or add an element there in $O(1)$ amortized time.

You can thus just keep a pointer to the minimum element and the root node in a 2-4 tree. Inserts should go through the root node. Updating the pointer to the minimum is trivial after a deleteMin, and deleteMins are $O(1)$ (amortized) time.

An interesting side note: red-black trees are just a way of looking at 2-4 trees. The designers of the C++98 standard expected library implementers to supply a red-black-tree-based container, and the standard specifies that insert and delete should be $O(1)$ amortized time at known locations (which they call "iterators"). However, this is actually much trickier for red-black trees than for 2-4 trees, since it requires lazily marking nodes that need to be recolored. To my knowledge, no implementations of the C++98 standard library met that particular requirement.

# Answer
> 9 votes
By request, here is the structure I found after I formulated the question:

The basic idea is to use a threaded Scapegoat tree along with a pointer to the minimum (and for good measure, the maximum as well). A simpler alternative to threading is maintaining predecessor and successor pointers in every node (which is equivalent, simpler, but has more overhead). I've come to call it a Scapegoat *heap*, just to give it some name.

Just this basic structure gives you these operations:

* Search: given a key, returns a pointer to the corresponding node in $\mathcal{O}(\log n)$ time.
* Insert: given a key, inserts the key into the structure, returning a pointer to that node in $\mathcal{O}(\log n)$ time.
* Predecessor/successor: given a pointer, returns the successor or predecessor in $\mathcal{O}(1)$ time.
* Get-Min/Max: returns the pointer to the minimum or maximum.

In the analysis of Scapegoat trees, the balancing overhead of deletion is analyzed as $\mathcal{O}(\log n)$, but the analysis actually gives a balance overhead of $\mathcal{O}(1)$ (which is ignored in the paper as they also count the $\mathcal{O}(\log n)$ time it takes to find the node that is to be deleted). So, if we have a pointer to a node, we can delete it in constant time (you can do this in threaded binary search tree in $\mathcal{O}(1)$ time) and combined with the $\mathcal{O}(1)$ overhead of balancing, this gives a $\mathcal{O}(1)$ time delete:

* Delete: given a pointer, deletes the node in $\mathcal{O}(1)$ time.

Combining this:

* Extract-Min/Max: deletes the minimum/maximum node in $\mathcal{O}(1)$ time.

You can do a bit more with pointers: for instance it's not hard to maintain a pointer to the median or some other order statistic, so you can maintain a constant number of such pointers if you need them.

Some other things:

* Construct: given $n$ keys in sorted order, build a Scapegoat heap in $\mathcal{O}(n)$ time.
* Balance: balance the tree so it forms a perfectly balanced binary search tree (reduces overhead of searching) in $\mathcal{O}(n)$ time (you can do this a constant factor faster than the paper suggests by the way, by making use of predecessor/successor pointers).

And finally, I'm pretty sure you can support these operations, but I need to think about these a bit more before knowing this for sure:

* Insert-New-Min/Max: given a key that is smaller/larger than any key already in the structure, inserts the key into the structure, returning a pointer to that node in $\mathcal{O}(1)$ time.

# Answer
> 3 votes
Okay, finally got you the complexity you were looking for, and what's best, I found it in the literature:

## Worst-Case Complexity

**Delete**: $\bf\mathcal{O}(1)$

**Delete-min**: $\bf\mathcal{O}(1)$

**Find-min**: $\bf\mathcal{O}(1)$

**Insert**: $\bf\mathcal{O}(log\ n)$

## Reference

> **IF MELD** is allowed to take linear time it is possible to support **DELETE-MIN** in worst case constant time by using the finger search trees of Dietz and Raman `[3]`. By using their data structure **MAKEQUEUE**, **FINDMIN**, **DELETEMIN**, **DELETE** can be supported in worst case time $\mathcal{O}(1)$, **INSERT** in worst case time $\mathcal{O}(log\ n)$ and **MELD** in worst case time $\mathcal{O}(n)$.

Brodal, Gerth Stølting. ‘Fast Meldable Priority Queues’. In Proceedings of the 4th International Workshop on Algorithms and Data Structures, 282–290. WADS ’95. London, UK, UK: Springer-Verlag, 1995.

`[3]`: Dietz, Paul F, and Rajeev Raman. ‘A Constant Update Time Finger Search Tree’. Information Processing Letters 52, no. 3 (1994): 147 – 154.

Though this uses the RAM model of computation:

> Our data structure uses the random-access machine (RAM) model with unit-cost measure and logarithmic word size;

More recently, a Pointer-Machine model of computation solution has been given`[1]`.

`[1]`: Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis, and Kostas Tsichlas. ‘Optimal Finger Search Trees in the Pointer Machine’. J. Comput. Syst. Sci. 67, no. 2 (September 2003): 381–418.

# Answer
> 2 votes
Approaching this problem by maintaining two data-structures: an Array and a Binary Tree.

To maintain indexing in the array, previously you'd have the $\Omega(\dfrac{\log n}{\log\log n})$ bound; but more recently this has been overcome by modifying the analysis from the chronogram technique. The new \[lower\] $\Omega(\log n)$ bound has been proved for similar problems in the cell-probe model . From reading that article; it is my understanding that that bound applies to the *list representation* problem also.

Now if you thread a binary tree into your array and rebalance+reindex every $\mathcal{O}(\log n)$ updates, then you'll have: $\mathcal{O}(\log n)$ complexities.

Your longest run—over `null` deleted elements—will be $\mathcal{O}(\log n)$. This clearly leaves no theoretical advantage over rebalancing+reindexing every update.

Depending on your distribution, you can make an assumption to only rebalance every insert; thus pull the complexity out of extract. Extract—from either end—will then only take $\mathcal{O}(1)$; as no reindex needs to occur (just keep track of index offsets to keep it in $\mathcal{O}(1)$).

If you can't make that assumption, them my approach will leave you with $\mathcal{O}(\log n)$ insert, rebalance, and extract. It does have an advantage over some other approaches though, in that you can get min/max and anywhere in-between—e.g.: give me the median value—in $\mathcal{O}(1)$. Additionally it does have `delete_at(idx)` functionality.

---

Patrascu, Mihai, and Erik D. Demaine. “Logarithmic Lower Bounds in the Cell-Probe Model.” SIAM J. Comput. 35, no. 4 (April 2006): 932–963. doi:10.1137/S0097539705447256.

# Answer
> 2 votes
A soft heap is a subtle modification of a binomial queue. The data structure is approximate with an error parameter $\epsilon$. It supports insert, delete, meld and findmin. The *amortized* complexity of each operation is $O(1)$, except for insert which takes $\log (1/\epsilon)$ time. The novelty of the soft heap is in beating the logarithmic bound on the complexity of a heap in the comparison-based model. In order to break the information theoretic barrier, the entropy of the data structure is reduced by artificially raising the values of some keys. This is called *corrupting* the keys. The data structure is fully pointer-based (no arrays nor numeric assumptions) and is optimal for any value of $\epsilon$ in the comparison-based model.

The applications of the soft heap include computing the minimum spanning tree for a graph, dynamically maintaining percentiles and linear time order statistics. It can be also used for approximate computation, such as approximate sorting where the rank of an element never differs by more than $\epsilon n$ from the true rank.

For the original, clear and nicely written paper, see Bernard Chazelle, The Soft Heap: An Approximate Priority Queue with Optimal Error Rate, Journal of the ACM, 47(6), pp. 1012-1027, 2000. For alternative implementation and analysis that claims to be simpler and more intuitive from SODA'09, see Kaplan H. & Zwick U., A simpler implementation and analysis of Chazelle's soft heaps, 2009.

# Answer
> -2 votes
Find-min in $O(1)$ with expected update time of $O(\sqrt{log\text{ }log\text{ }n})$

See the 2007 paper: Equivalence between priority queues and sorting by Mikkel Thorup.

Note: He refers to the 2002 article by Han & Thorup: Integer Sorting in $O(n\text{ }\sqrt{log\text{ }log\text{ }n})$ Expected Time and Linear Space.

# Answer
> -2 votes
## Analysis

**Insert**: $\mathcal{o}(n\ log\ log\ n)$

**Search**: $\mathcal{o}(log\ log\ n)$

**Delete**: $\mathcal{O}(1)$

**Space**: $\mathcal{O}(n)$

**Get-Min**: $\mathcal{O}(1)$

**Extract-Min**: $\mathcal{O}(1)$

## Implementation

1. Form a list out of an arbitrary (constant) number of elements, lets say 6: $\mathcal{O}(1)$
2. Sort the list: $\mathcal{O}(6)$=$\mathcal{O}(1)$
3. The insertion point for every subsequent node $k$, will be the second elements(') pos $\pm$ (-1 for \<, +1 for \> and with two args depends on which you start/finish at: $$((k \> n\_{\text{size}-1}) \lor (k\<n\_{0}) \lor ((k\<n\_{i}) \land (k\>n\_{i+1})))$$ and will be found using *Dynamic Interpolation Search*\[1\] in: $\mathcal{o}(log\ log\ n)$

\[1\]: Andersson, Arne, and Christer Mattsson. ‘Dynamic Interpolation Search in O(log log n) Time’. In Automata, Languages and Programming, edited by Andrzej Lingas, Rolf Karlsson, and Svante Carlsson, 700:15–27. Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-56939-1\_58.

---
Tags: data-structures, amortized-analysis, priority-queues
---


title: Counting certificates for a language

text:
# Question
Title: Counting certificates for a language
Let $M\_{1}$ and $M\_{2}$ be two (non-deterministic) turing machines accepting the language $L \subseteq \Sigma^{\ast}$.

Is is right to claim that:

$\\#M\_{1} \in \textbf{#C}$ *if and only if* $\\#M\_{2} \in \textbf{#C}$ ?

where $\textbf{#C}$ is a counting complexity class, that is closed under reductions (such as $\textbf{#P}$, $\textbf{#P-Hard}$, $\textbf{GapP}$, $\textbf{GapP-Hard}$, $\textbf{PP}$, etc).

If so, can we use the notation "$\\#L \in \textbf{#C}$" ?

# Answer
> 5 votes
Take the language to be $L=\Sigma^\*$. $L$ can be solved trivially, so there is a polytime NTM that doesn't use any nondeterminism and solves $L$, call it $M$. The counting function for $M$ is $\\#M(x)=1$ which is trivial.

Take $N$ be the following polytime NTM:

$N :=$ on input $x$,
1. nondeterministicly guess $b\in\\{0,1\\}$,
2. nondeterministicly guess an assignment $\tau$ for $x$,
3. if $b=0$,accept,
4. if $b=1$ and $\tau$ satisfies $x$, accept.
5. otherwise reject.

It is easy to see that $L(N) = L = L(M)$. However $\\#N(x)=2^{numvar(x)}+\\#SAT(x)$ which is essentially $\\#SAT$ and is complete for $\\#P$.

$numvar(x)$ denotes the number of propositional variables in $x$.

Therefore the notation $\\#L$ is not well-defined (even if we assume $L \in \mathsf{NP}$). You have to fix a NTM $M$ first for $L$ and then talk about $\\#M$. Depending on the NTMs you choose for $L$ you will get different counting languages.

In some cases like $SAT$, the intended NTM for the language is clear from context. In such cases, we may use the notation $\\#L$ to mean $\\#M$ where $M$ is the intended NTM for $L$. Note that even in those cases we are still fixing an NTM for $L$, we just don't state that explicitly.

---
Tags: complexity-theory
---


# Question
Title: distinction between $\textbf{P}^{\# \textbf{P}}$ and $\# \textbf{P}$-Complete
We know that $\\# \textbf{P}$ is closed under polynomial sums, i.e., sum of polynomially many $\\# \textbf{P}$ functions is still in $\\# \textbf{P}$.

Functions in $\textbf{P}^{\\# \textbf{P}}$ are those which make polynomially many (non-parallel) queries to an oracle for a $\\# \textbf{P}$-Complete problem. So, the computational complexity of such problems must be a sum of polynomially many $\\# \textbf{P}$ functions. Due to the closure property, this sum will be in $\\# \textbf{P}$.

If the above is right, then: What is the difference between the classes $\\# \textbf{P}$-Complete and $P^{\\# \textbf{P}}$ ?

Thanks.

# Answer
First they are different kind of problems. One is a class of decision problems, the other one is a class of function problems. So lets interpret the question as $\mathsf{FP^{\\#P}}$ vs. $\mathsf{\\#P\text{-}complete}$.

Second, the kind of reductions used for completeness are not simple polynomial time Turing reductions, see the definition of #P-complete.

A polynomial time TM with access to a $\mathsf{\\#P}$ problem might be able to do things that a $\mathsf{\\#P}$ machine cannot do. For example, it can check if a $\Sigma^p\_2$ formula is satisfiable and output $1$ if it is and $0$ if it is not.
> 3 votes

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


# Question
Title: Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is?
I am not sure I see it. From what I understand, edges and vertices are complements for each other and it is quite surprising that this difference exists.

Is there a good / quick / easy way to see that in fact finding a Hamiltonian path should be much harder than finding a Euler path?

# Answer
Maybe the following perspective helps:

When you are trying to construct a Eulerian path, you can proceed almost greedily. You just start the path somewhere and the try to walk as long as possible. If you detect a circle, you will delete its edges (but record that this circle was constructed). By this you decompose the graph in circles, which can be easily combined to an Eulerian tour. The point is, none of your decision "how to walk across the graph" can actually be wrong. You will always succeed and never get stuck.

The situation with Hamiltonian paths is different. Again, you might want to construct a path by walking along edges of the graph. But this time you can really make *bad* decisions. This means you cannot continue the path, but not all vertices have been visited. What you can do is back-track. That means you revert some of your old decisions and continue along a different path. Essentially all algorithms that are known for the general problem rely on some way or the other on back-tracking, or trying out a large set of solutions. This, however, is characteristic for NP-complete problems.

So (simplified) bottom-line: Eulerian path requires no back-tracking, but Hamiltonian path does.

(Notice that it might be that P=NP and in this case a *clever* Hamiltonian path algorithm would exist.)
> 12 votes

# Answer
Another detail that may help your intuition is that an Euler cycle exists if and only if each vertex has even degree. A similar theorem exists for Euler paths. This follows from a fairly straightforward proof--basically, every time you visit a vertex, you must then leave it, so each "visit" takes two from the degree of the vertex. This doesn't explain why Hamiltonian path is difficult (which, of course, we don't even actually know), but it does help to explain why finding an Euler path is easy.

Victor Adamchik gives an OK explanation of the proof. Most graph theory/discrete math books will likely have a proof as well which you may find easier.

The other answers give some good intuition why such a simple proof doesn't seem to work for Hamilton cycles.
> 5 votes

# Answer
> "Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is?"

The assumptions in your question are not correct.

Note that **we don't know** that $\mathrm{HamPath}$ is not in $\mathsf{P}$! Someone someday might find a very clever characterization of $\mathrm{HamPath}$ (similar to the characterization of $\mathrm{EulerPath}$ as having even degrees) which would put it inside $\mathsf{P}$.

Most people **believe** that it is not in $\mathsf{P}$ but it is not proven. The arguments (not proof!) for why it is unlikely to be in $\mathsf{P}$ is the same as the arguments for $\mathsf{P} \neq \mathsf{NP}$ and most of them don't say much about $\mathrm{HamPath}$ itself other than the fact that it is $\mathsf{NP\text{-}complete}$.

Now, you may ask why $\mathrm{HamPath}$ is $\mathsf{NP\text{-}complete}$ but we can't show that $\mathsf{EulerPath}$ is $\mathsf{NP\text{-}complete}$? Because someone has find a characterization of it which is in $\mathsf{P}$ and then answer would be similar to why we believe that $\mathsf{P} \neq \mathsf{NP}$ so it is unlikely (but not proven!) that $\mathsf{EulerPath}$ is $\mathsf{NP\text{-}complete}$.
> 2 votes

# Answer
Here's one quick way of looking at it. The HAM-PATH problem is $\mathsf{NP}$-complete, so currently we do not if it can be solved in polynomial time or not. At least nobody has come up with such an algorithm. The Eulerian path problem on the other hand is provably in $\mathsf{P}$ since we have polynomial time algorithms for it. An $\mathsf{NP}$-complete problem such as HAM-PATH has resisted attacks so far, so this is one immediate way of seeing or believing it is harder than a problem in $\mathsf{P}$, say finding an Eulerian path.
> 0 votes

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


# Question
Title: Existence of a route following one-way streets
I am trying to understand the approach for this problem:

> "If all streets are one way, there is still a legal way to drive from one intersection to another"

The question is to prove that it can be done in linear time. I am not looking for direct answers but the approach to this problem.

How can I think about this problem in terms of graph theory? AFAI understand, this will result in a DAG. But then should I choose BFS or DFS and why to prove it? (both are liner time algos)

# Answer
First, it definitely won't result in a DAG, just a digraph. You need to get from A to B and B to A in order to satisfy your condition for nodes A and B, but that itself is a cycle.

Lots of time BFS and DFS are equivalent in relation to a problem, so it doesn't matter which one you choose. Here, the real trick is not choosing between DFS and BFS, but dealing with the fact that the graph is directed.

If you don't want a direct answer, here's the strategy I would use: first find a representation for the streets in terms of a digraph. What corresponds to edges? What corresponds to nodes?

Then, you need to find a graph algorithm that will work for this problem. What information do BFS and DFS give you about the graph? How can they be adapted to a directed graph?

To give you a little hint, I'd recommend you Google Eulerian chains.
> 1 votes

# Answer
As a hint, think about the intersections as nodes and the streets as directed edges connecting intersections. Then, try thinking about the following: find all clusters of nodes that are mutually reachable from one another (such nodes are said to be strongly-connected.

Hope this helps!
> 0 votes

---
Tags: algorithms, graphs, algorithm-analysis
---


# Question
Title: Notation for operational semantics that can be used in code comments
I'm defining an intermediate language for a multi-backend code generator that I'm writing. I want to document the operational semantics for this intermediate language in a way that is readable both from within the source code and generated documentation (ocamldoc). The notation introduced used in "Types and Programming" languages is great for a book, but I don't want to try to do the prerequisite over conclusion style notation via ASCII art.

Is there a widely recognized notation for operational semantics that doesn't require non-ASCII characters? I looked through various RFCs but can't find any that use a non-natural language way of specifying semantics.

# Answer
> 8 votes
The input format for the tool OTT is based on ASCII and the rules look very much like type system/operational semantics rules. Maybe you could use that format. I'm sure that the parser for the input format is available as open source.

---
Tags: programming-languages, semantics, types-and-programming-languages, operational-semantics
---


# Question
Title: Why does NTIME consider the length of the longest computation?
In Sipser's textbook "Introduction to the Theory of Computation, Second Edition," he defines nondeterministic time complexity as follows:

> Let $N$ be a nondeterministic Turing machine that is a decider. The **running time** of $N$ is the function $f : \mathbb{N} \rightarrow \mathbb{N}$, where $f(n)$ is the maximum number of steps that $N$ uses on any branch of its computation on any input of length $n$ \[...\].

Part of this definition says that the running time of the machine $N$ is the maximum number of steps taken by that machine on any branch. Is there a reason that all branches are considered? It seems like the length of the shortest accepting computation would be a better measure (assuming, of course, that the machine halts), since you would never need to run the machine any longer than this before you could conclude whether the machine was going to accept or not.

# Answer
> 6 votes
Because you don't know ahead of time whether or not any given input is a 'yes' instance — that is, whether there exists *any* accepting path — it makes sense for the sake of uniformity to bound the run-time independently of any particular feature of the computational paths. Thus, it makes sense to require the worst-case behaviour to be polynomial time, regardless of whether or not any accepting paths exist.

# Answer
> 3 votes
Ah, but you don't know that the machine will select the shortest accepting path. All nondeterminism gives you is that the machine will select *some* accepting path, if at least one exists. So in the worst case it selects the longest.

# Answer
> 2 votes
The machine in this definition is a *decider*, that means it does halt on all inputs and accepts if and only if the input is in its language. That means that the maximum lengths of all computation makes sense, and should be the measure investigated.

You are probably thinking of *acceptors*. Those are Turing machines that halt and accept on inputs in the language, and do anything (but halt and accept) on inputs outside of the language. In particular, they can never terminate; some definitions even demand (equivalently) that acceptors loop when they don't accept. In this case, runtime does only make sense for positive inputs, but you still have to choose the longest one.

You could, of course, discuss to empower nondeterminism to not only choose a path towards acceptance, but also a shortest one. The standard notion does not include this, however, so the machine might take the longest path.

---
Tags: complexity-theory, time-complexity, terminology, turing-machines, nondeterminism
---


title: Bound on space for selection algorithm?

text:
# Question
Title: Bound on space for selection algorithm?
There is a well known worst case $O(n)$ selection algorithm to find the $k$'th largest element in an array of integers. It uses a median-of-medians approach to find a good enough pivot, partitions the input array in place and then recursively continues in it's search for the $k$'th largest element.

What if we weren't allowed to touch the input array, how much extra space would be needed in order to find the $k$'th largest element in $O(n)$ time? Could we find the $k$'th largest element in $O(1)$ extra space and still keep the runtime $O(n)$? For example, finding the maximum or minimum element takes $O(n)$ time and $O(1)$ space.

Intuitively, I cannot imagine that we could do better than $O(n)$ space but is there a proof of this?

Can someone point to a reference or come up with an argument why the $\lfloor n/2 \rfloor$'th element would require $O(n)$ space to be found in $O(n)$ time?

# Answer
It is an open problem if you can do selection with $O(n)$ time and $O(1)$ extra memory cells without changing the input (see here). But you can come pretty close to this.

Munro and Raman proposed an algorithm for selection that runs in $O(n^{1+\varepsilon})$ time while using only $O(1/\varepsilon)$ extra storage (cells). This algorithm leaves the input unchanged. You can pick any small $\varepsilon\>0$.

At its core, Munro and Raman's algorithm works as the classical $O(n)$ algorithm: It maintains a *left* and *right* bound (called *filter*), which are two elements with known rank. The requested element is contained between the two filters (rank-wise). By picking a good pivot element $p$ we can check all numbers against the filters and $p$. This makes it possible to update the filters and decreases the number of elements left to check (rank-wise). We repeat until we have found the request element.

What is different to the classical algorithm is the choice of $p$. Let $A(k)$ be the algorithm that solves selection for $\varepsilon=1/k$. The algorithm $A(k)$ divides the array in equally-sized blocks and identifies a block where many elements are, whose ranks are in between the filters (existence by pigeon-hole principle). This block will then be scanned for a good pivot element with help of the algorithm $A(k-1)$. The recursion anchor is the trivial $A(1)$ algorithm. The right block size (and doing the math) gives you running time and space requirements as stated above.

Btw, the algorithms you are looking for, were recently named *constant-work-space algorithms*.

I am not aware of any lower bound.
> 13 votes

---
Tags: algorithms, algorithm-analysis, space-complexity, lower-bounds
---