# Question
Title: $O(n^{k-1}$) algorithm for K-clique problem
Clique problem is a well known $NP$-complete problem where the size of the required clique is part of the input. However, k-clique problem has a trivial polynomial time algorithm ($O(n^k)$ when $k$ is constant). I'm interested in the best known upper bounds when k is constant.

> Is there an algorithm with run time $O(n^{k-1})$? A $o(n^k)$-time algorithm is also acceptable. Also, Is there any complexity-theoretic consequence for the existence of such algorithms?

# Answer
A 3-clique can be found in an $n$-vertex graph $G$ in time $O(n^\omega)$, where $\omega \< 2.376$ is the matrix multiplication exponent, and in $O(n^2)$ space by a result of Itai and Rodeh \[1\]. Basically, they show that $G$ contains a triangle if and only if $(A(G))^3$ has a non-zero entry on its main diagonal. Because a triangle is also a cycle $C\_3$, one can use general cycle finding methods for detecting triangles. Alon, Yuster and Zwick show how triangles can be detected on an $m$-edge graph in $O(m^{2\omega/(\omega+1)}) = O(m^{1.41})$ time \[6\].

For a long time, the result of Nesetril and Poljak \[2\] was the best known; they showed the number of cliques of size $3k$ can be found in time $O(n^{\omega k})$ and $O(n^{2k})$ space. Finally, Eisenbrand and Grandoni \[3\] improved on the result of Nesetril and Poljak for a $(3k+1)$-clique and a $(3k+2)$-clique for small values of $k$. Specifically, they gave algorithms for finding cliques of size 4, 5, and 7 in time $O(n^{3.334})$, $O(n^{4.220})$, and $O(n^{5.714})$, respectively.

As far as I know, for general $k$, the problem of designing better algorithms is open. For possible consequences or complexity theoretic considerations, Downey and Fellows (see e.g. \[4\]) showed $k$-clique with parameter $k$ is $W\[1\]$-hard. The class $W\[1\]$ denotes the class of parameterized decision problems reducible to CLIQUE with parameterized reductions. It is believed that CLIQUE is not fixed-parameter tractable. There are hundreds of other problems known to be equivalent to CLIQUE under parameterized reductions. Furthermore, Feige and Kilian \[5, Section 2\] have a result saying that when $k$ is part of the input and $k \approx \log n$, then a polytime algorithm is not likely to exist.

If you consider some restricted graph classes, you can solve the problem in linear time on chordal graphs. Simply compute a clique tree of a chordal graph $G$ in $O(n+m)$ time, and then check if any clique is of size exactly $k$. On planar graphs, one can also find triangles in $O(n)$ time using the methods of \[6\].

---

\[1\] Itai, Alon, and Michael Rodeh. "Finding a minimum circuit in a graph." SIAM Journal on Computing 7.4 (1978): 413-423.

\[2\] Nešetřil, Jaroslav, and Svatopluk Poljak. "On the complexity of the subgraph problem." Commentationes Mathematicae Universitatis Carolinae 26.2 (1985): 415-419.

\[3\] Eisenbrand, Friedrich, and Fabrizio Grandoni. "On the complexity of fixed parameter clique and dominating set." Theoretical Computer Science 326.1 (2004): 57-67.

\[4\] Downey, R. G., and Michael R. Fellows. "Fundamentals of Parameterized complexity." Undegraduate Texts in Computer Science, Springer-Verlag (2012).

\[5\] Feige, Uriel, and Kilian, Joe. "On Limited versus Polynomial Nondeterminism". Chicago Journal of Theoretical Computer Science. (1997)

\[6\] Alon, Noga, Raphael Yuster, and Uri Zwick. "Finding and counting given length cycles." Algorithmica 17.3 (1997): 209-223.
> 21 votes

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


# Question
Title: Context free language and the complement of it
Given the language $L\_1 = \\{a^i b^j c^k \mid i \neq j \vee i \neq k\\}$, I need to determine whether it is context-free by using the pumping lemma. I must do the same for the complement of this language.

I started off by breaking $L\_1$ into two parts, $L\_1 = L\_2 \cup L\_3$, where $L\_2 = \\{a^i b^j c^k \mid i \neq j\\}$ and $L\_3 = \\{a^i b^j c^k \mid i \neq k\\}$, and I proved that both the languages are not context free, hence the union which is $L\_1$ is also not context-free. Is this approach of mine correct?

Also would the complement of $L\_1$ be $L\_1' = \\{a^i b^j c^k \mid i = j \wedge i = k\\}$ and break down $L\_1'$ into two parts $L\_2'$ and $L\_3'$ and by the closed under intersection rule for context-free languages we know $L\_1' = L\_2' \cap L\_3'$ is not context free.

This how I approached both the parts, and I would like to know if my approach is correct or wrong. Help would be really appreciated.

# Answer
> 0 votes
Sorry, your approach does not work.

Breaking down $L\_1$ into two parts is a good idea. Unfortunately you proof these parts are context-free cannot be correct, as one can give a grammar for each of them.

As for the complement, there is no such thing as a *intersection rule*. The fact that context-free languages are not closed under intersection simply states that there exist two context-free languages the intersection of which is not context-free. The intersection of any random pair of context-free languages *can* be context-free (e.g., if the intersection is empty).

Back to the drawing board.

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


# Question
Title: More efficient algorithm for determining if one list is a sublist of another list
I'm trying to build an algorithm which takes two lists of natural numbers and finds if every element of the first list is displayed at least once in the second list.

What if the list is sorted?

An algorithm that can do this is by comparing every element of the first list with every element from the second list. I think there is an algorithm with a better complexity. Can anyone give me any idea?

# Answer
Let's start with the case when the lists are sorted. In that case, you can apply a simple modification of the basic merge algorithm on sorted lists: discard the elements instead of constructing a merged list, and only keep track of whether an element from list 1 was missing from list 2.

In the pseudo-code below, `head(list)` is the first element of `list`, and `advance(list)` means to discard the head of `list`. In other words, `head(cons(h,t)) = h` and `advance(list)` when `list = cons(h,t)` means `list := t`.

```
while list1 is not empty:
    if list2 is empty or head(list1) < head(list2):
        return false
    else if head(list1) = head(list2):
        let x = head(list1)
        while list1 is not empty and head(list1) == x: advance(list1)
        while list2 is not empty and head(list2) == x: advance(list2)
    else: (head(list1) > head(list2))
        advance(list2)
return true

```

Exercise: prove that this algorithm returns `true` when all the elements of `list1` occur in `list2` and `false` otherwise.

Let $n\_1 = \mathrm{length}(\mathtt{list1})$, $n\_2 = \mathrm{length}(\mathtt{list2})$ and $n = \max(n\_1, n\_2)$. The algorithm above removes at least one element of `list2` at each iteration, and in the worst case it removes all the elements of both list. Therefore it executes at most $n\_2$ iterations of the loop and performs at most $n\_1 + n\_2$ removals of the head of the list: its complexity is $O(n)$.

Now suppose that the lists are not sorted. An obvious solution is to sort them, then apply the known algorithm. Since sorting is $O(n \log n)$, this algorithm is $O(n \log n)$.

Exercise: make sure you understand why my statements about complexity are true.

Exercise (difficult!): can you do better than $O(n \log n)$ in the general case?
> 6 votes

# Answer
If you know the lists are sorted, you don't need to iterate over them all. For example, Let's say the lists are this:

```
l1 = [1,2,3,4,5,6,7,8,9,10]
l2 = [1,2,3,4,6,7,8,9,10]

```

When you are looking for value 5 in the second list, you can stop looking once you've found the element with the value 6 since you know all of the remaining values are greater than 5.
> 3 votes

---
Tags: algorithms, data-structures, sorting, lists, comparison
---


# Question
Title: Complexity class of Determining Hamiltonian cycle
I Know that determining Hamiltonian cycle in a graph is NP complete. For the sake of my clarification, I just want to know that whether the problem remains NP complete with following restrictions ?

1) Graph is undirected , and every node has degree two.

Any help will be appreciated. Thanks.

# Answer
If every node has degree two, then the test for a Hamiltonian cycle boils down to testing connectivity, since the graph must then consist of 0 or more disconnected cycles.

The algorithm is as follows:

```
Choose a starting node v
marked[v] = true
x := v
while x has an unmarked neighbour u
    x := u
    marked[u] = true
if all nodes in the graph are marked, return true, else return false

```

Suppose we see $v\_1 \cdots v\_n$ in this process. Since each node has degree 2, we only stop when we see a node with both its neighbors marked, so $v\_1 \cdots v\_n$ is a cycle in the graph. Since we see two edges from each $v\_i$, there can be no other nodes connected to any $v\_i$ that are unmarked. Thus, either $v\_1 \cdots v\_n$ is all nodes in the graph, and there is a cycle, or there is another connected component, and there is not a cycle.

Clearly this test is linear time, so the problem is in $P$.
> 1 votes

---
Tags: complexity-theory, graphs, p-vs-np
---


title: Prove L is NP-hard

text:
# Question
Title: Prove L is NP-hard
I have no clue how to prove this question.

Consider the language

$L = \\{ \langle D\_1, D\_2, ... ,D\_K \rangle : k \in {N},$ the $D\_i$ are DFAs and ${\bigcap}\_{i=1}^k L(D\_i) = \emptyset \\}$

Prove that L is NP-hard.

Can someone guide me through this problem? I understand that I will have to reduce it into something, I just don't know what to reduce to.

# Answer
Here are a few hints (the basic idea was in the comment of jmite). Try to reduce from CNF-SAT

1. You have to encode a truth assignment as a word. Say the word $\tt 101001001$ encodes $x\_1=\text{TRUE}$, $x\_2=\text{FALSE}$, and so on
2. Try to construct a DEA that accepts all words (truth assignments) that satisfy a clause. Yo know that the truth values come in order, so yo can decide check every literal one by one.
3. The intersection of the DEAs for the clauses accept the truth assignments that satisfy all clauses. So if there exists some truth assignment this language wont be empty.
4. You are left with a formal proof, and you have to check that the list of DEAs is not too long. In particular you have to check if the reduction is polytime.
> 1 votes

---
Tags: np-hard
---


title: Parsing Dice Notation

text:
# Question
Title: Parsing Dice Notation
The syntax of dice notation follows the following grammar:

$$ Roll \rightarrow Dice | Dice'x'Int | More \quad Mod \quad More $$ $$ Dice \rightarrow Int\_{1}'d'Int\_2$$ $$ Mod \rightarrow '+'|'-'$$ $$ More \rightarrow Int | Roll$$ $$ Int \rightarrow \<integer\>$$

Give a leftmost derivation for the sample string: $3d8 + 2d4x3 + 1d12 + 567$

I was able to parse the two first operands $3d8 + 2d4x3$ but I couldn't find a reasonable derivation for the rest.

My solution is like:

```
E -> More Mod More
E -> Roll Mod More
E -> Dice Mod More
E -> Int1’d’Int2 Mod More
E -> <integer>’d’Int2 Mod More
...
...
E -> <integer>’d’<integer> + <integer>’d’<integer>’x’<integer> + More Mod More
E -> <integer>’d’<integer> + <integer>’d’<integer>’x’<integer> + Roll Mod More
E -> <integer>’d’<integer> + <integer>’d’<integer>’x’<integer> + Dice Mod More
E -> <integer>’d’<integer> + <integer>’d’<integer>’x’<integer> + Int1’d’Int2 Mod More

```

I was thinking that the given string is not a valid string for this grammar.

Does any have any idea for this problem. I'm newbie in Compiler Design :-)

# Answer
> 1 votes
Hint: Your string is of the form *Dice+Dice+Dice+Int*. Figure out how to obtain this from *Roll* using only the first, third and fourth rule.

---
Tags: parsers, parsing
---


# Question
Title: Data structure used to implement recursion
Which data structure can be used to "eliminate" recursion from a recursive program? Array, stack, queue, or list? How is it used to that end?

When I eliminate recursion from the program computing factorial $n! = n(n-1)!$, I replace recursion with a loop. But I don't see how to do a similar transformation in general.

# Answer
Let me restate your question: Which data structure does the CPU use to implement recursion? This data structure is knows as the call stack. As you can imagine, it's a stack. I strongly suggest that you consult the Wikipedia page (or any other source) and try to understand *why* a stack is used and *how* it works. This is much more important than answering a multiple-choice question.
> 1 votes

---
Tags: data-structures
---


# Question
Title: Finding growth of "inter-recursive" functions
consider following code

```
int f(int x)
{
  if(x<1) return 1;
  else return f(x-1)+g(x);
}
int g(int x)
{
  if(x<2) return 1;
  else return f(x-1)+g(x/2);
}

```

**Questions:**

> How do I find the growth of `f(x)`, being that it contains a recursion to another function?
>
> Are growth and time complexity of a a function same thing? Are they the same for `f(x)`?

# Answer
Growth and time complexity are not the same, though in this case they probably have similar values (up to a multiplicative constant). The recurrences for the time complexity are $$ \begin{align\*} F(x) &= \begin{cases} \Theta(1) & x \< 1, \\ F(x-1) + G(x) + \Theta(1) & x \geq 1. \end{cases} \\ G(x) &= \begin{cases} \Theta(1) & x \< 2, \\ F(x) + G(\lfloor x/2 \rfloor) + \Theta(1) & x \geq 2. \end{cases} \end{align\*} $$ If you're uncomfortable with the notation $\Theta(1)$, mentally replace it with $1$. The difference between these recurrences and the ones for $f,g$ is the addition $\Theta(1)$ term in the inductive case (second lines above).

Ignoring the floors for the moment, we have $$ g(x) = f(x-1) + f(x/2-1) + f(x/4-1) + \cdots, $$ the sum ending when the argument is below $1$. Therefore $$ f(x) = f(x-1) + g(x) = 2f(x-1) + f(x/2-1) + f(x/4-1) + \cdots. $$ The recurrence $f'(x) = 2f'(x-1)$ with a base case $f'(0) = 1$ already has the solution $f'(x) = 2^x$, so we know that $f(x) = \Omega(2^x)$. Since $2^x$ grows so fast, we know that $f(x/2-1) + f(x/4-1) + \cdots \ll 2f(x-1)$, and this shows for example that $f(x) = O((2+\epsilon)^x)$ for all $\epsilon \> 0$.

At this point one can probably guess and prove an asymptotic formula for $f$, but I'll leave that for others to do. Given $f$, it should be easy to estimate $g$. Indeed, it seems probable that $g = \Theta(f)$.

**Update:** Experiments show that $$ \begin{align\*} \frac{f(n)}{2^n} &\longrightarrow 1.9635473337171197318620139352\ldots\\ \frac{g(n)}{2^n} &\longrightarrow 0.98177366685855986593100696758\ldots \end{align\*} $$ Let $\alpha = \lim\_{n \to \infty} f(n)/2^n$. Even more accurately, we get (for $n$ divisible by $4$) $$ \begin{align\*} f(n) &= \alpha \left( 2^n - 2^{n/2} + \frac{11}{28} 2^{n/4} + O(2^{n/8}) \right), \\ g(n) &= \alpha \left( \frac{1}{2} 2^n - \frac{1}{4} 2^{n/2} + \frac{1}{14} 2^{n/4} + O(2^{n/8}) \right). \end{align\*} $$ The curious reader can try to prove these expansions, up to the exact value of the constant $\alpha$.

Indeed, let $f'(x) = f(x)/2^x$. Then $$ f'(x) = f'(x-1) + 2^{\lfloor x/2 \rfloor - 1 - x} f'(\lfloor x/2 \rfloor - 1) + \cdots. $$ Easy induction shows that $f'(x) = O(x)$ and so $$ f'(x) = f'(x-1) + O\left(\frac{x\log x}{2^{x/2}}\right). $$ Since the series $\sum\_{x \geq 1} (x\log x)/2^{x/2}$ converges and the sequence $f'(x)$ is increasing, $f'(x)$ tends to some limit. Using the estimate $f'(x) = \Theta(1)$ and being more careful, we obtain $$ f'(x) = f'(x-1) + \Theta(2^{-x/2} + 2^{-3x/4} + \cdots) = f'(x-1) + \Theta(2^{-x/2}). $$ Let $C = \lim\_{t \to \infty} f'(t)$. Then $$ f'(x) = C - \Theta\left(\sum\_{t=x+1}^\infty 2^{-t/2}\right) = C - \Theta(2^{-x/2}). $$ This shows that $$ f(x) \sim C 2^x - \Theta(2^{x/2}), $$ which in turn implies that $$ g(x) = f(x) - f(x-1) = \frac{C}{2} 2^x \pm O(2^{x/2}). $$ The rest of the terms in the asymptotic expansion depend on the LSBs of $x$, and are left to the interested reader.
> 4 votes

---
Tags: algorithm-analysis, recurrence-relation, recursion
---


# Question
Title: Finding an instance of an n-element set cover
Below is a homework problem where we have been asked to alter a greedy algorithm to return n element instance of a set problem. The original algorithm is also below. I was thinking that I could alter line 3 so that it would run until the size of C was equal to n, and change the logic in line 4 so that it would pick and remove vertices until the size of n. A vertex would be removed when the size of C doesn't equal to n but the cover is complete. I can't really think of any other way to do it. The real problem is that I'm not entirely sure how to make the algorithm run in exponential time like they are asking.

> GREEDY-SET-COVER can return a number of different solutions, depending on how we break ties in line 4. Give a procedure BAD-SET-COVER-INSTANCE.n/ that returns an n-element instance of the set-covering problem for which, depending on how we break ties in line 4, GREEDY-SET-COVER can return a number of different solutions that is exponential in n.
>
> $X$ — some finite set
> $F$ — a family of subsets of $X$
> $C$ — cover being constructed
>
> GREEDY-SET-COVER($n$)
> 1 let $U = X$
> 2 let $C = \varnothing$
> 3 while $U \ne \varnothing$
> 3a select an $S \in F$ that maximizes $\left|S \cap U\right|$
> 3b set $U = U \setminus S$
> 3c set $C = C \cup \\{S\\}$
> 4 return $C$

Could it be said that since the number of subsets a set has is $2^n$ and that in the worst case this algorithm will end up finding all of those subsets before settling on an n-instance set to return?

# Answer
> 2 votes
I think you are being confused by the way the question is phrased. The question asks for a *sequence of instances $I\_n$*, consisting of triples $\langle X\_n,F\_n \rangle$, such that $|X\_n| = n$ and GREEDY-SET-COVER$(X\_n,F\_n)$ could have $C^n$ many results, for some constant $C\>1$. These results come from the fact that at step 4 there could be many sets that are eligible.

For some reason, the question asks you for an algorithm which *generates* the sequence: given $n$, it should output $\langle X\_n,F\_n \rangle$. Since the instances you are going to construct will be pretty simple, you should have no problem writing an algorithm that generates them, but in fact no one cares about this algorithm; the point is only that these "bad" instances exist (they're not actually bad, mind you).

The easiest way to construct these instances is to use a gadget, say $F\_3 = \\{(1,2),(1,3),(2,3)\\}$. You can check that running the greedy algorithm can result in three different covers. I'll let you continue from here.

---
Tags: algorithms, algorithm-analysis, greedy-algorithms, set-cover, approximation-algorithms
---


# Question
Title: Is it possible to mapping reduce either of these languages to the other?
I have the following two languages, which are languages of TM descriptions:

$$INFINITE = \\{ \langle M \rangle | \mbox{M is a TM and L(M) is infinite} \\}$$

$$A\_{ALL} = \\{ \langle M \rangle | \mbox{M is a TM and } L(M) = \Sigma^\* \\}$$

Neither of these languages are decidable, recognizable, or co-recognizable.

However, I believe they're in $\Pi\_2$, since a TM belongs to $INFINITE$ iff for every $x$, there is a string $y$ and computation history $H$ where $y$ has length greater than $x$ and $H$ is a history that shows that $M$ accepts $y$. And a TM belongs to $A\_{ALL}$ iff for every $w$, there is a computation history $H$ that shows that $M$ accepts $w$. (I'm not sure if this reasoning is correct or not, though).

I have been wondering for a while whether either of these languages are mapping reducible to one another. I don't see a quick way to prove that the languages are *not* reducible to one another, but I similarly can't see a simple reduction in either direction.

Are either of these languages reducible to the other? If so, how?

# Answer
> 2 votes
I'll assume that by $L(M)$ you mean the set of strings on which $M$ halts.

Hints:

1. INFINITE to A*ALL*: Given a Turing machine $M$, construct a Turing machine $M'$ that on input $x$ halts if and only if $M$ halts on some $y \geq x$. (Arrange the inputs in some arbitrary way of your choice.)
2. A*ALL* to INFINITE: Given a Turing machine $M$, construct a Turing machine $M'$ that on input $x$ halts if and only if $M$ halts on all $y \leq x$.

Both directions require use of *dovetailing*.

---
Tags: computability, reductions
---


# Question
Title: finding a an object with constant velocity on an infinite grid in discrete time steps
Assume you have an object moving at a constant velocity(up, down, left, right) in a grid. You have unlimited resources (memory, time). At any given time step in the grid, you can "guess" the location of the object, and you win if it is currently at that position. Without relying on probability techniques, what would be the best way to approach catching this object?

# Answer
> 1 votes
Hint: "Guess" the starting point and the velocity, and use diagonalization. (I.e. make a list $\langle p\_i, v\_i \rangle$ of pairs of starting points and velocities, and at time $t$ test $p\_i + tv\_i$.) I'll let you figure out why it works.

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


# Question
Title: L is a regular language and w is any word, not necessarily in L. Show that L is regular
$L$ is a regular language and $w$ is any word, not necessarily in $L$. We define the set as

$$L/w = \\{x \in \Sigma ^\* \mid xw \in L\\}.$$

Show that $L/w$ is regular.

I'm really struggling with this one. I know its going to come on my final next week.

# Answer
> 2 votes
Hint: Consider a DFA for $L$. Suppose that upon reading $x$, the DFA is at state $s$. Can you predict at which the DFA would be after reading $xw$?

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


# Question
Title: Which potential function does this algorithm minimize or maximize?
Considering two sets $A, B$ containing some $p$-dimensional points $x \in \mathbb{R}^p$. Let $d\_x^S = \min\_{x' \in S \setminus \\{x\\}} \lVert \mathbf{x} - \mathbf{x'} \rVert$ denote the Euclidean distance from $x$ to its nearest point in $S$. We have a very simple algorithm:

1. $\forall x \in A$, if $d\_x^A \> d\_x^B$ then move $x$ from $A$ to $B$.
2. $\forall x \in B$, if $d\_x^A \< d\_x^B$ then move $x$ from $B$ to $A$.
3. Repeat (1) and (2) until convergence

Convergence is when there is no more $x \in A$ such that $d\_x^A \> d\_x^B$, and there is no more $x \in B$ such that $d\_x^A \< d\_x^B$.

How could I figure out which function does this algorithm minimize or maximize at each iteration ? The function $\Phi(A)+\Phi(B) = \sum\_{x \in A} d\_x^A + \sum\_{x \in B} d\_x^B$ does not seem to decrease at each iteration.

Note: another version of this algorithm is when we define $d\_x^S$ as the mean distance from $x$ to its $k$ nearest points in $S$, instead of the distance to its nearest point in $S$. I don't know if $k \> 1$ would make the proof more complicated or not.

# Answer
> 3 votes
It takes at most $|A \cup B|$ iterations until convergence. Consider the directed graph $D(V,E)$ with a vertex $v \in V$ for each point $p\_v \in (A \cup B)$ and a directed edge $(u,v) \in E$ such that $p\_v, v \neq u$ is the nearest point to $p\_u$ (connect each point to its nearest neighbour point).

If points $p\_u$ and $p\_v$ are each other's nearest then $(u,v),(v,u) \in E$. On the other hand, there is no cycle consisting of more than two edges. For contradiction assume the corresponding points in such a cycle as $p\_0,p\_1,...,p\_k,p\_{0}$. Since each $p\_{((i+1) \bmod k)}$ is the nearest point to $p\_i$ the distances decrease as we go along the cycle. This means that $p\_k$ is closer to $p\_0$ than $p\_1$ and by construction this is not possible. A cycle of length three or more could cause an infinite chain of label changes (switching between labels $A$ and $B$).

The out degree of vertices in $D$ is exactly one, and in any path the last vertex have an out edge to its previous vertex in that path (because they are mutually each other's nearest). So the last vertex change label at most once, in the first iteration. Then its label propagates backward along all the path ending at this vertex until all the vertices in those paths receive this label.

Therefore, at each iteration, at least one vertex in any path gets its final label. So the number of iterations is the length of the longest path in $D$ which is at most $|V|-1$.

---
Tags: algorithms, complexity-theory, algorithm-analysis, optimization
---


# Question
Title: How to determine the size of training data using VC dimension?
I want to determine the size of training data ($m$) when I know the parameters $VC(H)$, $δ$ and $e$. As I know the $VC$ bound satisfy this equation:

$$ \mathrm{error}\_{\mathrm{true}}(h) \le \mathrm{error}\_{\mathrm{train}}(h) + \sqrt\frac{VC(H) \times \ln\left(\frac{2m}{VC(H)} + 1\right) + \ln(4δ)}m $$

but how can I determine the size of training data ($m$) if I know the others?

# Answer
> 1 votes
Thanks Yuval for your answer!:) I found the correct solution. The bound computed as follows:

$m \geq \frac{1}{e}(8\times VC(H)\times log\_2(\frac{13}{e})+4\times log\_2(\frac{2}{\delta}))$

# Answer
> 2 votes
Suppose you're aiming for a specific error rate. Suppose for the moment that there is no training error. You have an inequality involving all your known parameters and the unknown $m$, and you can solve it to obtain a value of $m$ that guarantees the specific true error rate, assuming that there is no training error. If you then run classification, you can correct for the training error and repeat.

The bound obtained through usage of VC dimension could be very pessimistic, and I don't know how useful it is in practice. Perhaps your instructor will address this later on in the course (or perhaps the issue will be swept under the rug).

---
Tags: machine-learning, learning-theory, vc-dimension
---


# Question
Title: Showing Context Free Grammars that are regular if and only if L(G) = Σ∗.
Suppose that G is a context-free grammar. How can I show that “Is L(G) regular?” is undecidable. Also, prove that L is always context-free but is regular if and only if L(G) = Σ∗.

This is what I have so far

Let N be some language that is known to be context-free but not regular (for example, {a^nb^n | n ≥ 0}). Consider the language L = N#Σ∗ ∪ Σ∗#L(G), where # is some symbol that is not in L(G) or N.

Where to? I just know my prof is going to put this on my exam :s.

# Answer
> 2 votes
This proof-snippet is what you are probably looking for.

We follow your definition. $N$ is a fixed non-regular context-free language over $\Sigma$, $\\#$ is a new symbol. For a given grammar $G$ let $L = N\\#\Sigma^\* \cup \Sigma^\* \\# L(G)$. Assume $L(G) = \Sigma^\*$, then $L = \Sigma^\*\\#\Sigma^\*$ which is a regular language. On the other hand, if $w\notin L(G)$, then $L\cap \Sigma^\*\\#w = N\\#w $, which is *not* regular (as regular languages are closed under quotient, and $N$ is not regular). Thus also $L$ itself is not regular (as regular languages are closed under intersection).

Conclusion: $L$ is context-free, and $L$ is regular iff $L(G) = \Sigma^\*$.

---
Tags: regular-languages, context-free
---


# Question
Title: Can Floyd-Warshall be used to solve an APSP problem without copying the matrix?
According to CLRS, each iteration of the outermost loop (on $k$) makes a new copy of the adjacency matrix. Is it safe not to copy the matrix on every iteration?

What I mean is, according to CLRS:

$d\_{ij}^K = \min(d\_{ij}^{K-1}, d\_{ik}^{K-1} + d\_{kj}^{K-1})$

Is the following possible?

$d\_{ij} = \min(d\_{ij}, d\_{ik} + d\_{kj})$

I have tried not copying the matrix, and got the same result before as the one which makes a copy after each iteration, but did I just get lucky?

# Answer
No you are not lucky, it is possible to use the program that way. The notation $d\_{ij}^k$ probably is used for better explaining what the algorithm has achieved in the $k$th step. Note that the variant where one overwrites the matrix as you suggest is presented in Exercise 25.2-4 (in my second edition of the book, which is not the latest).

The secret to that puzzle is in principle that an assignment to $d\_{i,j}^k$ is only done once, and that value is never again used in the computation, except for the case where either $i=k$ or $j=k$. However, the algorithm does not change those values in the $k$th step. You figure out why.
> 3 votes

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


# Question
Title: Easy way to prove that this algorithm eventually terminates
## Introduction and notations:

Here is a new and simple version of my algorithm which seems to terminates (according to my experiments), and now I would like to prove that.

Let the notation $x\_i \in \mathbb{R}^p$ refer to a $p$ dimensional data point (a vector). I have three sets A, B and C, such that $|A| = n$, $|B| = m$, $|C| = l$: $$A = \\{x\_i | i = 1, .., n\\}$$ $$B = \\{x\_j | j = n+1, .., n+m\\}$$ $$C = \\{x\_u | u = n+m+1, .., n+m+l\\}$$

Given $k \in \mathbb{N^\*}$, let $d\_{x\_i}^A$ denote the mean Euclidean distance from $x\_i$ to its $k$ nearest points in $A$; and $d\_{x\_i}^C$ denote the mean Euclidean distance from $x\_i$ to its $k$ nearest points in $C$.

## Algorithm:

I have the following algorithm which iteratively modifies the sets A and B by moving some selected elements from A to B and vis versa, and C remains always the same (do not change). To make it simple: the purpose of the algorithm is to better separate the sets $A$ and $B$ such that "the points of $B$ are more similar to those of a known fixed set $C$" and "the points of $A$ are finally self-similar and farther from those of $C$ and the final set $B$":

* $A' = \\{ x\_i \in A \mid d\_{x\_i}^A \> d\_{x\_i}^C \\}$ ... (1)
* $A = A \setminus A'$; $B = B \cup A'$ ... (2)
* $B' = \\{ x\_i \in B \mid d\_{x\_i}^A \< d\_{x\_i}^C$ } ... (3)
* $B = B \setminus B'$; $A = A \cup B'$ ... (4)
* Repeat (1), (2), (3), and (4) until: (no element moves from $A$ to $B$ or from $B$ to $A$, that is A' and B' become empty) or ($|A| \leq k$ or $|B| \leq k$)

The algorithm terminates in two cases:

* when $|A|$ or $|B|$ becomes less than or equals to $k$
* or the most standard case, when $A' = B' = \emptyset$, which means that no more elements moves between A and B.

## Question:

How to prove that this algorithm eventually terminates ? I didn't found a convenient potential function which can be strictly minimized or maximized by the algorithm. I have unsuccessfully tried some functions: the function $\sum\_{x \in A} d\_x^C + \sum\_{x \in B} d\_x^A$ but it is not increasing at each iteration. The function $\sum\_{x \in A} d\_x^A + \sum\_{x \in B} d\_x^C$ but it is not decreasing at each iteration. The function $\sum\_{x \in A} d\_x^A + \sum\_{x \in B} d\_x^B$ seems not to be decreasing at each iteration. The function $\sum\_{x \in A} d\_x^B + \sum\_{x \in B} d\_x^A$ seems not to be increasing at each iteration. So what is the convenient potential function which can be show to either increase or decrease at each iteration ? Or should we show that the function decreases but not at each iteration (after some iterations rather) ? How ?

## Notes:

* The $k$ nearest points to $x$ in a set $S$, means: the $k$ points (others than $x$) in $S$, having the smallest Euclidean distance to $x$. You can just take $k = 1$ to simplify the analysis.
* I don't know if this may help or not, but I have the following property for my initial sets $A, B, C$: initially $\forall x\_i \in B, x\_j \in A$, if $x\_b \in C$ is the nearest point to $x\_i$ and $x\_a \in C$ is the nearest point to $x\_j$ then always $distance(x\_i, x\_b) \< distance(x\_j, x\_a)$. This intuitively means that points in $B$ are closer to $C$ than points in $A$.
* If that makes the analysis easier: it is totally possible to consider a slightly different version of the Algorithm where as soon as a point from $A$ should be moved to $B$, it is moved from $A$ to $B$ (without passing by $A'$), and vis versa for $B$.

# Answer
Here's the solution for the case $k = 1$:

Assume the algorithm does not terminate. Since there are a finite number of states of the algorithm (assignments of points to $A$ and $B$), the algorithm state must repeat in a cycle. Since the cycle goes through different states, there must be a point that switches between $A$ and $B$ infinitely often.

Let $x$ be a point that switches infinitely often in this cycle. Pick the first iteration of the algorithm within the cycle during which $x$ switches from $B$ to $A$. For $x$ to switch to $A$, there must have been at least one point $x'$ in $A$, with $d\_x^C \> dist(x, x')$. Arbitrarily pick the smallest-labeled such point; define a function $f$ so that $f(x) = x'$. Note that $x'$ also must switch between $A$ and $B$ infinitely often (because if $x'$ stayed in $A$ permanently, so would $x$), so we can take $f(f(x)), f(f(f(x))),$ etc.

Since we have a finite number of points, the iterates of f must eventually repeat: $f^n(x) = f^m(x)$ for some $m \> n$. Now look at the corresponding sequences of distances from C: $d\_{f(x)}^C, d\_{f^2(x)}^C, ... d\_{f^n(x)}^C, ... $. Since it repeats, this sequence cannot be uniformly decreasing. There must be an iterate $o$ such that $d\_{f^{o-1}(x)}^C \leq d\_{f^o(x)}^C$

Now, $f^{o-1}(x)$ and $f^o(x)$ are close enough to each other to cause each other to be in $A$, if one of them is. That is, they're closer to each other than either of them is to $C$: $d\_{f^o(x)}^C \geq d\_{f^{o-1}(x)}^C \> dist(f^{o-1}(x), f^o(x))$ (from definition of $f$)

So as soon as $f^{o-1}(x)$ and $f^o(x)$ are both in $A$, they will keep each other in $A$ forever (see lines 1-2 of the algorithm). This contradicts the fact that all the iterates of $f$ must switch sets infinitely often. Thus, for the case when $k = 1$, the algorithm terminates.
> 2 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, optimization
---


# Question
Title: Design a DFA which accepts words with sorted letters
I have just started learning Theory of Computation and have come across a question which I am not able to solve.

The question is as follows:

```
Design a DFA that reads a word (character strings) and decides whether the letters
of the word are in sorted order.
For example: 'adept' and 'chilly' have their words in sorted order but 'baby' doesn't.

```

How should I design a DFA for this language?

What I have tried:

I think there must be two states.

```
1) While the DFA is scanning the word, the state (q1) will transit to itself
if it reads a letter greater than or equal to previous letter read.

That is if the current_letter_read >= previous_letter_read then
q1 transits to itself. Otherwise, there is no action.

2) If '\0' is encountered, then the DFA transits to the final accepting state.

```

But in DFA is it possible to do so? How should I draw a DFA for this? I got stuck at this point. Am I missing some basic concept that I should know?

# Answer
> 1 votes
Your suggestion is to use two states and stay in the first one until the machine reads a character that is strictly before the last one it read. This can't be right because a DFA can't test the current character against previous ones. A DFA knows exactly two things: which state it's in now and what the next character of the input is. Its decision about which state to move to is based only on those two pieces of information and everything from the past is forgotten.

When designing automata, it's a good idea to think about what each state means. For example, consider the following automaton, with states that I'll unhelpfully call $A$ and $B$. $A$ is the start state and is accepting; $B$ is non-accepting. Whenever the automaton reads a character, it moves to the other state. What does it do? Well, it accepts the empty string because the start state is accepting. If it reads a character, it moves to the non-accepting state $B$; if it reads another one, it moves back to $A$. So, whenever the machine has read an even number of characters, it's in $A$ and, whenever it's read an odd number of characters, it's in $B$. It would, therefore, make much more sense to call the states "even" and "odd" because that's what they represent. Knowing that, you could easily write an automaton that accepts exactly words whose length is, say, equal to 2, mod 3. Or exactly the words equal to 3, 5 or 11, mod 12. Being a bit more clever, you could write an automaton that accepts exactly the strings whose length is equal to 3 mod 5 and also equal to 0 mod 4 (hint: 20 states).

That doesn't directly answer your question but I think you've figured out the answer, from your comments. Yes, it's going to need about 28 states so it'll have about 28x27=756 arcs so you'll have to describe it instead of drawing it in full.

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


# Question
Title: For how large graphs can we still check for isomorphism?
Let $G\_1,$ $G\_2$ be two arbitrary graphs with $n$ vertices and we want to check if they are isomorphic.

**Question 1.** For what maximal value of $n$ we can actually perform such verification?

**Question 2.** Is there any result like as a list of all non-isomorphic graphs up to $n$, and what is the value of $n$ — 10, 20?

# Answer
> 7 votes
The number of non-isomorphic graphs on $n$ nodes is given by https://oeis.org/A000088. If you only care about connected graphs then it's https://oeis.org/A001349. Programs like *nauty* can enumerate these graphs for you. That answers your second question.

For your first question, it depends on the meaning on *actually*. There are algorithms which work for fairly large number of vertices, but fail (take a long time) on some bad examples that supposedly don't happen (or are rare) in practice. The worst-case asymptotic complexity of graph isomorphism is still open. The Wikipedia page has an old (2001) reference which compares real-world algorithms for graph isomorphism. Perhaps you could find a more recent one and update the page.

# Answer
> 6 votes
this is a nice recent survey incl empirical comparisons by a leading researcher who has worked decades in the field & can answer the question about state of the art/performance of best-optimized algorithms.

> We report the current state of the graph isomorphism problem from the practical point of view. After describing the general principles of the refinement-individualization paradigm and proving its validity, we explain how it is implemented in several of the key programs. In particular, we bring the description of the best known program nauty up to date and describe an innova- tive approach called Traces that outperforms the competitors for many difficult graph classes. Detailed comparisons against saucy, Bliss and conauto are presented.

---
Tags: algorithms, graph-algorithms
---


# Question
Title: Proving $ \{ \langle D_1, ... ,D_K \rangle : \text{ where } D_i \text{ are DFAs and } {\bigcap}_{i=1}^k L(D_i) = \emptyset \} $ is NP-Hard
The question (Prove L is NP-hard) was about proving that the following language is NP-hard: $$ L = \\{ \langle D\_1, D\_2, ... ,D\_K \rangle : k \in {N}\text{, the } D\_i \text{ are DFAs and } {\bigcap}\_{i=1}^k L(D\_i) = \emptyset \\} $$

That got me thinking about the related problem:

$$ L' = \\{ \langle D\_1, D\_2, ... ,D\_K \rangle : k \in {N}\text{, the } D\_i \text{ are DFAs and } {\bigcap}\_{i=1}^k L(D\_i) \neq \emptyset \\} $$

I would imagine that $L'$ is also NP-hard, but I couldn't think of any reductions.. am I missing something obvious?

# Answer
The language $L$ is in fact PSPACE-complete, so in particular it's both NP-hard and coNP-hard. Here is a quick sketch of the proof.

**$L$ is in PSPACE.** This part is easy. The intersection of the DFAs can be realized as a DFA with $n^n$ many states, hence if the intersection is non-empty, there must be a word of length $n^n$ accepted by all DFAs. Counting up to $n^n$ requires $O(n\log n)$ space, so there is an NPSPACE machine for $L$: the machine guesses a word of length at most $n^n$ and verifies (in parallel) that the word is accepted by all DFAs. Savitch's theorem shows that NPSPACE=PSPACE, so we're done.

**$L$ is PSPACE-hard.** The reduction is from TQBF, which is the problem, given a formula $\varphi(x\_1,\ldots,x\_n)$, to decide the truth value of $\psi = \exists x\_1 \forall x\_2 \exists x\_3 \cdots \varphi(x\_1,\ldots,x\_n)$. Consider some iterative algorithm for evaluating $\psi$: it goes over all possible assignments of $x\_1,\ldots,x\_n$, and computes intermediate values of $Q x\_i \bar{Q} x\_{i+1} \cdots \varphi(y\_1,\ldots,y\_{i-1},x\_i,\ldots,x\_n)$ (where $Q \in \\{\forall,\exists\\}$). We can write this computation as one long string $w$. The computation can be verified *locally*: for example, if all we wanted is to verify that $w$ is a $\\#$-separated list of all numbers from $0$ to $2^n-1$ in binary (i.e. for $n=2$, $\\#00\\#01\\#10\\#11$), then we can write several regular expressions which verify this:

* $w$ is a $\\#$-separated list: $(\\#(0+1)^n)^\*$
* $w$ starts with $0^n$: $\\#0^n\Sigma^\*$
* $w$ ends with $1^n$: $\Sigma^\*\\#1^n$
* The LSBs in $w$ behaves correctly: $(\\#(0+1)^{n-1}0\\#(0+1)^{n-1}1)^\*$
* The MSBs in $w$ behaves correctly: $(\sum\_{i=0}^{n-2} \\#0(0+1)^i0(0+1)^{n-2-i})^\*\\#01^{n-1}\\#10^{n-1}(\\#1(0+1)^{n-1})^\*$
* Similar (but more complicated) regular expression ensure that the other bits behave correctly.

All these expressions (and the corresponding DFAs!) are of length polynomial in $n$, and there is a polynomial number of them, so using DFA intersection you can express the fact that $w$ is of the given form.

The actual $w$ is more complicated, but the idea is the same. At the very end of $w$ will appear the actual value of $\psi$, and we can add a regular expression which verifies that $\psi$ is true. This reduces TQBF to DFA intersection.

The classical reference is Kozen's Lower bounds for natural proof systems, or you can check my account (Section 4) which proves a different result but contains everything that you need to prove that $L$ is PSPACE-hard.
> 6 votes

---
Tags: complexity-theory, np-hard
---


# Question
Title: Environment requirement in training image dataset for classifier
I have a question about preparing the dataset of positive samples for a cascaded classifier that will be used for object detection.

As positive samples, I have been given 3 sets of images:

1. a set of **colored** images in full size (about 1200x600) with a **white background** and with the object displayed at a different angles in each image
2. another set with the same images in grayscale and with a **white background**, scaled down to the detection window size (60x60)
3. another set with the same images in grayscale and with a **black background**, scaled down to the detection window size (60x60)

My question is that in Set 1, should the background really be white? Should it not instead be an **environment** that the object is likely to be found in in the testing dataset? Or should I have a fourth set where the images are in their natural environments? How does environment figure into the training samples?

# Answer
I think you should have a fourth dataset where the images are in their natural environments because you will need information with white background when you will be testing the datasets.
> 3 votes

---
Tags: machine-learning, image-processing, computer-vision, data-sets, classification
---


# Question
Title: Job sites for applied/interdisciplinary mathematics related to computer science?
I'm looking for job sites in applied/interdisciplinary mathematics, more specially, say postdocs or higher positions in mathematics and medical imaging, mathematics and computer vision. I'm aware of mostly all the popular job sites, mathjobs, euro math jobs, jobs.ac.uk, nordic math jobs etc etc, but most of the jobs there are of 'pure' nature, with very few for applied/interdisciplinary.

I'm trying to find postdoctoral position in mathematical imaging problems, which would use significant amount of conformal/quasiconformal mappings, Riemann surfaces, differential geometry etc. Looking into individual group's webpage is too much work. But if there's an webpage containing all the information, that'll be much better!

So, if you know any such website for the above (for Europe(preferable) and US), I'd appreciate if you could pass them onto me. Thanks!

# Answer
There are 2 google lists:

```
Imageworld

visionlist

```

You can join these. They have a lot of information.
> 2 votes

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


# Question
Title: Formulas for which any equivalent CNF formula has exponential length
I read a claim that

> there are formulas for which any equivalent CNF has exponential length.

Can you show me an example for such a boolean formula? I have been trying to build it myself and failed.

# Answer
There might be a difference between *equivalence* and *equisatisfiability* that you are getting caught up on.

If you want an example where an equivalent conversion into CNF has an exponential growth, see wikipedia on **Conjunctive normal form: Conversion into CNF**:

> $$(X\_1 \wedge Y\_1) \vee (X\_2 \wedge Y\_2) \vee \dots \vee (X\_n \wedge Y\_n).$$

This formula leads to exponential length CNF formulas, if the conversion must be *equivalent*.

The article continues on about how by introducing new variables, one can obtain an *equisatisfiable* formula that grows only linearly. These types of conversions usually create new models that contain the old model, so while the new formula is not equivalent, a satisfying assignment to the new formula will directly give a satisfying assignment to the old formula.

Though, there might be conversions that do not contain the old model, I've not seen one. As a side-note, Boolean satisfiabilty is **self-reducible**, which means that an algorithm that solves the decision problem, can be used to solve the optimization problem, via forcing one variable, and repeated calls to the solver. This means that even if you have a conversion that generates another, equisatisfiable formula, but for which the models are very different, you can find the satisfying assignment of the original formula (in time bounded by a polynomial of the runtime of the solver).
> 8 votes

# Answer
Try parity. Parity of $n$ variables has formulas of size $O(n^2)$, but every clause in the CNF must be of width $n$, so there must be at least $2^{n-1}$ of them.

Here are some more details. The $O(n^2)$ formula for parity is obtained by a recursive construction. For simplicity, let's assume that $n = 2^m$ and only count leaves. We use the following formulas: $$ \begin{align\*} \operatorname{parity}(x\_1,\ldots,x\_{2n}) = &(\operatorname{parity}(x\_1,\ldots,x\_n) \land \lnot \operatorname{parity}(x\_{n+1},\ldots,x\_{2n})) \\ \lor &(\lnot \operatorname{parity}(x\_1,\ldots,x\_n) \land \operatorname{parity}(x\_{n+1},\ldots,x\_{2n})) \end{align\*}$$ and $\operatorname{parity}(x\_1) = x\_1$. Let $P(n)$ be the number of leaves in $\operatorname{parity}(x\_1,\ldots,x\_n)$. Then $$ P(2n) = 4P(n), \quad P(1) = 1. $$ The solution to this recurrence is $P(2^n) = 4^n$. Since parity of $n$ variables can be obtained from parity of $2^{\lceil \log n \rceil} \< 2n$ variables, in total parity for $n$ variables can be realized using a formula containing at most $4n^2$ leaves. The length of a binary encoding of the formula is $O(n^2\log n)$ (the $\log n$ factor comes from the fact that the indices have length $\log n$).

Regarding CNFs, let's consider DNFs instead; the situation is symmetric. Suppose $\phi = T\_1 \lor \cdots \lor T\_\ell$ is a DNF for $\operatorname{parity}$. Each $T\_i$ must contain $n$ variables: given the values of even $n-1$ variables, you cannot be certain that $\operatorname{parity}$ is true. So each term "catches" one $1$-input of $\operatorname{parity}$, of which there are $2^{n-1}$.
> 9 votes

---
Tags: satisfiability
---


# Question
Title: Implement Mathematica's capability of rationalizing machine reals
If I have a variable `x` bound to a machine precision real in *Mathematica*, I can use

```
 y = FromDigits[RealDigits[x]]

```

then y is bound to a *completely equivalent* rational number which has *infinite precision*.

What are the basic principles behind `FromDigits` and `RealDigits`? How could I implement a similar conversion using common machine operations (fixed-size integers and floating point operations) to coerce a double in a rational, or at least obtain the long integer denominator and numerator of a double?

# Answer
> 2 votes
On most current machines a double-precision real number will be represented in IEEE 754's `binary64` format.

```
  63 62 x x x x x x 52 51 x x x x x x x x x x x x x x x x x x x x x 0
| s |      exp        |                mantissa                      |

```

`s`=0 implies positive, `s`=1 implies negative. `exp` is an 11 bit biased signed integer in the range \[-1023, 1024\] (take the unsigned number from the bits and subtract 1023). `mantissa` stores the bottom 52 bits of the fraction.

Numbers with exponents in the range \[-1022, 1023\] are normalized (bit 52 of the mantissa is implicitly "1".) The number represented by a particular bit pattern is $-1^s (1 + (\mathrm{mantissa} / 2^{52})) 2^\mathrm{exp}$.

Numbers with exp=1024 are special: if the mantissa is 0 then they represent + or - Infinity (from overflow or divide by 0, for example). If the mantissa is non-zero then the represent NaN (for example sqrt(-1)).

Numbers with exp=-1023 are special: if the mantissa is 0 then the represent + or - 0. If the mantissa is non-zero then the represent denormalized numbers: $-1^s (\mathrm{mantissa}/2^{1075})$.

In C++ on most current machines the following code will probably do most of what you want (I adapted this from some binary32 code without testing, so test first.) We will use `uint64_t` from the `cstdint` header for the bit-level representation, and a union for extracting the bits. The following code does *not* deal with zero, denormals, NAN or positive or negative Infinity (HUGE\_VAL).

```
#include <cstdint>    // for uint64_t

typedef union
{
  double   value;
  uint64_t bits;
} ieee754_binary64_union;

#define IEEE754_MANTISSA_BITS 52
#define IEEE754_EXPONENT_BITS 11

#define IEEE754_HIDDEN_BIT    (((uint64_t)1) << IEEE754_MANTISSA_BITS)
#define IEEE754_MANTISSA_MASK (IEEE754_HIDDEN_BIT - ((uint64_t)1))
#define IEEE754_EXPONENT_MASK ((1 << IEEE754_EXPONENT_BITS) - 1)
#define IEEE754_EXPONENT_BIAS ((1 << (IEEE754_EXPONENT_BITS - 1)) - 1)

static inline
double
ieee754_bits2float(uint64_t u)
{
  ieee754_binary64_union fiu;
  fiu.bits = u;
  return fiu.value;
}

static inline
uint64_t
ieee754_float2bits(double f)
{
  ieee754_binary64_union fiu;
  fiu.value = f;
  return fiu.bits;
}

static inline
int
ieee754_get_sign(double f)
{
  return ieee754_float2bits(f) >> 63;
}

static inline
int
ieee754_get_exponent(double f)
{
  uint64_t bits = ieee754_float2bits(f);
  return (((bits >> IEEE754_MANTISSA_BITS) &
           IEEE754_EXPONENT_MASK) -
          IEEE754_EXPONENT_BIAS);
}

static inline
uint64_t
ieee754_get_mantissa(double f)
{
  uint64_t bits = ieee754_float2bits(f);
  return ((bits & IEEE754_MANTISSA_MASK) + IEEE754_HIDDEN_BIT);
}

static inline
double
ieee754_make_double(int      sign,     // 1 (neg) or 0 (pos)
                    int      exponent, // range -1023 -> 1024
                    uint64_t mantissa) // with or without hidden bit
{
  uint64_t collected_bits =
    ((uint64_t)sign << (IEEE754_MANTISSA_BITS + IEEE754_EXPONENT_BITS))     |
    ((uint64_t)((exponent + IEEE754_EXPONENT_BIAS) & IEEE754_EXPONENT_MASK) <<
                IEEE754_MANTISSA_BITS)                                      |
    (mantissa & IEEE754_MANTISSA_MASK);
  return ieee754_bits2float(collected_bits);
}

```

# Answer
> 5 votes
The continued fraction algorithm is easy enough to implement. The first step is to compute the *continued fraction* of the input $x = \[c\_0;c\_1,\ldots\]$. You start with $x\_0 = x$, and use the recurrence $c\_i = \lfloor x\_i \rfloor$, $x\_{i+1} = 1/(x\_i - c\_i)$. You stop when $x\_i - c\_i$ is "small enough". The next step is to compute the convergent of the continued fraction. You can find the appropriate formulas on the web. In practice, both steps are performed at the same time.

There are some issues with numerical stability, and that might make it difficult to match the performance of Mathematica, but for simple cases it works well enough.

The resulting rational number is not actually *equivalent* to the floating point number - there's probably some small error. In fact, the rational approximation may be *more accurate* in some cases, and off the mark in others. However, floating point numbers are secretly rational numbers - they are of the form $\pm 2^x M$, where $x$ is the integer exponent (positive, zero or negative) and $M$, the mantissa, is a rational number between $0$ and $1$ (or $0$ and $2$). In fact, it's always of the form $A/2^B$, where $B$ is the length of the mantissa and $A$ is some non-negative integer. If you really care for it, you could decode a real number into this representation, and thus obtain a truly equivalent rational number.

---
Tags: number-theory, arithmetic, real-numbers
---


title: NFA to DFA convertion explanation

text:
# Question
Title: NFA to DFA convertion explanation
I've converted this NFA to a DFA and I get a similar soultion automata but I'm not sure if I really understand everything.

Please correct me if I'm explaining it wrong, I would love some feedback.

From the state 0 we only have the set {0} since there doesn't exist any ε-transition. After that we have to input "a" to move to state 1 and here I've got a question. Does it include the 0 also since "a" can either take you to state 1 but also to state 0 since it loops?

Continuing we want to move to state 2 via "a" input. Why does it include the "0"? Is it because you have to consider all the inputs from each set in the state 1? Like, if you input "a" at 0 you loop but you can also go to state 1. From 1 if you input "a" you move forward to state 2. Which gives us the set {0,1,2}.

If this is correct, then the procedure for state 3 should be the same, right? Also, at the third state {0,1,2,3} he can't just loop "b" since the other states can't "handle" the input so you have to create a new state containing the set {0,3} which can handle the "b" input?

Sorry if this is a bit long, I just want to understand what is going on really.

# Answer
> 2 votes
You've basically got it. The reason why the `a` loops is because whichever state you were in, you can end up in any one of them (if you were in 0, maybe you took the looping a and ended up in 0).

The way I think of it is, with the NFA, you are maintaining a list of states you are in at any one point. When you convert to DFA, we have a state for any set of states we can be in (the power set of all the states in the NFA). We can tidy this up if we want (removing inaccessible nodes etc.) but that is the basic principle.

So with yours, you state in state 0. Then we read an `a` and at this stage we could be in {0, 1}. Then we read in another `a` and now we could have done:

* Been in state 0 and stayed in state 0
* Been in state 0 and advanced to state 1
* Been in state 1 and advanced to state 2

Therefore we could now be in any of {0, 1, 2} so that's the node we go to in the DFA.

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


# Question
Title: Which algorithms are usable for heatmaps and what are their pros and cons
This is a cross post from Stack Overflow, and DSP at Stackexchange since I cannot really decide which part of Stackexchange is most fitting. If this is the wrong place please tell me and I'll remove the question.

I have a matrix with numerical data. The matrix contains values from 0 to an arbitrary integer value.

Each element of the matrix is equivalent to a coordinate on a map.

I want to display that data as a heatmap overlayed the original map.

The three approaches I have found so far are

1. Linear interpolation. I guess the interpolation is don from the original datapoint to some set distance away from it in each direction.
2. Average of surrounding cells. Each empty cell gets the average value of the eight adjacent cells.
3. Gaussian blur as suggested on the SO thread.
4. Box blur with 1..n passes.

Are there any more methods? What are the pros and cons of the different approaches? What is a good source, online or print, for a discussion on heatmaps or similar problems?

# Answer
> 8 votes
If I have understood your question correctly (an illustrative example would have been helpful), I would recommend either Gaussian blurring or linear interpolation depending on the behavior you are after. Both are simple and should perform relatively fast even on a handheld device.

**Linear interpolation** (or rather bilinear interpolation) is simple but requires a square heat sample grid and you get some boundary effects that might be undesirable. The method is the most representative since "empty cells" (i.e., cells without heat information) are simply empty because of sparse sampling and not because they are void of heat. The interpolation tries to fill in the missing heat information in the empty cells by looking at the nearby heat samples.

**Cell averaging** will give you an equally high response in a cell neighboring the heat sample as in the heat sample cell itself (granted that the average is computed for all cells including the cells containing heat samples). If the average is computed for empty cells only (i.e., for cells with no heat information) then the cells with the heat sample will keep its full signal while adjacent cells will contain an average, which in a sparse sample grid will be 1/8 of the heat sample, resulting in a distribution almost as misleading as only using the original heat samples.

**Gaussian blurring** with a wide enough kernel is simple and gives a better representation of the impact of the heat samples than the cell averaging. However, the values in the blurred heat map for the empty cells will only be affected by the heat "spread" from the sample cells. So if the heat map is sparse, there will likely be empty cells on equal distance between two heat cells that do not get any heat information at all.

I hope this helps.

---
Tags: algorithms, image-processing, matrices, signal-processing
---


title: Range of CRC-32

text:
# Question
Title: Range of CRC-32
What is the range of “the” CRC-32, the one used by Unix, Ethernet, zip, and many other industrial standards?

Mathematically, a CRC is defined as follows: let $G$ be the CRC polynomial in $\mathbb{F}\_2\[X\]$, and $M$ be a representation of the input bitstring in $\mathbb{F}\_2\[X\]$. Let $Q$ be the quotient of $M \cdot X^{\deg G}$ by $G$; the CRC value is $\bar Q(2)$ where $\bar Q$ is the canonical injection of $Q$ into $\mathbb{Z}\[X\]$. The codomain of the CRC function is thus the integer range $\[0,2^{\deg G}-1\]$ (or equivalently the set of polynomials of degree $\le \deg G$). Which values are reachable?

This question is specifically about $$G = G\_\text{Ethernet} = X^{32}+X^{26}+X^{23}+X^{22}+X^{16}+X^{12}+X^{11}+X^{10}+X^{8}+X^{7}+X^{5}+X^{4}+X^{2}+X^{1}+X^{0}$$ though I'm curious whether the result generalizes to other common CRC.

Bonus: is there anything known and interesting about the relative density of preimages?

# Answer
> 6 votes
The CRC polynomial is very probably *primitive*, that is the order of $X$ modulo $G$ is $2^{32}-1$. In other words, $X$ is a generator of $GF(2^{32})^\times$. So using inputs $0,2^0,\ldots,2^{2^{32}-2}$ will result in all possible $2^{32}$ values.

CRCs are hopefully always chosen with primitive polynomials, so this result is general. Even if the polynomial is irreducible but not primitive, you can always pick some generator $Q(X)$ of $GF(2^{32})^\times$ and use it to obtain the same result.

Addendum: if $CRC(M\_1) = CRC(M\_2)$ then $M\_1-M\_2$ is a multiple of the generating polynomial. Hence CRC is a bijection from the set of messages of length $4$ bytes to integers of length 32 bits.

---
Tags: arithmetic, error-correcting-codes, crc
---


# Question
Title: How to present ping data from ICMP timestamp
The ICMP timestamp protocol is useful for determining which path — forward or reverse — is contributing to the jitter on the line.

In an ideal world, all computers would have an excellent ntpd, and time accuracy of about 1ms (the granularity of ICMP timestamp) should not be a problem:

```
0       145.5   146 = 75 + 71
1       142.7   142 = 72 + 70
2       140.7   140 = 70 + 70
3       146.7   146 = 76 + 70
4       148.3   148 = 77 + 71
5       157.5   157 = 87 + 70
6       167.1   167 = 96 + 71
7       166.3   166 = 95 + 71
8       167.7   167 = 97 + 70
9       159.0   159 = 88 + 71

```

However, in reality, as per https://stackoverflow.com/questions/20172028/awk-hping-print-difference-between-icmp-originate-receive/20186781#20186781, the data could be like this:

```
0       165.9   166 = -142113 + 142279
1       160.2   160 = -142118 + 142278
2       155.2   155 = -142122 + 142277
3       156.5   156 = -142121 + 142277
4       164.7   165 = -142112 + 142277
5       164.4   164 = -142111 + 142275
6       160.9   161 = -142114 + 142275
7       158.1   158 = -142117 + 142275
8       155.6   156 = -142119 + 142275
9       143.0   143 = -142131 + 142274
10      153.2   153 = -142120 + 142273
11      157.1   157 = -142115 + 142272
12      158.3   158 = -142114 + 142272
13      148.6   149 = -142123 + 142272
14      144.3   144 = -142127 + 142271
15      145.3   145 = -142125 + 142270

```

Which still shows that only one path is responsible for the jitter, since only one value jumps up and down randomly, whereas the other one is decreasing monotonically (probably due to an actively-running ntpd, which is correcting the time as we ping).

Another example could be less wrong-looking of the time not being synchronised, say:

```
0       165.9   166 = -113 + 279

```

Or, better yet:

```
0       165.9   166 = 7 + 159

```

Or, say, still wrong by some 10ms to 40ms, on a landline link from Alberta to Vogtland, but much less obvious:

```
0       165.9   166 = 59 + 107

```

How to make scientific sense of this data, for it to be easily presentable, and not blatantly wrong?

Feel free to assume to have between 10 to 1000 measurement points, measured over a couple of seconds or minutes.

# Answer
> 1 votes
You ask:

> How to make scientific sense of this data, for it to be easily presentable, and not blatantly wrong?

Well, the bottom line is: this data *is* blatantly wrong. If your measurement method says that the latency on some link is negative 113 ms, there is something wrong with your measurement method.

Right now, you've got a "garbage in, garbage out" situation. The data you've got does not survive simple cross-checks, which tells you that your measurement methods has problems. What you need to do at this point is go back to the drawing board and devise a better measurement method. For instance, maybe you can find some way to measure the offset between your clock and the remote machine's clock more precisely, and then adjust for that offset.

But in any case, it's pretty clear that the current measurement method isn't adequate on its own.

---
Tags: algorithms, reference-request, computer-networks, synchronization
---


# Question
Title: Is it possible to support .(any symbol) or \d, \w, \W in DFA
Is it possible to build DFA that support \d, \w, .(any symbol)? I understand that we can add each symbol from \[0-9\] as a separate edge for some of the symbols, but what about the others? for example .(any symbol)? or \S (not white space)?

In other words, can we build equivalent DFA for this NFA

```
(1) ---a----> (2)
 |
 |
 .(any symbol)
 |
 \/
 (3)

```

# Answer
> 4 votes
The symbols you mention represent sets of characters. For example, \d represents the set $\\{0,1,2,3,4,5,6,7,8,9\\}$. Whenever you want to place \d, replace it with 10 parallel edges labeled with all digits instead. The same works for your other examples, as long as each symbol represents one *character*. (Otherwise you would get a "generalized NFA".)

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


# Question
Title: Turing machine with possible transitions to the final state
Let's say we want to draw the transition graph of a Turing Machine that accepts that language L and then write the sequence of moves done by the TM when the input sequence is $w = abbcbba$ so I had some thoughts on how this could be built.

$q0 - q1: a,a,R$

$q1-q2: b,b,R$

$q2 (loop): b,b,R$

$q2-q3: c,c,R$

$q3-q4: b,b,R$

But then I'm getting stuck here, I could see $b,b,R$ to the final state and then add a separate node to account for the case $m=3$, but I'm teaching this to myself so maybe someone can step in here and get me back on track.

EDIT:

This might work:

# Answer
> 1 votes
I would define F(set of final states)={$q\_4,q\_5,q\_6$} then:

$ q\_4-q\_5:b,b,R$

$q\_4-q\_7:X,X,R$ for X=a,c

$q\_5-q\_6:b,b,R$

$q\_5-q\_7:X,X,R$ for X=a,c

$q\_6-q\_7:X,X,R$ for X=a,b,c

---
Tags: formal-languages, turing-machines, automata
---


# Question
Title: Finding a function which is a mapping reduction of A to B
How do I precisely define the function which is a mapping reduction of A to B for the following examples?

What is the process of figuring this out?

Given: A and B are languages over the alphabet {0,1}.

Examples:

* A is the language described by 1\*0\*, B is the language described by 01\*0\*
* A={w | the length of w is even}, B={w | the length of w is odd}
* A=B={w | the length of w is even}
* A={0,1}\*, B={00,1,101}

I am studying this material and I am not sure of how to 'precisely' define these functions. Could somebody provide me with solutions and a methodology to finding the solution?

# Answer
The answers are as follows, just functions with input w:

* f(w) = 0w
* f(w) = 0w
* f(w) = w
* f(w) = 00

Basically make sure all scenarios which occur in A are mapped to B and that all which are not, do not map to B
> 1 votes

---
Tags: computability, turing-machines, reductions
---


# Question
Title: Given the set of length of triangle, find the Maximum Area Triangle
Suppose we are given an array of numbers representing lengths of line segments. Find which three of these segments can be assembled into a triangle with maximum area.

I can compute the areas of all $O(n^3)$ possible triangles in $O(n^3)$ time using Heron's formula, and then return the largest. Can this be improved to $O(n^2)$ time? Or even faster?

# Answer
> 7 votes
There is an $O(n^2)$ algorithm. By Heron's formula, the area of a triangle whose sides have length $a$, $b$, and $c$ is $S = \frac{1}{4}\sqrt{4a^2b^2 - (a^2+b^2-c^2)^2}$. Thus if we fix $a$ and $b$, the area is maximized when $c$ is closest to $\sqrt{a^2+b^2}$. A simple approach is to try all $O(n^2)$ possible pairs of $a$ and $b$ and perform binary search for the best value of $c$. This approach yields an $O(n^2 \log n)$ algorithm.

To achieve $O(n^2)$, we first sort the lengths of line segments ($l\_1, l\_2,\ldots, l\_n$) in non-decreasing order. Let $a = l\_i$ and $b = l\_j$ with $i \< j$, and let $k$ be the position in which $l\_k$ is closest to $\sqrt{l\_i^2 + l\_j^2}$. When $j$ runs from $i+1$ to $n$, $k$ also increases gradually to $n$. Thus finding $k$ has an $O(1)$ amortized run time, i.e., the whole algorithm takes $O(n^2)$.

Update 11/26/2013:

An easier $O(n \log n)$ algorithm is to sort $l\_i$ in a non-decreasing order, and find $3\leq k \leq n$ that maximizes the area of the triangle assembled from $l\_{k-2}, l\_{k-1}$, and $l\_{k}$. It follows from the fact that if $i ,j \< k$ then $S(l\_i, l\_j, l\_k) \leq S(l\_{k-2}, l\_{k-1}, l\_k)$ (can be proved by taking the derivative of $S$ and that $l\_k$ is the length of the longest side).

# Answer
> 3 votes
I'll give the same answer I did on Stackoverflow.

I believe you can solve this problem in linear time, except that you will have to order your set of triangle length first, which is $\Theta(n\cdot \log n)$.

Here's how I would do it.

PSEUDO-CODE:

```
// V is the set of length of triangle.

Order(V)

// Heron Formula
define A(a,b,c) = SQRT(4a^2*b^2 - (a^2 + b^2 - c^2) ^2) / 4

// I is the last position in V
I := V.length - 1

// T(I) is the area of Maximum Area Triangle
T(I) =
if V[I]^2 <= V[I-1]^2+V[I-2]ˆ2
     then return A(V[I-2],V[I-1],V[I])
else
     return MAX( A(V[I-2],V[I-1],V[I]), T(I-1) )

```

Explanation: Assuming that $a \le b \le c$, when $c^2\le a^2+b^2$, if you increase any of the variable (a, b or c), you will have a triangle that has a larger area. So, if you peak the three largest numbers and the equation $c^2\le a^2+b^2$ is true, that means you have found the largest area. But, if $c^2\le a^2+b^2$ is not true, that is $c^2\>a^2+b^2$, then a triangle with a different setup might have a greater area. If we change $b$ or $a$ with a lower value, we will have lower area, so that is not an option. So, the only option we have is to choose a different value for $c$, which is $T(I-1)$, which is also a recursion. The maximum value between $A(V\[I-2\],V\[I-1\],V\[I\])$ and $T(I-1)$ will be your answer.

---
Tags: algorithms
---


# Question
Title: Type for difference of two absolute values
I always see that people in the fields consider confusing vectors with positions as a severe error in one and n dimensions. Recently I have also encoutered a timedelta type in Python. By increadably inadequate reaction and severe punishment, I realize that people in the fields taboo answering why is the difference.

Might be the computer scientists are different and can tell the principal difference among the types. Does time differece has different nature from the datetime? Does `a = b-c` has the same nature as the `b` and `c`? In which case do you introduce a new type? Why do they say that `a` has the same type in case of int but not in case of time or position?

Is this related to dimensional analysis? It seems like dimensional analysis would say that `a` has the same unit of measurement (and therefore the type) as the `b` and `c` in `a=b-c`. Is this correct?

# Answer
You already got a reasonable answer, the last time you asked this question. For instance

> In a nutshell, because datetimes have additional metadata (e.g. timezone) and behave non-linearly, while timedeltas are always linear and have no timezone, etc attached. For example, adding two one-day timedeltas always produces a two-day timedelta, while adding a one-day timedelta to a given datetime may or may not advance the datetime to the next day depending on what value the datetime has (i.e. daylight savings, leap seconds, etc) \[Joe Kington\]

Some friendly advice: if you really want an answer, take care to avoid ranting. Approach things with an open mind and from the perspective that you want to learn, not from the perspective that you already know the correct answer and anyone who disagrees with you must be wrong. Try to be a little less aggressive and a little more humble and open to learning. I have edited your question above to remove the ranting for you.
> 1 votes

---
Tags: type-theory
---


# Question
Title: The importance of normal forms like Chomsky normal form for CFGs
I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't understand the need of that.

Why they are important in the theory of languages? All the textbooks I referred to tell about these normal forms but not telling anything about their importance.

# Answer
> 13 votes
There are at least two relevant uses.

1. **Simplicity of proofs**
There are plenty of proofs around context-free grammars, including reducability and equivalence to automata. Those are the simpler the more restricted the set of grammars you have to deal with is. Therefore, normal forms can be helpful there.

As a concrete example, Greibach normal form is used to show (constructively) that there is an $\varepsilon$-transition-free PDA for every CFL (that does not contain $\varepsilon$).
2. **Enables parsing**
While PDAs can be used to parse words with any grammar, this is often inconvenient. Normal forms can give us more structure to work with, resulting in easier parsing algorithms.

As a concrete example, the CYK algorithm uses Chomsky normal form. Greibach normal form, on the other hand, enables recursive-descent parsing; even though backtracking may be necessary, space complexity is linear.

# Answer
> 7 votes
Chomsky normal form enables a polynomial time algorithm to decide whether a string can be generated by a grammar. The algorithm is pretty slick if you know dynamic programming...

If the length of your input ($I$) is $n$ then you take a 2d array ($A$) of dim $n$x$n$.

$A\[i,j\]$ denotes all the symbols in the grammar $G$ that can derive the sub-string $I(i,j)$.

So finally if $A\[1,n\]$ contains the start symbol ($S$) then it means that the string I can be derived by $S$ which is what we wanted to check.

```
def decide (string s,grammar G):
    //base case
    for i=1 to n:
        N[i,i]=I[i]    //as the substring of length one can be generated by only a
                       terminal.
    //end base case

    //induction
    for s=1 to n:       //length of substring
        for i=1 to n-s-1: //start index of substring
            for j=i to i+s-1:   //something else
                 if there exists a rule A->BC such that B belongs to N[i,j] and C
                 belongs to N[j+1,i+s-1] then add A to N[i,i+s-1]
    //endInduction

    if S belongs to N[1,n] then accept else reject.

```

I know that the indexes seem pretty crazy. But basically here's whats happening.

- The base case is pretty clear I think.
- In the inductive step we build the solution for a length $s$ substring from all the solutions with length less than $s$.
- Say, you are finding the solution for length $5$ substring (`sub`) starting at index $1$. Then you start a loop (something else part).....which checks whether there is a rule ($A-\>BC$) such that $B$ and $C$ derive two contiguous and disjoint substrings of sub and if so add all such $A$'s to $N\[1,6\]$.
- Finally, if you have the start symbol in $N\[1,n\]$ then you accept!

# Answer
> 5 votes
Sheila Greibach invented the Greibach normal form to prove that every CFG can be recognized by a PDA that works in real time (i.e., without $\epsilon$-transitions).

---
Tags: formal-languages, context-free, formal-grammars, normal-forms
---


# Question
Title: help with the probability of acceptance of a Nondeterministic Pushdown automata
I have this nondeterministic pda: $$\Sigma= \\{a,b,c\\}$$

and

$$ L=\\{\omega\ \epsilon\ \Sigma^\*\ |\ \omega\ = \alpha\beta\beta^R\gamma\ and\ \alpha,\beta,\gamma\ \epsilon\ \Sigma^\*\ and\ |\beta|\ \>3 \\} $$

So once i have create the NPDA, i have to calculate the probability of accepting a correct word, i know it depends on the size of $\alpha$ and the "free" jumps ($\varepsilon,\varepsilon-\>\varepsilon$). My problem is that i can't find the exact function of probability can someone explain me how to do it?

Thanks.

# Answer
> 1 votes
In general when constructed in a natural way, you have to guess the correct position of $\beta$, so you have to have two positions right.

But there is a catch. In fact $L$ can alternatively be defined as $\\{\omega \mid \omega = \alpha\beta\beta^R\gamma \text{ and } |\beta|=4 \\}$. This is seen as folows: if you find any substring $\beta\beta^R$ then the central part of length 4+4=8 will also satisfy the palindromic substring constraint. So, $L$ is regular, and one can find a DFA for it.

# Answer
> 1 votes
There is nothing probabilistic about nondeterminism. A nondeterministic machine is defined to accept a word $w$ if any of the possible sequences of "guesses" leads to acceptance, and to reject only if all possible sequences of guesses reject.

Perhaps you meant to ask about the proportion of the computation paths that accept. However, in this case, the question is ill-defined. The proportion of accepting paths depends not on the language but on the exact machine that is being used to accept it. Any language that is accepted by some machine in a class (e.g., DFAs, PDAs, Turing machines) is accepted by infinitely many different ones.

As Hendrik Jan points out in his answer, the language $L$ you ask about is, in fact, regular. This means that one of the machines that accepts it is a deterministic finite automaton and the proportion of accepting paths is $1$ for every string in $L$. However, you could make a nondeterministic automaton from that DFA by adding a million rejecting states and nondeterministic transitions from every "real" states to every one of these rejecting states. The proportion of accepting states for that machine is $1000001^{-|w|}$ for any string $w\in L$.

---
Tags: context-free, probability-theory, pushdown-automata, nondeterminism
---


# Question
Title: When does an algorithm run in $O(1)$ time?
When can an algorithm be said to have $O(1)$ complexity? My doubt is if $n$ is specified to be a large number but constant and we cannot implement it in reality without a loop even then can we call it to have $O(1)$ time complexity? Consider the following examples.

1. Algorithm to add first 1000 natural numbers (that is I mean to say if n is specified directly). Then can we say this has $O(1)$ time complexity?
2. Finding the $7$th smallest element in a min heap. This element is present in anywhere in the first 6 levels of the heap (considering root at level 0). So to find the element we need to check $2^7 - 1$ elements. Then can we say this has $O(1)$ time complexity?

# Answer
If you follow the definition of $\mathcal O$, a function $f(x)\in\mathcal O(1)$ when there's an $x\_0$ and $M$ such that for all $x\>x\_0$, $f(x) \leq M$.

For both algorithms you mention, there clearly is an upper bound on the number of steps a machine has to take to compute the result. Therefore, the time complexity for either problem will be some function $T(n)$, where $n$ is the length of the input, such that $T(n)\leq M$ for some $M$ for all $n$. Therefore $T(n)\in \mathcal O(1)$.

Note that the $\mathcal O$ notation has to do with *asymptotic* behavior of functions, i.e. their behavior as their input grows beyond all bounds. It doesn't care about tiny inputs, whether their length is $1$, $2^7$, or $10^{100}$.
> 2 votes

# Answer
Remeber that, in complexity theory, "$n$" is the length of the input to the problem, in bits.

In your first example, the machine just writes "500500" to its output tape (or "1111010001100010100", if you prefer to work in binary), which takes 6 (or 19) steps, which is $O(1)$. This problem has no input so it doesn't make sense to talk about $n$.

In your second example, you only need to check a constant number $c$ of entries in the heap. But what's your input? How is it represented? What model of computation are you using? Presumably, the input (which, remember, has $n$ bits) is the whole heap, containing $k$ entries. Therefore, each entry takes about $n/k$ bits. On a Turing machine, you're going to have to scan at least $cn/k$ tape cells, so your complexity is $\Theta(n)$. On a random access machine, the time complexity will depend on your data representation but it's probably still going to be $\Theta(n)$.
> 1 votes

# Answer
There is something tricky about this question. The answer for whether an algorithm runs in constant time depends on how large the input to the algorithm is (in bits). In practice we usually assume the size is small enough so that it fits in the memory of our physical random access machine and also each basic operation is performed in constant time.

But in theory the input size can be arbitrarily large and complexity results are the same on both RAM and Turing machine. However, working with a TM is more convenient.

The first example is always of constant size because the input size is zero (notice that 1000 cannot be the input). On the contrary the second example would not be of constant time if the input size is not a constant (this is the answer to your first question). Suppose the heap contains $m$ elements, each encoded in at least $\log m$ bits (under a reasonable encoding). A simple operation like comparison takes $\theta(\log m)$ time. So it has $\theta(2^7.\log m)$ time complexity to find the first 7 smallest elements.

Similarly, the first example wouldn't be of constant time if it was "Algorithm to add first 1000 numbers in a given list of $n$ natural numbers".
> 0 votes

---
Tags: algorithms, asymptotics, runtime-analysis
---


# Question
Title: Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete
I tried to solve the exercise:

> Proof that determining the existence of a Hamilton Path in a bipartite graph is NP-complete

by making a bipartite graph from a general one (undirected) by inserting a vertex in the middle of every edge of the first (general) graph. This generates problems as suggested here: Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs Can anyone give a hint on how to make a bipartite graph from a general one without using the above method and how the Hamiltonian property can be passed to it?

# Answer
I actually found a solution (one that I could understand completely and explain). I want to prove that HP on bipartite graphs is NP-complete.

1. Firstly, I prove that **HC on bipartite graphs** is *NP-complete* (reduction from HC on digraphs): From $G=(V,E)$ construct $G'=(V',E')$ as follows: replace each vertex $u$ with 4 others instead: $u\_{in},u\_{mid,1},u\_{mid,2},u\_{out}$ and apply the 3 consecutive edges between those vertices. Also for each $(u,v)$ in $E$ there will be an undirected edge $(u\_{out},u\_{in})$ in $E'$. So $G'$ is bipartite (since all vertices $u\_{in}$ and $u\_{mid,2}$ are one independent set and the rest are the other). Going from a cycle in $G$ to a cycle in $G'$ is very clear now and much more easier to understand.
2. Secondly, I prove that **HP on bipartite graphs** is *NP-complete* (reduction from HC on bipartite graphs): From $G$ construct $G'$ as follows: add a $w$ vertex and an edge $(w,u)$, where $u$ is a vertex in $V$. Add a vertex $x$. For every $v$ in $Γ(u)$ (every neighboor of $u$) add edge $(v,x)$. Add vertex $y$ and connect it to $x$ (edge $(x,y)$). Now the $G'$ is bipartite (since $x,u$ belong to the same independent set and $y,w$ to the other one). The proof afterwards is easy, since we can observe that a HP on $G'$ will have the edge $(y,x)$ and also $(x,v), v \in Γ(u)$.
> 3 votes

# Answer
Given $G = (V,E)$, define $\tilde{G} = (\tilde{V},\tilde{E})$ by adding vertices $i^+$ and $i^-$ to $\tilde{V}$ for each $i\in V$ and edges $i^-j^+$ and $i^+j^-$ for each edge $ij\in E$.

It's not too hard to check that if $|V|$ is odd, $G$ has a Hamiltonian cycle if and only if $\tilde{G}$ is. If $|V|$ is even, just add one new vertex of degree 2 with neighbors that have an edge between them.

So far, we've seen that Hamiltonian Cycle in bipartite graphs is hard. To reduce this to Hamiltonian Path, just continue in the way you normally would to reduce Hamiltonian Cycle to Hamiltonian Path.
> 3 votes

# Answer
If a bipartite graph has an odd number of vertices then it is proven that it is non-Hamiltonian thus it is not a HC. The proof is in the pdf here: http://www.cs.helsinki.fi/u/polishch/pages/teaching/solutions03.pdf

Now I think for the HC with even number of vertices, you just do the known reduction from the HP we have done in class. I'm not quite sure about this though.

Also, I found this. Maybe it helps you maybe not. It has the proof from a directed HC to undirected HC. http://classes.soe.ucsc.edu/cmps201/Fall09/Handouts/ho11-hc-dir.pdf

Also you can check this out: http://courses.cs.tau.ac.il/cc/02a/exercises/ex04\_ans.pdf question 4

Also maybe Reza Zamani Nasab's thesis will help you.
> -3 votes

---
Tags: graphs, np-complete
---


# Question
Title: Peer grading design - choosing a graph, to get accurate rankings/ratings
**Background.** I am writing some code for semi-automated grading, using peer grading as part of the grading process. Students are given pairs of essays at a time, and the students have a slider to choose which is better and how much better it is. e.g., the slider might look something like this:

`A---X-B`

Based on the results of the peer grading, essays are ranked and the teacher will then grade the top X% and bottom X% and scores for all essays will be automatically calculated based on this. I have already come up with methods for doing this ranking/scoring process; that part works well.

**My question.** How should I select which pairs of essays to give to students?

Simulations suggest we need an essay to be peer-graded at least 3 times, to get an accurate ranking. Thus, each essay should appear in at least 3 of the pairs that are presented for peer grading.

We can think of this as a graph problem. Think of the essays as nodes. Each edge represents a pair of essays that are presented during the peer grading process. The accuracy results above suggest that the degree of each node (or of most nodes) should be at least 3. What sort of graph should I use? How should I generate the graph to be used during peer grading?

One challenge is that if you have clusters in the graph, this will skew the peer-gradings. For example, we wouldn't want to have high-quality essays peer-graded mostly against high-quality essays, because that would skew the results of the peer grading.

What would you recommend?

I think this problem could be modelled with a undirected graph using something like the following:

* Start by taking the node with the least degree and link it with the next least
* Continue until your average degree is at least 3
* Maximise node connectivity
* Minimise number of cliques

Is this a good approach? If not what would you recommend instead?

# Answer
> 10 votes
There are two parts to this: (a) selecting a graph (*experimental design*) to determine which pairs of essays the students will evaluate in the peer grading process, and (b) ranking all the essays, based upon the student's peer grades, to determine which the teacher should rank. I will suggest some methods for each.

## Choosing a graph

**Problem statement.** The first step is to generate a graph. In other words, you need to select which pairs of essays to show to the students, during the peer grading exercise.

**Suggested solution.** For this task, I suggest that you generate a random graph $G$, selected uniformly at random from the set of all 3-regular (simple) graphs.

**Justification and details.** It is known that that a random $d$-regular graph is a good expander. In fact, the regular graphs have asymptotically optimal expansion factor. Also, because the graph is random, this should eliminate the risk of skewing the grading. By selecting a graph uniformly at random, you are ensuring that your approach is equally fair to all students. I suspect that a uniformly random 3-regular graph will be optimal for your purposes.

This raises the question: how do we select a 3-regular (simple) graph on $n$ vertices, uniformly at random?

Fortunately, there are known algorithms for doing this. Basically, you do the following:

1. Create $3n$ points. You can think of this as 3 copies of each of the $n$ vertices. Generate, uniformly at random, a random perfect matching on these $3n$ points. (In other words, repeat the following procedure until all $3n$ points are paired off: select any unpaired point, and pair it with another point chosen uniformly at random from the set of unpaired points.)
2. For each two points that are matched by the matching, draw an edge between the corresponding vertices (that they are a copy of). This gives you a graph on $n$ vertices.
3. Next, test if the resulting graph is simple (i.e., it has no self-loops and no repeated edges). If it is not simple, discard the graph and go back to step 1. If it is simple, you are done; output this graph.

It is known that this procedure generates a uniform distribution on the set of 3-regular (simple) graphs. Also, it is known that at step 3 you have a constant probability of accepting the resulting graph, so on average the algorithm will do $O(1)$ trials -- so this is pretty efficient (e.g., polynomial running time).

I have seen this approach credited to Bollobas, Bender, and Canfield. The approach is also summarized briefly on Wikipedia. You can also find a discussion on this blog post.

Technically speaking, this requires that the number $n$ be even (otherwise there is no 3-regular graph on $n$ vertices). However, this is easy to deal with. For instance, if $n$ is odd, you can randomly choose one essay, set it aside, generate a random 3-regular graph on the remaining essays, then add 3 more edges from the set-aside essay to 3 randomly chosen other essays. (This means that there will be 3 essays that are actually graded 4 times, but that shouldn't do any harm.)

## Ranking all the essays

**Problem statement.** OK, so now you have a graph, and you have presented these pairs of essays (as indicated by the edges in the graph) to the students for them to grade during the peer grading exercise. You have the results of each comparison of essays. Now your task is to infer a linear ranking on all of the essays, to help you determine which ones to have the teacher evaluate.

**Solution.** I suggested you use the Bradley-Terry model. It is a mathematical approach that solves exactly this problem. It was designed for ranking players in some sport, based upon the results of matches between some pairs of the players. It assumes that each player has an (unknown) strength, which can be quantified as a real number, and the probability that Alice beats Bob is determined by some smooth function of the difference of their strengths. Then, given the pairwise win/loss records, it estimates the strength of each player.

This should be perfect for you. You can treat each essay as a player. Each comparison between two essays (during the peer grading process) is like the result of a match between them. The Bradley-Terry model will allow you to take all of that data, and infer a *strength* for each essay, where higher strengths correspond to better essays. Now you can use those strengths to rank-order all of the essays.

**Details and discussion.** In fact, the Bradley-Terry model is even better than what you asked for. You asked for a linear ranking, but the Bradley-Terry model actually gives a (real-number) rating to each essay. This means you know not only whether essay $i$ is stronger than essay $j$, but a rough estimate of *how* much stronger it is. For instance, you could use this to inform your selection of which essays to rank.

There are alternative ways to infer ratings or rankings for all the essays, given the data you have. For instance, the Elo method is another. I summarize several of them in my answer to a different question; read that answer for more details.

One other comment: The Bradley-Terry model assumes that the result of each comparison between two players is a win or a loss (i.e., a binary result). However, it sounds like you will actually have more detailed data: your slider will give a rough estimate of how much better the peer grader rated one essay than another. The simplest approach would be to just map each slider to a binary result. However, if you really want, you might be able to use all of the data, by using a more sophisticated analysis. The Bradley-Terry model involves doing logistic regression. If you generalize that to use ordered logit, I bet that you could take advantage of the extra information you have from each slider, given that the results from the sliders are not binary but are one of several possibilities.

## Efficient use of the teacher

You suggest having the teacher manually grade the top X% and bottom X% of all of the essays (using the ranking inferred from the results of the peer-grading). This could work, but I suspect it is not the most efficient use of the teacher's limited time. Instead, I'd like to suggest an alternate approach.

I suggest that you have the teacher grade a subset of the essays, with the subset carefully selected to try to provide the best possible calibration for all of the essays that weren't graded by the teacher. For this, I think it might help if you selected a sample of essays that cover the range of possible answers (so for every essay, there is some teacher-graded essay that is not too far away from it). For this, I can think of two approaches you could consider trying:

* **Clustering.** Take the ratings that are produced by the Terry-Bradley model. This is a set of $n$ real numbers, one real number per essay. Now cluster them. Suppose you want to have the teacher grade $k$ essays. One approach would be to use $k$-means clustering (on these one-dimensional data points) to cluster the essays into $k$ clusters, and then randomly select one essay from each cluster for the teacher to grade -- or have the teacher grade the "cluster head" of each cluster.
* **Furthest-point first.** An alternative is to try to select a subset of $k$ essays that are as different from each other as possible. The "furthest-point first" (FPF) algorithm is a clean approach for this. Assume that you have some distance function $d(e\_i,e\_j)$ that lets you quantify the distance between two essays $e\_i$ and $e\_j$: a small distance means that the essays are similar, a larger distance means they are dissimilar. Given a set $S$ of essays, let $d(e,S) = \min\_{e' \in S} d(e,e')$ be the distance from $e$ to the nearest essay in $S$. The furthest-point first algorithm computes a list of $k$ essays, $e\_1,e\_2,\dots,e\_k$, as follows: $e\_{i+1}$ is the essay that maximizes $d(e,\\{e\_1,e\_2,\dots,e\_i\\})$ (out of all essays $e$ such that $e \notin \\{e\_1,e\_2,\dots,e\_i\\}$). This algorithms generates a set of $k$ essays that are as dissimilar from each other as possible -- which means that each of the remaining essays is pretty similar to at least one of those $k$. Therefore, it would be reasonable to have the teacher grade the $k$ essays selected by the FPF algorithm.

I suspect either of these approaches might provide more accurate scores than having the teacher grade the top X% and bottom X% of essays -- since the very best and worst essays probably are not representative of the mass of essays in the middle.

In both approaches, you could use a more sophisticated distance function that takes into account not just the strength estimates based upon peer grading but also other factors derived from the essays. The simplest possible distance function would take into account only the result of the Terry-Bradley model, i.e., $d(e\_1,e\_2) = (s(e\_1)-s(e\_2))^2$ where $s(e)$ is the strength of essay $e$ as estimated by the Terry-Bradley model based upon the results of the peer grading. However, you can do something more sophisticated. For instance, you could compute the normalized Levenshtein edit distance between essay $e\_1$ and $e\_2$ (treating them as text strings, computing the edit distance, and dividing by the length of the larger of the two) and use that as another factor in the distance function. You could also compute feature vectors using a bag-of-words model on the words in the essays, and use the L2 distance between these feature vectors (with features normalized using tf-idf) as another factor in the distance function. You might use a distance function that is a weighted average of the difference in strengths (based upon the Terry-Bradley estimates), the normalized edit distance, and anything else that seems helpful. Such a more sophisticated distance function might help do a better job of helping the clustering algorithm select which are the best $k$ essays to have the teacher grade.

# Answer
> 0 votes
a few ideas based on your not-exactly-precise description of inputs and outputs and what is to be calculated (maybe you can revise your question with that in mind).

apparently this is basically the "hot or not" "facemash" problem that originated with the founding of Facebook (as portrayed in the movie "social network"). in the original "game", users had two pictures and chose between the more attractive female. in your system, the choice is between two essays, one of which is better.

from near-cyber-folklore apparently Elo ranking algorithms used in chess match scoring systems can be used to calculate a converging solution (in this case basically estimate the score of the essays consistent with the directed preference graph expressed), but havent yet seen a careful description/writeup of this.

another option is to use Pagerank. that calculates estimated influence of a page based on the directed link graph. preferences to essays are analogous to links to a web page.

the problem also seems similar to citation analysis where scientific papers cite other papers and the influence of papers is estimated. \[but note Pagerank is also a leading algorithm in this area.\]

\[1\] why use Elo rankings for facemash algorithm? stackoverflow

\[2\] Elo ranking system, wikipedia

\[3\] Pagerank, wikipedia

\[4\] citation analysis, wikipedia

---
Tags: algorithms, graphs, modelling
---