# Question
Title: Typical set in Shannon's source coding theorem
I was following the textbook by David Mackay: *Information theory inference and learning algorithms*.

I have question on asymptotic equiparition' principle:

> For an ensemble of $N$ $i.i.d$ random variables $X^N=(X\_1,X\_2....X\_N),$ with $N$ sufficiently large, the outcome $x=(x\_1,x\_2...x\_N)$ is almost certain to belong to a subset of $|A\_x^N|$ having only $2^{NH(x)}$ members, with each member having probability "close-to" $2^{-NH(x)}$.

And then in the textbook, it also says that **typical set doesn't nesscarry to contain the most probable element set.**

On the other hand, "smallest-sufficient set" $S\_{\delta}$ which defines to be:

> the smallest subset of of $A\_x$ satisfying $P(x\epsilon S\_{\delta})\ge 1-\delta $, for $0\leq{\delta}\leq1. $ In other words, $S\_{\delta}$ is constructed by taking the most probable elements in $A\_x$, then the second probable......until the total probabily is $\ge1-{\delta}$.

My question is, **as $N$ increases, does $S\_{\delta}$ approaches typical set such that these two sets will end up be equivalent of each other?** If the size of the typical set is identical to the size of $|S\_{\delta}|$, then why are we even bother with $S\_{\delta}$? Why can't we just take the typical set as our compression scheme instead?

# Answer
> 2 votes
The elements in the typical set have typical probability, close to $2^{-NH(x)}$. An element with untypically large probability, say the one with maximal probability, may not satisfy this constraint. Same goes for the rest of $S\_\delta$.

The source coding theorem *does* take the typical set as an *encoding* scheme.

---
Tags: sets, coding-theory, encoding-scheme
---


# Question
Title: The complement of $\{w: w\text{ has equal numbers of $a$'s, $b$s' and $c$'s}\}$ is context-free
Let $L$ be the language $\\{w \mid w \text{ has equal numbers of \\(a\\)'s, \\(b\\)'s and \\(c\\)'s}\\}$. Prove that its complement $\overline{L}$ is context free.

# Answer
So let us remember the closure properties of context-free languages, gone over in class and stated by the TFS:

```
* closed under union
* closed under concatenation
* closed under Kleene Star

```

Now I will show that my language $L'$ is the same as the language $L$. Let $NE(x,y,z)$ be an operation that generates a language such that the number of x's is not the same as the number of y's, with as many z's as one wants anywhere in the language. Thus my language $L'$ is defined as:

$$ NE(a,b,c) \cup NE(c,a,b) \cup NE(b,c,a) $$

This language is obviously $L$. It is all instances of a not equal to b, b not equal to c, and c not equal to a. The nice thing here is that if we prove $NE()$ is context free, then because of symetry and closure under union operation. Let us represent NE as a PDA here:

$$ (s,\epsilon,\epsilon) \rightarrow (p,\\$) $$ $$ (p,a,\epsilon) \rightarrow (p,1) $$ $$ (p,b,1) \rightarrow (p,\epsilon) $$ $$ (p,b,\\$) \rightarrow (m,1\\$) $$ $$ (p,c,\epsilon) \rightarrow (p,\epsilon) $$ $$ (m,c,\epsilon) \rightarrow (p,\epsilon) $$ $$ (m,b,\epsilon) \rightarrow (m,1) $$ $$ (m,a,1) \rightarrow (m,\epsilon) $$ $$ (m,a,\epsilon) \rightarrow (p,1\\$) $$ $$ (p,\epsilon,a) \rightarrow (f,\epsilon) $$ $$ (p,\epsilon,b) \rightarrow (f,\epsilon) $$ $$ (m,\epsilon,a) \rightarrow (f,\epsilon) $$ $$ (m,\epsilon,b) \rightarrow (f,\epsilon) $$

So now that I have represented this language as a PDA, all I need to show is that the language I represented corresponds to $NE()$.

First I will show that my PDA, $X$ is $X \subseteq NE$. This is quite easy to see. The only way that one can enter a final state in $X$ is when, under one of our rules, we hit the end of the string, and there is something left on the stack (meaning that there is an unequal number of either a's or b's). we can see here that this is a subset.

Next I will show that $X \supseteq NE$, or in other words, all strings that are part of $NE()$ can be made by $X$. One can see that one can have as many c's as one wants in this model, by the rules: $ (p/m,c,\epsilon) \rightarrow (p/m,\epsilon) $, so that is not a problem. But how does it promise that all strings of unequal number of a's and b's are not in this language. Again, the grammar only keeps track of how many excess a's or b's there are, and can accept any string of arbitrary length with any permutation of letters as long as one of a or b, has an excess. Thus $X \supseteq NE$.

I have shown that $NE$ is Context Free by building a PDA, and I have shown that $L$ is a finite union of $NE$s, thus $L$ is context-free.
> 3 votes

# Answer
Hint: if $w \notin L$ then for some two characters $\alpha,\beta$, $w$ has more of $\alpha$ than of $\beta$. It is enough to show that each such language $L\_{\alpha\beta}$ is context-free. Here the idea is to suitably modify a grammar for $\\{ w : w \text{ has the same number of $\alpha$'s as $\beta$'s}\\}$.
> 1 votes

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


# Question
Title: PERMUTE-BY-SORTING with similar priorities
Let $a$ and $b$ be integers, and let $\text{RANDOM}(a,b)$ be a method returning an integer from the range $\[a,b\]$ uniformly at random. Now consider the following program, that takes as input an array $A$ of integers.

```
PERMUTE-BY-SORTING(A)
    1. n = A.length
    2. let P[1..n] be a new array
    3. for i = 1 to n
    4.     P[i] = RANDOM(1, n^3)
    5. sort A, using P as sort keys

```

I'm solving the problem 5.3-6 in CLRS, which is asking me to explain how to implement the algorithm PERMUTE-BY-SORTING to handle the case in which two or more priorities are identical. In other words, the algorithm should produce a uniform random permutation, even if two or more priorities are identical.

Because priorities are repeated in $P$, we will not get a uniform random permutation. I thought of adding `i` to step 4 but that doesn't produce the uniform random permutation. More specifically, the problem is that if two or more priorities are identical we will not get a uniform random permutation since the probability is not same for all the numbers. Ex 1,2,2,3 the probability of 2 in the example is 1/2 and the probability of 1 is 1/4 and 3 is 3/4.

# Answer
The easiest way is to generate a random permutation in $P$. Here is pseudocode:

1. Initialize $P$ with $P\[i\] = i$ for $i = 1,\ldots,n$.
2. Repeat for $i = 1,\ldots,n-1$:
    1. Let $j$ be a random number in the range $i,\ldots,n$.
    2. Swap $P\[i\]$ and $P\[j\]$.
> 5 votes

# Answer
If our initial array is A = \<1, 2, 3, 4\> and we choose random priorities P = \<36, 3, 97, 19\>, we would produce an array B = \<2, 4, 1, 3\>

Now if random priority array P= \<36,3,3,19\> and now we use elements of P to sort array A, using say merge sort, our resulting array B would be \<2,3,4,1\>. As we saw, all the elements are still equally likely to be produced.
> -2 votes

# Answer
A way to do is this:

```
PERMUTE-BY-SORTING-2(A)
 1. n=A.length
 2. Let P be an array [1 .. n^3]
 3. Initialize P with P[i]=i for i=1,...,n^3.
 4. For i=1,…,n:
 5.     Let j be a random number in the range i,…,n^3.
 6.     Swap P[i] and P[j].
 7. sort A[1..n], using P[1..n] as sort keys

```

However this only produces unique priorities in P\[1..n\]. Thus avoiding rather than handing the case where P\[1..n\] has non-unique numbers.
> -2 votes

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


title: Is a door lock a finite state machine?

text:
# Question
Title: Is a door lock a finite state machine?
Must the states of a finite state machine be worked off sequentially or could you understand the different shaped parts of the key as input and the position of the pins as states?
If not all the input is right: failure state = stays locked
If all the input is right: end state = lock opens

I was inspired by this (German grammar-school) resource, where on page 7 are diagrams of a combination lock as a finite state machine.

# Answer
> 2 votes
Yes and no. Arguably, the lock is not a *finite* state machine, since the key can be inserted to any degree and, if it fits, rotated through any angle. However, we can abstract away these unimportant details, yes, the system can be modeled as a finite number of states: essentially, if you code up the ridges of the key as symbols in some alphabet, the lock is a DFA that accepts exactly one word (or perhaps more, if there's a master key).

---
Tags: automata, finite-automata
---


# Question
Title: Efficient representation of a given surjective function $\{1 \ldots N\} \rightarrow \{1 \ldots M\}$ when $N \gg M$
More precisely: The input is set of $M$ sets (most likely stored sequentially on disk) that contain partitions of the set $\\{1..N\\}$. I want to efficiently (as far as memory and time complexity goes) represent this structure. Let's call this hypothetical structure $S$. I need the structure to support just a single function $p : S \times \\{1 \ldots N\\} \rightarrow \\{1 \ldots M\\}$.

It's also safe to assume that I will call this function in order, meaning I will be interested first in $p(S, 1)$, then in $p(S,2)$, etc.

I can represent this structure as an array of $N \times \lceil log\_2(M)\rceil$ bits, but that seems too memory inefficient when $M$ is small and $N$ is in billions. I have a hunch that perfect-hashing might be of use here.

# Answer
You can reduce your $N \lceil \log\_2 M \rceil$ bits to $\lceil N \log\_2 M\rceil$ by using Dodis et al's "Changing Base without Losing Space".

I don't think you're going to get much smaller than $N \log\_2 M$ bits. For $N \gg M$, many functions will be surjective. In particular, there are $\\{{N \atop M}\\}$ surjective functions, which is at least $M^{N-M}$. Thus, at least $\log\_2 \left(M^{N-M}\right) = N \log\_2 M - M \log\_2 M \in \Omega(N \log\_2 M)$ bits must be used to represent one, on average.
> 4 votes

# Answer
You essentially want to store a compressed string of size N, with characters from an alphabet of size M. I suspect that wavelet trees http://www.dcc.uchile.cl/~gnavarro/ps/cpm12.pdf may be exactly what you need. They are a "succinct data structure", which means they take almost the information-theoretically optimal amount of space.
> 1 votes

---
Tags: data-structures, hash, hash-tables
---


title: Is this variant of ATM decidable?

text:
# Question
Title: Is this variant of ATM decidable?
Ok so I understand how $\mathrm{ATM} = \\{\langle M,w \rangle \mid \text{$M$ is a TM and $M$ accepts $w$}\\}$ is undecidable.

Is this because $w$ is a variable?

What if the parameter is fixed?

Consider $\mathrm{BTM} = \\{\langle M,w \rangle \mid \text{$M$ is a TM and $M$ accepts the string 101}\\}$.

BTM is decidable right? The diagnolization problem here doesn't seem to apply because it would seem trivial to build a Turing machine that is 100% capable of accepting only the input "101" and rejecting every other possible input, correct?

And our machine would always reject itself as an input, since it only accepts "101", right?

# Answer
> 3 votes
You can show that $\mathrm{BTM}$ is undecidable with a simple reduction from $\mathrm{ATM}$.

Let $\langle M,w\rangle \in ATM$. We define the reduction function $f$, $\mathrm{HP} \leq \mathrm{BTM}$ as follow:

$f(\langle M,w\rangle) = M\_w $, Where $M\_w$ on every input $x$, runs $M$ with input $w$. if $M$ stopped, then $M\_w$ accepts $x$. if $M$ rejects, then $M\_w$ rejects. Clearly, if $\langle M,w\rangle \in ATM$ then $L(M\_w) = \Sigma^\*$, and in particular $101 \in L(M\_w)$. if $\langle M,w\rangle \notin ATM$ then $L(M\_w) = \emptyset$, and $101 \notin L(M\_w)$.

Because $\mathrm{ATM} $is undecidable, so is $\mathrm{BTM}$.

It should be intuitive that $\mathrm{BTM}$ is undeciadble, because given a turing machine $M$, you can't tell if $M$ will **halt** with input $101$

# Answer
> 1 votes
BTM is also undecidable, with a similar diagonalization proof. Suppose the Turing machine $M$ decided BTM. Define a Turing machine $T$ that, on input $x$ an encoding of a Turing machine, it computes the encoding $y\_x$ of a Turing machine which runs the Turing machine encoded by $x$ on input $x$; if $M(y\_x)=1$ then $T$ gets into an infinite loop, and otherwise it halts. Then $T$ halts on input $\\#T$ (where $\\#T$ is the encoding of $T$) iff $M(y\_{\\# T})=0$ iff $y\_{\\# T}$ doesn't halt on 101 iff $T$ doesn't halt on input $\\#T$, contradiction.

---
Tags: computability, undecidability
---


# Question
Title: Does the complement of sigma Kleene star exist?
If $\Sigma^\*$ is the set of ALL strings including the empty string, then what can its complement possibly be? The empty set?

# Answer
Yes, the complement of all possible strings1 is no strings at all. A machine that decides $\Sigma^\*$ accepts every input; a machine that decides the complement of $\Sigma^\*$ rejects every input.

1 Strictly speaking, all finite strings over some fixed alphabet $\Sigma$.
> 1 votes

# Answer
Note that the complement of $A \subseteq \Sigma^\*$ is defined as $\Sigma^\* \setminus A$; so yes: the complement of $\Sigma^\*$ itself is the empty set.

To be completely accurate, you need to state with respect to *which universe* you want to take the complement. For instance, if you were to take the complement of $\Sigma^\*$ w.r.t. $\Sigma'^\*$ where $\Sigma' = \Sigma \mathbin{\dot\cup} \\{a\\})^\*$, $a \not\in \Sigma$, it would not be empty but $\Sigma'^\* \cdot \\{a\\} \cdot \Sigma'^\*$ (the set of words with at least one $a$).
> 2 votes

---
Tags: formal-languages
---


# Question
Title: Prove that REG is closed against removing all but lexicographicaly largest words (per length)
> Let $\Sigma\_n = \\{0, 1, ... , n-1\\}$. Suppose $L \subseteq$ $\Sigma^\*\_n$, and let
>
> $\qquad\displaystyle\mathcal{B}(L) = \\{ x \in L : x = \textrm{lex}\max L\_m, m \in \mathbb{N}\_0 \\}$,
>
> where $L\_m = L \cap \Sigma\_n^m$ and $\mathrm{lex}\max$ denoting the lexicographic maximum.
>
> For example, $\mathcal{B}(\\{0,1\\}^\*) = 1^\*$ and $\mathcal{B}(\epsilon \cup 1(0 \cup 01)^\*) = (10)^\*(\epsilon \cup 1)$. Prove that if $L$ is regular, then so is $\mathcal{B}(L)$.

Any hints? I was thinking of perfect shuffling $L$ with itself, and then defining a morphism to compare each pair of characters in a shuffle to determine which is the lexicographically greater one.

# Answer
Here is the basic idea. Suppose that $x0y \in L$. When would $x0y \notin \mathcal{B}(L)$? Exactly when $x1z \in L$ for some $|z| = |y|$. When does that happen? Fix some DFA for $L$, and suppose that after reading $x1$, it is at state $q$. Parikh's theorem shows that the set of lengths $\ell$ such that $x1z \in L$ for some $|z| = \ell$ is eventually periodic, that is, it is of the form $L\_0(q) \cup \\{k m(q) + a : a \in L\_1(q) \text{ and } k \geq 0\\}$ for some finite $L\_0(q),L\_1(q)$. We can further assume that $m(q) = m$ is the same for all states $q$, since there are only finitely many of them and we can take the LCM of the minimal periods.

As we read more and more zeroes, we obtain more and more constraints, which can be summarized in the form: the word cannot end in $\ell$ characters for $\ell \in L\_0 + \\{ km + a : a \in L\_1 \\}$. Note that there are only finitely many possibilities for $L\_0$ and $L\_1$, since $\max L\_0 \leq \max\_q \max L\_0(q)$, and similarly for $L\_1$. This means that we can store and maintain this information in a finite state automaton, and use it to decide $\mathcal{B}(L)$.
> 3 votes

# Answer
Consider the language $\mathrm{less}(L)$ of all strings that are of the same length as one in $L$ but lexicographically less. For a two letter alphabet these are strings of the form $x0z$ with $x1y\in L$ and $|y|=|z|$.

Now $\mathrm{less}(L)$ is regular, and can be accepted by a nondeterministic automaton. It runs as the original automaton $\mathcal A$ for $L$, but at some nondeterministic point, when $\mathcal A$ reads a $1$, then the new automaton reads a $0$. Now the new automaton reads any letter (from $z$), and takes a step on whatever letter in $\mathcal A$ (the corresponding $y$). It accepts when this simulation accepts.

If everything goes well, then $\mathcal B(L) = L - \mathrm{less}(L)$ is regular.
> 3 votes

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


# Question
Title: Interpret bits as a signed integer in 2s complement
Imagine you load this data as a `4-byte word` into a register R. What is the value in `R` on a **big endian** machine and what is it on a **little endian** machine if you **interpret the bits as a signed integer encoded in 2s complement**

On a big endian machine the register R would be something like this

not considering the last sentence, **interpret the bits as a signed integer encoded in 2s complement**, which I don't understand completely.

Should I convert all bits, 0s to 1s and 1s to 0s and then sum 1 to all the string or to sum 1 to each byte in the string?

Thanks.

# Answer
> 1 votes
To convert a 4-byte = 32-bit *word* to its negative you apply the two's complement *operator*. The operator is, as you said, invert all the bits, then add 1 to the *word*.

You can tell a 4-byte = 32-bit word represents a positive value if its most significant bit (the one all the way on the left) is "0". If the most significant bit is a "1" then the 32-bit word represents a negative value. Thus your example big-endian register, 01001101101101101111001111010111 must represent a positive number.

I assume you know how to convert a positive binary number to its decimal or hexadecimal equivalent. The hexadecimal equivalent of 01001101101101101111001111010111, for example, is 0x4db6f3d7.

If, on the other hand the leading bit had been a "1", as in, (just making a number up): 11001101101101101111001111010111 that represents a negative number. The negative of what positive number? The positive number that you will get if you apply the two's complement operator. Flip the bits and add 1. So the negative of 11001101101101101111001111010111 must be 00110010010010010000110000101000 \+ 1 = 00110010010010010000110000101001, which is hexadecimal 0x32490c29 so 11001101101101101111001111010111 must be -0x32490c29.

---
Tags: computer-architecture
---


# Question
Title: Definition of “K-fairness” with respect to concurrency?
There are definitions of Absolute, Strong and Weak Fairness available across the internet, but I cannot find a definition of "K-Fairness" property for critical section algorithms (also algorithms that satisfy a 1-fairness or 3-fairness property). Does this actually exist or is this something that was made up to describe a phenomenon that I am not recognizing?

# Answer
Perhaps you should look for "bounded fairness", the property that something happens within the next $k$ times, where $k$ is the bound.
> 1 votes

# Answer
It should refer the paper: Ryan Porter, Yoav Shoham and Moshe Tennenholtz, "Fair imposition", *Journal of Economic Theory* 118(2):209–228, 2004. (doi, Science Direct)
> 0 votes

---
Tags: concurrency
---


# Question
Title: Algorithm for maximum independent set in trees
While studying the dynamic programing algorithm for the maximum independent set problem in trees I thought about the following simple alternative algorithm. I tried to prove it's correctness but I do not know how to attack the proof.

The algorithm iteratively finds a two vertices $u,v$ of the tree which have maximum distance among all pairs of vertices, puts $u$ in the independent set and removes $u$ and its neighbor from the tree. This procedure is continued until no more vertices are in the tree.

Does anybody have an idea how to prove that this indeed yields a maximum independent set?

# Answer
**Lemma.** Every tree $T$ with at least three vertices has a maximum-cardinality independent set which includes all its leaves.

*Proof.* Let $I$ be a maximum-cardinality independent set containing the greatest number of leaves of $T$ of all such independent sets. Suppose that $v\notin I$ for some leaf $v$ of $T$ and let $w$ be $v$'s unique neighbour. If $w\notin I$, then $I\cup\\{v\\}$ is independent, contradicting the supposed maximality of $I$. Otherwise, $w\in I$ but $I' = (I\setminus\\{w\\}) \cup \\{v\\}$ is an independent set of the same cardinality as $I$. Since $T$ has at least three vertices, $w$ has degree at least two, so is not a leaf. Therefore, $I'$ contains one more leaf than $I$, again contradicting the choice of $I$. $\square$

Now we can see that the algorithm proposed in the question produces a maximum-cardinality independent set because it actually mimics a particular set of choices by the dynamic programming algorithm. Let $v$ and $w$ be vertices in the tree at maximal distance (which must, of course, be leaves). By the lemma, there is a maximum-cardinality independent set that includes both of these vertices. Therefore, we can pick either one to add to our independent set.

Note that there is a slight wrinkle in the algorithm as presented in the question. Suppose $v$ and $w$ are at maximal distance in $T$ and we decide to add $v$ to our independent set. We delete $v$ and its neighbour $v'$ from $T$. However, if $v'$ had degree at least three, we have disconnected the tree. This is OK because, by maximality of the distance from $v$ to $w$, all but one of the neighbours of $v'$ must have been leaves, so all but one of the components of $T-\\{v,v'\\}$ are isolated vertices. But these isolated vertices must also be added to the independent set and deleted from $T$. If they are not, then $d(v'',x)=\infty$ for any isolated vertex $v''$ and *any* other vertex $x$. Thus, the algorithm would be entitled to add any vertex $x$ to the independent set at the next step, which is not guaranteed to lead to a maximum-cardinality independent set (and, indeed, might disconnect the graph even more when we delete it and its neighbours).
> 5 votes

---
Tags: algorithms, trees
---


# Question
Title: How can one search in O(log n) time in a red-black tree?
How does the *search operation* for a red-black tree work and how does it take $O(\log n)$ time, where $n$ is the number of items? I know a red-black tree takes $O(\log n)$ recolorings and $O(1)$ rotations, but I was specifically interested in a good description of its search operation.

# Answer
> 8 votes
The search operation is the same for all binary search trees - recurse into the left or right branch depending on whether the element is smaller or larger than the current root. Red-black trees are not special.

The complexity of the search operation is equal to the height of the tree.

Different varieties of binary search trees differ in what guarantees on height of the tree they give, and in how exactly they maintain these guarantees. Red-black trees and AVL trees give you guaranteed O(log n) height, which is why search is O(log n).

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


# Question
Title: Array-like immutable (persistent) data structure implementation with fast indexing, append, prepend, iteration
I'm looking for a persistent data structure similar to array (but immutable), allowing for fast indexing, append, prepend, and iteration (good locality) operations.

Clojure provides persistent Vector, but it's only for fast append. Scala's Vector has effectively constant-time append and prepend, but I can't get how it's implemented, since it's based on same data structure (bit-mapped vector trie) as Clojure vector, and, as I understand, bit-mapped vector trie can't have fast prepend without some tricks.

I'm interested not in ready to use implementation but in a description of how to implement such a data structure myself.

# Answer
> 13 votes
The obvious candidate is a persistent balanced binary tree. All the operations you listed can be performed in $O(1)$ or $O(\lg n)$ time, using path copying. For more details on how to achieve this runtime, see Chris Okasaki's book referenced below or my answer here.

Of course, as an variant, each leaf of such a tree could itself contain an immutable array (a sequence of consecutive values). This makes updating a value less efficient, but it might work well for your situation, if you never intend to modify an existing value, just append and prepend. In this way, your vector is represented as a sequence of immutable sequences, represented as a balanced binary tree with immutable arrays in the leaves. This allows for fast indexing (logarithmic in the number of leaves), fast append and prepend, and fast iteration. The worst-case asymptotic complexity is no better, but the performance in practice might be significantly better.

The standard reference is Chris Okasaki's 1998 book "Purely functional data structures".
See also

# Answer
> 4 votes
I have described one implementation of such a data structure in my article about incremental regular expression matching - see http://jkff.info/articles/ire/#ropes-strings-with-fast-concatenation and the text below and above that section.

It's a variety of a constant-height tree (like B-trees or 2-3 trees). Basically it's a (2,3) tree, whose leaves are (N, 2N-1) arrays, in order to avoid per-element overhead. (A (N, 2N-1) array is an array whose lengths in the range N..2N-1.) Larger N gives you smaller overhead but linearly increases the complexity of splitting and concatenation. Operations such as indexing, splitting and concatenation are very similar to the way they work in 2-3 trees, generalizing to (N, 2N-1) at the leaf level.

---
Tags: data-structures, functional-programming, persistent-data-structure
---


# Question
Title: Divide and conquer algorithm to sort nk items in n lists that runs in O(nk*logn) time?
In trying to write pseudocode for it, this is my attempt:

I'm just trying to write a pseudo-code for it and explain the run time.

So far this is what I have:

```
k-merge-sort(L)
  { if length(L1) <2 return L1
   else
     { split L into L1, L2, L3
     A1 = k-merge-sort(L1)
     A2 = k-merge-sort(L2)
     ....
     An = k-merge-sort(Ln)
     Bn = k-merge(A1..An)
     }

```

Thoughts? Thank you! As for the run time, the logn part of it comes for it being a complete binary tree's height, the height being the number of lists and the n\*k part from the items.

# Answer
This is classic multi-way merge: Create a heap of pairs (element, which list did it come from). Initialize with first elements of each list. Repeatedly remove the minimum element and add the next element from its originating list.

Also discussed before at https://stackoverflow.com/questions/5055909/algorithm-for-n-way-merge .
> 1 votes

---
Tags: algorithms, divide-and-conquer
---


# Question
Title: What all can a valid approximation algorithm access?
For example can an approximation algorithm call a subroutine which is solving a NP-Hard problem? (like say its trying to find the longest path in some graph as an intermediate step) Is that allowed?

# Answer
> 3 votes
Depends. Typically, with "approximation algorithms" people understand algorithms that run in polynomial time and return a possibly non-optimal solution (with a formal guarantee on the solution quality). In this definition, **no**, you can't spend exponential time solving an NP-hard problem.

On the other hand, nothing is forcing you to consider polynomial time algorithms that return non-optimal solutions. In fact, it is interesting to consider algorithms that take exponential time, and still return non-optimal solutions. See for instance \[1, 2\].

---

\[1\] Cygan, Marek, Lukasz Kowalik, Marcin Pilipczuk, and Mateusz Wykurz. "Exponential-time approximation of hard problems." arXiv preprint arXiv:0810.4934 (2008).

\[2\] Cygan, Marek, Łukasz Kowalik, and Mateusz Wykurz. "Exponential-time approximation of weighted set cover." Information Processing Letters 109, no. 16 (2009): 957-961.

# Answer
> 1 votes
It depends entirely on what complexity you want your algorithm to have. For example, if you're trying to approximate an **EXP**-hard problem then a polynomial algorithm that uses an **NP** oracle might be acceptable; if you're trying to approximate something that's only **NP**-hard, using an **NP** oracle more than once would be potentially more expensive than just solving the problem exactly.

---
Tags: algorithms, approximation
---


# Question
Title: Decide whether there exists a walk of weight exactly k
Consider the following problem:

*Input:* a directed graph $G = (V,E,\omega)$ where $\omega : E \longrightarrow \mathbb{Z}$, two vertices $v\_1, v\_2 \in V$, and a weight $k \in \mathbb{Z}$

*Question:* Does there exist a walk from $v\_1$ to $v\_2$ with weight exactly $k$?

The weight of a walk is simply the sum of all edges in the path. Note that the walk can contain cycles.

Is this problem decidable? Is there any algorithm to solve this problem, if I don't care about the running time? My problem is that since we can have edges weighted with either positive or negative integers, it is hard to determine when to stop or turn back when it gets too low or too high.

For example, given the graph $G$ where $V = \\{ v\_1,v\_2 \\}$ and $E = \\{e\_1:(v\_1,v-1), e\_2:(v\_1,v\_2)\\}$ and $\omega(e\_1)=-2$ and $\omega(e\_2)=1$, the question could be is there a walk from $v\_1$ to $v\_2$ with weight $-99$. The algorithm should say yes, as there is a walk starting from $v\_1$ and self looping 50 times over edge $e\_1$ before taking edge $e\_2$ and terminating.

I previously asked about the complexity of a similar problem here, but there I was focused on the complexity of the problem. Others have shown that this problem is NP-hard. Also, the previously question asked about a path, whereas here I am asking about a walk (a vertex might be visited multiple times); the version with paths is in NP and thus decidable, but here I am asking about walks rather than paths.

Notice that this problem is not trivial, largely because we are talking about walks rather than simple paths. There is no a priori upper bound on the length of a walk from $v\_1$ to $v\_2$, so just enumerating all possible walks might never terminate. Also, the graph could contain exponentially many cycles, and the walk might visit some of them any number of times. And, there is no obvious upper bound on the number of times that we traverse any given cycle. In particular, it is not obvious whether this problem is in NP or not. A straightforward reduction to integer linear programming (an integer variable for each edge, counting how many times the walk traverses that edge) runs into the difficulty that it is not clear how to ensure that you have a walk and not a flow.

# Answer
We start by converting your graph into an NFA $A$, by replacing the weights with strings. Positive weights $k \> 0$ are replaced by $a^k$, negative weights $k \< 0$ are replaced by $b^{-k}$, and zero weights are replaced by $\epsilon$ (the empty string). We make $v\_1$ the initial state and $v\_2$ the only accepting state. Consider now the context-free language $L\_k = \\{ w : \\#\_a(w) - \\#\_b(w) = k \\}$. We construct a context-free grammar for $L\_k \cap A$ and check whether $L\_k \cap A = \emptyset$.

The size of the generated NFA is polynomial in $n + \sum\_{ij} |w\_{ij}|$ where $n$ is the number of vertices and $w\_{ij}$ are the weights. The size of a grammar for $L\_k$ is polynomial in $k$. In order to intersect it with $A$, we convert it to a PDA, use the product construction, and then convert back. We get a CFG of size polynomial in $n + \sum\_{ij} |w\_{ij}| + k$. Checking emptyness takes polynomial time, so the entire algorithm takes time polynomial in $n + \sum\_{ij} |w\_{ij}| + k$, showing that the problem is in NP if the weights and the target sum are encoded in unary (otherwise the bound we get is only NEXP).

Interestingly, this argument doesn't work for real weights. The natural extension would be to find a basis for the weights over $\mathbb{Q}$, clear off the denominators, and have a pair of symbols $(a\_i,b\_i)$ for each element in the basis. The argument fails since $L\_{\mathbf{k}} = \\{ w : \forall i \\#\_{a\_i}(w) - \\#\_{b\_i}(w) = k\_i \\}$ is not context-free if there is more than one pair of symbols.

> Is the problem with real weights (given as linear combinations over $\mathbb{Q}$ of some $\mathbb{Q}$-linearly independent set) decidable?
> 4 votes

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


title: Asymptotic Proofs - BigOh/BigTheta

text:
# Question
Title: Asymptotic Proofs - BigOh/BigTheta
This is not homework, but from a past exam. I do not know how to solve this one at all. Can anyone please take the time and show me how to do these? Thank you.

> Prove that $5^n \in O(6^n)$, but that $5^n \notin \Theta(6^n)$. (Doing this shows that $6^n$ bounds $5^n$ from above, but that $6^n$ is not the tightest such bound.)

I am familiar with the definitions, but it seems that $5^n$ is clearly $\lt 6^n$. and $5^n$ is not $\gt 6^n$.

# Answer
First we show that $5^n \in O(6^n)$. To do this, we need to find constants $n\_0$ and $c$ such that, for all $n \> n\_0$, $5^n \leq c6^n$. Without getting into a deep philosophical discussion about how I arrived at these constants, you should be able to convince yourself that $n\_0 = 1$ and $c = 1$ work.

Now, to show that $5^n \notin \Theta(6^n)$, we need to show that $5^n \notin \Omega(6^n)$. This is because we already know $5^n \in O(6^n)$ and $\Theta(6^n)$ is simply $O(6^n) \cap \Omega(6^n)$. Read that a few times to make sure we're on the same page. For simplicity's sake, we can stick with $O$ and show that $6^n \notin O(5^n)$, which is equivalent to our condition.

To show that $6^n \notin O(5^n)$, we need to show that for any $c$ we pick, there's an $n\_0$ after which $6^n \> c5^n$; in other words, no matter what constant we multiply $5^n$ by, $6^n$ always eventually wins. To do this, we can calculate $n\_0$ from $c$. We solve:

$$6^n \> c5^n$$ $$\frac{6^n}{5^n} \> c$$ $$1.2^n \> c$$ $$n \> log\_{1.2} c$$

We can choose the smallest integer greater than the RHS and get a value for $n\_0$ that will break any $c$ we choose. For instance, for $c = 10^{100}$, my formula says that 1,263 should work for $n\_0$. Plugging in, looks like we're good to go.
> 1 votes

# Answer
Hint: Show that $$\lim\_{n\to\infty} \frac{5^n}{6^n} = 0.$$
> 1 votes

---
Tags: asymptotics, proof-techniques
---


# Question
Title: Smallest(k) in red-black tree. How is it O(logn)?
Is it the same as find minimum for a binary search tree? I know recoloring runs in O(logn) and rotations are O(1).

Even if we are wanting it to find the 'k-th' smallest key in the red-black tree.

Could someone help me understand it in more detail? Thank you!

# Answer
The idea is to use an algorithm whose running time is linear in the height, which is $O(\log n)$ in a red-black tree. As JarkkoL mentions, you can maintain a count of the number of children in every subtree without effecting the asymptotic running time of the usual operations (insert, delete and search). You then go down the tree. Suppose you're at a vertex $v$ whose two children have subtrees of sizes $L,R$. If $k = L+1$ then $v$ is the $k$th smallest. If $k \< L$ then you descend to the left child. If $k \> L$ then you descend to the right child and replace $k$ by $k-L-1$. This algorithm runs in time $O(\log n)$.
> 4 votes

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


title: Find strings in L^4

text:
# Question
Title: Find strings in L^4
```
Let L = {ab,aa,baa}.

```

I need to find L^4. From my understanding, I union the set.

So:

```
L^1 = {ab,aa,baa}
L^2 = {abab,abaa,abbaa,aaab,aaaa,aabaa,baaab,baaaa,baabaa}
L^3 = {abababab,abababaa,abababba,....} ??

```

I concatenate L^3 with L^2 as I did above correct? And then I concatenate L^4 with L^3?

# Answer
> 2 votes
The set $L^4$ consists of all words $xyzw$ where $x,y,z,w \in L$. In our case, there are (at most) $3^4 = 81$ such words, but I don't see why you'd want to write all of them. If you want, you can also compute $L^4$ by squaring $L$ twice: $L^4 = (L^2)^2$. Then there is no need to compute $L^3$.

---
Tags: formal-languages, sets
---


# Question
Title: Non-deterministic Turing machine and palindromes
I have to design a Non-deterministic Turing machine that accepts only non-palindromes in $NTime(n\log n)$.

I think this would be easy on a 2-tape DTM. Simply copy the string onto the second tape – $O(n)$ time – and then check both tapes (one from beginning and the second from the end) – $O(n)$ time again.

However, I can't picture how to do such procedure in a non-deterministic TM using only one tape. All the procedures I came up with take $O(n^2)$ steps. How can the non-determinism reduce the running time here?

# Answer
> 6 votes
Guess a position $\ell$ and add it to the left of the input. Copy it to the beginning of the tape, on top of the input string (use an expanded alphabet). Now go to position $\ell$, carrying your counter around with you. For each position you move, you need to spend $O(\log n)$ time to copy the counter, but that's fine. Decrementing the counter and comparing it to zero also take only $O(\log n)$. Once at position $\ell$, remember the symbol there, and go back to the beginning. Now move your counter all the way to the other end of the string, and count $\ell$ positions from there. Compare the symbol you find to the one you remember.

---
Tags: turing-machines, decision-problem
---


# Question
Title: Speaker independent voice command recognition
I am looking for a software, a library or an algorithm that can be trained to recognize about a dozen speaker independent voice commands. The commands will be very distinct phrases of 4-5 words each. They can be chosen to sound very different from each other. Additionally, the commands will be in more than two different languages. The user will be guided to say only the exact phrases and talk slowly, loud and clear in front of the microphone.

I am currently looking for an algorithm that can compare speech spectrograms and give me a matching percentage, but no luck so far. Any ideas?

If it helps, the code can be written for the specific phrases only, and, in worst case, the phrases can be reduced to 3 or 4.

# Answer
> 1 votes
## Software

There are many many speech recognition toolkits and software packages, which should be able to do what you want. See, e.g., https://en.wikipedia.org/wiki/List\_of\_speech\_recognition\_software for a partial list.

For instance, if you're looking for open source software, you could try Sphinx, Simon, or any number of other software packages. They can be trained in various ways, and probably can be used for what you want. There are also many proprietary speech recognition tools, which might meet your needs as well.

## Algorithms

The algorithms used by speech recognition systems are pretty standard. You split the audio into frames, use the MFCC transform to compute Mel features, then use Dynamic Time Warping or a HMM with Gaussian mixture model to recognize the spoken phrases. I would anticipate this standard pipeline would likely work for your requirement, if you train it appropriately.

(I'm not sure why you want to start from a spectrogram rather than from the audio clip itself.)

---
Tags: speech-recognition
---


# Question
Title: Computational complexity for more general problems
When I read computational complexity I encounter problems like 3-SAT, set cover, knapsack. In the first two variables are discrete. In knapsack the weights and values are integer and all three problems have a combinatorial structure, what I mean is selecting a finite number from a finite set.

How about problems in continuous domains like finding the minimum or maximum of a function in real numbers? Or solving a differential equation to find a function? Can we prove that these problems too are hard or easy in a computational complexity sense?

Finally how do I know, by looking at a problem, if asking "is the problem NP-hard?" is a valid question?

# Answer
I can answer for the first part.

Computational completely is usually defined using Turing machines, that operate over finite alphabets, so questions about algorithms over the reals cannot be answered in that framework.

With regards to possible approaches to machines over the reals, they can be broadly divided into machines that work over representation and machines that can directly and atomically manipulate real numbers.

See also this question here on SE.
> 2 votes

---
Tags: complexity-theory, real-numbers
---


# Question
Title: Where is knowing the 2^k largest elements in a array useful?
I came across this question today on stackoverflow. It asks:

> Find the largest, $2$nd, $4$th, $8$th, ..., $2^{\log n}$-th largest element in an arrary. Use $O(n)$ algorithm. $2^k$

I've come across this before and know how it can be done, but I've been been trying to find examples of algorithms that incorporate the above into the actual algorithm for a while now since I'm curious about how it can be used in practice. However, I haven't had any luck at looking this up online haven't had any results. Therefore, I'm asking if anyone knows a formal name for an algorithm that solves the above or some examples of algorithms that use the above in some way or another.

# Answer
If you implement a solution to the problem in an obvious way using quickselect with partitioning ($\log\_2 n$ selects, with the $i$th one costing $n/(2^i)$), you will end up with an array partitioned in such a way that it is essentially Williams's binary heap.
> 4 votes

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


title: Maximum minimal set coverage

text:
# Question
Title: Maximum minimal set coverage
Suppose we are given a universal set $U$ and a family of subsets of $U$, denoted by $F$ (elements in $F$ are subsets of $U$). We assume that all elements in $F$ can cover $U$, i.e., $U\subseteq \bigcup\_{e\in F}e$. Consider the following max-cost set covering problem:

$\text{argmax}\_{E\subseteq F} |E|$

s.t. $U\subseteq \bigcup\_{e\in E}e$ and $U\not\subseteq \bigcup\_{e\in E'}e,\forall E'\varsubsetneqq E$

I failed to find any literature addressing this. I was just wondering if I could have some references with regard to this problem. Thank you!

# Answer
> 4 votes
## Hardness

Your problem might be called "maximum minimal set cover". In particular, your problem feels like it might be related to minimum maximal matching, which is NP-hard. If you wanted to try to prove NP-hardness, you might try to see if you can find a reduction from minimum maximal matching.

## Algorithms

Your problem can be expressed as an instance of SAT, and then you could apply an off-the-shelf SAT solver. In particular, we formulate the decision problem variant, where we are given $F$ and an integer $k$, and we ask whether there exists a maximal cover $E$ such that $|E|=k$. To express this decision problem in SAT, we introduce constraints to capture two different aspects of the problem:

* *The requirement that $E$ be a cover of size $k$:* We introduce boolean variables $x\_f$ (one for each $f \in F$), with the intent that $E=\\{f \in F : x\_f = \text{true}\\}$. It is easy to write down boolean constraints on the $x\_f$'s to express the requirement that $E$ be a cover (i.e., for each $u \in U$, you have a clause $\lor\_{u \in f} \\; x\_f$) and that $|E|=k$ (see this answer for several ways to express the latter in SAT).
* *The requirement that no subset of $E$ be a cover:* We introduce the boolean variables $y\_g$ (one for each $g \in F$), with the intent that $y\_g$ is true if and only $E\setminus\\{g\\}$ is a cover. It is straightforward to write down boolean constraints to ensure that each $y\_g$ has the appropriate value (i.e., $y\_g = \land\_{u \in U} \lor\_{u \in f, f \ne g} \\; x\_f$; now apply the Tseitin transform). Then, we can add the clause $\neg x\_g \lor \neg y\_g$ for each $g \in F$.

Now there exists a maximal cover $E$ of size $k$ if and only if there is some satisfying assignment for this SAT instance. So, run an off-the-shelf SAT solver on this, and do binary search over $k$ to find the largest such cover, and you are done.

Alternatively, you can express your problem as an instance of integer linear programming, and then apply an off-the-shelf ILP solver. This might provide reasonable approximations to the optimum in practice, as many ILP solvers have heuristics to try to find an approximate optimum (i.e., a valuation to the variables that makes the objective function as large as they're able to).

One approach to formulate this as an ILP instance is similar to that for SAT:

* *The requirement that $E$ be a cover of size $k$:* We introduce an integer variable $k$. Also, we introduce integer variables $x\_f$ (one for each $f \in F$) that are constrained to be zero or one. Zero plays the role of false, one the role of true. Thus, the intent is that $E=\\{f \in F : x\_f=1\\}$. It is easy to write down linear constraints to express the requirement that $E$ be a cover (i.e., for each $u \in U$, we have the inequality $\sum\_{u \in f} x\_f \ge 1$) and that $E$ have size $k$ (i.e., $\sum\_f x\_f = k$).
* *The requirement that no subset of $E$ be a cover:* We introduce linear constraints to express the requirement that if $x\_f=1$, then $E\setminus \\{g\\}$ is not a cover, for all $g \in F$. This can be done using the methods described here: Express boolean logic operations in zero-one integer linear programming (ILP).

In particular, here's what it looks like. Introduce zero-or-one integer variables $y\_{g,u}$ for each $g \in F$ and each $u \in U$, where $y\_{g,u}=1$ is intended to represent that $E \setminus \\{g\\}$ does not cover $u$. In particular, for each $u \in U$ and each $g \in F$, add the inequality

$$\sum\_{u \in f,f \ne g} x\_f \le K - K y\_{g,u},$$

where $K$ is a sufficiently large constant ($K=|U|$ will suffice).

Also, for each $g \in F$, add the inequality

$$\sum\_{u \in U} y\_{g,u} \ge 1.$$

This ensures that, for each $g \in F$, $E\setminus\\{g\\}$ is not a cover (since there exists $u \in U$ such that $E\setminus\\{g\\}$ does not cover $u$).
* *Maximize $k$:* You want to maximize $k$. So, your integer linear program is: maximize $k$, subject to the linear inequalities mentioned above.

Now you can apply an off-the-shelf ILP solver to this ILP instance.

---
Tags: reference-request, optimization, set-cover
---


# Question
Title: Should compilers automatically translate operations into shortcuts?
There are several coding operations that (I suspect) most compilers will change into more efficient operations at the assembly or machine code level. I have several questions about whether or not the compiler does any of this work, and if it's even best for the compiler to automatically do so.

(Note: These examples use C and C-like language syntax. However, just because i'm doing examples in C, doesn't mean I only want answers for the C compilers. I'm interested in how most major languages handle these things.)

The first is `a += 1;` vs `a++;`, where `a` is any integer variable. Both these codes ultimately result in the same thing (incrementing by 1), but `a++` does it quicker somehow. I was self-taught for my first few languages and just never came across the `a++` style, so I use the `a += 1` style in all my private programming. However, of course later I discovered that `a++` is more common when you only need to increment by 1. I believe the origins of it are from the old days where computers were super slow, therefore finding a shortcut for incrementing (or decrementing) by 1 was a huge deal. Now don't get me wrong, it could still make a difference today like in huge nested loops, and the most common place i see the shortcut is in loops anyway. **Is there any reason why you would strictly want the slower `a += 1` style?** Incidentally, do most compilers automatically translate a `a += 1` into a `a++`?

The second is dividing by a power of 2. `b /= 8;` can be shortcut to a simple bit shift by 3 bits to the right (towards the least significant bit, and filling in zeros on the MSB side)---as long as `b` is an integer. **Should compilers make this translation, or is there some instance where you want the slower `b /= 8` operation?** Do compilers typically optimize this?

Can't think of any more simple types of shortcuts, but wouldn't be surprised if some exist.

# Answer
First compilers may (and often will depending on the optimization level) do transformations far more complex than the one you describe. You should not be concerned about the performance implication of the way you express the increment or the division before being sure that you are using a compiler for which it matters.

But there are some other implications. Some are just stylistic (and here my recommendation is that you just follow what is the style of your organization, if you are in position to chose the style, chose one which suit you and don't second guess yourself about it every other week). Other are semantic.

`a += 1` and `a++` are equivalent only if the context allows. In C and C++, they are both expressions, and if the result of the expression is different (`a += 1` is the incremented value; `a++` is the non incremented value, `++a` returns the incremented value).

`a/8` and `a>>3` are equivalent only if the value of a is positive or null. For negative values, C and C++ the result is not determined by the C and C++ standards but left to the implementation(\*). The most common behavior gives the same result as `a/8` for exact multiple of 8. For negative values which are not a multiple of 8, `a/8` has a result truncated towards 0 (i.e. `-1/8` is 0) while `a>>3` is truncated towards minus infinity (i.e. `-1 >> 3` is -1). You may know that the replacement is valid for your program but that is hard to determine for the compiler which will often not do the replacement or use a more complex one.

---

(\*) Two reasons: the standards are defined in such a way that machines with ones' complement or sign and magnitude representation for signed values is possible and what is the natural result depend on the representation; some uncommon machines have only an unsigned shift.
> 4 votes

# Answer
In many languages there is no1 performance difference between the forms. `a++`, `++a` and `a += 1` are simply all syntactic sugar for `a = a + 1` (similarly with other assignment operators that encode an operator and a basic assignment together). They just provide the programmer a shorter way of writing the same thing.

Sticking to addition, Java offers four ways of writing a (simple) increment:

```
int a = 0;
a++;

int b = 0;
b += 1;

int c = 0;
c = c + 1;

int d = 0;
++d;

```

This gets compiled into the following bytecode (up to the variable numberings changing etc):

```
0: iconst_0
1: istore_1
2: iinc          1, 1
5: iconst_0
6: istore_2
7: iinc          2, 1
10: iconst_0
11: istore_3
12: iinc          3, 1
15: iconst_0
16: istore        4
18: iinc          4, 1

```

You can see that all four versions get translated into three steps; the constant zero is loaded, store in variable $i$ (the names are not visible in this snippet, they just get a number indexing into a table), then variable $i$ is incremented by $1$. The first two correspond to the declaration and initialisation, the third is the increment. The translation of all four different increments is identical at the bytecode level.

For the division example, Java similarly unpacks `v /= 8` to `v = v / 8`, and they produce the same bytecode2.

**Footnotes**

1. In all languages that I have seen that support these forms, there is a slight, but important difference between `++a` and the three others, but it does not occur in the translation of the increment, but in when the increment happens. If we have a function and pass the increment as an argument `foo(++a)`, `foo(a+=1)` or `foor(a=a+1)`, this will increment `a` *before* invoking the function and pass the result of the increment to the function. With the call `foo(a++)`, a is incremented before the function call, but the value of the argument to the function is the old value of `a`.
2. Interestingly with no optimisation in the bytecode, it literally just divides by 8. There may be further optimisation once it hits the JVM though.
> 3 votes

# Answer
First of all, regarding `++`. For basic data types, `++a` is a shortcut for `a+=1`, so I expect the resulting code to be the same. Indeed, `gcc` generates the same code for both. In `-O1` the increment instruction is used, while in `-O0` the code adds 1. This implies that `++a` is converted internally to `a+=1`, and then during code generation this is optimized to an increment instruction.

The operator `a++` is different since it returns the old value `a` rather than the new value `a+1`, and if the value is actually used, might require another register.

If `a` is an object then `++` and `+` could be overloaded independently, so `++a` and `a=a+1` are not necessarily equivalent, and the compiler won't translate between them.

Regarding division of an integer by a constant power of 2, this is a common optimization. A quick check reveals that `gcc` performs it even in `-O1`. In `-O0` the resulting codes are different although the division is still implemented by a shift.
> 2 votes

---
Tags: compilers, program-optimization
---


# Question
Title: Finding a specific "balls-into-bins" partition given its index in the lexicographical ordering
Given numbers $n,k\in \mathbb{N}$, we consider $\mathcal P$ to be the set of all possible partitions of $n$ balls into $k$ bins.

Alternatively, $\mathcal P$ is the set of all $k$-ary vectors in $\\{0,1,\ldots,n\\}^k$ such that the sum of the entries is exactly $n$.

For example, if $n=4$ and $k=3$, we get: $$\mathcal P =$$$$ \\{\<0,0,4\>,\<0,1,3\>,\<0,2,2\>,\<0,3,1\>,\<0,4,0\>,\<1,0,3\>,\<1,1,2\>,\<1,2,1\>,\<1,3,0\>,\<2,0,2\>,\<2,1,1\>,\<2,2,0\>,\<3,0,1\>,\<3,1,0\>,\<4,0,0\>\\}$$

Simple combinatorics (Stars and bars) tells us that $|\mathcal {P}| =$$n+k-1 \choose n$.

Now the goal would be to compute $p\in \mathcal P$ given it's index in a lexicographical ordering on $\mathcal P$ (alternatively, consider each vector as a number in base $n+1$ and order $\mathcal P$ based on the number).

In the example above $\mathcal P$ is ordered, so for example, given the input $3$, we'd like to output $\<0,2,2\>$.

So the question is:

> How to we compute $\mathcal P(i)$ efficiently (without enumerating all $\leq i$ partitions)?

# Answer
> 4 votes
The procedure of generating the $i$-th structure according to some ordering of a combinatorial class is called `unranking`.

In your specific case an unranking algorithm for $P\_{n,k}(i)$ can be created as follows:

Define $s\_m := \sum\_{j=0}^m |P\_{n-j,k-1}|$, the number of vectors that start with $m$ or a smaller number, $s\_{-1}=0$.

* If $k=1$, the vector contains the single entry $n$.
* Otherwise,
    + The first entry in the vector is $m$ so that $s\_{m-1} \< i \le s\_m$.
    + The remaining vector is $P\_{n-m,k-1}(i-s\_{m-1})$.

---
Tags: algorithms, combinatorics, balls-and-bins, integer-partitions
---


# Question
Title: Are there functions in the same Θ-class that are not linear transformations of each other?
looking for some help, or at least if I'm going the right direction...

> Are there functions $f$ and $g$ such that $f$ is $O(g)$ and $g$ is $O(f)$ and NO constants $c\_1$ and $c\_2$ exist for which $f(x) = c\_1 \cdot g(x) + c\_2$?

I want to say that there is not, because the definition of big O states that if $f(x)$ is $O(g(x))$ then $|f(x)| \leq c\_1 \cdot |g(x)|$ for all values $x \> k$

and if $f(x) = c\_1 \cdot g(x) + c\_2$ then $g(x) = \frac{f(x) - c\_2}{c\_1}$

and thus $0 \leq f(x) \leq c\_1 \cdot g(x)$

$0 \leq c\_1 \cdot g(x) + c\_2 \leq c\_1 \frac{f(x) - c\_2}{c\_1}$

$0 \leq c\_1 \cdot g(x) + c\_2 \leq f(x) - c\_2$

$0 \leq c\_1 \cdot g(x) \leq f(x)$

Which contradicts the initial definition of $f(x)$ being $O(g(x))$.

Am I on the right path, here?

# Answer
Your proof must be wrong since the result is incorrect. For example, if $f=x^2$ and $g=x^2+x$ then $f = \Theta(g)$ but $f$ is not an affine shift of $g$. To see where the proof goes wrong, I suggest substituting these $f$ and $g$ in the proof and seeing which step fails. This is how one debugs their proof.
> 3 votes

# Answer
There are some wrong or unexplained points in your proof sketch. You need to justify these steps, if they are indeed correct.

1. You don't prove that $0 \leq f(x) \leq c\_1 \cdot g(x)$.
2. You don't explain why $c\_1 \cdot g(x) \leq f(x)$ contradicts $f(x)$ being $O(g(x))$.
> 2 votes

# Answer
Yes there are.

Take $f(n) = n + log(n)$ and $g(n) = n$.
> 2 votes

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


title: Recursion: base case vs. small version

text:
# Question
Title: Recursion: base case vs. small version
I'm reviewing the definition of recursion and in my notes are two questions about a recursive problem. One question asks about the **base case**, the other one about the **small version** of the problem, I always get confused about which is which... can you help me to find a way to better understand these concepts?

The examples in the exercise are:

* a function that determines if there is a "x" element in an array
* a function that determines if the string is palindrome or not

for both:

1. Find the base case
2. Find the small version of the problem
3. (Implement the recursive solution)

# Answer
When you use recursion to solve a problem, you typically partition your input into one or more smaller instances (and possibly a part that you don't process further). Those smaller instances are what your exercise calls the **small version**.

Upon recursing, your inputs get smaller and smaller until it is no longer possible (or sensible) to further split them up. The inputs that are left to be solved directly are called the **base case**.
> 2 votes

# Answer
"Small version" is wrong. What you have to find is a way to operate on the n+1 element assuming that the previous (or next) n elements have already been considered.

E.g.

Is there x in an array?

* If the array is empty then no.
* If the array is not empty then check the first element, if the first element is x then yes, if not then apply recursion, i.e. the answer is whether x is in the remainder of the array.

The second point is not a "small case", it is smaller in exactly one element than the general case. Infinite (arbitrarily long) minus one doesn't make for something "small".
> 0 votes

---
Tags: terminology, data-structures, recursion, arrays
---


# Question
Title: How to determine the set of numbers read by a DFA from one state to another?
Using the Deterministic Finite Automaton (Q, Σ, Δ, q\_0, F):

Alphabet: Σ is {(0 0), (0 1), (1 0), (1 1)}

Definition of Δ to strings recursively:

Δ\*(q, ε) = q for all q ∈ Q

Δ\*(q, xa) = Δ(Δ\*(q, x), a) for all q ∈ Q, x ∈ Σ\*, a ∈ Σ

Given a string, s ∈ Σ\*, we define left(s) and right(s) to be the numbers represented in custom binary numbers by the reverse of the left and right rows of bits in s. For example, if

s = (1 0)(0 0)(0 1)(1 0)(0 0)(1 1)

then left(s) = n(s) = n(101001) = 19 and right(s) = n(s) = n(100100) = 16 where

$\sum\_{i=1}^L s\_i \bullet F\_i $ where s is of length L.

and s = $s\_L$$s\_{L-1}$$s\_{L-2}$...$s\_1$ for s in n(s)

also the Fibonacci numbers start off as follows:

$F\_0$ = 1

$F\_1$ = 1

$F\_n$ = $F\_{n-1}$ + $F\_{n-2}$ for n \>= 2

Questions:

(a) If s is a string of length L and Δ\*(A, s) = B, state a very simple arithmetic expression (in terms of L) for left(s).

(b) If s is a string of length L and Δ\*(A, s) = C, state a very simple arithmetic expression (in terms of L) for left(s).

(c) Prove by induction on n: For all L \>= 1, and every string s of length L, my answers to part (a) and (b) are correct.

This is a question for some homework and I have no idea where to start. For parts a and b I thought I'd use the formula for n(s) for something like this:

$\sum\_{i=1}^L top(s\_i) \bullet F\_i $, but this formula doesn't take into account the transition from A to B or A to C. I'm not completely sure about what the expression should calculate either the string or the number?

# Answer
> 0 votes
For part (a) of your question, you want to know which input strings will take you from state $A$ to state $B$. We'll ignore the right element (the bottom of your pairs, in your picture), since it's always $0$ for the transitions we're interested in.

We can get from $A$ to $B$ directly, on input $1$, or we can go from $A$ to $B$ through $C$ on input $01$. In either case, once we're in state $B$, we can get back to there on input $01$. In other words, the input strings that take you from the start to state $B$ are $$ 1, 101, 10101, 1010101, \dotsc \qquad\text{or}\qquad 01, 0101, 011010, 01101010, \dotsc $$ Reversing these strings, we have $$ 1, 101, 10101, 1010101, \dotsc \qquad\text{or}\qquad 10, 1010, 101010, 10101010, \dotsc $$ For the odd-length strings, the values in this Fibonacci base representation will be $$ \begin{array}{lccccl} \text{value} & F\_1 & F\_1 + F\_3 & F\_1+F\_3+F\_5 & F\_1+F\_3+F\_5+F\_7 & \dotsc\\ \hline \text{length} & 1 & 3 & 5 & 7 & \end{array} $$ and we can get a similar result for the even-length input strings, only in this case we'll have values like $F\_2+F\_4+F\_6$ for the length 6 input string. In simple terms, the value for length $k$ inputs, $v(k)$, will be $$ v(k) = \begin{cases} F\_1 + F\_3 + F\_5 + \dotsm F\_n & \text{ if $k$ is odd}\\ F\_2 + F\_4 + F\_6 + \dotsm F\_n & \text{ if $k$ is even} \end{cases} $$ Now you have a bit of work to do on your own. Compute the values $v(k)$ for, say, $k = 1, 2, 3, 4, 5$ and look at the results. If you stare at the values for a while, you might notice that they're almost equal to one of the Fibonacci numbers, except for the addition or subtraction of a constant. That'll be the answer you're looking for, and you'll find that it is indeed simple.

For part (b), do the same sort of thing, and, finally, for both of these parts, proving that your guesses were correct by induction on the lengths, $k$, shouldn't be too difficult.

---
Tags: automata, finite-automata
---


# Question
Title: Efficient algorithm for detecting overlaps in time intervals
Let's say I am building a time clock app. The employee can log into the interface and then enter time for multiple projects so that we can generate reports for billing as well as payroll.

A table in the database will record the time-in and time-out for each project as a row. A user should be able to sign out and back into the same project multiple times throughout the day, and also can enter time out of order (e.g. sign into Project X at 9:00 AM to 2:00 PM, then into Project Y from 7:00 AM to 8:30 AM).

So let's say my table looks like this:

```
Project   | Time In | Time Out
----------|---------|---------
Project X | 9.25    | 14.25
Project Y | 7.00    | 8.50

```

(I am representing the data as a decimal number of hours simply because it's easy to read in the example; the data is actually MySQL TIMESTAMPs.)

Assuming that the data is not in any particular order, I am wondering what would be the simplest and/or most optimized way to validate that the next entry does not conflict with the existing time in such a way that the employee is signed into two projects simultaneously.

e.g. If the user tries to sign in at 12:00 PM or at 7:30 AM, it throws an error because the user was already working on Project X at noon and Project Y at 7:30.

I know I could do this by getting all the time clock data and then detecting if time\_in \<= input\[time\] \<= time\_out, but I'm wondering if there's a cleaner method to accomplish this task.

# Answer
> 1 votes
select * from table where end\_time \> 12.00PM order by end\_time

fetch single row, and check if start\_time \< 12.00PM.

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


# Question
Title: How many possible prime implicants are there in total for a 4-variable Karnough-map?
The answer for this question is 81. But I count figure out why. Can someone explain to me how does this work. Thank you.

# Answer
Hint: $81 = 3^4$. So each variable can appear in a prime implicant in three different forms. Can you figure out which?
> 0 votes

---
Tags: digital-circuits
---


# Question
Title: Are all known algorithms for solving NP-complete problems constructive?
Are there any known algorithms that correctly output "yes" to an NP-complete problem without implicitly generating a certificate?

I understand that it is straightforward to turn a satisfiability oracle into a satisfying-assignment finder: just iterate over the variables, each time asking the satisfiability oracle to solve the conjunction of that variable with the original problem.

But would such a wrapper ever be useful? Do all sat solvers search over the space of possible assignments?

Or are there some types of NP-complete problems (traveling salesman, subset sum, etc.) in which the solver can, say, exploit a mathematical theorem to prove that a solution must exist? Like doing a proof by contradiction?

# Answer
> 12 votes
As I understand it, you are asking two questions: **(1)** are there e.g. SAT algorithms that are more clever than naive brute force, and **(2)** are there algorithms that simply give a YES/NO answer when solving an NP-complete problem without actually *finding* the solution. I'll answer both questions in this order.

**(1)** It is perfectly possible to solve a problem without brute force, i.e. without naively trying all possibilities. To take your example, modern complete SAT solvers *can* apply clever algorithms that infer or prove certain (partial) assignments can't lead to a solution, so they don't even examine that part.

More generally, even NP-hard problems often exhibit some kind of algorithmic foothold that allows us to design algorithm faster than brute force. The field of this research is *exact (exponential) algorithms*. Such algorithms take exponential time, but are still faster than naive algorithms. For instance, you can solve TSP in roughly $n!$ time, where $n$ is the number of cities to visit. This method won't scale to even moderate values of $n$, but there is a classic dynamic programming $O(2^nn^2)$ time algorithm due to Held & Karp. For general techniques, see e.g. branch & bound.

**(2)** There are "oracle algorithms" for NP-complete problems that just output YES/NO with no explicit certificate. For instance, consider the $k$-path problem:

> **(The $k$-path problem)** Given a graph $G$ and an integer $k$, is there a simple path in $G$ on $k$ vertices?

The above problem is easily seen to be NP-complete. An $O^\*(2^k)$ algorithm for the problem is given in \[1\]. The algorithm itself only gives a YES/NO answer to the problem, but we can use additional tricks to construct the actual $k$-path itself. More generally, when given such an "oracle algorithm", one can use tools from combinatorial group testing for extracting the witness itself.

---

\[1\] Williams, Ryan. "Finding paths of length $k$ in $O^\*(2^k)$ time." Information Processing Letters 109.6 (2009): 315-318. publisher link, PDF

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


# Question
Title: Why do Benes networks form bipartite graphs when you build a constraint graph for them?
I was learning about Benes networks and was wondering why they formed bipartite graphs (and thus are two colorable) when one draws a constraint graph for them. The constraint graph is based on the intuition that we don't want two paths for packets to intersect because we want to show that the congestion is 1 (i.e. that even in the worst case, packet paths don't collide). This is what at least I think is implied from the following OCW notes:

If one looks at page 3 of the notes it says:

> Color (i.e., label) the vertices of your graph red and blue so that adjacent vertices get different colors. Why must this be possible, regardless of the permutation π?

**I understand it maybe for this small example, but why would the above be true in general?**

I guess I didn't really understand why every constraint graph had to be bipartite or why it had to be 2 colorable.

For example, how do I know that as I form the constraint graph, that I will not have a some clique of size 3 or more? If this were the case it would be bad, because I would for sure need 3 colors at least!

I did notice that when we form the constraints, we form them by first considering a matching of the output packets that might collide and another set of constraint about packets that might collide when arriving to the destination. This two constraints adds two matching to the graph. Maybe the union of matchings forms bipartite graphs?

# Answer
> 1 votes
You didn't explain what Beneš networks are (note that your course notes use the wrong accent on the s!), but from the notes it seems that they describe FFT algorithms. In particular, they seem to be *layered graphs*. Such graphs have $L$ layers $1,\ldots,L$, and edges only go between adjacent layers $i,i+1$. Color all nodes in odd layers with one color and all nodes in even layers with another color. Since $i,i+1$ have different parities, this is a valid coloring.

---
Tags: graphs, colorings
---


# Question
Title: Does 2-edge-colourability imply 2-colourability?
Why is it that if the edges of an undirected graph G can be grouped into two sets such that every vertex is incident to at most 1 edge from each set, then the graph is 2-colorable.

The reason that I am guessing this happens is because the graph is bipartite. But I was not sure about this... I was trying to show it was bipartite and then show thus that it was two colorable, but I didn't really know how to start showing it was bipartite. Somebody know of a rigorous way to show this? Or what the intuition for the proof is?

# Answer
> 1 votes
Hint: Consider a cycle in your graph. The edge colors must alternate, so the cycle must have even length. A graph is bipartite iff it has no odd cycles.

# Answer
> 0 votes
Bipartite is the same as two colorable.

To show that your graph is two colorable you just need to show that once you color the vertices there are no edges going between two vertices with the same color. Should be easy to show based on the definition of your graph.

---
Tags: graphs, colorings
---


# Question
Title: Why do 3D engines use rectangular projections for the camera perspective?
In most 3d applications, the scene is projected onto a rectangular area. As the field of view increases, you see terrible distortions near the edges of the screen. Why do modeling engines limit themselves to a projection matrix when they cannot produce reasonable perspectives above 90 degrees? Why are these engines not capable of having 180 or 360 degree fields of view for a panorama image?

I ask because I game with three screens and I recently have been manipulating some opengl code, and the question has always driven me crazy.

# Answer
You need to be careful what you mean by "3D applications".

Most high-end batch rendering systems (e.g. the sort that are used for feature animation and visual effects) do have pluggable camera models. If you look around the graphics literature, you can easily find papers on these, like A Realistic Camera Model for Computer Graphics. Camera models aren't just about projection, either. There's depth of field/bokeh effects and shutter effects to take into account, and these days there's also 3D stereoscopic rendering.

However, even in that scenario, these sophisticated camera models aren't often used at render time. If you need to simulate an anamorphic lens or panorama, the effect could be achieved by either rendering to a larger target or rendering to multiple cameras (e.g. in a hemicube or hemicuboid pattern) and then performing the camera projection as a post-processing effect using image resampling techniques. This has the added advantage that the camera settings can be adjusted in real-time by an artist without having to recompute the whole image.

Incidentally, there is a similar thing with video games. Game designers may make an artistic decision to simulate a cinematic lens, but there's also a bunch of other dynamic distortion-like effects which may be required (e.g. simulating water splash on the camera), and anamorphic output devices such as the Oculus Rift. Given that you have to do different image-space effects anyway, doing camera lens effects in image-space just makes sense.

So it's fair to say that most camera transforms are performed in projective space. The chief reason why is that projective space has one extremely convenient property: straight lines in Euclidean space map to straight lines in the corresponding projective space. (It's also the case that conic sections map to conic sections, which is the reason why projective space was first studied, but that's another story.)

This simplifies things enormously, both in software and in hardware. Complex geometry is typically tessellated into polygons for the purpose of sampling, because we know how to sample polygons efficiently. Polygon edges are straight lines. If they remain straight lines after the camera projection, then everything we know about sampling polygons still works in the obvious way.
> 3 votes

---
Tags: graphics
---


title: Meaning of empty clause

text:
# Question
Title: Meaning of empty clause
Why does the empty clause is logically equivalent to a contraddiction: $\square \cup \square \Longleftrightarrow \perp$

and why the empty cube is logically equivalent to a tautology: $\square \cap \square \Longleftrightarrow \top$ ?

# Answer
You have to understand that this is a *convention*. Conjunctions and disjunctions are supposed to be applied to formulas. Sometimes we want to keep things general, so that we may have to allow "empty disjunctions" and "empty conjunctions", and to that purpose we *define* what they are.

Here is one way to see why this convention is used. Let us consider a binary commutative associative operation $\oplus\colon A\times A\rightarrow A$ on some set $A$. Suppose moreover that there exists an element $e\in A$ such that $\forall a\in A, a\oplus e = e\oplus a = a$.

Since the operation is associative, we can make sense of the expresion $\bigoplus\_{i\in I} a\_i $ when $I$ is a finite non-empty set, which we define to be $(\dots(a\_{i\_1}\oplus a\_{i\_2})\oplus\ldots\oplus a\_{i\_{n-1}})\oplus a\_{i\_n}$. Since we don't want to always have to specify what happens when $I$ is empty, we take the convention that $\bigoplus\_{i\in I} a\_i = e$ when $I=\emptyset$. Why is this convention useful? It allows to write things like $$\left(\bigoplus\_{i\in I} a\_i\right) \oplus \left(\bigoplus\_{i\in J} a\_i\right) = \bigoplus\_{i\in I\cup J} a\_i$$ even if $I,J$ are allowed to be empty sets (where we implicitly replace $J$ by some other enumeration $J'$ that is so that $J'\cap I=\emptyset$). If we were to take some other convention, we would always have to be careful when writing the expression above.

See how this general situation occurs a lot in mathematical writing:

* the empty sum $\sum\_{i\in I} a\_i$ is taken to be $0$ when $I=\emptyset$, as $0$ is a neutral element for the addition of real numbers,
* the empty product $\prod\_{i\in I} a\_i$ is taken to be $1$ when $I=\emptyset$,
* in the example of formulas, consider the binary operator $\lor$. A clause is a disjunction of propositional variables, as you say, hence it can be written as $\bigvee\_{i\in I} p\_i$. When $I$ is empty, we want to define the empty disjunction as the neutral element for $\lor$. This element is $\bot$ (up to logical equivalence), as $p\lor \bot \Leftrightarrow \bot\lor p\Leftrightarrow p$ holds.
* in the example of formulas and cubes, we want to give a meaning to $\bigwedge\_{i\in I}p\_i$. Following the same convention, we use the neutral element for $\land$, which is $\top$: indeed, for any proposition variable it holds that $p\land\top\Leftrightarrow\top\land p\Leftrightarrow p$.
> 6 votes

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


# Question
Title: For a graph to be connected, you need at least n-1 edges rigorous proof
This fact seems obvious but I was unsure how to go about proving it very **rigorous**.

Let $|V| = n$ and $|E| = m$ for some connected graph $G$. Then consider the following proposition:

> If a graph is connected then $|E| \geq n-1$, i.e. it needs at least n-1 edges.

The fact seems simple and maybe obvious but I was unsure how to rigorously prove the implication. Maybe contrapositive?

The issue that I have with it is that it nearly feels like an axiom. Is there a way to conclude this without assuming it to be true?

# Answer
One way to prove this is by showing that a graph on $n$ vertices with $m$ edges has at least $n-m$ connected components. The proof is by induction on $m$. If $m = 0$ the graph is empty and no vertex is connected to any other. Now suppose that the claim is true for $m$ edges, and consider some graph with $m+1$ edges. Let $C\_1,\ldots,C\_k$ be its connected components. Choose some arbitrary edge $e = (x,y)$, and suppose that $e \in C\_i$. Let $A$ be the set of vertices $v \in C\_i$ for which there is a path from $x$ to $v$ not passing through $e$. Any vertex in $C\_i \setminus A$ has some simple path to $v$ which passes through $e$. This path ends at $e$, and so there is a path from $y$ to $v$ not passing through $e$. This shows that both $A$ and $C\_i \setminus A$ are connected even if we remove $e$. Other connected components are not effected by the removal of $e$ (since $e$ doesn't touch any of their vertices), and so if we remove $e$, the graph has at most $k+1$ connected components. The induction hypothesis shows that $k+1 \geq n-m$, and so $k \geq n-(m+1)$, proving the inductive step.

If a graph is connected then it has one connected component, so $n-m \leq 1$, that is, $m \geq n-1$.
> 4 votes

# Answer
A simple proof. Starting from n vertices with no edges, we add the edges one by one in an arbitrary order. Since adding one edge reduces the number of components by at most one, a graph with less than n-1 edges cannot be connected.
> 3 votes

---
Tags: graphs
---


# Question
Title: Term for binary search tree using hashes?
I was looking for a way to easily store and access a symbol table using the least memory and code as possible and I went with a BST. Symbols, however, tend to be defined in order as in foo0, foo1, foo2... so tree balance is an issue.

I considered balancing and auto-balancing algorithms, but then I realized that the hash for a key given a good hash function should have a 50% average chance for left/right. And I already had a hash function so that meant no additional code. So I would get a balanced tree for free(**edit**: at no point did I want to imply a perfectly balanced tree, this is emergent behavior).

I wanted to check if my theory was correct. When I search for BSTs, hashes, and hash trees, however, no relevant information turns up.

What is the term for a binary search tree that balances itself by using a hash?

**edit**: I am going to accept the answer because if something doesn't have a name it just doesn't, but I tested this because some comments and asides imply that it is worse than it actually is.

I tested a sorted list of 468685 words containing both English words and "elite" password cracking words.

```
balanced-tree:    worst(19)     average(18.84)
edlin-tree:       worst(47)     average(22.72)
edlin-tree(SHA2): worst(46)     average(23.25)
regular BST:      worst(468685) average(234342.50)

```

So it's not going to replace your language library algorithms but, as stated in the accepted answer, it is obviously logarithmic.

As for the hash function(Which for reference is add+xorshift as in:

```
do{h+=*s;h^=h<<left1;h^=h>>right;h^=h<<left2;}while(*s);

```

), I have also tested how bad it is by comparing collisions to the expected value.

```
8 bits:
   expected :  468428.99
   axs      :  468429
   SHA2-256 :  468429

16 bits:
   expected :  403200.35
   axs      :  403189
   SHA2-256 :  403198

24 bits:
   expected :    6485.99
   axs      :    6451
   SHA2-256 :    6433

31 bits:
   expected :      51.14
   axs      :      59
   SHA2-256 :      47

32 bits:
   expected :      25.57
   axs      :      30
   SHA2-256 :      20

33 bits:
   expected :      12.79
   axs      :      14
   SHA2-256 :      11

35 bits:
   expected :       3.19
   axs      :       7
   SHA2-256 :       2

36 bits:
   expected :       1.59
   axs      :       1
   SHA2-256 :       2

37 bits:
   expected :       0.80
   axs      :       0
   SHA2-256 :       0

```

So, while it appears to lag for some bitnesses, it generally follows the expected values, both for tree depth and collisions. What would a hash which is not good for your input mean? That your input generates a sequence when passed to it? That would be ridiculously unlikely statistically speaking. Worst case is O(n) but you are not going to see it.

The algorithm is not good compared to AVL or red-black, even though insertion will probably be faster generally, however it beats a linked list or betting on input for a BST any day.

# Answer
> 4 votes
It's not that the analysis in the previous answer is wrong regarding the weight balance, but the answer I was looking for was that this algorithm is basically equivalent to a http://en.wikipedia.org/wiki/Random\_binary\_tree .

The longest path is $$4.311 \times \log\_{e} n$$

---

**EDIT:** I'll update this answer because the information below was relatively hard to come by.

The magic number comes from:

```
Reed, Bruce (2003), "The height of a random binary search tree", Journal of the ACM 50 (3): 306–332, doi:10.1145/765568.765571.

```

The author shows that the expected height of a random binary tree is $E(H\_n ) = \alpha \log\_e n − \beta\log\_e \log\_e n + O(1)$, where $α = 4.311\ldots$ and $β = 1.953\ldots$. The magic number represents the upper bound.

The expected height happens to be $\approx\log\_{\frac{4}{3}} n$, which is somewhat intuitive when you consider that each parent node represents a random pivot partitioning the node search space like in random quicksort.

Finally, the average access time for any given node is actually $\approx\log\_{\frac{4}{3}} \sqrt{n}$(I can't find a reference for this).

That makes using hash as the key $\approx1.205\log\_2n$ or 20% slower on average than a self-balancing binary tree.\*

Similar structures with various trade-offs include the hash-as-priority *treap*, hash+*b-tree*, and hash+*suffix tree*. The *suffix tree* is only a bit less lazy than the proposed structure and provides expected $\log\_2n$ access time.

\[\*\] Many balanced tree algorithms also have a worst-case height upper bound of $\log\_\phi n$

# Answer
> 3 votes
To answer the explicitly asked question: There probably is no specific name for this data structure since noone has bothered to use or study it.

Regarding the underlying question: Even using a "good" hash function, you can not expect as well a degree of balanced as you think:

Looking at the node with key $foo$, we see that all keys (in the subtree below $foo$) with a hash smaller than $h(foo)$ will be in the left subtree, while all those with a larger hash will be in the right subtree. So the balancedness of the tree will depend on how far $h(foo)$ is away from the center. This has an expected value of $\frac 12 N$, where $N$ is the number of hash values that belong in the subtree below $foo$. So we can expect an average weight balance of $1:3$ in each node. While this is still enough to give logarithmic expected height, it is already notably worse than the $1:1.6$ balance an AVL tree has in the worst case. Factoring in the additional risk of the hash function being not "good" for the data of a specific run, the idea quickly becomes unattractive.

Additionally, in many practical scenarios you have the option of using a library implementation of AVL trees, while you have to implement the "hash tree" yourself. So your "for free" argument will typically be the other way round.

---
Tags: data-structures, search-trees, hash, dictionaries
---


# Question
Title: What is the intuition behind the Potential Function in Amortized Analysis of some algorithm?
I have come across many amortized analysis using a potential function. They all look magical to me. Everything works perfectly but I never got the intuition behind how they come up with such a "magical" potential function which makes everything work. My question is can someone share their experience in developing a potential function for amortized analysis and the intuition behind it?

# Answer
> 8 votes
Imagine filling up a huge water tank. Now when you open the faucet you have nice water pressure. The pressure will last probably until the tank is almost empty (depending on its size). At that point you need to refill it to have your constant pressure again, so you make the effort again.

The potential function is the water tank. You do some work that will "last" for a while and "store" the energy used in the potential function, e.g., allocating an new array in dynamic arrays/tables. You won't need to do any more work for a while, e.g., until the size of your array grows too much or shrinks too much. At that point you have used all the energy in your potential function (all the water is gone) and need to recharge (refill the tank).

As far as designing such a function, let's take as example the case of a dynamic array. The main point to bring home here is that the potential function Φ is linear in the input size. The coefficients and constant values matter to a certain point (in physics, what really matters is the derivative of the potential function, or the difference between values of the potential function in different points, so additive constants don't really matter in general). We know the function is linear in this case because the expensive operation that we want to amortize is a linear operation (resizing of the array) and we want to prove that this operation determines the cost of a sequence of operations. So, from a practical standpoint, we could have written Φ = a\*n + c, performed our analysis and then assigned reasonable values to our two constants so that the potential is always positive. Note that these coefficients might heavily depend on the details of the algorithm/data structure being analysed. For example it's be interesting to try and change when the array gets resized and the amount by which it gets resized and see if the function still hold and also if the linearity still holds. This is discussed in CLRS.

It's also worth noting that, although possible, it might be impractical or tedious to apply amortized analysis to any algorithm. In many cases simpler approaches, e.g., the use of the master theorem, will suffice. The potential method works well for cases like the dynamic array, where you have an expensive operation that you are trying to "amortize" over a sequence of operations, thus not all the operations have the same cost, but the overall cost of performing a given sequence of operations is well defined (linear in this example).

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


# Question
Title: Are "data structures" part of algorithms or of programming languages?
I often heard that "program = algorithm + data structure".

But I notice that

1. It seems to me that a data structure is (or may be) just a data type or extension thereof. Is it correct? But a data type is a part of a programming language, but a data structure isn't.
2. the operations/methods in a data structure actually implement algorithms.
3. both computability of a problem (i.e. existence of an algorithm for solving the problem) and complexity of an algorithm seem not depend on which data structure to use. Is it correct?
4. Although there are books specially for data structures.

* books on programming languages introduce their data types, but not data structures.
    * books on algorithms may introduce data structures in an appendix.

So are "data structures" part of algorithms or of programming languages?

where does "data structure" lie in computer science wrt algorithms and programming languages? Thanks.

# Answer
> 3 votes
Some aspects of data structures belong to algorithmics ("Theory A"), some to programming language theory ("Theory B"). Since I'm not qualified to discuss the latter, I can mention a few aspects of the former.

Suppose we want to implement a data structure supporting a certain set of operations:

1. How fast can the operations be, given some computational model (Turing machine, RAM machine, decision trees, memory accesses \[the cell probe model\])? Worst case, average case; amortized, non-amortized; offline (the list of operations is known in advance) or online.
2. How much space is required to support the data structure? Is there a tradeoff between the space used and the running times of operations?
3. If implemented in a distributive fashion (say given limited space on each computation node), how much communication is needed?

Data structure theory is also related to complexity theory, which is used as a tool to prove lower bounds on data structures. For example, communication complexity has been used to this end.

# Answer
> 3 votes
Data structures belong with algorithms. You can implement a red-black tree, associative array, fibonacci heap, and so on in any general purpose language.

However, a language can certainly favor certain kinds of data structures. For example, J, K, APL, and Matlab all favor array/matrix oriented programming styles. Haskell and Clojure suggest use of persistent tree-based data structures. TCL, PHP, and Perl encourage stringly-typed programming.

Regarding your third question: Complexity of algorithms depends **very heavily** on data structures chosen. Much of the reason to develop data structures, such as red-black trees or finger trees, is to help control and reduce algorithmic complexity of programs that use them.

---
Tags: algorithms, data-structures, programming-languages
---


# Question
Title: Prove, using only the definition of $O()$, that $2^{\sqrt{x}}$ is not $O(x^{10})$
Prove, using only the definition of $O()$, that $2^{\sqrt{x}}$ is not $O(x^{10})$.

I have been doing a few exercises on Big O and this is the first time I have encountered the variable in the exponent. I was wondering how to disprove this function. Any help would be appreciated

# Answer
Hint: Try converting both functions to the form $e^{f'(x)}$.
> 2 votes

# Answer
$O(x^{10})$ is $O(x^k)$ for some constant $k$ (polynomial complexity) whereas $O(2^{\sqrt{x}})=O(2^{x^k})$ is subexponential by definition.

Using De l'Hôpital's rule, you can find the following:

$ \lim\_{x\rightarrow\infty} \displaystyle\frac{x^{10}}{2^{\sqrt{x}}} = \lim\_{x\rightarrow\infty} \frac{\frac{\delta x^{10}}{\delta x}}{\frac{\delta 2^{\sqrt{x}}}{\delta x}}=0 $

which shows that the denominator grows faster than the numerator. You can actually differentiate the fraction until you get a constant numerator while the denominator will always stay a function of $x$.
> 0 votes

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


# Question
Title: What is the name of this function of a tree?
I've written a recursive function of a tree, and I would like to know what it's called! It's not quite the same as the height or the width of a tree, but it seems kind of like a width.

Assuming the tree $T$ is binary, we can define the function $f(T)$ as follows. If $T$ has a only a single node, let $f(T) = 1$. Otherwise, let $T\_0$ and $T\_1$ be the two trees rooted at the child nodes $T$'s root. If $f(T\_0) = f(T\_1)$, then let $F(T) = F(T\_0) + 1$; otherwise, let $f(T) = \max(f(T\_0), f(T\_1))$.

The function $f$ is generalized as follows to trees that are not necessarily binary. As before, let $f(T) = 1$ when $T$ has no edges. Otherwise, let $T\_0, \dots, T\_k$ be the $k+1$ subtrees rooted at the child nodes of $T$'s root, sorted by descending values of $f$. Then let $f(T) = \max\_i(f(T\_i) + i)$.

# Answer
> 2 votes
This is basically the Strahler number, which is great because now I can call my function `ComputeStrahlerNumber` instead of keeping the profane function name I was using as a placeholder.

---
Tags: trees
---


# Question
Title: Use of -1 to express edge cases in computer programs and data structures
Often I will encounter the use of - or even use myself - the value **`-1`** as an edge case in otherwise integer data structures. For instance, as the value for "irreplaceable" in a *Replacement Cost* field.

This is especially useful where **`null`** is either unrecognised; semantically overburdened; or converted into **`empty`** when migrating data across formats.

***What is the formal computer science view on the use of negative integers for non-numeral meanings in data fields which are still used normally for positive integers?***

# Answer
Most PL folks would probably suggest that an option type is better suited.

For instance, in Haskell you'd use a `Maybe T` type: you use `Nothing` instead of `-1`, and `Just x` instead of `x`. In SML, you'd use a `T option` type, and use `None` instead of `-1` and `SOME x` instead of `x`.

The benefit of this is to better document the meaning of the sentinel value, and also to force the programmer to consider both cases everywhere it is relevant. This helps avoid certain kinds of programming mistakes, where a `-1` value is inadvertently used as if it were a real value. It also ensures that the domain of the type `T` is separate from the sentinel value.

In a language without an option type, you can also use tagged unions or other methods of encoding this into the type system or class hierarchy.

That said, this is a pretty subjective question. Opinions will vary. You should not expect everyone in a field to share the same opinion about a subjective matter like this.
> 2 votes

---
Tags: data-structures, integers
---


# Question
Title: Finding the minimum number of calls in a tree
I was asked this question in an interview and struggled to answer it correctly in the time allotted. Nonetheless, I thought it was an interesting problem, and I hadn't seen it before.

Suppose you have a tree where the root can call (on the phone) each of it's children, when a child receives the call, he can call each of his children, etc. The problem is that each call must be done in a number of rounds, and we need to minimize the number of rounds it takes to make the calls. For example, suppose you have the following tree:

> ```
>    A
>   / \
>  /   \
>  B    D
>  |
>  |
>  C
>
> ```

One solution is for A to call D in round one, A to call B in round two, and B to call C in round three. The optimal solution is for A to call B in round one, and A to call D and B to call C in round two.

Note that A cannot call both B and D in the same round, nor can any node call more than one of its children in the same round. However, multiple nodes with a different parent can call simultaneously. For example, given the tree:

> ```
>       A
>     / | \
>    /  |  \
>    B  C   D
>   /\      |
>  /  \     |
> E   F     G
>
> ```

We can have a sequence (where "-" separates rounds), such as:

> A B - B E, A D - B F, A C, D G

(A calls B first round, B calls E and A calls D second, ...)

I'm assuming some type of dynamic programming can be used, but I'm not sure which direction to take this in. My initial inclination is to use DFS to order the longest path from the root to leaves in decreasing order, but when it comes to the nodes actually making calls, I'm not sure how we can achieve optimality given any tree, nor how we can output the paths that the optimal calls would make (i.e. in the first example we could output

> A B - B C, A D

# Answer
You can traverse the tree in postorder and compute for each node the number of rounds that the subtree below that node needs as follows:

* If the node is a leaf, the subtree takes 0 rounds.
* If the node is not a leaf, sort its children by the number of rounds their respective subtrees take, from longest to shortest. You will traverse them in this order. The number of rounds for the current node is $\max\_i\\{n\_i +i\\}$, where $n\_i$ is the number of rounds the subtree of the $i$-th child (in sorted order) takes.

Regarding output: The best format depends on what you want to do with the data. Do you need information on which calls happen concurrently? Or do you want to actually implement the calls?
In the latter case, listing the processing order for each node seems like a reasonable format.
In the former case, your format is nice, but probably needs an additional traversal to be obtained.
> 4 votes

---
Tags: algorithms, graphs, trees, graph-traversal
---


# Question
Title: What are the treatises on how to build mechanical computers?
I've just watched this replica of the Antikythera mechanism. I've heard also about Babagge's analytical machine and the Curta calculator. I got curious: What did they use to build computers made of gears? We have nowadays some treatises to make logic gates with transistors, how did they manage to *build logic gates* or to do whatever was needed for building their computers?

I'm not sure if this question really fits this forum, but it was the nearest one I could think about.

# Answer
> 2 votes
This is a very broad question, with a different answer for each kind of device. The computers before modern times did NOT use logic gates.

For example the January 2004 Scientific American article "The Curious History of the First Pocket Calculator" covers how Curta calculators work, in addition to the history.

The Antikythera mechanism used gear reductions (gears with differing teeth counts) to implement the ratios of times of various periodic events to predict positions. Given the \[known even then\] frequencies, it is straightforward to compute the required gear ratios. http://www.cs.virginia.edu/~robins/Decoding\_an\_Ancient\_Computer.pdf

In addition (as mentioned in a comment above) there were many many different flavors of analog computers, that a quick google search should be able to find explanations for many of them.

# Answer
> 1 votes
as in other answer, this is a broad question, but there is some general study of mechanical computers and how their conceptual elements led to modern computers. note that ref to the Antikythera mechanism and some other physical systems as a "computer" is a modern projection and more of an analogy/ metaphor. one book that comes close to answering your question is Pebbles to computers: the Thread by Blohm/ Beer. it takes an achaeological pov on the question and looks at the construction of very old computer-like devices. note that the Antikythera mechanism while very old (~2Millenia) and (re)discovered/ excavated about ~1Century ago was not well understood until more recently through scientific research.

---
Tags: reference-request, computer-architecture
---