# Question
Title: What goes wrong with sums of Landau terms?
I wrote

$\qquad \displaystyle \sum\limits\_{i=1}^n \frac{1}{i} = \sum\limits\_{i=1}^n \cal{O}(1) = \cal{O}(n)$

but my friend says this is wrong. From the TCS cheat sheet I know that the sum is also called $H\_n$ which has logarithmic growth in $n$. So my bound is not very sharp, but is sufficient for the analysis I needed it for.

What did I do wrong?

**Edit**: My friend says that with the same reasoning, we can prove that

$\qquad \displaystyle \sum\limits\_{i=1}^n i = \sum\limits\_{i=1}^n \cal{O}(1) = \cal{O}(n)$

Now this is obviously wrong! What is going on here?

# Answer
What you are doing is a very convenient abuse of notation.

Some pedants will say that what you write is nonsense, as $\mathcal{O}(f)$ denotes a *set* and you cannot do arithmetic operations on them the way you are doing.

But it is a good idea to ignore those pedants and assume that $\mathcal{O}(f)$ stands for *some* member of the set. So when we say $f(n) = g(n) + \mathcal{O}(n)$, what we really mean if that $f(n) - g(n) \in \mathcal{O}(n)$. (Note: some pedants might shudder at this statement too, claiming that $f(n)$ is a number and $f$ is the function!)

This makes it very convenient to write expressions like

$$ n \le \sum\_{k=1}^n k^{1/k} \le n + \mathcal{O}(n^{1/3})$$

What this means is that there is some $f \in \mathcal{O}(n^{1/3})$ such that

$$ n \le \sum\_{k=1}^n k^{1/k} \le n + f(n)$$

In your case of

$$\sum\_{k=1}^{n} \frac{1}{k} = \sum\_{k=1}^{n} \mathcal{O}(1) = \mathcal{O}(n)$$

you are abusing it even further and you need to be careful.

There are two possible interpretations here: Does the $\mathcal{O}(1)$ refer to a function of $n$, or a function of $k$?

I believe the right interpretation is to interpret it as a function of $k$.

If you try thinking of it as a function of $n$, thought not incorrect, it might lead to potential fallacies, like thinking $k$ is $\mathcal{O}(1)$ and trying to write $\sum\_{k=1}^{n} k = \sum\_{k=1}^{n} \mathcal{O}(1)$

If you try thinking of it as a function of $k$, then it is true that, if $f = \mathcal{O}(g)$ (as the argument goes to $\infty$) and $g$ is never $0$, that

$$ S(n) = \sum\_{k=1}^{n} f(k) = \sum\_{k=1}^{n} \mathcal{O}(g(k)) = \mathcal{O}(\sum\_{k=1}^{n} |g(k)|)$$

Note that in the middle, we have used the convenient abuse of notation $\mathcal{O}(g(k))$ to mean that for some function $h \in \mathcal{O}(g)$ the sum is $\sum\_{k=1}^{n} h(k)$. Note that the final function inside the $\mathcal{O}$ refers to a function of $n$. The proof is not that difficult, but you have to cater to the fact that you are dealing with an asymptotic upper bound (i.e. for sufficiently large arguments), but the sum starts right at $1$.

If you try thinking of it as a function of $n$, then it is also true that if $f = \mathcal{O}(g)$ (as the argument goes to $\infty$) then

$$ S(n) = \sum\_{k=1}^{n} f(k) = \sum\_{k=1}^{n} \mathcal{O}(g(n)) = \mathcal{O}(n g(n))$$

So your proof is essentially correct, in either interpretation.
> 10 votes

# Answer
What you wrote is perfectly correct. The $n$th harmonic number is indeed in the set $O(n)$.

*Proof:* $\sum\_{i=1}^n \frac{1}{i} \le \ln n + 1 \le 2n = O(n)$. $\square$

The upper bound $O(n)$ isn't *tight*, but it's correct.
> 8 votes

# Answer
For the second example, you can't claim that $$i = O(1)$$

since $i$ varies with $n$. After few steps it will be the case that $i\>n/2$. A more appropriate way is to say that $i = O(n)$ since indeed, throughout the summation $i$ never exceeds $1\cdot n$. By this reasoning, $$\sum\_{i=1}^n i = \sum\_{i=1}^n O(n)= nO(n) = O(n^2)$$

However the right thing to do is actually use the big-O notation only at the end. Upper bound your summation as tight as you can, and only when your done use the asymptotic notations to avoid these pitfalls.
> 6 votes

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


# Question
Title: Computational power of deterministic versus nondeterministic min-heap automata
*This is a follow-up question of this one.*

In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show that the set of languages accepted by such machines ($HAL$) is neither a subset nor a superset of the set of context-free languages. Given the successful resolution of and apparent interest in that question, I proceed to ask several follow-up questions.

It is known that deterministic and nondeterministic finite automata have equivalent computational capabilities, as do deterministic and nondeterministic Turing machines. However, the computational capabilities of deterministic push-down automata are less than those of nondeterministic push-down automata.

> Are the computational capabilities of deterministic min-heap automata less than, or are they equal to, those of nondeterministic min-heap automata?

# Answer
> 3 votes
It seems that for this model, non-deterministic machines are not equivalent to deterministic ones, for basically the same reason that deterministic PDAs are not equivalent to non-deterministic ones.

Consider the language $$L =\\\{ x\\$y \mid |x|=|y| \wedge x\ne y\\\}$$ (where $\\$$ is a special sign not contained in $x$ and $y$).

I claim that a non-deterministic machine $N$-$HAL$ can decide this language: It performs the same as the PDA for $L$. The standard PDA solution uses the stack only to count offsets: it nondeterministically guesses an offset $i$, remembers the value of $x\_i$ (adding a symbol to the stack at each step), then the PDA ignores the input until it find the $\\$$, and then it pops symbols out of the stack until it is empty. At this stage we are exactly at $y\_i$ and he PDA can check if $x\_i \ne y\_i$. (if anything goes wrong in the middle, the PDA "dies"). Since the stack alphabet is unary, it can be simulated with a min-heap machine. Actually: any $L$ that is is accepted by a PDA with a unary alphabet can be accepted by a min-heap machine. (I'm ignoring, maybe, another special sign added to identify an empty stack, but an equivalent sign can be added to the heap)

For the other direction, I don't have the formal proof, but here are my thoughts:

I claim that a deterministic machine $D$-$HAL$ is incapable of deciding this language. Intuitively, the content of the heap can not be correlated with $x$ (otherwise, permute $x$. the content of the heap remains the same..). This suggests that only thing that matters is the number of elements in the heap, but then, if $D$-$HAL$ can decide $L$, so can a deterministic-$PDA$.

**Edit:** more details about the "permute $x$" claim. Assuming Raphael's conjecture there exist $x\_1$ and $x\_2$ that after reading them, the content of the heap is the same. Then consider the words $x\_1\\$x\_1$ and $x\_2\\$x\_1$. The content of the heap is the same when the HAL gets to the dollar sign, thus it must either accept both or reject both. **contradiction**.

anyone sees an immediate proof for the conjecture?

---
Tags: formal-languages, automata, nondeterminism
---


# Question
Title: Efficient compression of unlabeled trees
Consider unlabeled, rooted binary trees. We can *compress* such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $T$ and replace all pointers to $T'$ with pointers to $T$. See uli's answer for an example.

Give an algorithm that takes a tree in the above sense as input and computes the (minimal) number of nodes that remain after compression. The algorithm should run in time $\cal{O}(n\log n)$ (in the uniform cost model) with $n$ the number of nodes in the input.

This has been an exam question and I have not been able to come up with a nice solution, nor have I seen one.

# Answer
Yes, you can perform this compression in $O(n \log n)$ time, but it is not easy :) We first make some observations and then present the algorithm. We assume the tree is initially not compressed - this is not really needed but makes analysis easier.

Firstly, we characterize 'structural equality' inductively. Let $T$ and $T'$ be two (sub)trees. If $T$ and $T'$ are both the null trees (having no vertices at all), they are structurally equivalent. If $T$ and $T'$ are both not null trees, then they are structurally equivalent iff their left children are structurally equivalent and their right children are structurally equivalent. 'Structural equivalence' is the minimal fixed point over these definitions.

For example, any two leaf nodes are structurally equivalent, as they both have the null trees as both their children, which are structurally equivalent.

As it is rather annoying to say 'their left children are structurally equivalent and so are their right children', we will often say 'their children are structurally equivalent' and intend the same. Also note we sometimes say 'this vertex' when we mean 'the subtree rooted at this vertex'.

The above definition immediately gives us a hint how to perform the compression: if we know the structural equivalence of all subtrees with depth at most $d$, then we can easily compute the structural equivalence of the subtrees with depth $d+1$. We do have to do this computation in a smart way to avoid a $O(n^2)$ running time.

The algorithm will assign identifiers to every vertex during its execution. An identifier is a number in the set $\\{ 1, 2, 3, \dots, n \\}$. Identifiers are unique and never change: we therefore assume we set some (global) variable to 1 at the start of the algorithm, and every time we assign an identifier to some vertex, we assign the current value of that variable to the vertex and increment the value of that variable.

We first transform the input tree into (at most $n$) lists containing vertices of equal depth, together with a pointer to their parent. This is easily done in $O(n)$ time.

We first compress all the leaves (we can find these leaves in the list with vertices of depth 0) into a single vertex. We assign this vertex an identifier. Compression of two vertices is done by redirecting the parent of either vertex to point to the other vertex instead.

We make two observations: firstly, any vertex has children of strictly smaller depth, and secondly, if we have performed compression on all vertices of depth smaller than $d$ (and have given them identifiers), then two vertices of depth $d$ are structurally equivalent and can be compressed iff the identifiers of their children coincide. This last observation follows from the following argument: two vertices are structurally equivalent iff their children are structurally equivalent, and after compression this means their pointers are pointing to the same children, which in turn means the identifiers of their children are equal.

We iterate through all the lists with nodes of equal depth from small depth to large depth. For every level we create a list of integer pairs, where every pair corresponds to the identifiers of the children of some vertex on that level. We have that two vertices in that level are structurally equivalent iff their corresponding integer pairs are equal. Using lexicographic ordering, we can sort these and obtain the sets of integer pairs that are equal. We compress these sets to single vertices as above and give them identifiers.

The above observations prove that this approach works and results in the compressed tree. The total running time is $O(n)$ plus the time needed to sort the lists we create. As the total number of integer pairs we create is $n$, this gives us that the total running time is $O(n \log n)$, as required. Counting how many nodes we have left at the end of the procedure is trivial (just look at how many identifiers we have handed out).
> 10 votes

# Answer
Compressing a non-mutable data structure so that it does not duplicate any structurally equal subterm is known as **hash consing**. This is an important technique in memory management in functional programming. Hash consing is a sort of systematic memoization for data structures.

We're going to hash-cons the tree and count the nodes after hash consing. Hash consing a data structure of size $n$ can always be done in $O(n\\:\mathrm{lg}(n))$ operations; counting the number of nodes at the end is linear in the number of nodes.

I will consider trees as having the following structure (written here in Haskell syntax):

```
data Tree = Leaf
          | Node Tree Tree

```

For each constructor, we need to maintain a mapping from its possible arguments to the result of applying the constructor to these arguments. Leaves are trivial. For nodes, we maintain a finite partial map $\mathtt{nodes} : T \times T \to N$ where $T$ is the set of tree identifiers and $N$ is the set of node identifiers; $T = N \uplus \\{\ell\\}$ where $\ell$ is the sole leaf identifier. (In concrete terms, an identifier is a pointer to a memory block.)

We can use a logarithmic-time data structure for `nodes`, such as a balanced binary search tree. Below I'll call `lookup nodes` the operation that looks up a key in the `nodes` data structure, and `insert nodes` the operation that adds a value under a fresh key and returns that key.

Now we traverse the tree and add the nodes as we go along. Although I'm writing in Haskell-like pseudocode, I'll treat `nodes` as a global mutable variable; we'll only ever be adding to it, but the insertions need to be threaded throughout. The `add` function recurses on a tree, adding its subtrees to the `nodes` map, and returns the identifier of the root.

```
insert (p1,p2) =
add Leaf = $\ell$
add (Node t1 t2) =
    let p1 = add t1
    let p2 = add t2
    case lookup nodes (p1,p2) of
      Nothing -> insert nodes (p1,p2)
      Just p -> p

```

The number of `insert` calls, which is also the final size of the `nodes` data structure, is the number of nodes after maximum compression. (Add one for the empty tree if needed.)
> 4 votes

# Answer
Here is another idea that aims at (injectively) encoding the structure of trees into numbers, rather than just labelling them arbitrarily. For that, we use that any number's prime factorisation is unique.

For our purposes, let $E$ denote an empty position in the tree, and $N(l,r)$ a node with left subtree $l$ and right subtree $r$. $N(E,E)$ would be a leaf. Now, let

$\qquad \displaystyle \begin{align\*} f(E) &= 0 \\ f(N(l,r)) &= 2^{f(l)}\cdot 3^{f(r)} \end{align\*}$

Using $f$, we can compute the set of all subtrees contained in a tree bottom-up; in every node, we merge the sets of encodings obtained from the children and add a new number (which can be computed in constant time from the children's encodings).

This last assumption is a stretch on real machines; in this case, one would prefer to use something similar to Cantor's pairing function instead of exponentiation.

The runtime of this algorithm depends on the structure of the tree (on balanced trees, $\cal{O}(n \log n)$ with any set implementation that allows union in linear time). For general trees, we would need logarithmic time union with a simple analysis. Maybe a sophisticated analysis can help, though; note that the usual worst-case tree, the linear list, admits $\cal{O}(n \log n)$ time here, so it is not so clear what the worst-case may be.
> 3 votes

# Answer
As pictures are not allowed in comments:

top left: an input tree

top right: the subtrees rooted in nodes 5 and 7 are isomorphic too.

lower left and right: the compressed trees are not uniquely defined.

Note that in this case the size of the tree has gone down from $7+5|T|$ too $6+|T|$.
> 1 votes

# Answer
Edit: I read the question as T and T′ were children of the same parent. I took the definition of compression to be recursive as well, meaning you could compress two previously compressed subtrees. If that's not the actual question, then my answer may not work.

$O(n \log n)$ begs for a $T(n) = 2T(n/2) + cn$ divide and conquer solution. Recursively compress nodes and compute the number of descendants in each subtree after compression. Here's some python-esque pseudo code.

```
def Comp(T):
   if T == null:
     return 0
   leftCount = Comp(T.left)
   rightCount = Comp(T.right)
   if leftCount == rightCount:
     if hasSameStructure(T.left, T.right):
       T.right = T.left
       return leftCount + 1
     else
       return leftCount + rightCount + 1

```

Where `hasSameStructure()` is a function that compares two already compressed subtrees in linear time to see if they have the exact same structure. Writing a linear time recursive function that traverses each and checks if the one subtree has a left child every time the other one does etc. shouldn't be hard.

Let $n\_\ell$ and $n\_r$ be the sizes of the left and right subtrees respectively (after compression). Then the running time is $$ T(n) = T(n\_1) + T(n\_2) + O(1) \mbox{ if $n\_\ell \neq n\_r$} $$ and $$ 2T(n/2) + O(n) \mbox{ otherwise} $$
> -1 votes

---
Tags: algorithms, data-structures, trees, binary-trees
---


# Question
Title: Proving closure under complementation of languages accepted by min-heap automata
*This is a follow-up question of this one*.

In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show that the set of languages accepted by such machines ($HAL$) is neither a subset nor a superset of the set of context-free languages. Given the successful resolution of and apparent interest in that question, I proceed to ask several follow-up questions.

It is known that the regular languages are closed under a variety of operations (we may limit ourselves to basic operations such as union, intersection, complement, difference, concatenation, Kleene star, and reversal), whereas the context-free languages have different closure properties (these are closed under union, concatenation, Kleene star, and reversal).

> Is HAL closed under complementation?

# Answer
> 4 votes
**Claim**: $\mathrm{HAL}$ is *not* closed against complement.

**Proof Idea**: We have agreed that $\mathrm{EPAL}$ (the language of even palindromes over a non-unary alphabet) is not in $\mathrm{HAL}$. We show that $\overline{\mathrm{EPAL}} \in \mathrm{HAL}$.
*This works for type-1 only (as type-2 can accept $\mathrm{EPAL}$); the proof can be adapted to suit type-2 though, see below.*

**Proof**: Note that

$\qquad \displaystyle \begin{align\*} \overline{\mathrm{EPAL}} &= \\{vw : |v|=|w|, v\neq w^R\\} \\ &\cup\ \\,\\{w : |w| \in 2\mathbb{N}\\!+\\!1\\} \end{align\*}$

We construct a min-heap automaton with two heap symbols $b \< a$ that works like this:

* In the starting state, decide nondeterministically wether the input's length is even.
* On the uneven path, use finite control to accept the input if and only if its length is odd.
* On the even path, proceed like this: $$ \underbrace{v\_1\ \dots\ \mathbf{v\_{i}}}\_{+a}\ \underbrace{v\_{i+1}\ \dots\ v\_n}\_{+b}\ \underbrace{w\_n\ \dots\ w\_{i+1}}\_{-b}\ \underbrace{\mathbf{w\_i}\ \dots\ w\_1}\_{-a}$$
    + Start by adding one $a$ to heap for every read symbol.
    + At a nondeterministically determined position, store the current symbol in finite control and start adding one $b$ (and no $a$) to heap for every read symbol.
    + At a nondeterministically determined position, stop adding symbols and consume one $b$ per input symbol.
    + When all $b$ are consumed, compare the current symbol with the one stored in control. If they are unequal, continue; else reject the input.
    + Consume one $a$ per input symbol. If the heap is empty at the same time the input ends, accept the word; reject otherwise.

The described min-heap automaton accepts $\overline{\mathrm{EPAL}}$. As its complement, $\mathrm{EPAL}$, is not in $\mathrm{HAL}$, we have proven the claim.

*Note:* The proof can be performed in the same way with $\\{ww \mid w \in \\{a,b\\}^\*\\}$ (which is in $\mathrm{CSL} \setminus \mathrm{HAL}$) and its complement. This extends above result to type-2.

---
Tags: formal-languages, automata, closure-properties
---


title: AVL trees are not weight-balanced?

text:
# Question
Title: AVL trees are not weight-balanced?
In a previous question there was a definition of weight balanced trees and a question regarding red-black trees.

This question is to ask the same question, but for AVL trees.

The question is, given the definition of $\mu$-balanced trees as in the other question,

> Is there some $\mu \gt 0$ such that all big enough AVL trees are $\mu$-balanced?

I presume there is only one definition of AVL trees and there is no ambiguity.

# Answer
> 18 votes
**Claim**: No, there is no such $\mu$.

**Proof**: We give an infinite sequence of AVL trees of growing size whose weight-balance value tends to $0$, contradicting the claim.

Let $C\_h$ the complete tree of height $h$; it has $2^{h+1}-1$ nodes.

Let $S\_h$ the *Fibonacci tree* of height $h$; it has $F\_{h+2} - 1$ nodes. \[,,TAoCP 3\]

Now let $(T\_h)\_{i\geq 1}$ with $T\_h = N(S\_h,C\_h)$ the sequence of trees we claim to be a counter example.

Consider the weight-balancing value of the root of $T\_h$ for some $h \in \mathbb{N}\_+$:

$\qquad \displaystyle \begin{align\*} \frac{F\_{h+2}}{2^{h+1} + F\_{h+2} - 1} &= \frac{1}{1 + \frac{2^{h+1}}{F\_{h+2}} - \frac{1}{F\_{h+2}{}}} \\ &\sim \frac{F\_{h+2}}{2^{h+1}} \\ &= \frac{\frac{1}{\sqrt{5}}(\phi^{h+2} - \hat{\phi}^{h+2})}{2^{h+1}} \\ &\sim \frac{\phi^{h+2}}{\sqrt{5}\cdot 2^{h+1}} \underset{h \to \infty}{\to} 0 \end{align\*}$

This concludes the proof.

*Notation*:

* $F\_n$ is the $n$th Fibonacci number
* $\phi \approx 1.6$ is the Golden Ratio, $\hat{\phi} \approx -0.62$ its conjugate.
* $f \sim g$ means that $f$ and $g$ are asymptotically equal, i.e. $\lim\_{n \to \infty} \frac{f(n)}{g(n)} = 1$.

*Nota bene*: Fibonacci trees are exactly those AVL trees with the least nodes for a given height (or, equivalently, the maximum height for a given number of nodes).

*Addendum*: How can we come up with Fibonacci trees if we had not overheard a professor mentioning them? Well, what would an AVL tree of height $h$ with as few nodes as possible look like? Certainly, you need a root. One of the subtrees needs to have height $h-1$, and we have to choose it with as few nodes as possible. The other one can have height $h-2$ without violating the height balancing condition, and we choose it also with as few nodes as possible. In essence, we construct the trees we want recursively! These are the first four:

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

We set up a recurrence for the number of nodes $f(h)$ in the thusly constructed tree with height $h$:

$\qquad \displaystyle \begin{align\*} f(1) &= 1 \\ f(2) &= 2 \\ f(h) &= f(h-1) + f(h-2) + 1 \qquad n \geq 3 \end{align\*}$

Solving it leads to $f(h) = F\_{h+2} - 1$ which we used above.

---

The same proof is given (with less detail) in Binary search trees of bounded balance by Nievergelt and Reingold (1972).

---
Tags: data-structures, binary-trees, search-trees, balanced-search-trees, avl-trees
---


title: How to find a superstar in linear time?

text:
# Question
Title: How to find a superstar in linear time?
Consider directed graphs. We call a node $v$ *superstar* if and only if no other node can be reached from it, but all other nodes have an edge to $v$. Formally:

$\qquad \displaystyle $v$ \text{ superstar } :\Longleftrightarrow \mathrm{outdeg}(v) = 0 \land \mathrm{indeg}(v) = n-1$

with $n$ the number of nodes in the graph. For example, in the below graph, the unfilled node is a superstar (and the other nodes are not).

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

How can you identify all superstars in a directed graphs in $\mathcal{O}(n)$ time? A suitable graph representation can be chosen from the usual candidates; please refrain from using representations that move the problem's complexity to preprocessing.

No assumptions regarding density can be made. We don't assume the graph contains a superstar; if there is none, the algorithm should recognize it.

*Notation*: $\mathrm{outdeg}$ is a node's number of outgoing edges, $\mathrm{indeg}$ similar for incoming edges.

# Answer
> 19 votes
We can eliminate all but one of the vertices by checking for the existence of $n-1$ edges because we can eliminate one possibility for each edge we check. In particular, if there is an edge going from $x$ to $y$, we eliminate $x$ and move on to $y$ (as another vertex can be reached from it); if not, we eliminate $y$ (as it cannot be reached from $x$). Once we reach the last vertex, whichever vertex is not eliminated should be compared with each other vertex (ensure the superstar condition is upheld: there is an edge incoming but not outgoing) until it is eliminated or confirmed as the superstar. Some pseudocode:

```
vertex superstar(graph g)
    current vertex = first
    # Go through each vertex
    for each subsequent vertex in g ("next")
        # If there's an edge from this to the next, we eliminate this one [move to the new one].
        # If not, we just stay here.
        if edge exists from current to next
            candidate = next
        end if
    end for
    # Now we are on the final remaining candidate, check whether it satisfies the requirements.
    # just a rename for clarity
    candidate = current
    for each other vertex in g
        if edge from current to other exists
            return null
        else if no edge from other to current
            return null
        end if
    end for
    return candidate
end superstar

```

Let's walk through an example to illustrate the method. Take this array, with the source vertex on the top and destination on the side. 1 indicates an edge:

$$ \begin{array}{r|c c c c|r} & 1 & 2 & 3 & 4 \\ \hline 1 & - & 1 & 0 & 1 \\ 2 & 1 & - & 0 & 1 \\ 3 & 1 & 1 & - & 1 \\ 4 & 1 & 1 & 0 & - \\ \end{array} $$

I'll grey out the vertices we have ruled out as potential superstars. I'll use green and red to indicate the edges we are looking at when they do and do not contain the edge we're looking for, and blue to indicate where we have already looked.

We start by looking at vertices 1 and 2.

$$ \begin{array}{r|c c c c} & 1 & 2 & 3 & 4 \\ \hline 1 & - & \color{green}{1} & 0 & 1 \\ 2 & 1 & - & 0 & 1 \\ 3 & 1 & 1 & - & 1 \\ 4 & 1 & 1 & 0 & - \\ \end{array} $$ The green number shows there is an edge from 2 to 1, so we eliminate 2 and look for an edge from 3 to 1:

$$ \begin{array}{r|c c c c} & 1 & \color{grey}{2} & 3 & 4 \\ \hline 1 & - & \color{blue}{1} & \color{red}{0} & 1 \\ \color{grey}{2} & 1 & - & 0 & 1 \\ 3 & 1 & 1 & - & 1 \\ 4 & 1 & 1 & 0 & - \\ \end{array} $$

We see there is no such edge, so we eliminate 1 and take 3 as our current vertex. Recall that we have eliminated 2 already, so see whether there is an edge from 4 to 3:

$$ \begin{array}{r|c c c c} & \color{grey}{1} & \color{grey}{2} & 3 & 4 \\ \hline \color{grey}{1} & - & \color{blue}{1} & \color{blue}{0} & 1 \\ \color{grey}{2} & 1 & - & 0 & 1 \\ 3 & 1 & 1 & - & \color{green}{1} \\ 4 & 1 & 1 & 0 & - \\ \end{array} $$

There is an edge from 4 to 3, so we eliminate 4. At this point we have eliminated all but one of the vertices (3), so check out its edges and see whether it qualifies:

$$ \begin{array}{r|c c c c} & \color{grey}{1} & \color{grey}{2} & 3 & \color{grey}{4} \\ \hline \color{grey}{1} & - & \color{blue}{1} & \color{red}{0} & 1 \\ \color{grey}{2} & 1 & - & 0 & 1 \\ 3 & \color{green}{1} & 1 & - & \color{blue}{1} \\ \color{grey}{4} & 1 & 1 & 0 & - \\ \end{array} $$

There is an edge from 1 to 3 but not the reverse, so 3 is still a candidate.

$$ \begin{array}{r|c c c c} & \color{grey}{1} & \color{grey}{2} & 3 & \color{grey}{4} \\ \hline \color{grey}{1} & - & \color{blue}{1} & \color{blue}{0} & 1 \\ \color{grey}{2} & 1 & - & \color{red}{0} & 1 \\ 3 & \color{blue}{1} & \color{green}{1} & - & \color{blue}{1} \\ \color{grey}{4} & 1 & 1 & 0 & - \\ \end{array} $$

There is also an edge from 2 to 3 but not the reverse, so 3 is still a candidate.

$$ \begin{array}{r|c c c c} & \color{grey}{1} & \color{grey}{2} & 3 & \color{grey}{4} \\ \hline \color{grey}{1} & - & \color{blue}{1} & \color{blue}{0} & 1 \\ \color{grey}{2} & 1 & - & \color{blue}{0} & 1 \\ 3 & \color{blue}{1} & \color{blue}{1} & - & \color{green}{1} \\ \color{grey}{4} & 1 & 1 & \color{red}{0} & - \\ \end{array} $$

There is an edge from 4 to 3 but not 3 to 4; that completes our check of 3's edges and we have found that it is, in fact, a superstar.

Since we eliminate one vertex as a possible superstar on each of the first $n-1$ edge checks, the best case is that the $n$th check eliminates the final vertex for a complexity of $n$. In the worst case (the last or second-to-last vertex is a superstar, or the final check disqualifies it), after the first $n-1$ comparisons we compare the candidate with $2\times(n-1)$ more vertices, for a worst case complexity of $3n-3$ ($O(n)$). So, this algorithm is $\Theta(n)$.

# Answer
> 9 votes
Isn't this the Celebrity Problem?

There will only be one superstar(celebrity) if there is one.

We use the adjacency matrix representation, where $A\[i,j\] = 1$ if there is a directed edge from $i$ to $j$, otherwise it is $0$. (I am guessing that is allowed).

By looking at $A\[i,j\]$ (can be done in $\mathcal{O}(1)$ time) we can eliminate at least one of them as a candidate for being the celebrity: If $A\[i,j\] = 1$, then you can eliminate $i$. If $A\[i,j\] = 0$ we can eliminate $j$.

Maintain a list of current candidates, eliminating one by one. A linked list should suffice.

At the end, you can verify if your candidate is indeed a superstar.

This algorithm will be $\mathcal{O}(n)$.

# Answer
> 7 votes
*This answer addresses the version of the question where any graph representation was possible, not the current version of the question.*

* Store your graph as a pair of adjacency list and reverse adjacency list, where each list contains in addition the length of the list, hence the number out- and in-edges, respectively.
* Preprocessing: compute reverse adjacency list (that is, the list of in-edges). Cost $\mathcal{O}(|E|)$.
* Traverse the lists and select any node where the number of out-edges is $0$ and the number of in-edges is $n-1$. Cost $\mathcal{O}(|N|)$.

# Answer
> 2 votes
Just for reference, this is pseudocode of a recursive version of what Kevin posted.

```
superstar(V, E) {
  if ( |V| == 1 ) {
    return V.pop
  }

  a = V.pop
  b = V.pop
  if ( (a,b) ∈ E ) {
    no_ss = a
    keep  = b
  }
  else {
    no_ss = b
    keep = a
  }

  s = superstar(V ++ keep)

  return ( s != null && (no_ss, s) ∈ E && !(s, no_ss) ∈ E ) ? s : null
}

hasSuperstar(V, E) = superstar(V, E) != null

```

---
Tags: algorithms, graphs
---


title: An indexing function for graphs

text:
# Question
Title: An indexing function for graphs
Definition from wikipedia:

> A graph is an ordered pair $G = (V, E)$ comprising a set $V$ of nodes together with a set $E$ of edges, which are two-element subsets of $V$.

The set of all finite graphs (modulo isomorphism: we don't want nodes to have identities) is countable and could be enumerated. But what would be an *efficient* (low-complexity, from a programming point of view) injection from graphs to $\mathbb{N}$?

***Edit:** Gilles' comment indicates that it is not know whether there is a such function feasible in polynomial time. An example of an exponential-complexity function would be good enough; we can surely do better than a brute enumeration?*

# Answer
> 3 votes
A graph $G$ whose nodes are numbered is uniquely described by its adjacency matrix. Concatenating the matrix's rows yields a natural number $\cal{G}$ in binary representation; in order to deal with leading $0$, prepend a $1$. This mapping is obviously injective. For easier decoding, you might want to use Cantor's pairing function on $(\cal{G}, |V|)$ and use the result as graph number.

Computing this mapping is easy, but the resulting number can be huge ($\approx 2^{|V|^2}$).

In the case nodes cannot be identified, the (conjectured) hardness of Graph Isomorphism (probably) prevents an efficient, *real* mapping from Graphs to the naturals; for now, we have to be satisfied with a mapping from graph presentations to naturals---or show considerable genius.

---
Tags: algorithms, graphs
---


# Question
Title: Easy to state open problems in computability theory
I was searching for interesting and easy to state open problems in computability (understandable by undergraduate students taking their first course in computability) to give examples of open problems (and obviously I want the students to be able to understand the problem without needing too much new definitions and also be interesting to them).

I found this list but the problems in it seem too complicated for undergraduates and will need spending considerable time giving definitions before stating the problem. The only problem I have found so far is

> Is Diophantine problem over rational numbers decidable?

Do you know any other interesting and easy to state open problem in computability theory?

# Answer
One famous open question about the poset $(D, \leq\_T)$ of Turing degrees is whether it has any non-trivial automorphisms. That is, does there exist a non-identity bijection $f\colon D \to D$ such that $a \leq\_T b $ if and only if $f(a) \leq\_T f(b)$?.
> 5 votes

---
Tags: computability
---


# Question
Title: Is it possible to derive a string in this rewriting system?
Rewriting system is a set of rules in the form of $A \leftrightarrow B$. If we apply that rule to a string $w$ we replace any substring $A$ in $w$ with a substring $B$ and vice versa.

Given a starting string $AAABB$ can we derive $BAAB$ in the system with the following rules:

* $A \leftrightarrow BA$
* $BABA \leftrightarrow AABB$
* $AAA \leftrightarrow AB$
* $BA \leftrightarrow AB$

Is there a general algorithm for that?

# Answer
Notice that the parity of the number of $A$s does not change. Since one string contains an odd number $A$ and the other even, they are not reachable.

I believe in general (for an arbitrary set of rules, not your specific example), this is likely to be an undecidable problem. If the transforms are one way(i.e rules of the form $A \to BA$) it is so , for eg see: Tag System.
> 7 votes

---
Tags: computability, term-rewriting
---


# Question
Title: Which combinations of pre-, post- and in-order sequentialisation are unique?
We know post-order,

```
post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]

```

and pre-order

```
pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)

```

and in-order traversal resp. sequentialisation.

```
in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)

```

One can easily see that neither describes a given tree uniquely, even if we assume pairwise distinct keys/labels.

Which combinations of the three can be used to that end and which can not?

Positive answers should include an (efficient) algorithm to reconstruct the tree and a proof (idea) why it is correct. Negative answers should provide counter examples, i.e. different trees that have the same representation.

# Answer
First, I'll assume that all elements are distinct. No amount of sequentialisations is going to tell you the shape of a tree with elements `[3,3,3,3,3]`. It is possible to reconstruct some trees with duplicate elements, of course; I don't know what nice sufficient conditions exist.

Continuing on the negative results, you can't fully rebuild a binary tree from its pre-order and post-order sequentializations alone. `[1,2]` preorder, `[2,1]` post-order has to have `1` at the root, but `2` can be either the left child or the right child. If you don't care about this ambiguity, you can reconstruct the tree with the following algorithm:

* Let $\[x\_1,\dots,x\_n\]$ be the pre-order traversal and $\[y\_n,\ldots,y\_1\]$ be the post-order traversal. We must have $x\_1=y\_1$, and this is the root of the tree.
* $x\_2$ is the leftmost child of the root, and $y\_2$ is the rightmost child. If $x\_2 = y\_2$, the root node is unary; recurse over $\[x\_2,\ldots,x\_n\]$ and $\[y\_n,\ldots,y\_2\]$ to build the single subtree.
* Otherwise, let $i$ and $j$ be the indices such that $x\_2 = y\_i$ and $y\_2 = x\_j$. $\[x\_2,\ldots,x\_{j-1}\]$ is the pre-order traversal of the left subtree, $\[x\_j,\ldots,x\_n\]$ that of the right subtree, and similarly for the post-order traversals. The left subtree has $j-2=n-i+1$ elements, and the right subtree has $i-2=n-j+1$ elements. Recurse once for each subtree.
By the way, this method generalizes to trees with arbitrary branching. With arbitrary branching, find out the extent of the left subtree and cut off its $j-2$ elements from both lists, then repeat to cut off the second subtree from the left, and so on.

As stated, the running time is $O(n^2)$ with $\Theta(n^2)$ worst case (in the case with two children, we search each list lineraly). You can turn that into $O(n\\,\mathrm{lg}(n))$ if you preprocess the lists to build an $n\\,\mathrm{lg}(n)$ finite map structure from element values to positions in the input lists. Also use an array or finite map to go from indices to values; stick to global indices, so that recursive calls will receive the whole maps and take a range as argument to know what to act on.

With the pre-order traversal $\[x\_1,\ldots,x\_n\]$ and the in-order traversal $\[z\_1,\ldots,z\_n\]$, you can rebuild the tree as follows:

* The root is the head of the pre-order traversal $x\_1$.
* Let $k$ be the index such that $z\_k = x\_1$. Then $\[z\_1,\ldots,z\_{k-1}\]$ is the in-order traversal of the left child and $\[z\_{k+1},\ldots,z\_n\]$ is the in-order traversal of the right child. Going by the number of elements, $\[x\_2,\ldots,x\_k\]$ is the pre-order traversal of the left child and $\[x\_{k+1},\ldots,x\_n\]$ that of the right child. Recurse to build the left and right subtrees.

Again, this algorithm is $O(n^2)$ as stated, and can be performed in $O(n\\,\mathrm{lg}(n))$ if the list is preprocessed into a finite map from values to positions.

Post-order plus in-order is of course symmetric.
> 21 votes

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


title: Reflection on Concurrency

text:
# Question
Title: Reflection on Concurrency
Reflection is a common mechanism for accessing and changing the structure of a program at run-time, found in many dynamic programming languages such as Smalltalk, Ruby and Python, and in impoverished form in Java and (hence) Scala. Functional languages such as LISP and Scheme also support a good reflect framework.

Modern languages support concurrency, either by adding threads on top of the existing language constructs, or by designing from the ground up with concurrency in mind.

My question is:

> What models of reflection for the concurrency aspects in concurrent languages (multi-threaded, actor-based, active-object-based) exist?

# Answer
> 1 votes
The closest I can think of is the MetaKlaim language. Klaim is a process calculus with asynchronous communication via tuple spaces. MetaKlaim is an extension of Klaim that integrates the meta-programming features of MetaML, namely multi-stage programming with types. (You may be more familiar with the syntax of MetaOCaml)

I am not an expert in any of these fields, so I don't really know if multi-stage programming fit in this definition of reflection. (I know this does not capture *all* aspects of reflection anyway so that's at most a partial answer).

---
Tags: programming-languages, semantics, concurrency, reflection
---


# Question
Title: How hard is counting the number of simple paths between two nodes in a directed graph?
There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search).

However it seems that, surprisingly, the problem gets much harder if instead of testing for the existence we want want to *count* the number of paths.

If we allow paths to reuse vertices then there is a dynamic programming solution to find the number of paths from *s* to *t* with *n* edges. **However, if we only allow simple paths, that don't reuse vertices, the only solution I can think of is brute force enumeration of the paths**, something that has exponential time complexity.

So I ask,

* Is counting the number of simple paths between two vertices hard?
* If so, is it kind of NP-complete? (I say kind of because it is technically not a decision problem...)
* Are there other problems in P that have a hard counting versions like that too?\**

# Answer
The most common complexity class associated to counting problems is #P. Deciding if there a simple path from a given node to another is clearly in NP. Counting them is then in #P.

About the NP-completeness: even if that's not a decision problem, it would hardly fit in NP: there may be $n!$ paths, and non-determinism does not help you about that (you'd still need to check them all)

The answer to your two first two question is: yes, it is hard, it is #P-complete (ref).

The Wikipedia article gives pertinent facts: 1) probabilistic algorithms are useful to approximate #P-complete functions, and that's the kind of algorithm used for the approximation in the previous article. 2) There are other easy problems with hard (#P-complete) counting versions:

* finding (linear) vs. counting all assignments satisfying a DNF formula or an instance of 2-SAT
* finding (linear) vs. counting topological sortings
* finding (O(VE)) vs. counting perfect matching in bipartite graphs

You already know that if you remove the constraint "simple path" the problem falls into P (well you have to bound the length of the paths by a polynomial of the size of the graph or give the bound in unary)
> 18 votes

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


# Question
Title: CCS process for a drink dispenser with two different prices
A drink dispenser requires the user to insert a coin ($\bar c$), then press one of three buttons: $\bar d\_{\text{tea}}$ requests a cup of tea $e\_{\text{tea}}$, ditto for coffee, and $\bar r$ requests a refund (i.e. the machine gives back the coin: $\bar b$). This dispenser can be modeled by the following CCS process:

$$ M \stackrel{\mathrm{def}}= c.(d\_{\text{tea}}.\bar e\_{\text{tea}}.M + d\_{\text{coffee}}.\bar e\_{\text{coffee}}.M + r.\bar b.M)$$

A civil war raises the price of coffee to two coins, while the price of tea remains one coin. We want a modified machine that delivers coffee only after two coins, and acquiesces to a refund after either one or two coins. How can we model the modified machine with a CCS process?

# Answer
You can easily profit from warfare that way:

$$ M \stackrel{\mathrm{def}} = c.( d\_{\text{tea}}.\bar e\_{\text{tea}}.M \+ r.\bar b.M \+ c.( d\_{\text{coffee}}.\bar e\_{\text{coffee}}.M \+ r.\bar b.\bar b.M ) ) $$

note that you have to press refund to get a tea if you put too many coins. If you don't want that, you can adapt it (or maybe set up a (finite is enough) counter) :

$$ M \stackrel{\mathrm{def}} = c.( d\_{\text{tea}}.\bar e\_{\text{tea}}.M \+ r.\bar b.M \+ c.( d\_{\text{coffee}}.\bar e\_{\text{coffee}}.M \+ d\_{\text{tea}}.\bar b.\bar e\_{\text{tea}}.M \+ r.\bar b.\bar b.M ) ) $$
> 9 votes

# Answer
This $M\_0$ machine is more convenient than the one you propose:

$$ M\_0 := c.M\_1 $$

$$ M\_1 := d\_{\text{tea}}.\bar e\_{\text{tea}}.M\_1 + r.\bar b.M\_0 + c.M\_2$$

$$ M\_{n} := d\_{\text{tea}}.\bar e\_{\text{tea}}.M\_{n-1} + d\_{\text{coffee}}.\bar e\_{\text{coffee}}.M\_{n-2} + r.\underbrace{\bar b.\dots\bar b.}\_{n}M\_0 + c.M\_{n+1}$$

(But using infinite processes is like cheating).
> 5 votes

---
Tags: logic, concurrency, modelling, process-algebras, ccs
---


# Question
Title: termination of two concurrent threads with shared variables
We're in a shared memory concurrency model where all reads and writes to integer variables are atomic.

* `do:` $S\_1$ `in parallel with:` $S\_2$ means to execute $S\_1$ and $S\_2$ in separate threads, concurrently.
* `atomically(`$E$`)` means to evaluate $E$ atomically, i.e. all other threads are stopped during the execution of $E$.

Consider the following program:

```
x = 0; y = 4
do:                 # thread T1
    while x != y:
        x = x + 1; y = y - 1
in parallel with:   # thread T2
    while not atomically (x == y): pass
    x = 0; y = 2

```

Does the program always terminate? When it does terminate, what are the possible values for `x` and `y`?

<sub> Acknowledgement: this is a light rephrasing of exercise 2.19 in *Foundations of Multithreaded, Parallel, and Distributed Programming* by Gregory R. Andrews. </sub>

# Answer
This trace is possible, in two separate threads T1 and T2. $state$ is $(x,y)$.

* T1: `...` $state=(0, 4)$
* T1: `x = x + 1; y = y - 1` $~~state=(1, 3)$
* T1: `x = x + 1; y = y - 1` $~~state=(2, 2)$
* T2: `x == y` evaluates to true, `pass` and then `x = 0;` $~~state=(0, 2)$
* T1: `x != y` evaluates to true, `x = x + 1; y = y - 1` $~~state=(1, 1)$
* T2: `y = 2` $~~state=(1, 2)$
* T1: `x != y` evaluates to true, `x = x + 1; y = y - 1` $~~state=(2, 1)$
* $state=(3, 0)$
* $state=(4, -1)$
* ...

(Note that it works even if `x = expr;` is atomic)

There are other possible interleavings. The point $(2,2)$ is common to all of them, where T1 has pending (logically) atomic instructions:

```
T1: push x; push y; eq ? stop : push(x + 1); pop@x; push(y - 1); pop@y; repeat
T2: (x != y) ? repeat : x = 0; y = 2;

```

In the first case, T1 proceeds to `stop` and then T2 can only proceed and the final state is $(0,2)$.

If T2 finally skips the repeat and (T1:`push x`) is run before (T2:`x = 0`) then T1 will stop looping and the same final state is reached.

If T2 finally skips the repeat and (T1:`push x`) is run after (T2:`x = 0`) then T2 can proceed after the `stop` independently of (T1:`y = 2`).

```
state = (0, 2)
T1: push(x + 1); pop@x; push(y - 1); pop@y; ...
T2: y = 2;

```

If T2 is run now then it will loop as above, so T1 proceeds:

```
state = (1, 2); stack = 1
T1: pop@y; ...
T2: y = 2;

```

If T2 is run now, this will go to the final state $(1,1)$. Otherwise:

```
state = (1, 1)
T1: push x; push y; eq ? stop : push(x + 1); pop@x; push(y + 1); pop@y; repeat
T2: y = 2;

```

If T2 does not act before `push y`, this will stop and go to the state $(1,2)$. If it does, then the state is $(1, 2)$ and this will loop into $(2,1)$, $(3,0)$, ...

To sum up the possible final states are $(0,2)$, $(1,1)$, $(1,2)$. I don't think it was worth the effort though, since I probably made mistakes.
> 4 votes

---
Tags: concurrency, shared-memory, imperative-programming
---


title: (When) is hash table lookup O(1)?

text:
# Question
Title: (When) is hash table lookup O(1)?
It is often said that hash table lookup operates in constant time: you compute the hash value, which gives you an index for an array lookup. Yet this ignores collisions; in the worst case, every item happens to land in the same bucket and the lookup time becomes linear ($\Theta(n)$).

Are there conditions on the data that can make hash table lookup truly $O(1)$? Is that only on average, or can a hash table have $O(1)$ worst case lookup?

*Note: I'm coming from a programmer's perspective here; when I store data in a hash table, it's almost always strings or some composite data structures, and the data changes during the lifetime of the hash table. So while I appreciate answers about perfect hashes, they're cute but anecdotal and not practical from my point of view.*

P.S. Follow-up: For what kind of data are hash table operations O(1)?

# Answer
> 42 votes
There are two settings under which you can get $O(1)$ worst-case times.

1. If your setup is static, then FKS hashing will get you worst-case $O(1)$ guarantees. But as you indicated, your setting isn't static.
2. If you use Cuckoo hashing, then queries and deletes are $O(1)$ worst-case, but insertion is only $O(1)$ expected. Cuckoo hashing works quite well if you have an upper bound on the total number of inserts, and set the table size to be roughly 25% larger.

There's more information here.

# Answer
> 22 votes
*This answer summarises parts of TAoCP Vol 3, Ch 6.4.*

Assume we have a set of values $V$, $n$ of which we want to store in an array $A$ of size $m$. We employ a hash function $h : V \to \[0..M)$; typically, $M \ll |V|$. We call $\alpha = \frac{n}{m}$ the *load factor* of $A$. Here, we will assume the natural $m=M$; in practical scenarios, we have $m \ll M$, though, and have to map down to $m$ ourselves.

The first observation is that even if $h$ has uniform characteristics¹ the probability of two values having the same hash value is high; this is essentially an instance of the infamous birthday paradox. Therefore, we will usually have to deal with conflicts and can abandon hope of $\mathcal{O}(1)$ worst case access time.

What about the average case, though? Let us assume that every key from $\[0..M)$ occurs with the same probability. The average number of checked entries $C\_n^S$ (successful search) resp. $C\_n^U$ (unsuccessful search) depends on the conflict resolution method used.

### Chaining

Every array entry contains (a pointer to the head of) a linked lists. This is a good idea because the expected list length is small ($\frac{n}{m}$) even though the probability for having collisions is high. In the end, we get \\\[ C\_n^S \approx 1 + \frac{\alpha}{2} \quad \text{ and } \quad C\_n^U \approx 1 + \frac{\alpha^2}{2} .\\\] This can be improved slightly by storing the lists (partly or completely) inside the table.

### Linear Probing

When inserting (resp. searching a value) $v$, check positions \\\[h(v), h(v)-1,\dots,0,m-1,\dots,h(v)+1\\\] in this order until an empty position (resp. $v$) is found. The advantage is that we work locally and without secondary data structures; however, the number of average accesses diverges for $\alpha \to 1$: \\\[ C\_n^S \approx \frac{1}{2}\left(1 +\frac{1}{1-\alpha}\right) \quad \text{ and } \quad C\_n^U \approx \frac{1}{2}\left(1 +\left(\frac{1}{1-\alpha}\right)^2\right).\\\] For $\alpha \< 0.75$, however, performance is comparable to chaining².

### Double Hashing

Similar to linear probing but search step size is controlled by a second hash function that is coprime to $M$. No formal derivation is given, but empirical observations suggest \\\[ C\_n^S \approx \frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\quad \text{ and } \quad C\_n^U \approx \frac{1}{1-\alpha} .\\\] This method has been adapted by Brent; his variant amortises increased insertion costs with cheaper searches.

Note that removing elements from and extending tables has varying degrees of difficulty for the respective methods.

Bottom-line, you have to choose an implementation that adapts well to your typical use cases. Expected access time in $\mathcal{O}(1)$ is possible if not always guaranteed. Depending on the used method, keeping $\alpha$ low is essential; you have to trade off (expected) access time versus space overhead. A good choice for $h$ is also central, obviously.

---

1\] As arbitrarily dumb uninformed programmers may provide $h$, any assumption regarding its quality is a stretch in practice.
2\] Note how this coincides with recommendations for usage of Java's `Hashtable`.

# Answer
> 10 votes
A *perfect hash function* can be defined as an injective function from a set $S$ to a subset of the integers $\\{0, 1, 2, ..., n\\}$. If a perfect hash function exists for your data and storage needs, you can easily get $O(1)$ behavior. For instance, you can get $O(1)$ performance from a hash table for the following task: given an array $l$ of integers and a set $S$ of integers, determine whether $l$ contains $x$ for each $x \in S$. A pre-procesing step would involve making a hash table in $O(|l|)$, followed by checking each element of $S$ against it in $O(|S|)$. Altogether, this is $O(|l| + |S|)$. A naive implementation using linear search might be $O(|l||S|)$; using binary search, you can do $O(\log(|l|)|S|)$ (note that this solution is $O(|l|)$ space, since the hash table must map distinct integers in $l$ to distinct bins).

EDIT: To clarify on how the hash table is generated in $O(|l|)$:

The list $l$ contains integers from a finite set $U \subset \mathbb{N}$, possibly with repeats, and $S \subseteq U$. We want to determine whether $x \in S$ is in $l$. To do so, we pre-compute a hash table for elements of $l$: a lookup table. The hash table will encode a function $h: U \rightarrow \\{true, false\\}$. To define $h$, initially assume $h(x) = false$ for all $x \in U$. Then, linearly scan through elements $y$ of $l$, setting $h(y) = true$. This takes $O(|l|)$ time and $O(|U|)$ space.

Notice that my original analysis assumed that $l$ contained at least $O(|U|)$ distinct elements. If it contains fewer distinct elements (say, $O(|1|)$), the space requirement may be higher (although it is no more than $O(|U|)$).

EDIT2: The hash table can be stored as a simple array. The hash function can be the identity function on $U$. Notice that the identity function is trivially a perfect hash function. $h$ is the hash table and encodes a separate function. I am being sloppy/confused in some of the above, but will try to improve it soon.

# Answer
> 9 votes
A perfect hash function will result in $\cal{O}(1)$ worst case lookup.

Moreover, if the maximum number of collisions possible is $\cal{O}(1)$, then hash table lookup can be said to be $\cal{O}(1)$ in the worst case. If the expected number of collisions is $\cal{O}(1)$, then the hash table lookup can be said to be $\cal{O}(1)$ in the average case.

---
Tags: algorithm-analysis, data-structures, runtime-analysis, hash-tables
---


# Question
Title: Identifying events related to dates in a paragraph
Is there an ~~*algorithmic*~~ approach to identify that dates given in a paragraph correlate to particular events (phrases) in the paragraph?

Example, consider the following paragraph:

> In June 1970, the great leader took the oath. But it was only after May 1972, post the death of the Minister of State, that he took over the reins of the country. While he enjoyed popular support until Mid-1980, his influence began to fall thereafter.

Is there an algorithm (deterministic or stochastic)# that can generate a 2-tuple (date, event), where the *event* is implied, by the paragraph, to have occured on the *date*? In the above case:

* (June 1970, great leader took oath)
* (May 1972, took over the reins)

or better yet
* (May 1972, *the great leader* took over the reins)
* (1980, fall in influence)

---

#Later addition

# Answer
In general, the problem of identifying dates and other temporal markers in text is called the problem of extracting temporal references. The search linked will take you to papers related to this.
> 4 votes

# Answer
Since you ask for a algorithmic approach, I will be as stubborn as an algorithm. I'm sorry to treat this question like this, but since it doesn't seem like a complex theoretical problem, I will synthesize the possible approaches.

Question: can you give me a algorithmic definition of a date and of particular event?

**If you can:** Since your definition is algorithmic, then this is probably some kind of formal grammar, and your problem will be to tune that grammar to catch every case you need to consider. (I'm interested if you can give me an exact definition that *isn't* a formal grammar)

**If you can't:** then at least you can come up with examples. Alright then. The best – and only I can think of – approach is machine learning algorithms, that you will have to train in order to recognize your dates and then your events. (Using a corpus of sentences annotated by hand) However this is quite overweening compared to some big hand-made regexp that will probably do the job. If you really, really want to do it I think the most efficient will be this kind of regexp given as a parameter to the learning algorithm but you better ask machine learning experts.

Good luck with this, It's much easier just to talk about it (in both cases).
> 2 votes

---
Tags: algorithms, data-mining, natural-language-processing
---


# Question
Title: Break an authentication protocol based on a pre-shared symmetric key
Consider the following protocol, meant to authenticate $A$ (Alice) to $B$ (Bob) and vice versa.

$$ \begin{align\*} A \to B: &\quad \text{“I'm Alice”}, R\_A \\ B \to A: &\quad E(R\_A, K) \\ A \to B: &\quad E(\langle R\_A+1, P\_A\rangle, K) \\ \end{align\*} $$

* $R$ is a random nonce.
* $K$ is a pre-shared symmetric key.
* $P$ is some payload.
* $E(m, K)$ means $m$ encrypted with $K$.
* $\langle m\_1, m\_2\rangle$ means $m\_1$ assembled with $m\_2$ in a way that can be decoded unambiguously.
* We assume that the cryptographic algorithms are secure and implemented correctly.

An attacker (Trudy) wants to convince Bob to accept her payload $P\_T$ as coming from Alice (in lieu of $P\_A$). Can Trudy thus impersonate Alice? How?

<sub> This is slightly modified from exercise 9.6 in *Information Security: Principles and Practice* by Mark Stamp. In the book version, there is no $P\_A$, the last message is just $E(R\_A+1,K)$, and the requirement is for Trudy to “convince Bob that she is Alice”. Mark Stamp asks us to find two attacks, and the two I found allow Trudy to forge $E(R+1,K)$ but not $E(\langle R, P\_T\rangle, K)$. </sub>

# Answer
This protocol seems to be insecure due to the fact that Bob sends $E(R\_A,K)$. This can be used by Trudy to "generate" encryptions of $E(\langle R\_A+1,P\_T\rangle , K)$ that will later be used to complete the authentication protocol.

Specifically, consider the following attack:

Trudy picks random $R\_1$ and runs the protocol with Bob in the following manner: $$ \begin{align\*} T \to B: &\quad \text{“I'm Alice”}, \langle R\_1+1,P\_T \rangle \\ B \to T: &\quad \color{blue}{E(\langle R\_1+1,P\_T \rangle, K)} \\ \end{align\*} $$ and then Trudy cuts the protocol in the middle (since she doesn't know how to reply). We assume both Trudy and Bob abort.

Now Trudy starts another instance of the protocol: $$ \begin{align\*} T \to B: &\quad \text{“I'm Alice”}, R\_1 \\ B \to T: &\quad E(R\_1, K) \\ T \to B: &\quad \color{blue}{E(\langle R\_1+1,P\_T \rangle, K) } \end{align\*} $$ How did Trudy complete the protocol this time without knowing $K$? it's easy! Bob actually performed the encryption for her in the first instance.

Lesson learned: in a cryptographic protocol, it's good for each message or separable fragment to contain a unique tag that prevents its reuse as some other message in the protocol. If Bob's reply was $E(\langle 1, R\_A\rangle)$ and the third message was $E(\langle 2, R\_A+1, P\rangle)$, this attack would not work.
> 5 votes

---
Tags: cryptography, protocols, authentication
---


# Question
Title: Why do neural networks seem to perform better with restrictions placed on their topology?
Fully connected (at least layer to layer with more than 2 hidden layers) backprop networks are universal learners. Unfortunately, they are often slow to learn and tend to over-fit or have awkward generalizations.

From fooling around with these networks, I have observed that pruning some of the edges (so that their weight is zero and impossible to change) tends to make the networks learn faster and generalize better. Is there a reason for this? Is it only because of a decrease in the dimensionality of the weights search space, or is there a more subtle reason?

Also, is the better generalization an artifact of the 'natural' problems I am looking at?

# Answer
> 9 votes
Fewer nodes/edges (or edges with fixed weights) means that there are fewer parameters whose values need to be found, and this typically reduces the time to learn. Also, when there are fewer parameters, the *space* that can be expressed by the neural network has fewer dimensions, so the neural network can only express more general models. It is thus is less capable of over-fitting the data, and hence the models will seem more general.

# Answer
> 5 votes
By pruning edges you've reduced the search space for the training algorithm, which will have an immediate payoff in time performance. You've also introduced constraints on the functions the network can model. The constraints may force your model to find a more general solution since the more accurate one is unreachable. A common technique for training neural networks is using a gradient descent technique. Another consequence of the pruning may be that you've eliminated some local minima in the parameter landscape that again allows the training algorithm to find a better solution.

I would not be surprised if your better generalization is related to the problems you're looking at. I've enjoyed success with neural networks where the underlying model has a continuous structure, while cases where there are discontinuities things didn't work so well. Keep in mind also that neural network performance is often intimately related to how you structure you input and output.

---
Tags: machine-learning, network-topology, neural-networks
---


# Question
Title: List of intro TCS books for those who don't know much about TCS
If you have to recommend books for someone who wants to learn more about TCS at the introductory level such as automata theory, algorithmics, complexity theory, etc, what book(s) would you recommend for those who are interested and want to learn more about TCS, but not had any exposure to it?

# Answer
If you would like to have a general introduction without getting to deep into the technical details, I suggest David Harel's Algorithmics: The Spirit of Computing. After that, this is my favorite list:

* Michael Sipser's Introduction to the Theory of Computation: the best introduction to automata theory, computability and complexity.
* Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: the most intuitive introduction to algorithms with stronger focus on intuition than technical proofs.
* Jon Bentley's Programming Pearls: this is not a textbook on algorithms, but it demonstrates beautifully how to use algorithm design techniques to solve real problems that irritated real programmers. :-) This might be a good start if you have some pre-knowledge on programming.
> 9 votes

# Answer

> 7 votes

# Answer
For the mathematics needed in algorithm analysis, I recommend the one and only GKP:

Concrete Mathematics by Graham, Knuth, Patashnik
A comprehensive, high quality treatment of practically all the math you will need in (basic) algorithmics. It is an entertaining read and includes a wealth of exercises (and solutions).
> 6 votes

# Answer
Algorithms 4. Edition R. Sedgewick

An Introduction to the Analysis of Algorithms P. Flajolet, R. Sedgewick

Introduction to Automata Theory, Languages, and Computation J. E. Hopcroft, J. D. Ullman, (R. Motwani)
The 1979 first Edition has more theoretical results that are missing in the 2001 second Edition. Haven’t look at the third Ed yet.

Introduction to formal language theory M. A. Harrison
It is from 1978 but I still would like to see it on the list.

Logicomix: An Epic Search for Truth A. Doxiadis, C. H. Papadimitriou
Because it is totally awesome!

Again 1979
Garey and Johnson's Computers and Intractability: A Guide to the Theory of NP-Completeness

I’d love to have TAoCP on the list but I fear, that Don Knuth’s meticulous approach is nothing that could be considered as “introductory”. Sadly...
> 5 votes

# Answer
If you are entirely new to the field of TCS then Sipser's Introduction to the Theory of Computation is definitely the best book to get you started. I have read other introductionary books, and none of them, in my opinion, come close to Sipser's way of bringing the matter.

Other, more specific, good theoretical books are:
> 4 votes

# Answer
*This is an aggregate answer that contains books from answers with score at least five. Please discuss its content in the chat.*

### Algorithms & Data Structures

* Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (3rd ed 2009)
A comprehensive treatment of basic algorithms and data structures and their analysis without digging too deep.
* Algorithms by Dasgupta, Papadimitriou, Vazirani (2006)
The most intuitive introduction to algorithms with stronger focus on intuition than technical proofs.

### Computability & Complexity

### Formal Languages & Automata

### Applied Theory

* Principles of Model Checking by Baier, Katoen (2008)
Massive book that an be used as a comprehensive introduction to model checking.
* Programming Pearls by Jon Bentley (2nd ed 1999)
Not a textbook on algorithms but demonstrates beautifully how to use algorithm design techniques to solve real problems. Might be a good start if you have some pre-knowledge on programming.
> 3 votes

# Answer
Some good books covering the Theory B part of TCS:

* **Logic in CS**: *Logic in Computer Science: Modelling and Reasoning about Systems* By Michael Huth and Mark Ryan.
Broad coverage of various uses of logic in computer science. About 3rd year undergraduate level.
* **The Lambda Calculus**: *Lambda-Calculus and Combinators. An introduction* by J. Roger Hindley and Jonathan P. Seldin.
Introduces the lambda calculus, which is an essential ingredient in the foundations of programming languages. About 3rd year undergraduate level.
* **Lead in to domain theory**: *Introduction to Lattices and Order (2nd ed.)* by Davey, B. A. and Priestley, H. A. Cambridge University Press. (2002).
Covers a very useful topic, especially if you plan to work with semantics. It is a bit more mathematical than the other topics, but the early chapters are certainly at an advanced undergraduate level.
* **Semantics**: *Semantics with Applications: An Appetizer* by Hanne Riis Nielson and Flemming Nielson.
A really nice introduction to programming language semantics. Rather than going deep into any particular formalism, it gives a broad presentation and includes applications generally not considered in other books on semantics. Could possibly be useful for 2nd year undergraduates.
> 3 votes

---
Tags: education
---


# Question
Title: How is the key in a private key encryption protocol exchanged?
Windows NT used a point-to-point protocol where a client can communicate "securely" with a server by using a stream cipher to encrypt an array of messages with some key $k$. The server also encrypts its response with the same key $k$. But how is it aware of this key?

More general: if Alice and Bob use some encryption/decryption algorithm that operates on the same private key $k$, what is a secure way of exchanging this key? (without using a different key ofcourse)

This is something that I've always asked myself whilest studying private key cryptography.

# Answer
> 6 votes
Most private key algorithms rely on infeasibility of certain computations like factorisation of a number into its prime factors given the current computing infrastructure.

At the same time, most of them are also computationally intensive when used for encryption and decryption and therefore the entire message stream is not encrypted using the private keys. Rather, the message is encrypted using some other (less intensive) algorithm and the key used for that encryption is encrypted using the Private Key.

Of course, as you point out, secure exchange of keys remains an issue which can be to a certain extent be addressed by:

* **Diffie-Hellman Key Exchange**: Uses modular arthimetic to securely exchange keys.
* **Single/Multiple Key Distribution Center (KDC)**: Uses trusted third party based ticketing system.
* **Kerberos Authentication Protocol**: A relatively complex protocol based on KDC.

# Answer
> 6 votes
Whenever Alice and Bob wants to agree on a same private key, the most popular method is to use Diffie-Hellman. It works as follows:

1. Two public values are first chosen lets say $n=13$ and $g=17$. (These are usually very large prime numbers and known to everyone using that protocol).
2. Alice chooses a Private Value $a = 3$ and Bob chooses a Private Value $b = 7$. These are private to themselves.
3. Alice computes: $A = g^a\mod n$ and Bob computes: $B = g^b\mod n$, in this case $A = 12$ and $B = 4$ and they exchange each others values (may be through chat), i.e. everybody knows the values of $A$ and $B$.
4. Alice computes: $K = B^a \mod n$ and Bob computes: $K = A^b\mod n$, in this case $K = 12$.

Now Alice and Bob have both agreed upon the value $K$ as their key. Note that since the value $n$ and $g$ and **very large prime numbers** it is almost impossible for a eavesdropper to factorize them and compute the key himself.

A problem in private key cryptography is man-in-the-middle attack and that is one of the main reasons to choose public key cryptography over private key cryptography.

# Answer
> 5 votes
First, a point of terminology: what you describe is symmetric encryption, and a key that's shared between participants is usually known as a secret key; “private key” usually means the part of a key in public-key cryptography that only one participant knows.

There are two ways of disseminating a secret key: it can be transported in some physically secure fashion, or it can be transported using some other form of encryption, commonly public-key cryptography.

There are ways to exchange a secret key that do not require a secret communication channel. The most popular is the Diffie-Hellman key exchange protocol. The principle of Diffie-Hellman is that each participant generates its own key pair, and there is a mathematical operation that constructs a large number from one public key and one private key. This mathematical operation has a very interesting property: the large number can be constructed from Alice's private key and Bob's public key, or from Bob's private key and Alice's public key; you get the same number either way. So Alice and Bob exchange their public keys, and both parties know the large number, which can then be used as a secret key. An eavesdropper can find out both public key, but it is impossible¹ to find the large number from the public keys alone.

The Diffie-Hellman key exchange allows two parties to exchange a secret, no matter who is listening. However, it does not authenticate Alice to Bob or vice versa. Therefore it is amenable to a man-in-the-middle attack: Mallory performs the key exchange with Alice (who believes she's talking to Bob) and separately with Bob (who believe he's talking to Alice), and thus gets to decide or at least know the secret.

When the attacker can intercept and inject messages, more cryptography is needed for the participants to authenticate each other. (A passive attacker effectively means that the underlying transport protocol provides authentication.) The easy way is for each participant to already know each other's public key. If Alice knows Bob's public key:

* Alice can authenticate Bob by sending him a challenge: a random value (a nonce) encrypted with Bob's public key. If Bob can decrypt that value and send it back, Alice knows she is really talking to Bob.
* Bob can authenticate with Alice by sending her a message signed with his public key. Alice verifies the signature to check she is really talking to Bob.

There are many variants that use one of these methods (or yet another variant) in one direction and either the same or a different method in the other direction, or that authenticate in one direction only. For example, SSL/TLS (the cryptography layer for many -s protocols such as HTTPS, SMTPS, IMAPS, etc.) can use several different cipher combinations, and usually authenticates the server to the client but can optionally authenticate the client as well. Diffie-Hellman is slow and cumbersome for this application; the most widely algorithm with public key distribution is RSA.

Of course, Alice and Bob might not know each other's public key beforehand. So they instead rely on a trust chain: Bob sends Alice his public key, alongside a signed statement from a third party that affirms that this key is really Bob's public key. This signed statement is called a certificate and the third partie is a certificate authority. The third party may be known to Bob, or its identity may be confirmed by a fourth party, and so on. Eventually this chain of trust (… vouches for Dominique vouches for Charlie who vouches for Bob) must reach some party Ron that Bob already trusts, meaning that Bob has Ron's public key and trusts Ron to only sign valid certificates.

There are protocols that do not rely on public-key cryptography. In particular, the Kerberos protocol is used in both unix-based and Windows-based networks to establish connections between a client and a server. Kerberos uses a central authentication server called a key distribution center (KDC). The KDC must have the user's password stored in a database, and the client normally prompts the user for the password. To avoid exposing the password, the protocol does not use the password directly, but a cryptographic hash or more generally a key derivation function applied to the password.

With this shared secret, the client and the KDC establish a secure channel and the KDC sends the client a “ticket”. The ticket contains a session key (i.e. a newly generated secret key), as well as a copy of the key that is encrypted with another symmetric key shared between the KDC and the server that the client wants to contact. The client then forwards this encrypted copy to the server. The server decrypts this message to get the session key, and generates a nonce that it encrypts with the session key and sends back to the client. The client then initiates a secure channel with the server, encrypted with the session key, and starts by showing that it could decrypt the nonce: this authenticates the client to the server. A Kerberos session establishment is a variant of the Needham-Schroeder protocol.

¹ <sub> In the sense that cryptographers have tried very hard, but the best way they've found to do it requires an unachievable amount of computing power. </sub>

# Answer
> 3 votes
A possible way is to first use Public-Key Cryptography to exchange a private key. However, when it's not possible, there are some specific key exchange protocols, probably the most well-known is the Diffie-Hellman protocol.

# Answer
> 3 votes
There is always the trivial solution: the users meet and exchange keys. This is not very practical for many cases, but possible.

In addition to the Diffie-Hellman (DH) key-exchange protocol, there are also quantum key distribution protocols. One of the most known QKD protocols is the Bennett-Brassard protocol, BB84.

The advantage of BB84 over DH, is that DH is secure only if discrete logarithm cannot be done efficiently (see discrete logarithm assumption, and also the related DDH Assumption). However, BB84 is *information-theoretically* secure. That is, even if $P=NP$, BB84 would still be secure (but DH would not).

On the flip side, MITM attack is a problem for BB84 as well, and one must assume the users use authenticated channel to overcome this problem (but this usually requires them to preshare an authentication key, and we're back in square one).

---
Tags: cryptography, encryption
---


# Question
Title: Clustering of Songs (The Joe Walsh Problem)
The Eagles are a rock supergroup from the 70s and 80s, responsible for such classics as *Hotel California*. They have two quite distinctive sounds, one where guitarist Joe Walsh is present (for example, in *Life in the Fast Lane*) and one where he is absent. The latter songs have a markedly more sombre/boring feel.

I'm curious to understand the degree to which an (unsupervised) learning algorithm would be able to detect the difference between the two sounds. One could imagine that it would be easy to tell the difference between speed metal and classical music, but what about sounds by the same band.

> How would I set up such an experiment? Assume that I already have the relevant audio files in some standard format.

Note that this should also apply to other rock groups, such as AC/DC who had a change of lead singer in 1980, and possibly even to other genres, possibly even more modern music.

# Answer
> 13 votes
What you want to do seems to be known as *Audio Feature Extraction* or, more specifically, *Music Information Retrieval*, that is automated methods that distill characteristics out of (sets of) music files. You would have to extract features of samples of both equivalence classes and look at differences that can inform song choice.

Researchy tools are available for instance here and here. A finalist of Google Science Fair 2011 presented interesting stuff but I can not find his tools anywhere.

---
Tags: machine-learning, modelling
---


title: What is coinduction?

text:
# Question
Title: What is coinduction?
I've heard of (structural) induction. It allows you to build up finite structures from smaller ones and gives you proof principles for reasoning about such structures. The idea is clear enough.

> But what about coinduction? How does it work? How can one say anything conclusive about an infinite structure?

There are (at least) two angles to address, namely, coinduction as a way of defining things and as a proof technique.

> Regarding coinduction as a proof technique, what is the relationship between coinduction and bisimulation?

# Answer
First, to dispel a possible cognitive dissonance: reasoning about infinite structures is not a problem, we do it all the time. As long as the structure is finitely describable, that's not a problem. Here are a few common types of infinite structures:

* languages (sets of strings over some alphabet, which may be finite);
* tree languages (sets of trees over some alphabet);
* execution traces of a non-deterministic system;
* real numbers;
* sets of integers;
* sets of functions from integers to integers; …

### Coinductivity as the largest fixpoint

Where inductive definitions build a structure from elementary building blocks, coinductive definitions shape structures from how they can be deconstructed. For example, the type of lists whose elements are in a set `A` is defined as follows in Coq:

```
Inductive list (A:Set) : Set :=
  | nil : list A
  | cons : A -> list A -> list A.

```

Informally, the `list` type is the smallest type that contains all values built from the `nil` and `cons` constructors, with the axiom that $\forall x \\, y, \\: \mathtt{nil} \ne \mathtt{cons} \\: x \\: y$. Conversely, we can define the largest type that contains all values built from these constructors, keeping the discrimination axiom:

```
CoInductive colist (A:Set) : Set :=
  | conil : colist A
  | cocons : A -> colist A -> colist A.

```

`list` is isomorphic to a subset of `colist`. In addition, `colist` contains infinite lists: lists with `cocons` upon `cocons`.

```
CoFixpoint flipflop : colist ℕ := cocons 1 (cocons 2 flipflop).
CoFixpoint from (n:ℕ) : colist ℕ := cocons n (from (1 + n)).

```

`flipflop` is the infinite (circular list) $1::2::1::2::\ldots$; `from 0` is the infinite list of natural numbers $0::1::2::\ldots$.

A recursive definition is well-formed if the result is built from smaller blocks: recursive calls must work on smaller inputs. A corecursive definition is well-formed if the result builds larger objects. Induction looks at constructors, coinduction looks at destructors. Note how the duality not only changes smaller to larger but also inputs to outputs. For example, the reason the `flipflop` and `from` definitions above are well-formed is that the corecursive call is guarded by a call to the `cocons` constructor in both cases.

Where statements about inductive objects have inductive proofs, statements about coinductive objects have coinductive proofs. For example, let's define the infinite predicate on colists; intuitively, the infinite colists are the ones that don't end with `conil`.

```
CoInductive Infinite A : colist A -> Prop :=
  | Inf : forall x l, Infinite l -> Infinite (cocons x l).

```

To prove that colists of the form `from n` are infinite, we can reason by coinduction. `from n` is equal to `cocons n (from (1 + n))`. This shows that `from n` is larger than `from (1 + n)`, which is infinite by the coinduction hypothesis, hence `from n` is infinite.

### Bisimilarity, a coinductive property

Coinduction as a proof technique also applies to finitary objects. Intuitively speaking, inductive proofs about an object are based on how the object is built. Coinductive proofs are based on how the object can be decomposed.

When studying deterministic systems, it is common to define equivalence through inductive rules: two systems are equivalent if you can get from one to the other by a series of transformations. Such definitions tend to fail to capture the many different ways non-deterministic systems can end up having the same (observable) behavior in spite of having different internal structure. (Coinduction is also useful to describe non-terminating systems, even when they're deterministic, but this isn't what I'll focus on here.)

Nondeterministic systems such as concurrent systems are often modeled by labeled transition systems. An LTS is a directed graph in which the edges are labeled. Each edge represents a possible transition of the system. A trace of an LTS is the sequence of edge labels over a path in the graph.

Two LTS can behave identically, in that they have the same possible traces, even if their internal structure is different. Graph isomorphism is too strong to define their equivalence. Instead, an LTS $\mathscr{A}$ is said to simulate another LTS $\mathscr{B}$ if every transition of the second LTS admits a corresponding transition in the first. Formally, let $S$ be the disjoint union of the states of the two LTS, $L$ the (common) set of labels and $\rightarrow$ the transition relation. The relation $R \subseteq S \times S$ is a simulation if $$ \forall (p,q)\in R, %\forall p'\in S, \forall\alpha\in L, \text{ if } p \stackrel\alpha\rightarrow p' \text{ then } \exists q', \\; q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R $$

$\mathscr{A}$ simulates $\mathscr{B}$ if there is a simulation in which all the states of $\mathscr{B}$ are related to a state in $\mathscr{A}$. If $R$ is a simulation in both directions, it is called a bisimulation. Simulation is a coinductive property: any observation on one side must have a match on the other side.

There are potentially many bisimulations in an LTS. Different bisimulations might identify different states. Given two bisimulations $R\_1$ and $R\_2$, the relation given by taking the union of the relation graphs $R\_1 \cup R\_2$ is itself a bisimulation, since related states give rise to related states for both relations. (This holds for infinite unions as well. The empty relation is an unintersting bisimulation, as is the identity relation.) In particular, the union of all bisimulations is itself a bisimulation, called bisimilarity. Bisimilarity is the coarsest way to observe a system that does not distinguish between distinct states.

Bisimilarity is a coinductive property. It can be defined as the largest fixpoint of an operator: it is the largest relation which, when extended to identify equivalent states, remains the same.

### References

* Coq and the calculus of inductive constructions

+ Yves Bertot and Pierre Castéran. *Interactive Theorem Proving and Program Development — Coq'Art: The Calculus of Inductive Constructions*. Springer, 2004. Ch. 13. \[website\] \[Amazon\]
    + Eduardo Giménez. *An application of co-inductive types in coq: verification of the alternating bit protocol*. In *Workshop on Types for Proofs and Programs*, number 1158 in *Lecture Notes in Computer Science*, pages 135–152. Springer-Verlag, 1995. \[Google Books\]
    + Eduardo Giménez and Pierre Castéran. A Tutorial on \[Co-\]Inductive Types in Coq. 2007. \[PDF\]
* Labeled transition systems and bisimulations

+ Robin Milner. *Communication and Concurrency*. Prentice Hall, 1989.
    + Davide Sangiorgi. *On the origins of bisimulation and coinduction*. ACM Transactions on Programming Languages and Systems (TOPLAS), volume 31 issue 4, May 2009. \[PDF\] \[ACM\] Associated course slides: \[PDF\] \[CiteSeer\]
    + Davide Sangiorgi. *The Pi-Calculus: A Theory of Mobile Processes*. Cambridge University Press, 2003. \[Amazon\]
    + A chapter in *Certified Programming with Dependent Types* by A. Chlipala
    + D. Sangiorgi. "Introduction to Bisimulation and Coinduction". 2011. \[PDF\]
    + D. Sangiorgi and J. Rutten. *Advanced Topics in Bisimulation and Coinduction*. Cambridge University Press, 2012. \[CUP\]
> 70 votes

# Answer
Let us consider the following inductive definition:

$\qquad \displaystyle \begin{align\*} &\phantom{\Rightarrow} \quad \varepsilon \in \mathcal{T} \\ w \in \mathcal{T} \quad &\Rightarrow \quad aw \in \mathcal{T}\\ aw \in \mathcal{T} \quad &\Rightarrow \quad baw \in \mathcal{T} \end{align\*}$

What is $\mathcal{T}$? Clearly, the set of strings with no two subsequent $b$, i.e.

$\qquad \displaystyle \mathcal{T} =\\{\varepsilon, a, aa, ba, aaa, aba, \dots\\} = \mathcal{L}\left((ba\mid a)^\*\right) \subseteq \Sigma^\*.$

Right? Well, what we need for that is the innocuous sentence "and $\mathcal{T}$ is the smallest set that fulfills these conditions". True enough, as otherwise $\mathcal{T}=\\{a,b\\}^\*$ would work, too.

But there is more to it than that. Write above definition as (monotone) function $f : 2^{\Sigma^\infty} \to 2^{\Sigma^\infty}$:

$\qquad f(T) = T \cup \\{\varepsilon\\} \cup \\{aw \mid w\in T\\} \cup \\{baw \mid aw \in T\\}$

Now $\mathcal{T}$ is the *smallest fixpoint* of $f$. In fact, because $f$ is monotone and $\left(2^{\Sigma^\infty},\subseteq\right)$ is a *complete lattice*, Knaster-Tarski theorem tells us that such a smallest fixpoint exists and is a proper language. Because this works with any reasonable¹ inductive definition, we normally don't talk about this. It just fits our intuition: we start with $\\{\varepsilon\\}$ and apply the rules step by step; in the limit, we get $\mathcal{T}$.

Now we turn things around. Instead of saying "if $w$ is included, so is $aw$" we say "if $aw$ is included, so must have been $w$". We can not turn the anchor around, so it goes away. That leaves us with a problem: we have to be able to take *arbitrarily long* prefixes away from any word in $\mathcal{T}'$ and remain in $\mathcal{T}'$! This is not possible with finite words; good thing I sneaked in $\Sigma^\infty$ above! We end up with the set of infinite words without a factor (substring) $bb$, i.e. $\mathcal{T}'=\mathcal{L}\left((ba\mid a)^\omega\right)$.

In terms of $f$, $\mathcal{T}'$ is its *largest* fixpoint². This is actually quite intuitive: we can not hope to hit $\mathcal{T}'$ from *below*, i.e. inductively by starting from $\\{\varepsilon\\}$ and *adding* stuff that fulfills the rules, so we go from *above*, i.e. coinductively by starting from $\Sigma^\infty$ and *removing* stuff that does *not* conform to the rules.

---

*Notation:*

* $\Sigma^\infty = \Sigma^\* \cup \Sigma^\omega$
* $\Sigma^\omega$ is the set of all *infinite* sequences over $\Sigma$.

---

¹ You are not allowed to do stuff like $w \in \mathcal{T} \Rightarrow aw \notin \mathcal{T}$; the corresponding function would not be monotone.
² We have to sweep $\\{\varepsilon\\}$ under the rug somehow.
> 25 votes

---
Tags: terminology, logic, proof-techniques, formal-methods, coinduction
---


# Question
Title: Break an authentication protocol based on a pre-shared symmetric key, with message numbers
Consider the following protocol, meant to authenticate $A$ (Alice) to $B$ (Bob) and vice versa.

$$ \begin{align\*} A \to B: &\quad \text{“I'm Alice”}, R\_A \\ B \to A: &\quad E(\langle 1, R\_A\rangle, K) \\ A \to B: &\quad E(\langle 2, R\_A+1, P\_A\rangle, K) \\ \end{align\*} $$

* $R$ is a random nonce.
* $K$ is a pre-shared symmetric key.
* $P$ is some payload.
* $E(m, K)$ means $m$ encrypted with $K$.
* $\langle m\_1, \ldots, m\_n\rangle$ means an assemblage of the $m\_i$'s that can be decoded unambiguously ($n$ is encoded unambiguously as well).
* We assume that the cryptographic algorithms are secure and implemented correctly.

An attacker (Trudy) wants to convince Bob to accept her payload $P\_T$ as coming from Alice (in lieu of $P\_A$). Can Trudy thus impersonate Alice? How?

<sub> This is a follow-up to Break an authentication protocol based on a pre-shared symmetric key. </sub>

# Answer
*(re-post of my comment as an answer)*

The only party that generates encryptions of messages $m$ such that $m$:

* contains 3 parts
* begins with a "2"

is Alice. Each time she generates such a chipertext, the last component is $P\_A$. If $E$ is a strong enough encryption (non malleable), then Trudy will not be able to generate by herself a an encryption $E(m)$ of a massage in the formt $m=\langle 2,R,P\_T \rangle $ that Bob would accept (except with negligible probability).
> 2 votes

---
Tags: cryptography, protocols, authentication
---


# Question
Title: Are two-level schedulers only useful to manage swapping?
Two-level scheduling is useful when a system is running more processes than fit in RAM: a lower-level scheduler switches between resident processes, and a higher-level scheduler swaps groups of processes in and out.

I find no other mention of two-level scheduling in Andrew Tanenbaum's *Operating Systems: Design and Implementation*, 1st ed. Exercise 2.22 asks why two-level scheduling might be used; I don't know whether it's there as a reading comprehension check or there are other reasons not prominently mentioned in the text.

Is two-level scheduling useful to manage other resource contentions, besides memory?

# Answer
> 8 votes
There are other forms of two-level scheduling than the type you describe. For example, one level of scheduling could be per-user and the other could be per-process, aiming for giving a user with 20 processes the same amount of CPU time as a user with 1 process. With a single-level scheduler, each process might get 1/21 of the CPU time.

Another form of two-level scheduling could be per-process and per-thread, aiming to give a process with 20 threads the same amount of CPU time as a process with 1 thread.

---
Tags: operating-systems, process-scheduling
---


# Question
Title: When are two simulations not a bisimulation?
Given a labelled transition system $(S,\Lambda,\to)$, where $S$ is a set of states, $\Lambda$ is a set of labels, and $\to\subseteq S\times\Lambda\times S$ is a ternary relation. As usual, write $p \stackrel\alpha\rightarrow q$ for $(p,\alpha,q)\in\to$. The labelled transition $p\stackrel\alpha\to q$ denotes that the system in state $p$ changes state to $q$ with label $\alpha$, meaning that $\alpha$ is some observable action that causes the state change.

Now a relation $R \subseteq S \times S$ is a called a *simulation* iff $$ \forall (p,q)\in R, \text{ if } p \stackrel\alpha\rightarrow p' \text{ then } \exists q', \\; q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R. $$

One LTS is said to *simulate* another if there exists a simulation relation between them.

Similarly, a relation $R \subseteq S \times S$ is a *bisimulation* iff $\forall (p,q)\in R,$ $$ \begin{array}{l} \text{ if } p \stackrel\alpha\rightarrow p' \text{ then } \exists q', \\; q \stackrel\alpha\rightarrow q' \text{ and } (p',q')\in R \text{ and } \\ \text{ if } q \stackrel\alpha\rightarrow q' \text{ then } \exists p', \\; p \stackrel\alpha\rightarrow p' \text{ and } (p',q')\in R. \end{array} $$

Two LTSs are said to be bisimilar iff there exists a bisimulation between their state spaces.

Clearly these two notions are quite related, but they are not the same.

> Under what conditions is it the case that an LTS simulates another and vice versa, but that the two LTSs are not bisimilar?

# Answer
Because a CCS process is worth a thousand pixels – and it is easy to see the underlying LTS – here are two processes that simulates each other but are not bisimilar:

$$P = ab + a$$ $$Q = ab$$

$\mathcal{R\_1}=\\{(ab+a, ab), (b, b), (0,b), (0, 0)\\}$ is a simulation.

$\mathcal{R\_2}=\\{(ab, ab+a), (b, b), (0,0)\\}$ is a simulation.

$P\ \mathcal R\_1\ Q$ and $Q\ \mathcal R\_2\ P$ but $P$ and $Q$ are not bisimilar. Why not? Because $P\stackrel{a}→0$ and the only $Q'$ such that $Q\stackrel{a}→Q'$ is $b$ ... and $0$ is not bisimilar to $b$.

Why can they simulate each other, then? Because $P$ simulates $Q$ since it can do everything $Q$ does. And $Q$ simulates $P$ because even if $P$ can go in one $a$-step to a program that does nothing, $Q$ can still do that $a$-step, and that's all it takes to simulate something. The key difference with the bisimulation is really that, as Charles said, you have to relate the same processes with both simulations. (i.e. $\mathcal R$ such that both $\mathcal R$ and $\mathcal R^{-1}$ are simulations)
> 12 votes

# Answer
Even if there's a simulation in each direction, the simulations back and forth may not relate the same sets of states. Sometimes you have a simulation $R\_1$ in one direction, and a simulation $R\_2$ in the other direction, and two states $p\_1$ and $q$ which are related by $R\_1$ but not by $R\_2$ nor by any other simulation in the same direction.

The canonical example is two systems which have the same traces, yet make **choices** differently. Consider two drinks machines: the first machine (the evil one) takes a coin (`c`) and non-deterministically decides whether to deliver a cup of tea (`t`). The second machine (the good one) takes a coin (`c`) and delivers a cup of tea (`t`).

The good machine simulates the evil machine: take $R\_1 = \\{(s,s'), (p,p'), (q,q'), (r,p')\\}$. All states' outgoing transitions are covered, including $r$ (which has no outgoing transition, so it's trivial). Notice how the good machine forgets the difference between $r$ and $p$.

The evil machine simulates the good machine: take $R\_2 = \\{(s',s),(p',p),(q',q)\\}$. The state $r$ happens not to be used by this simulation. In fact, it is not possible for a simulation to use $r$, since $s'$ must map onto a state from which a trace of length $2$ is possible, so it has to be $s$; $p'$ has to map to a successor of $s'$ with the label $c$, so it's $p$ or $r$, but that state also has to have a possible trace of length $1$, so it has to be $p$; and by the same reasoning $q'$ must map to $q$, leaving no possibility of mapping any state to $r$.

A simuation in one direction must send $r$ somewhere. A simulation in the other direction must avoid $r$. Therefore there is no relation that is a simulation in both directions: the systems are not bisimilar.

The difference between the two machines is that the good machine is deterministic and (assuming liveness) always delivers tea if you insert a coin, whereas the evil machine may on a whim take the coin but become stuck, unable to deliver tea.

This kind of difference comes up often in the study of concurrent systems. jmad's answer shows a CCS process with this LTS.

For more information about bisimulations, I recommend Davide Sangiorgi's notes *On the origins of bisimulation and coinduction*. (This is exercise 1 p. 29, and the notes use the same example.)
> 10 votes

# Answer
Gilles' answer is very good and formal, and indeed, if $LTS\_1$ is simulated by $LTS\_2$ with a relation $R$, and $LTS\_2$ is simulated by $LTS\_1$ with the inverse of $R$, then $R$ is a bisimulation.

However, if the two relations are not the inverse of one another, then you might not be able to build a bisimulation. For instance, a simple example comes from the fact that the empty relation is simulation for any LTS. So, we can have $LTS\_1$ is simulated by $LTS\_2$ with a relation $R$, and $LTS\_2$ is simulated by $LTS\_1$ with the empty relation, and yet $R$ is not necessarily a bisimulation (although note that the empty relation is also a bisimulation for any LTS).
> 2 votes

---
Tags: programming-languages, formal-methods, semantics, process-algebras
---


title: Saving on array initialization

text:
# Question
Title: Saving on array initialization
I recently read that it is possible to have arrays which need not be initialized, i.e. it is possible to use them without having to spend any time trying to set each member to the default value. i.e. you can start using the array as if it has been initialized by the default value without having to initialize it. (Sorry, I don't remember where I read this).

For example as to why that can be surprising:

Say you are trying to model a *worst* case $\mathcal{O}(1)$ hashtable (for each of insert/delete/search) of integers in the range $\[1, n^2\]$.

You can allocate an array of size $n^2$ bits and use individual bits to represent the existence of an integer in the hashtable. Note: allocating memory is considered $\mathcal{O}(1)$ time.

Now, if you did not have to initialize this array at all, any sequence of say $n$ operations on this hashtable is now worst case $\mathcal{O}(n)$.

So in effect, you have a "perfect" hash implementation, which for a sequence of $n$ operations uses $\Theta(n^2)$ space, but runs in $\mathcal{O}(n)$ time!

Normally one would expect your runtime to be at least as bad as your space usage!

Note: The example above might be used for an implementation of a sparse set or sparse matrix, so it is not only of theoretical interest, I suppose.

So the question is:

> How is it possible to have an array like data-structure which allows us to skip the initialization step?

# Answer
> 16 votes
This is a very general trick, which can be used for other purposes than hashing. Below I give an implementation (in pseudo-code).

Let three uninitialized vectors $A$, $P$ and $V$ of size $n$ each. We will use these to do the operations requested by our data structure. We also maintain a variable $pos$. The operations are implemented as following:

```
init:
  pos <- 0

set(i,x):
if not(V[i] < pos and P[V[i]] = i)
  V[i] <- pos, P[pos] <- i, pos <- pos + 1
A[i] <- x

get(i):
if (V[i] < pos and P[V[i]] = i)
  return A[i]
else
  return empty

```

The array $A$ simply stores the values that are passed through the $set$ procedure. The arrays $V$ and $P$ work as certificates that can tell if a given position in $A$ has been initialized.

Note that at every moment the elements in $P$ ranging from $0$ to $pos-1$ are initialized. We can therefore safely use these values as a certificate for the initialized values in $A$. For every position $i$ in $A$ that is initialized, there is a corresponding element in the vector $P$ whose value is equal to $i$. This is pointed by $V\[i\]$. Therefore, if we look at the corresponding element, $P\[V\[i\]\]$ and its value is $i$, we know that $A\[i\]$ has been initialized (since $P$ never lies, because all the elements that we're considering are initialized). Similarly, if $A\[i\]$ is not initialized, then $V\[i\]$ may point either to a position in $P$ outside the range $0..pos-1$, when we know for sure that it's not initialized, or may point to a position within that range. But this particular $P\[j\]$ corresponds to a different position in $A$, and therefore $P\[j\] \neq i$, so we know that $A\[i\]$ has not been initialized.

It's easy to see that all these operations are done in constant time. Also, the space used is $O(n)$ for each of the vectors, and $O(1)$ for the variable $pos$, therefore $O(n)$ in total.

---
Tags: data-structures, arrays
---