# Question
Title: What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?
We have a function which takes an array as input. It breaks an array into $\log\_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there are only two elements left in it. What is the depth of this recursion?

Example of the process:

First we have $n$ elements and break them up into $\log\_2(n)$ parts with equal sizes. Each of these parts has $\frac {n} {log\_2(n)}$ elements in it. In the next level of recursion we will break each of the subarrays into $log\_2(\frac {n} {log\_2(n)})$ parts again with equal sizes. These will now have $\frac {\frac {n} {log\_2(n)}} {log\_2(\frac {n} {log\_2(n)})}$ elements in each one of them. And we keep on breaking the array in this manner until we reach a subarray with only two elements in it.

# Answer
> 5 votes
Let $f(n) = n/\log n$, and denote by $g(n)$ the number of applications of $f$ it takes to get $n$ below some arbitrary constant. On the one hand, $f^{(t)}(n) \geq n/\log^t n$, and so $$ g(n) \geq \log\_{\log n} n = \frac{\log n}{\log \log n}. $$ To obtain an upper bound, notice that as long as $f^{(t)}(n) \geq \sqrt{n}$, we have $\log f^{(t)}(n) \geq (\log n)/2$, and so it takes at most $\log\_{(\log n)/2} n = O(\log n/\log\log n)$ iterations to reduce $n$ to $\sqrt{n}$. The same argument applies for reducing $\sqrt{n}$ to $\sqrt\[4\]{n}$ and so on, and therefore $$ g(n) \ll \frac{\log n}{\log\log n} + \frac{\log \sqrt{n}}{\log\log \sqrt{n}} + \frac{\log \sqrt\[4\]{n}}{\log\log \sqrt\[4\]{n}} + \cdots. $$ (Here $\cdot \ll \cdot$ is the same as $\cdot = O(\cdot)$.) Notice that $\log \sqrt{n} = \frac{1}{2} \log n$. For large $n$, we will have $\log\log \sqrt{n} \geq \frac{2}{3} \log \log n$ (say), and so $$ \frac{\log \sqrt{n}}{\log\log \sqrt{n}} \leq \frac{2}{3} \frac{\log n}{\log\log n}. $$ Therefore the sum is majorized by a convergent geometric series, and we conclude that $$ g(n) = O\left(\frac{\log n}{\log\log n}\right). $$ In total, we get that $$ g(n) = \Theta\left(\frac{\log n}{\log \log n}\right). $$ With more work, we can probably prove a more refined estimate such as $$ g(n) \sim \frac{\log n}{\log \log n}. $$

# Answer
> 2 votes
Seems that you are refering to iterated logarithm, also know as the $log \*$ function. It is a function that expresses how many times you can take the logarithm of a number until it produces a number less than or equals to 1.

The $log\*$ function grows very slowly. It is the inverse of tetration.

See more of that here.

# Answer
> 2 votes
Let n be the size of the array. Let k = log2 (n). At the first step, you divide by k. As long as the array size is more than $n^{1/2}$, you divide by more than k/2. I'd say this is O (log n / log log n).

(Always splitting into k parts takes log n / log k splits. You asked for the special case k = log n, therefore log n / log log n. Then you need to decide whether the shrinking k makes a difference or not. )

# Answer
> 1 votes
All logarithm below means logarithm with base 2, $\log\_2(\cdot)$.

---

Let us name the function given in the question $\operatorname{slog}$. ("slog" comes from **s**plitting with **log**. It can also imply "**s**maller than **log**".) In precise terms, $\operatorname{slog}$ on $\Bbb N$ is defined by the following conditions.

* base case, $\operatorname{slog}(1)=0$ and $\operatorname{slog}(2)=1.$
* the recurrence relation, $\operatorname{slog}(n)=1+ \text{slog}\left(\left\lceil\dfrac{n}{ \lceil\log n\rceil}\right\rceil\right)$ for $n\gt2.$

We can prove the following proposition on **the asymptotic behavior of $\operatorname{slog}(n)$**. $$\lim\_{n\to\infty}\dfrac{\quad\text{ slog}(n)\quad}{\dfrac{\log n}{\log\log n}}=1.$$

Here is the basic idea of the proof.

$$\begin{align} \lim\_{n\to\infty}\frac{\log n}{\log\log n}-\frac{\log \frac n{\log n}}{\log\log \frac n{\log n}} &=\lim\_{m\to\infty}\frac{m}{\log m}-\frac{m-\log m}{\log(m-\log m)}\\ &=\lim\_{m\to\infty}\frac{m}{\log m}-\frac{m-\log m}{\log m + \log(1- \frac{\log m}m)}\\ &=\lim\_{m\to\infty}\frac{(\log m)^2+ m\log(1- \frac{\log m}m)}{(\log m)(\log m+ \log(1- \frac{\log m}m))}\\ &=\lim\_{m\to\infty}\frac{(\log m)^2+ m(-\frac{\log m}m)}{(\log m)(\log m)}\\ &=1 \end{align}$$

Corollary. $\text{slog}(n)=\Theta\left(\dfrac{\log n}{\log\log n}\right)$.

---

The same conclusion holds if we define $\text{slog}(x)$ for $x\>1$ with $\text{slog}(x)=1$ for $1\lt x\le 2$ and $\operatorname{slog}(n)=1+ \text{slog}\left(\dfrac{n}{ \log n}\right)$.

---

**Exercise.** Write the full proof of $\text{slog}(n)\sim \dfrac{\log n}{\log\log n}$.

---
Tags: complexity-theory, time-complexity, asymptotics, recursion, mathematical-analysis
---


# Question
Title: Partitioning vertices in a bipartite graph according to minimum vertex covers
How to solve this problem?

> A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. A minimum vertex cover is a vertex cover with minimal cardinality.
>
> Consider a set of all minimum vertex covers of a given bipartite graph. Your task is to divide all vertices of the graph into three sets. A vertex is in set N (“Never”) if there is no minimum vertex cover containing this vertex. A vertex is in set A (“Always”) if it is a part of every minimum vertex cover of the given graph. If a vertex belongs neither to N nor to A, it goes to the set E (“Exists”).

# Answer
> 2 votes
The following idea comes from a Chinese blog.

Find a maximum matching $M$ ($2m$ vertices and $m$ edges) firstly. For convenience, for a vertex $v$, we denote by $M(v)$ the vertex that is matched with $v$ in $M$, and denote by $N(v)$ the set of neighbors of $v$.

We have the following observations:

1. All vertices not in $M$ must belong to $\mathrm{Never}$.

*Proof.* Suppose a minimum vertex cover contains a vertex $v$ not in $M$, to cover the $m$ edges in $M$, the vertex cover must also contains another $m$ vertices, so the size of the vertex cover is at least $m+1$, which contradicts to Kőnig's theorem.
2. If a vertex $v$ in $M$ belongs to $\mathrm{Always}$, then $M(v)$ must belong to $\mathrm{Never}$.

*Proof.* Suppose a minimum vertex cover contains both $v$ and $M(v)$, to cover the rest $m-1$ edges in $M$, the vertex cover must also contains another $m-1$ vertices, so the size of the vertex cover is at least $m+1$, which contradicts to Kőnig's theorem.
3. If a vertex $v$ belongs to $\mathrm{Never}$, then $N(v)$ must be a subset of $\mathrm{Always}$.

These observations lead us to the following algorithm:

```
A = A[0] = empty set
N = N[0] = all the vertices not in M
i = 0
while True:
    i = i + 1
    A[i] = empty set
    for each vertex v in N[i - 1]:
        temp = N(v) \ A
        A[i] = union(A[i], temp)
        A = union(A, temp)

    if A[i] is empty:
        break

    for each vertex v in A[i]:
        add M(v) into N[i]
        add M(v) into N

```

After the execution of this algorithm, all vertices in `A` belong to $\mathrm{Always}$ and all vertices in `N` belong to $\mathrm{Never}$. For those rest vertices, we partition them into two sides by intersecting respectively with $L$ and $R$, where $L$ and $R$ are respectively the two sides of the bipartite graph. We can see either side along with the vertices in `A` forms a minimum vertex cover, so these vertices belong to $\mathrm{Exist}$.

---
Tags: algorithms, graphs, bipartite-graph, vertex-cover
---


title: Sorting elements of linked list

text:
# Question
Title: Sorting elements of linked list
I've been looking over sorting algorithms for linked list and here's what I came up with.

As we know, for element access arrays will work better than linked list. Also, there is the benefit of elements being stored in consecutive memory locations: due to spatial locality of cache, arrays give better performance.

Thus for sorting linked list:

1. Extract all elements from linked list to a array: $O(n)$
2. Sort the array using quicksort: $\Theta(n \log n)$
3. Store the elements in linked list: $O(n)$

Is this approach better than other approaches for sorting linked lists such as using merge sort directly, as described on geeksforgeeks.

# Answer
The downside of your algorithm is that you need to allocate enough space to hold pointers to all the elements in the list. This requires knowing the length of the list (which would need traversing it once to count) and you may not have enough memory to get a contiguous space for it.

---

A variation of classic merge sort will work a lot better for linked lists:

Have a array of $\lceil \log\_2 n \rceil$ linked lists initially empty. (or just fix to size 64 because when are you ever going to need to sort anywhere near $2^{64}$ elements).

For each element in the original list you extract it into a single element list and do the following:

for the first list in the array if a list is already there merge the list into that list and remove the list from the array and repeat for the next list in the array.

otherwise move on to the next element in the original list.

Once you've done the last element of the list you merge the lists in the array starting from the lowest index.

---

This is the algorithm used for linked lists in the linux kernel. And has a few handy features:

* no allocations needed, no recursion, so no chance of an out of memory situation.
* you only walk the original list once.
* the merge passes except the final ones are all with lists of equal length. This means there are few unbalanced passes which would have more traversing of the longer list than actually merging the two lists together in.
> 1 votes

---
Tags: algorithms, linked-lists
---


title: Computing number of ways to make change

text:
# Question
Title: Computing number of ways to make change
> Given a list $C=\[c\_1,c\_2,\dots,c\_k\]$ of positive integers, representing the values of $k$ varieties of coins, and a positive integer $n$, let $f(n,C)$ be the number of handfuls of coins with total value $n$. The order within the handful does not matter, and there is an infinite supply of each variety of coin.
>
> What is the state-of-the-art algorithm to compute $f(n,C)$?

Equivalently, $f(n,C)$ is the number of ways to choose non-negative integers $x\_i$ so that $n=\sum\_{i=1}^k x\_ic\_i$.

The list $C$ can have repeats, and the interpretation is that there are two varieties of coin with the same value. For example, $f(3,\[2,1,1\])=6$. Letting $A$ and $B$ be the coins of value $1$, and $C$ be the coin of value $2$, the $6$ possible handfuls are $$ (A,A,A),(A,A,B),(A,B,B),(B,B,B),(A,C),(B,C) $$

I can think of two solutions. Which is faster depends on $n$ and $C$.

* **Dynamic programming:** Let $C'$ denote $C$ with its last entry removed. A use-it-or-lose-it argument gives $$f(n,C) = f(n-c\_k,C)+f(n,C') .$$ This lets you compute $f(n,C)$ by filling out an $n\times k$ DP table, which takes $$\boxed{\Theta(nk)}$$ additions and look-ups.
* **Matrix exponentiation:** I will illustrated in the case $C=\[2,3,4\]$. Letting $a\_n=f(n,C)$, then $a\_n$ satisfies the recurrence (see https://cs.stackexchange.com/a/87810/24590) $$ a\_n = a\_{n-2}+a\_{n-3}+a\_{n-4}-a\_{n-5}-a\_{n-6}-a\_{n-7}+a\_{n-9} $$ Any linear recurrence can be solved by computing the $n^{th}$ power of a certain matrix. In this case, the recurrence has order $c\_1+\dots+c\_k$, so this algorithm takes $$ \boxed{O(\log n \cdot M(c\_1+\dots+c\_k))} $$ arithmetic operations, where $M(k)$ is the number of arithmetic operations required when multiplying two $k\times k$ matrices (naively $M(k)=k^3$, state of the art is $k^{2.3728639}$). We get $\log n$ by using exponentiation by squaring.

The second algorithm is asymptotically much better as $n\to\infty$, but the first is better when the sum of $C$ is large.

> Are there any known faster algorithms?

# Answer
> 2 votes
From a theoretical perspective, you can diagonalise (well, decompose to Jordan normal form) to do the matrix power. It costs $O(M(c\_1+\dots+c\_k))$ to decompose, $O(\log n \cdot (c\_1+\dots+c\_k))$ to raise the diagonal matrix to the $n$th power, and $O(M(c\_1+\dots+c\_k))$ to finish up.

---
Tags: time-complexity, dynamic-programming, recurrence-relation
---


# Question
Title: Looking for algorithm to iterate over matrix
I have such a product example:

```
{
  "color": ["red", "blue"],
  "material": ["metal", "textile", "plastic"],
  "options": ["handle", "wire", "bt"],
  "textile": ["silk", "cotton"]
}

```

I need to know what algorithm can help me to produce all options possible for such product, f.e.:

```
{
  "color": "red",
  "material": "metal",
  "options": "handle",
  "textile": "cotton"
}

```

Each option can be single for a product.

Obviously, I don't want to use tons of for loops. It should be possible to easily add new options and new variations, f.e.:

```
{
  "color": ["red", "blue", "new"],
  "material": ["metal", "textile", "plastic", "new"],
  "options": ["handle", "wire", "bt", "new"],
  "textile": ["silk", "cotton", "new"],
  "newOption": ["new option]
}

```

# Answer
The classical recursive algorithm to calculate the Cartesian product $A\_1 \times \cdots \times A\_n$ goes as follows:

* If $n = 0$, return the empty tuple.
* Otherwise, for every $x\_1 \in A\_1$ and $(x\_2,\ldots,x\_n) \in A\_2 \times \cdots \times A\_n$, output $(x\_1,x\_2,\ldots,x\_n)$.

In the second step, you compute $A\_2 \times \cdots \times A\_n$ recursively.

You can convert this into an iterative algorithm. Suppose that $|A\_i| = m\_i$, and that the individual elements are $a\_{ij}$. We count from $0$ to $m\_1 \cdots m\_n - 1$, and interpret each of these numbers as a mixed base number, involving the bases $m\_1,\ldots,m\_n$. We then convert the number into a tuple.

An alternative presentation of the iterative approach uses $n$ counters $c\_1,\ldots,c\_n$ counting from $0$ to $m\_i-1$; when a counter reaches $m\_i$, we reset it and all following counters to zero, and update the tuple accordingly.

Details of all these approaches left to you.
> 1 votes

---
Tags: algorithms, performance, matrix
---


title: Running Time of Sorting Algorithm

text:
# Question
Title: Running Time of Sorting Algorithm
Determine the asymptotic running time of the sorting algorithm maxSort.

*Algorithm maxSort(A)*
*Input: An integer array A*
*Output: Array A sorted in non-decreasing order*

```
1. for j <- n-1 down to 1 do
2.     m <- 0
3.     for i = 1 to j do
4.         if A[i] > A[m] then m <- i
5. exchange A[m], A[j]

```

Can you say anything about the "best-case" function $B\_{maxSort}(n)$?

---

With a question like this, what is the way to tackle it? I have tried counting number of executions per line, but I can't translate it into asymptotic notation. My intuition is that it has something to do with $n^2$ due to the nested *for* loop, but I am not sure about this.

# Answer
> 0 votes
When the indexes of the for loops depend on each other you can think like this:

When the index of the outer for loop takes its first value how many times is the inner for repeated? What about when the index of the outer for takes its second value? ... What happens when the index of the outer for takes its last value?

In your case: When $j = n-1$, $i$ is repeated $n-1$ times. When $j = n-2$, $i$ is repeated $n-2$ times. ... When $j = 1$, $i$ is repeated $1$ time.

In total, the inner for loop is executed $(n-1) + (n-2) + ... + 2 + 1 = \dfrac{n}{2} * n = n^2$ times. Therefore the complexity is $O(n^2)$.

The best case is obviously when the matrix is already sorted.

# Answer
> 0 votes
I find the most useful phrase when trying to quickly understand the asymptotic behavior of an algorithm (and likewise in quick dimensional analysis of physical problems) is "suppose we have twice as many..."

In the above problem, suppose we have twice as many elements. Then the outer loop will run twice as many times. But `j` is proportional to `n`, so the inner loop will also run twice as many times per run. Therefore the inner loop will run four times as often in total. So that's `O(n^2)`.

---
Tags: algorithms, algorithm-analysis, time-complexity, asymptotics, runtime-analysis
---


# Question
Title: Search on Conformant Problem: solution for subset of a belief state
I am having trouble understanding the following statement.

I have understood why in a sensorless/conformant problem, if there exists a solution (a sequence of actions) for a belief state $b$, then it is also a solution for any $b'$ that is a subset $b$.

Next claim is what is confusing me.

Then in a standard graph search, we can save time by pruning some branches from the search tree.

**Example from the Sensorless Vacuum World problem in Russel Norvig.**

When we have a successor $\\{1,3,5,7\\}$ *generated* during graph search, we do not add it to the frontier if we have already expanded the belief state $\\{5, 7\\}$ which is a subset.

I thought those cases are totally unrelated since each belief state may encode a different path from the start state. If $\\{5, 7\\}$ does give us a solution, we have no guarantee it will work for $\\{1, 3, 5, 7\\}$. It's also possible $\\{1, 3, 5, 7\\}$ can lead to a solution through a different path.

I must be missing something.. can someone please explain?

# Answer
> 1 votes
'different path from the start state': The sensorless vacuum world is by definition a 'single-state problem', that is, all variables in the world are incorporated into a single state variable. In that case, history doesn't matter. If we are in state 5 by one path, the world is exactly as it would be if we had got there by another path.

For an example of something else represented as a single-state problem, consider chess: you might say history matters because whether you can castle, depends on whether the king has moved, not just the current board position. Okay so if we represent chess as a single-state problem, then the state would encode not only the current board position but also other relevant variables like whether the king has moved.

Subsets: if we know how to get to `{5,7}`, we don't need to be interested in `{1,3,5,7}`. Getting to `{5,7}` gives us all the same information plus more besides.

---
Tags: artificial-intelligence, search-trees, search-problem
---


# Question
Title: Calculate number of cache lines per set or cache size
How can I calculate the number of cache lines per set or the cache size with the given information?

* m (number of physical address bits): 32
* C (cache size): unknown
* B (Block size in bytes): 32
* E (number of lines per set): unknown
* S (number of cache sets): 32
* t (tag bits): 22
* s (set index bits): 5
* b (block offset bits): 5
* associativity unknown

Since we can calculate C with C=B\*E\*S or E with E=C/(B\*S). I just need to know how to calculate C or E.

# Answer
You can calculate it with the help of tag, index, and offset bits. Read about it here.
> 0 votes

---
Tags: cpu-cache, caching
---


# Question
Title: Is there an algorithm to find the minimal number of dimensions, given the distances between points?
Given some finite set $S := \\{x\_1,x\_2,\ldots,x\_k\\} \subset \mathbb R^n$ we can define a distance matrix $D = (d(i,j))\_{ij}$ with $$d(i,j) = \Vert{x\_i - x\_j}\Vert$$

where $\Vert \cdot \Vert$ is the euclidean norm.

Is there an algorithm to determine the minimal $m$ just from $D$ such that there are $\\{y\_1,y\_2,\ldots,y\_k\\} \in \mathbb R^m$ with $d(i,j) = \Vert{y\_i -y\_j}\Vert$?

Or equivalently: Given $D$ as well as some $m$, can we determine whether $D$ can stem from $k$ points in $\mathbb R^m$?

# Answer
> 5 votes
This problem of minimal dimensionality has been studied intensively.

Here is a slightly-edited excerpt from *Learning metrics via discriminant kernels and multidimensional scaling: Toward expected euclidean representation* by Zhihua Zhang, Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003), Washington DC, 2003.

> Definition 1 (Gower & Legendre, 1986) An $m × m$ matrix $\[a\_{ij} \]$ is Euclidean if $m$ points $P\_i$ $(i = 1, . . . , m)$ can be embedded in an Euclidean space such that the Euclidean distance between $P\_i$ and $P\_j$ is $a\_{ij}$.
>
> The following theorem provides the conditions for a matrix to be Euclidean.
>
> Theorem 1 (Gower & Legendre, 1986) The matrix $\[a\_{ij}\]$ is Euclidean if and only if $H^{\text{tr}}BH$ is positive semi-definite, where $B$ is the matrix with elements ${-\frac12}{a\_{ij}}^2$ and $H = (I − \mathcal 1\_ms)$ is a centering matrix where $I$ is the identity matrix, $\mathcal 1\_m$ is the $m \times 1$ vector $(1, 1, \cdots , 1)$ and $s$ is a $1\times m$ vector satisfying $s\mathcal 1\_m = 1$.

Note that in theorem 1, if the condition is true for one choice of $s$ (say $s=e\_i$, the vector whose entry is 1 at $i$-th position and whose entries are 0 otherwise), it is true for every valid choice of $s$. That fact is included in *Metric and Euclidean properties of dissimilarity coefficients* by Gower & Legendre, 1986.

Thanks to theorem 1, we know the minimal $m$ such that there are $\\{y\_1,y\_2,\ldots,y\_k\\} \in \mathbb R^m$ with $d(i,j) = \Vert{y\_i -y\_j}\Vert$ is one less than the minimum order of non-Eucidean sub-square-matrix of $\[d(i,j)\]$. A simple algorithm to compute that minimum order is to iterate through all submatrix (that allow non-consecutive rows or columns) of $\[d(i,j)\]$, checking whether each submatrix is Euclidean.

For more related information, we can read that article and dig further.

---
Tags: algorithms, graphs, computational-geometry
---


# Question
Title: Pumping Lemma. Why is there a word w in L for infinite languages with n≤|w|≤2n
The following comment on an other question says that if we have an infinite language L that satisfies the pumping lemma for regular languages then we have a word with n≤|w|≤2n which is in L. (n is the constant in the pumping lemma)

https://cs.stackexchange.com/a/55606/99669

Why is this the case? The lower limit can be explained by the constant of the regular pumping lemma, because in infinite languages there exists a word in L which is longer than n.

But how comes there is an upper limit? The pumping lemma does not say anthing about a upper limit for the words we choose.

# Answer
Suppose that $L$ is an infinite language which satisfies the pumping lemma with constant $n$. Let $w \in L$ be a word of minimal length in $L \cap \Sigma^{\geq n}$ (i.e., among the words in $L$ of length at least $n$, choose a word of minimal length). Since $L$ satisfies the pumping lemma, we can write $w = xyz$ in such a way that $|xy| \leq n$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. In particular, $xz \in L$. Since $|xz| \< |xyz|$, we must have $|xz| \< n$, and so $|w| = |xz| + |y| \< n + |xy| \leq 2n$.
> 2 votes

# Answer
Think about it in terms of the proof of the pumping lemma.

The pumping lemma is true because, if you read a long enough word, you must visit the same state of the automaton twice, so you can go around that loop as many times as you want (including zero) and then go on to an accepting state. How long does this take? If the automaton has $n$ states, you know you must have been once around the loop after at most $n+1$ steps. From there, you need to get ot an accepting state and either you're in one already, or you need to visit at most $n-1$ more states before you get there. So the total is at most $2n$.

If that procedure results in a word of length less than $n$, just go around the loop enough times to lengthen it.
> 1 votes

---
Tags: formal-languages, computability, regular-languages, finite-automata, pumping-lemma
---


# Question
Title: Find the computational complexity of the given program
```
int seq(int n)
{
   if(n == 0 || n == 1)
       return n;
   return(seq(floor(n/2)) + seq(ceil(n/2));
}

```

Find the computational complexity of the above program.

I have tried doing it in the following way: $$\begin{align\*} T(0) &= 1 \\ T(1) &= 1 \\ T(2) &= 2T(1) = 2 \\ T(3) &= T(1) + T(2) = 3 \\ T(4) &= 2T(2) = 4 \\ T(5) &= T(3) + T(2) = 5 \\ &\vdots \end{align\*}$$

So the thing I have observed here was:

$$T(n) = n$$

However I am not sure if this result/approach is even somehow correct, is it? If not can someone show me the way how to approach problems like this one? Thanks

# Answer
> 1 votes
You can analyze using master theorem: $$T(n) = T(\lfloor\frac{n}{2}\rfloor) + T(\lceil\frac{n}{2}\rceil) + 1$$

As we can suppose $n = 2^k$ and there is no a difference in the asymptotic complexity, We can say $T(n) = 2T(\frac{n}{2})+ 1$.

Hence, from master theorem we can say $T(n) = \Theta(n)$.

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


# Question
Title: Christofides algorithm (by hand) (suboptimal solution - is it my fault?)
I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance)

* $\alpha$ denotes the start and end vertex of the Eulerian path

---

## **Step 1** \- Calculate minimum spanning tree $T$

---

## **Step 2** \- Calculate the set of verices $O$ with odd degree in $T$

---

## **Step 3** \- Form the subgraph of $G$ using only the vertices of $O$

**This is starting to get confusing**

---

## **Step 4** \- Construct a minimum-weight perfect matching $M$ in this subgraph

---

## **Step 5** \- Unite matching and spanning tree $T$ and $M$ to form an Eulerian multigraph

---

## **I am NOT satisfied**

Did I do something wrong or did I simply just hit an sub-optimal solution. It is not hard to see that the Eulerian path easily could be improved by either connection $G \rightarrow H$ or $A \rightarrow B$ as illustrated underneath:

# Answer
> 5 votes
As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you could end up with a sub-optimal solution of

On the other hand, you did make a mistake while computing the minimal spanning tree. In your step 1 that calculates the minimum spanning tree, edge H$\alpha$ should be replaced by edge HG.

# Answer
> 2 votes
1. It's an approximation algorithm, so the answer *can* be suboptimal.
2. The answer of a given TSP is a **Hamiltonian cycle**, NOT Eulerian path.

But the above doesn't justify that you have a wrong result, because simply:

3. You forgot the last step, which is short-cutting -- removal of repeated vertices.

So because you have two paths ($A \alpha B$ and $G \alpha H$) with repeated $\alpha$, you should modify one of those. For example -- make a short-cut (and skip $\alpha$) when travelling from $G$ to $H$ and go directly with your upper red edge. Then you'll have a valid solution to this problem.

EDIT: Jack has pointed out (correctly) that you didn't create a minimum spanning tree. However, if we suppose that the tree is correct (for example the cost of $GH$ edge is 56) and you get the result as seen above, then my rules still apply.

---
Tags: algorithms, graphs, matching, spanning-trees
---


# Question
Title: Poly-time reductions for proving EXPTIME-hardness are _not_ enough?
Wikipedia says that in order to prove EXPTIME-hardness of our problem, we need to prove that every EXPTIME problem can be poly-time reduced to our problem. Here is a "counter-example" that bugs me.

Suppose our problem can be solved in time $O(2^k)$, where $k$ is an input number to our problem instance; let it be in binary. Consider some EXPTIME-complete problem that takes a number $n$ as input. Consider a hypothetical reduction that creates our problem instance with $k=2^n$; it is is poly-time, because it computes $2^n$ by shifting $n$ times the letter $1$ to the right. Our reduction implies that the original problem can be solved in $2^{2^n}$ time. But that is not sufficient for proving EXPTIME-hardness of our problem, because we cannot derive the contradiction by assuming our problem is solveable in poly-time. Therefore, we cannot use poly-time reductions.

Where is the mistake? Is it about binary/unary encoding of numbers? Is it about meaning of $O(2^k)$ vs. $O(2^{|\text{string representing k}|})$?

# Answer
If your problem can be solved in time $O(2^k)$, where $k$ is some number in the input, all you can say about its membership in conventional complexity classes is that it's in $\mathrm{2EXP}$, since an instance of length $\ell$ can be decided in time $O(2^{2^\ell})$. You've not established that the problem is in $\mathrm{EXP}$.

$\mathrm{EXP}$, like all conventional complexity classes, is defined in terms of the length of the input, not the values represented in that input.
> 2 votes

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


# Question
Title: Provide "regular" grammar for this language {${a^ib^j \mid i>0\ and \hspace{2.5mm}i\leq j \leq(2*i)}$}
I'm trying to understand the approach to constructing an grammar which accepts the language ${a^ib^j \mid i\>0\ and \hspace{2.5mm}i\leq j \leq(2\*i)}$ } Thanks.

# Answer
Short answer: unfortunately, it can't be done.

It can be proven mathematically that this language isn't regular. The easiest way is a fooling set argument: the set $\\{a^{3^i} \mid i \in \mathbb{N}\\}$ is infinite, and for any two distinct strings $x$ and $y$ you take from this set, I can construct a suffix $z$ such that $xz$ is in your language and $yz$ is not.

Thus, it's utterly impossible to make a regular grammar for this language.

Note that this language *is* context-free; the following context-free grammar (CFG) recognizes it:

$$S \rightarrow aXb \mid aXbb \\ X \rightarrow aXb \mid aXbb \mid \varepsilon$$

(The distinction between $S$ and $X$ is just to ensure that $i \> 0$; if you drop that requirement, you can do this in one line.)

EDIT: Thanks to Apass.Jack, here's a one-liner for you anyway!

$$S \rightarrow aSb \mid aSbb \mid ab \mid abb$$
> 3 votes

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


# Question
Title: Prove that the following algorithm has STOP property (number of steps is finite)
Prove that the following algorithm has STOP property. I am not sure if this term is widely know, so the definition of STOP property that I got during classes looks as follows:

> STOP property (for all input data satisfying $ \alpha $ the computation halts - the number of steps is finite)

$\alpha: x \in N $

```
void BB(int x)
{
    int y = x;
    int z = 0;
    while((z != 0) || (y <= 300))
    {
        if(y <= 300)
        {
            y = y + 3;
            z = z + 1;
        }
        else
        {
            y = y - 2;
            z = z - 1;
        }
    }
}

```

I do not really have any idea how to approach such a problem. I was thinking about using the method of loop counters, but I couldn't success with it.

# Answer
> 3 votes
You have three possible cases:

* $y \> 300$. Since $z = 0$ initially, the algorithm terminates.
* $y = 300$ and $z = 0$. You enter the first if and you get $y = 303$ and $z = 1$. Then you enter the second if and you get $y = 301$ and $z = 0$. Since $y \> 300$ and $z = 0$ the algorithm stops.
* $y \< 300$ and $z = 0$. After $k$ iterations $y = 301$ or $y = 302$ or $y=303$ and $z = k$. By executing the algorithm for each $y$ you can see that $y$ only takes values in a specific range while $z$ is always decreasing and will eventually reach 0 (or it will become less than 0). For example, let $y = 301$ and $z = k$. By executing the algorithm you get the following values:

${\bf y = 301, z = k} \\ y = 299, z=k-1 \\ y=302, z = k\\ y = 300, z = k-1 \\ y = 303, z = k \\ {\bf y = 301, z = k-1}\\ y = 299, z = k-2 \\ y=302, z = k-1\\ y = 300, z = k-2 \\ y = 303, z = k-1 \\ {\bf y = 301, z = k-2}\\\$

Obviously each time you reach $y = 301$, z is decreased by 1. After showing that the same thing happens for the other two possible values of $y$ you have proved that for every possible starting value, the algorithm stops after a finite number of steps.

# Answer
> 2 votes
A simple case: What happens if x \> 300? (Think about it). So that was easy, the program stops.

What if x ≤ 300, including x = 0? First there is a phase where y is increased by 3 each time, and that will happen at least once (if x ≥ 298) and at most 101 times (if x = 0), so we end that phase with x ≤ 101, and y is 301, 302, or 303.

Now comes a second phase: We have y = 301, 302, or 303. If y = 301 (you think what the next two steps will be), and we have y = 302 and x unchanged. If y = 302 (you think what the next two steps will be), and we have y = 303 and x unchanged. But in the last case y = 303 (you think what the next three steps will be), and we have y = 301 and x is one less than before!

If x isn't 0 already, you figure out what will happen after every 7 iterations of the loop, and then it is obvious that the program stops.

---
Tags: algorithms, algorithm-analysis, correctness-proof
---


title: Large-scale string clustering

text:
# Question
Title: Large-scale string clustering
I've more than 10 million strings of length 1-100 characters. This number will be even bigger in the future. I'm interested in clustering this data, but I'm not quite sure what would be effective at this scale.

These are the clustering algorithms I've been looking into:

* **Affinity propagation:**: seems like a good solution, but the memory usage seems way too high, since the data is dense.
* **DBSCAN:** could also be an option, but I want all nodes/strings to belong to a cluster and not be considered "noise.
* **K-medoids:** seems like a good option in terms of memory usage, but the computation time seems worrying. It would also be highly preferred if the number of clusters was not determined before running the algorithm as in affinity propagation.

Do you have any ideas on how this problem can be solved? The computation time is not extremely important, as long as the result is satisfiable and it can be done within a couple of days.

Thank you in advance!

# Answer
There are many possible approaches. One approach that I would suggest investigating is finding all pairs of similar strings, and then applying a standard algorithm for clustering of sparse graphs. There are multiple possible approaches for finding similar strings, depending on how you plan to measure similarity.

One approach is to measure similarity using the Levenshtein edit distance. If you have $N$ strings, the naive way is to loop over all $N^2/2$ pairs, compute the edit distance for each, and save the pairs where the edit distance is below some threshold. However, this doesn't scale when $N$ gets large. Another alternative is to use fancier data structures and algorithms to find only the pairs of strings that are similar, e.g., BK-trees, ternary search trees, metric trees, Levenshtein automata, shingling, or other methods. See, e.g., How fast can we identifiy almost-duplicates in a list of strings?, How to speed up process of finding duplicates/similar items in a large amount of strings?, Find all pairs of strings in a set with Levenshtein distance \< d, Efficient map data structure supporting approximate lookup, Efficient data structures for building a fast spell checker, and https://cstheory.stackexchange.com/q/4165/5038 for some references. Credits to Pseudonym for part of this suggestion.

Alternatively, if you want to measure similarity using the number of characters the differ (i.e., like the edit distance but with only the "replace" operation and without the "insert" or "delete" operations), you could look at locality sensitive hashing as a way to find all pairs of similar strings.
> 1 votes

---
Tags: algorithms, algorithm-analysis, strings, clustering, big-data
---


# Question
Title: Constructing a new graph. G'. What does it mean v ∈ S_{i+1}?
> John lives in a city whose streets has the same length. His apartment is located at a specified node H. John need to do his errands where he visits each of k different shop in order. However, each store have more than one location in his city. More particularly, for each 1 ≤ i ≤ k there is a set $S\_{i}$ of vertices at which a branch of the $i^{th}$ shop is located (you can assume that the $S\_{i}$ are disjoint). Construct a new graph G' as following:
>
> Create a new graph G' whose nodes are given by both a node of G, representing John’s current location, and a number 0 ≤ i ≤ k, giving the number of stops that John has successfully made. In particular, the vertices of G' are exactly given by (v, i) with v ∈ Node and i ∈ {0, 1,..., k}. Edges in G' are between (u, i) and (v, i) if (u, v) is an edge of G, or between (u, i) and (v, i + 1) if (u, v) is an edge of G and v ∈ $S\_{i+1}$.

**What does it really mean by "between (u,i) and (v,i+1) if (u,v) is an edge of G and V v ∈ $S\_{i+1}$"?**

Let's say we have simple graph G as below:

Here is my attempt of constructing the new graph G'.

How many new nodes do we need to make, 3 or 4 copies? I only make 3 so far since there are only 3 errands. Please let me know if my G' is correct. Thank you.

# Answer
> The vertices of $G'$ are exactly given by $(v, i)$ with $v\in Nodes$ and $i \in \\{0, 1,\cdots, k\\}$. Edges in $G'$ are between $(u, i)$ and $(v, i)$ if $(u, v)$ is an edge of $G$, or between $(u, i)$ and $(v, i + 1)$ if $(u, v)$ is an edge of $G$ and $v\in S\_{i+1}.$

We know $Nodes$ are 6 nodes, i.e., $H, B1, B2, Bus, P, M$ and $k=3$ as there are three kinds of shops, i.e., bank, post office and movie where $S\_1$ is the set of banks, $S\_2$ post offices and $S\_3$ movies.

There are 24 vertices of $G'$ $$\begin{align} (H,0),(B1,0), (B2,0), (Bus,0), (P,0), (M,0), \\ (H,1),(B1,1), (B2,1), (Bus,1), (P,1), (M,1), \\ (H,2),(B1,2), (B2,2), (Bus,2), (P,2), (M,2), \\ (H,3),(B1,3), (B2,3), (Bus,3), (P,3), (M,3). \\ \end{align}$$

The edges are $$\begin{align} &(H,0)(B1,0), (B1,0)(Bus,0), (Bus,0)(P,0), (P,0)(M,0), (H,0)(B2,0) \\ &(H,1)(B1,1), (B1,1)(Bus,1), (Bus,1)(P,1), (P,1)(M,1), (H,1)(B2,1) \\ &(H,2)(B1,2), (B1,2)(Bus,2), (Bus,2)(P,2), (P,2)(M,2), (H,2)(B2,2) \\ &(H,3)(B1,3), (B1,3)(Bus,3), (Bus,3)(P,3), (P,3)(M,3), (H,3)(B2,3) \\ &(H,0)(B1,1), (Bus,0)(B1,1), (H,0)(B2,1) \\ &(Bus,1)(P,2), (M,1)(P,2)\\ &(P,2)(M,3)\\ \end{align}$$

> What does it really mean "between $(u, i)$ and $(v, i + 1)$ if $(u, v)$ is an edge of $G$ and $v\in S\_{i+1}$" ?

It means exactly what it means.

For $i=0$, $v$ must be one of two nodes in $S\_{0+1}=S\_1$, i.e., $B1$ and $B2$.

* If $v$ is $B1$, $u$ must be either $H$ or $Bus$ since all edges in $G$ whose endpoints include $B1$ are $HB1$ and $BusB1$. So $(H,0)(B1,1)$ and $(Bus,0)(B1,1)$ are edges in $G'$.
* If $v$ is $B2$, $u$ must be $H$ since the only edge in $G$ whose endpoints include $B2$ is $HB2$. So $(H,0)(B2,1)$ is an edge of $G'$.

It should be clear now what should happen if $i=1$ or $i=2$. Note $i$ cannot be 3 since there is no $S\_{3+1}.$

> How many new nodes do need to make, 3 or 4 copies ? I only make 3 so far since there are only 3 errands.

Yes, besides the $G$ itself, we should make 3 copies of $G$, one copy of $G$ for each shop John should visit. There should be 4 copies of $G$ with 6 extra (red) edges.
> 2 votes

---
Tags: algorithms, graphs, notation
---


# Question
Title: Why proving that two languages used to merge into a regular language are not necessarily regular isn't possible with closure properties?
> Let $L$ be a regular language over alphabet $\Sigma$. $L$ is the result of merging $2$ languages letter by letter that is for $a\_1a\_2...a\_n\in L\_1, b\_1b\_2...b\_n\in L\_2, L=a\_1b\_1a\_2b\_2...a\_nb\_n$. $\epsilon \in L \iff\epsilon \in L\_1,L\_2$. Does this mean that $L\_1$ is necessarily regular?

At first I tried to prove that this is true using closure properties of regular languages before finding out that the claim is not true (e.g. $L\_1=\\{a^ib^i|i\ge 0\\}, L\_2=\\{ab\\}$).

I'd like to understand though what's wrong with my proof:

1) Define homomorphism $h:\Sigma\to \Sigma^\*\cup \Sigma'^\*$ as follows: $h(\sigma)=h(\sigma')=\sigma$ for $\sigma,\sigma'\in \Sigma.$

2) Let $X=h^{-1}(L)\cap(\Sigma\Sigma^\*)$

3) Define another homomorphism: $f\_1:\Sigma^\*\cup \Sigma'^\*\to \Sigma$ like this: $$ f\_1(\sigma)=\sigma\\f\_1(\sigma')=\epsilon $$ 4) Define another homomorphism: $f\_2:\Sigma^\*\cup \Sigma'^\*\to \Sigma$ like this: $$ f\_2(\sigma')=\sigma'\\f\_2(\sigma)=\epsilon $$ Then $L\_1=f\_1(X), L\_2=f\_2(X)$. Now if either $L\_1$ or $L\_2$ is not regular than it's contradiction because by closure properties they should've been regular. Where is my mistake?

---

**EDIT:** following one of the comments, the problem with the attempt to use closure properties is that apply the homomorphisms $f\_1,f\_2$ on $X$ we may get a different language from the original one.

# Answer
Your construction outputs the language $$ \\{ w \in L\_1 : \exists z \in L\_2 \text{ s.t. } |z|=|w| \\}. $$ In words, it outputs those words in $L\_1$ whose length matches the length of some word in $L\_2$. In general, this could be much smaller than $L\_1$.

In particular, if $L\_2$ is a finite language, then the result of merging $L\_1$ and $L\_2$ is finite, and so regular, for *every* language $L\_1$.
> 3 votes

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


# Question
Title: How to build a finite automaton for right quotient of a regular language?
> Let $L$ be a regular language over $\Sigma=\\{a,b,c\\}$. Build a finite automaton for $L/\\{a\\}$.

Because $L$ is regular then a DFA exists for it: $A=(\Sigma, Q, q\_0, F, \delta)$.

Let $M$ be a finite automaton, $L(M)=L/\\{a\\}$.

$M=(\Sigma, Q\times\\{0,1\\}, (q\_0,0), \delta', F\times\\{1\\})$ with the transition function defined below for all $q\in Q, \sigma \in \Sigma$: $$ \delta'((q,0),\sigma)=(\delta(q,\sigma),0)\\ \delta'((q,0),\epsilon)=(\delta(q,a),1) $$

The reasoning is that in state $0$ we just read letters in $M$ because those exact letters also exist in $L$. But when we reach end of input in $M$ via $\epsilon$ we still need to read $a$ in $L$. I'm not sure if it's valid to assume that $\epsilon$ means end of input?

# Answer
> 2 votes
First of all, note that you are constructing an NFA, and so $\delta'$ should output a set of possible transitions.

You can prove by induction the following identities: $$ \begin{align\*} \delta'((q,0),w) &= \\{ (\delta(q,w),0), (\delta(q,wa),1)\\}, \\ \delta'((q,1),w) &= \begin{cases} \\{(q,1)\\} & w = \epsilon, \\ \emptyset & w \neq \epsilon. \end{cases} \end{align\*} $$ In particular, $\delta'((q\_0,0),w)$ intersects $F \times \\{1\\}$ iff $\delta(q\_0,wa) \in F$. In other words, $w$ is accepted by your NFA iff $wa \in L$, so your automaton is computing $L/a$.

You can simplify your construction by taking the original DFA and simply modifying the set of accepting states, replacing $F$ with $$ F' = \\{ q : \delta(q,a) \in F \\}. $$ The new automaton accepts a word $w$ iff $\delta(q\_0,w) \in F'$ iff $\delta(q\_0,wa) = \delta(\delta(q\_0,w),a) \in F$ iff $wa \in L$.

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


# Question
Title: Are $A$ and $B$ necessarily be decidable if $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable and $A$ & $B$ being exhaustive?
I found the following question

> Suppose A and B are recursively enumerable languages such that $A∪B=Σ^∗$. Further, suppose $(A∩\overline{B})∪(\overline{A}∩B)$ is decidable. Which of the following is true?
> A- It is possible that either A or B is decidable but not both
> B- None of them can be decidable
> C- Both of them are regular
> D- Both of them are decidable

**My attempt:** It is possible for $A$ & $B$ to be mutually exclusive and yet be exhaustive. Now this can happen even when one of them is not decidable. So $A$.

But answer given id $D$. Are my arguments flawed? If yes, how and where?

---

The source of the question is reputable test series, but still there are chances of it being wrong.

# Answer
> It is possible for $A$ & $B$ to be mutually exclusive and yet be exhaustive. Now this can happen even when one of them is not decidable. So option A.

The analysis above is correct except the last conclusion "So option A". We cannot exclude the possibility that $A$ and $B$ are both decidable. In fact, it happens in the current situation because of the extra condition, as shown in the latter part of this answer.

---

Hints, try using the following facts. If you do not know them, prove them first.

* For any two languages $X$ and $Y$, if $X$ is exhaustive and $Y$ is decidable, then $X\cap Y$ is exhaustive. (Moreover, $X\setminus Y$ is exhaustive, too. We do not need this fact, though.)
* For any language $X$, $X$ is decidable if (and only if) both $X$ and $\overline X$ are exhaustive.

---

Here is how we can find both $A$ and $B$ are decidable.

Since $A$ is exhaustive and $(A\cap \overline B)\cup(\overline A\cap B)$ is decidable, $A\cap ((A\cap \overline B)\cup(\overline A\cap B))=A\cap\overline B$ is exhaustive. Since $A\cup B=\Sigma^\*$, $A\cap\overline B=\overline B$. Since $B$ and $\overline B$ are exhaustive, $B$ is decidable.

Symmetrically, $A$ is decidable.
> 2 votes

# Answer
Answer by Arjuna

To check whether a string belongs to $A$ run a TM $M$ giving the string as input. $M$ must accept if string is in $A$ and reject if string is not in $A$. Accepting part is trivial as we are told $A$ is recursively enumerable and hence a semi-deciding Turing machine (will always going to $ACCEPT$ state for strings in the language but may not always go to $REJECT$ state for strings not in the language) must exist for $A$. Now, $M$ only needs a way to go to reject state if string is not in $A$. This can be done as follows:

* If string is not in $A$ it must be in $B$ because $A∪B=Σ∗$
* But if a string is in $B$ it can also be in $A$.
* To be sure a string is not in $A$
    + It must be in $B$ -- can be checked using the semi-deciding Turing machine for $B$.
    + It must not be in $A∩B$ -- can be checked using the decider for $(A∩\overline{B})∪(\overline{A}∩B)$. If string is in $A∩B$ the decider TM will definitely go to a REJECT state.

So, our Turing machine $M$ now knows to accept strings in $A$ and reject strings not in $A$. This makes $A$ a recursive language (decidable). Same construction works for $B$ as well. So, both $A$ and $B$ are recursive (decidable).
> 1 votes

---
Tags: turing-machines, undecidability
---


# Question
Title: minimum cardinality maximal matching of graph
How to find minimum cardinality maximal matching? I tried that pick a edge from highest degree vertex remove other edges from same vertex and so on.

# Answer
> 2 votes
A 2-approximation can be obtained by returning a maximal matching, Call it M. Let OPT be a minimum maximal matching then for each edge in M OPT covers at least one of its endpoints thus: |OPT|\>=|M|/2 It would be better if you’ll be more explicit about what you did and what you’d like the algorithm to achieve (analysis of your idea, approximation factor, so on...)

---
Tags: algorithms, graphs, approximation, matching, bipartite-matching
---


title: Meaning of $ e^x = 1 + x + Θ(x^2)$?

text:
# Question
Title: Meaning of $ e^x = 1 + x + Θ(x^2)$?
In the CLRS chapter 3: When $x → 0$, the approximation of $e^x$ by $1+x$ is quite good:

> $$e^x = 1 + x + Θ(x^2).$$

How is it to be interpreted, what is the role of asymptotic notation here?

# Answer
> 4 votes
There are constants $c,C,\epsilon \> 0$, such that $1+x+cx^2 \le e^x \le 1+x+Cx^2$ whenever $|x| \leq \epsilon$.

# Answer
> 0 votes
This is an example of "placeholder notation". In such expressions, you should mentally replace "$\Theta(x^2)$" with "$f$, for some function $f=\Theta(x^2)$".

---
Tags: asymptotics
---


# Question
Title: Can a non-RE language be reduced to an RE language?
Let $L$ be recursively enumerable and $U$ be non-recursively-enumerable. Is it possible to reduce $U$ to $L$ recursively, $U\leq\_R L$? Personally, I do not think this is possible. If we can reduce $U$ to $L$ by a Turing machine that always halt and we also have an Turing machine that compute $L$ (may not halt), then we connect these two parts, we will have a Turing machine to compute $U$. Then $U$ is also recursively enumerable.

I was asked to show some language $L$ is recursively enumerable first, which was OK. But afterwards, I was asked to show some language which is known not recursively-enumerable, $L\_{diag}=\\{w\_i|M\_i\text{ does not accept } w\_i\\}$ can be reduced to it. I.e. $L\_{diag}\leq\_R L$ which does not make sense to me.

# Answer
> 1 votes
As you say, no non-RE language $U$ can be reduced to any RE language $L$, because, then, we could recognize $U$ using the reduction and the recognition algorithm for $L$.

The language $L\_{diag}$ that you mention is indeed non-RE: it's the complement of an RE set that isn't recursive. There is no recursive reduction from $L\_{diag}$ to $L$.

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


# Question
Title: If graph isomorphism is in P, is then P = NP?
I think that, since graph isomorphism is not known to be $\textbf{NP}$-complete, we can not reduce all problems in $\textbf{NP}$ to it, and therefore the implication does not hold.

Additionally, in the accepted answer to this question it is stated, that a proof that graph isomorphism is not $\textbf{NP}$-complete would prove $\textbf{P} \neq \textbf{NP}$. Why?

# Answer
> 22 votes
**We don't know.**

We do know that $\textbf{P} = \textbf{NP}$ implies graph isomorphism is in $\textbf{P}$, but the other implication has not been proven (to the best of my knowledge). It is suspected graph isomorphism is $\textbf{NP}$-intermediate (i.e., it is in $\textbf{NP} \setminus \textbf{P}$ and not $\textbf{NP}$-complete). This question as well as this other one list evidences supporting said suspicions.

---

Regarding your second question: If $\textbf{P} = \textbf{NP}$, then any (nontrivial) problem in $\textbf{NP}$ is trivially $\textbf{NP}$-complete because any (nontrivial) problem in $\textbf{P}$ is $\textbf{P}$-complete (and we have assumed $\textbf{P} = \textbf{NP}$). Hence, by contraposition, if the conclusion of this implication is false (i.e., there is a problem in $\textbf{NP}$ which is not $\textbf{NP}$-complete), then the premise (i.e., $\textbf{P} = \textbf{NP}$) must also be false.

---
Tags: complexity-theory, np-complete, p-vs-np, graph-isomorphism
---


# Question
Title: Can one get Turing-completeness without nontermination?
As I'm reading the movfuscator paper by Stephen Dolan, I encounter this claim:

> In order to have Turing-completeness, we must allow for nontermination.

This seems like a reasonable statement. But I'm also aware of this work by Wouter Swierstra which aims to prove quite the opposite (as I see it): that one can *simulate a Turing-complete machine* in a *total* language such as Agda.

From a purely theoretic point of view: I'm somewhat confused. Total languages permit only total functions, and total functions *always terminate*. Yet there exists a total interpreter of a Turing-complete language. Can somebody help reconcile this confusion?

Is nontermination necessary for Turing-completeness? Is this a valid question at all?

# Answer
> 2 votes
Many total languages, including Agda and Coq, allow you to define coinductive data types. These model infinite objects, like infinite lists.

Obviously, a function producing an infinite list cannot terminate. However, it must, in a total language, be *productive*. This means that any finite prefix of the produced infinite list can be computed in finite time. Coq and Agda have productivity checkers to ensure this, like they have termination checkers for functions which consume inductive data types.

Using these coinductive data types, you can model infinite executions. In the example you linked, 'running' a brainfuck program produces a trace, which is a potentially-infinite list of machine states.

Whether this is enough to declare the language 'Turing-complete' is, I guess, a question for philosophers. Agda only ever allows you to inspect a finite prefix of the generated trace, so you can't 'run' a program for an infinite amount of time. Then again, no physical machine can run a program for an infinite amount of time. And in practice, you can just disable Agda's termination checker for the one function that prints out your potentially-infinite trace.

---
Tags: computability, turing-completeness, agda
---


title: Show how to do FFT by hand

text:
# Question
Title: Show how to do FFT by hand
Say you have two polynomials: $3 + x$ and $2x^2 + 2$.

I'm trying to understand how FFT helps us multiply these two polynomials. However, I can't find any worked out examples. Can someone show me how FFT algorithm would multiply these two polynomials. (Note: there is nothing special about these polynomials, but I wanted to keep it simple to make it easier to follow.)

I've looked at the algorithms in pseudocode, but all of them seem to be have problems (don't specify what the input should be, undefined variables). And surprisingly, I can't find where anyone has actually walked through (by hand) an example of multiplying polynomials using FFT.

# Answer
> 30 votes
Suppose we use fourth roots of unity, which corresponds to substituting $1,i,-1,-i$ for $x$. We also use decimation-in-time rather than decimation-in-frequency in the FFT algorithm. (We also apply a bit-reversal operation seamlessly.)

In order to compute the transform of the first polynomial, we start by writing the coefficients: $$ 3,1,0,0. $$ The Fourier transform of the even coefficients $3,0$ is $3,3$, and of the odd coefficients $1,0$ is $1,1$. (This transform is just $a,b \mapsto a+b,a-b$.) Therefore the transform of the first polynomial is $$ 4,3+i,2,3-i. $$ This is obtained using $X\_{0,2} = E\_0 \pm O\_0$, $X\_{1,3} = E\_1 \mp i O\_1$. ( From twiddle factor calculation ).

Let's do the same for the second polynomial. The coefficients are $$2,0,2,0.$$ The even coefficients $2,2$ transform to $4,0$, and the odd coefficients $0,0$ transform to $0,0$. Therefore the transform of the second polynomial is $$ 4,0,4,0. $$

We obtain the Fourier transform of the product polynomial by multiplying the two Fourier transforms pointwise: $$ 16, 0, 8, 0. $$ It remains to compute the inverse Fourier transform. The even coefficients $16,8$ inverse-transform to $12,4$, and the odd coefficients $0,0$ inverse-transform to $0,0$. (The inverse transform is $x,y \mapsto (x+y)/2,(x-y)/2$.) Therefore the transform of the product polynomial is $$6,2,6,2.$$ This is obtained using $X\_{0,2} = (E\_0 \pm O\_0)/2$, $X\_{1,3} = (E\_1 \mp i O\_1)/2$. We have obtained the desired answer $$ (3 + x)(2 + 2x^2) = 6+2x+6x^2+2x^3. $$

# Answer
> 10 votes
Define the polynomials, where `deg(A) = q` and `deg(B) = p`. The `deg(C) = q + p`.

In this case, `deg(C) = 1 + 2 = 3`.

$$ A = 3 + x \\ B = 2x^2 + 2 \\ C = A\*B = ? $$

We can easily find C in $O(n^2)$ time by brute-force multiplication of coefficients. By applying FFT (and inverse FFT), we could achieve this in $O(n\log(n))$ time. Explicitly:

1. Convert the coefficient representation of A and B to its value representation. This process is called **evaluation**. Performing Divide-and-Conquer (D&C) for this would take $O(n\log(n))$ time.
2. Multiply component-wise the polynomials in their value representation. This returns the value representation of C = A\*B. This take $O(n)$ time.
3. Invert C using inverse FFT to get C in its coefficient representation. This process is called **interpolation** and it also takes $O(n\log(n))$ time.

Continuing along, we represent each polynomial as a vector whose value are its coefficients. We pad the vector with 0's up to the smallest power of two, $n = 2^k, n \geq deg(C) $. Thus $n = 4$. Choosing a power of two provides us a way to recursively apply our divide-and-conquer algorithm.

$$ \begin{align} &A = 3+x+0x^2+0x^3 \Rightarrow &\vec{a} = \[3, 1, 0, 0\]\\ &B = 2+0x+2x^+0x^3 \Rightarrow & \vec{b} = \[2, 0, 2, 0\] \end{align} $$

Let $A', B'$ be the value representation of A and B, respectively. Notice that FFT (Fast *Fourier Transform*) is a linear transformation (linear map) and can be represented as a matrix, $M$. Thus

$$ A' = M \overrightarrow{a} \\ B' = M \overrightarrow{b} $$

We define $M = M\_n(\omega)$ where $\omega$ is complex roots $n^{th}$ complex roots of unity. Notice `n = 4`, in this example. Also notice that the entry in the $j^{th}$ row and $k^{th}$ column is $\omega\_n^{jk}$ . See more about the DFT matrix here

$$ M\_4(w) = \begin{bmatrix} 1 & 1 & 1 & ... & 1\\ 1 & \omega^1 & \omega^2 & ... & \omega^{n-1}\\ 1 & \omega^2 & \omega^{4} & ... & ... \\ ... & ... & ... & \omega^{jk} & ...\\ 1 & \omega^{n-1} & \omega^{2(n-1)} & ... & \omega^{(n-1)(n-1)} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 &1 \\ 1 &\omega & \omega^2 & \omega^3\\ 1 &\omega^2 & \omega^4 & \omega^6\\ 1 &\omega^3 & \omega^6 & \omega^9 \end{bmatrix} $$

Given the $\omega\_4 = 4^{th}$ roots of unity, we have the ordered set equality:

$$\\{\omega^{0},\omega^1, \omega^2, \omega^3, \omega^4, \omega^5, ... \\} = \\{1, i, -1, -i, 1, i, ...\\}$$

This can be visualized as iterating thru roots of the unit circle in the *counter-clockwise* direction.

Also, notice the `mod n` nature, i.e. $\omega^6 = \omega^{6 \mod n} = \omega^{2} = -1 $ and $-i = \omega^{3} = \omega^{3+n}$

To complete step 1 (*evaluation*) we find $A', B'$ by performing

$$ A' = M * \vec{a} = \begin{bmatrix} 1 & 1 & 1 &1 \\ 1 &\omega & \omega^2 & \omega^3\\ 1 &\omega^2 & \omega^4 & \omega^6\\ 1 &\omega^3 & \omega^6 & \omega^9 \end{bmatrix} \begin{bmatrix} 3 \\ 1 \\ 0 \\ 0 \end{bmatrix} = \begin{bmatrix} 3 + 1 \\ 3 + 1 \omega \\ 3 + \omega^2 \\ 3 + \omega^3 \end{bmatrix} = \begin{bmatrix} 4 \\ 3 + i \\ 2 \\ 3 - i \end{bmatrix} \\ B' = M * \vec{b} = \begin{bmatrix} 1 & 1 & 1 &1 \\ 1 &\omega & \omega^2 & \omega^3\\ 1 &\omega^2 & \omega^4 & \omega^6\\ 1 &\omega^3 & \omega^6 & \omega^9 \end{bmatrix} \begin{bmatrix} 2 \\ 0 \\ 2 \\ 0 \end{bmatrix} = \begin{bmatrix} 2 + 2 \\ 2 + 2 \omega^2 \\ 2 + 2\omega^4 \\ 2 + 2\omega^6 \end{bmatrix} = \begin{bmatrix} 4 \\ 0 \\ 4 \\ 0 \end{bmatrix} $$

This step can be achieved using D&C algorithms (beyond the scope of this answer).

Multiply $A' * B'$ component-wise (step 2)

$$ A' * B' = \begin{bmatrix} 4 \\ 3 + i \\ 2 \\ 3 - i \end{bmatrix} \begin{bmatrix} 4 \\ 0 \\ 4 \\ 0 \end{bmatrix} = \begin{bmatrix} 16 \\ 0\\ 8 \\ 0 \end{bmatrix} = C'\\ $$

Finally, the last step is to represent C' into coefficients. Notice

$$ C' = M \vec{c} \\ \Rightarrow M^{-1}C' = M^{-1} M \vec{c} \\ \Rightarrow \vec{c} = M^{-1}C' $$

Notice $M\_n^{-1} = \frac{1}{n} M\_n(\omega^{-1})$1 and $\omega^j = -\omega^{n/2 + j}$.

$$ M\_n^{-1} = \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 &1 \\ 1 &\omega^{-1} & \omega^{-2} & \omega^{-3}\\ 1 &\omega^{-2} & \omega^{-4} & \omega^{-6}\\ 1 &\omega^{-3} & \omega^{-6} & \omega^{-9} \end{bmatrix} = \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1\\ 1 & i & -1 & -i \end{bmatrix} $$

$\omega^{-j}$ can be visualized as iterating thru roots of the unit circle in the *clockwise* direction.

$$\\{\omega^{0},\omega^{-1}, \omega^{-2}, \omega^{-3}, \omega^{-4}, \omega^{-5}, ... \\} = \\{1, -i, -1, i, 1, -i, ...\\}$$

Also, it is true that, given the $n^{th}$ root of unity, the equality $\omega^{-j} = \omega^{n-j}$ holds. (Do you see why?)

Then, $$ \vec{c} = M^{-1}C' = \frac{1}{n} M\_n(w^{-1}) = \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1\\ 1 & i & -1 & -i \end{bmatrix} \begin{bmatrix} 16 \\ 0\\ 8 \\ 0 \end{bmatrix} = \begin{bmatrix} (16 + 8) /4 \\ (16 - 8) /4 \\ (16 + 8) /4 \\ (16 - 8) /4 \end{bmatrix} = \begin{bmatrix} 6 \\ 2\\ 6 \\ 2 \end{bmatrix} $$

Thus, we get the polynomial $$ C = A * B = 6 + 2x + 6x^2 + 2x^3$$ 1: Inversion Formula pg 73, Algorithms by Dasgupta et. al. (C) 2006

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


# Question
Title: Infinite sequence has $m$ consecutive digits – regular languages
Suppose we have an infinite sequence over the decimal alphabet, call it $w$. For $k\in \\{0,1,2,3,4,5,6,7,8,9\\}$, let $L\_k = \\{m\geq 0: \text{$w$ contains a run of $m$ $k$'s}\\}$ be a language. Here a run denotes a contiguous block of the sequences. Prove that $L\_k$ is a regular language.

Here is my idea. Clearly, if $w$ contains arbitrarily long runs of $k$, then $L\_k$ is pretty much just the set of all positive natural numbers, which is regular. But if $w$ has a maximum run of $k$'s, then $L\_k$ is a finite set, which means it's regular. This is as far as I got, this language "feels" like it shouldn't be regular, but I am told it is. Would the regularity of $L\_k$ even depend on whether it is possible to compute whether $w$ has a maximum run of $k$'s?

# Answer
You don't explain how the input to $L\_k$ is encoded, but $L\_k$ will be regular under any reasonable encoding.

Indeed, if $w$ contains a run of $m$ many $k$'s, then it also contains a run of $m'$ many $k$'s for any $m' \leq m$. Therefore either $L\_k$ is finite (indeed, of the form $\\{0,\ldots,m\\}$) or it consists of all of $\mathbb{N}$.

You seem to be troubled by the fact that $L\_k$ is not necessarily computable from (a description of) $w$. But there is absolutely no such requirement – all we have to show is that for each $w$, the languages $L\_k$ are regular. We are not claiming that we can compute $L\_k$ from (a description of) $w$.
> 3 votes

---
Tags: regular-languages
---


# Question
Title: Prove that a sequence of increasing find operations on a splay tree takes $\mathcal{O}(n)$ time
When studying about splay trees, I found the following statement:

> Suppose we have a splay tree and a sequence of Find operations, where the elements we are searching for are in increasing order. Then the total time necessary to run the sequence is $\mathcal{O}(n)$ ($n$ is the number of nodes in the tree).

I looked around, but haven't been able to find anything. Can this be proven formally? Or shown that it is true?

# Answer
Here is a helper fact.

(**Simple cost of splaying**) Let $c(v)$ be the time it takes to find an element $v$ in a splay tree. There exists a constant $c\_0$ independent of the splay tree and $v$ such that $c(v)\le c\_0d(v)$, where $d(v)$ is the depth of $v$.

Here is the sketch of a proof.

There are two tasks that contribute to $c(v)$.

* To locate $v$ by going from the root downwards to the $v$, which takes at most $c\_1d(v)$ time for some constant $c\_1$.
* To splay $v$ to the root. It takes each splay operation of zig, zag, zig-zig, zag-zag, zig-zag, zag-zig some constant time to move $v$ nearer to the root by 1 or by 2, splaying $v$ to the root takes at most $c\_2d(v)$ time for some constant $c\_2$.

Let $c\_0=c\_1+c\_2$. Proof is done.

---

> Suppose we have a splay tree and a sequence of Find operations, where the elements we are searching for are in increasing order. Then the total time necessary to run the sequence is $O(n)$, where $n$ is the number of nodes in the tree.

Let $v\_0, v\_1,\cdots, v\_m$ be an array of elements in increasing order.

It takes $O(n)$ to find $v\_0$ (including splaying $v\_0$ to the root).

What about finding the remaining $m$ elements?

* Finding $v\_1$ when $v\_0$ is at the root takes at most $c\_0d\_{v\_0}(v\_1)$ time, where $d\_{v\_0}(v\_1)$ is the depth of $v\_1$ in the splay tree with $v\_0$ as the root. Note that splay tree is a binary search tree, $d\_{v\_0}(v\_1)$ is at most one one more than the number of elements between $v\_0$ and $v\_1$ exclusively.
* Finding $v\_2$ when $v\_1$ is at the root takes at most $c\_0d\_{v\_1}(v\_2)$ time, where $d\_{v\_1}(v\_2)$ is at most one one more than the number of elements between $v\_1$ and $v\_2$ exclusively.
* $\vdots$
* Finding $v\_{m}$ when $v\_{m-1}$ is at the root takes at most $c\_0d\_{v\_{m-1}}(v\_m)$ time, where $d\_{v\_{m-1}}(v\_m)$ is at most one more than the number of elements between $v\_{m-1}$ and $v\_m$ exclusively.

So, the total time necessary to run the sequence of finding $v\_1, v\_2,\cdots,v\_m$ is at most $c\_0d(v\_0, v\_m)$, where $d(v\_0, v\_m)$ is at most one more than the number of elements between $v\_0$ and $v\_m$ exclusively, i.e., $d(v\_0, v\_m)\le m\lt n$.

So the total time necessary to run the sequence of finding $v\_0, v\_1, v\_2,\cdots,v\_m$ is at most $O(n) + c\_0n$, which is $O(n)$ still.
> 1 votes

---
Tags: data-structures, splay-trees
---


title: Reduction between these two languages

text:
# Question
Title: Reduction between these two languages
I'm given $L\_\cap=\\{\langle M\_1\rangle\\#\langle M\_2\rangle\mid L(M\_1)\cap L(M\_2)\neq\emptyset\\}$ and $L\_U=\\{\langle M\rangle\\#w|M \text{ accepts } w\\}$.

How can I reduce the former to the latter: $L\_\cap\leq\_RL\_U$? My idea was to build a machine $M$ simulating $M\_1$ and $M\_2$ in series. $M$ accepts a word if and only if both $M\_1$ and $M\_2$ do. So we feed all words to the machine taking $M$ and words until we find one, otherwise keep running. But the proplem is the machine is not halting guaranteed since it can run forever. What will be the correct solution?

# Answer
Your solution is *almost* there: I do not think it is necessary to construct a machine that always halts. The problem running $M$ on input $w$ does not always halt either.

Running $M\_1$ and $M\_2$ over all input strings $x$ is tricky: indeed,if one of the machines does not halt on a particular input, then the new machine $M$ will not consider the next input. The solution for that is usually called dove tiling, where more and more inputs are simulated step by step.

This can be avoided (or better: hidden) by assuming non-deterministic machines. $M$ guesses an input $x$ and simulates both $M\_1$ and $M\_2$ on that input $x$. Now $M$ halts (on the empty input) whenever the languages of $M\_1$ and $M\_2$ intersect.
> 1 votes

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


title: Topological sorting colored tree

text:
# Question
Title: Topological sorting colored tree
EDIT: The most general case I need is not a tree but any Directed Acyclic Graph.

I have a directed acyclic graph.

I need to sort it in a list so that in the list every node comes after any node it can walk to in the graph.

So far so good, just use a topological sorting algorithm.

However, I have an additional constraint: Each node in the graph is colored, and I need to find a sorting so that the list is as cohesive as possible. In other words, if you walk the list, you should see a change in colors as few times as possible.

Other thoughts:

* I need an efficient algorithm. No iterating through all possible sortings.
* The set of colors is typically much smaller than the set of nodes in the graph.
* If no efficient exact algorithm is possible, I would be happy with a heuristic one that is likely to produce good results.
* There is some information that one could potentially use for the heuristic: The colors are also partially ordered, and this ordering of the colors is correlated to the ordering of the nodes. I.e. a node is likely (but not guaranteed) to have a color that is "smaller than" the color of its parent node.
* You can think of the problem this way: I have a set of jobs, and each job can depend on the output of several other jobs (if x depends on y there is an arrow from x to y). There is an overhead associated with setting up the data needed for each job, but this overhead is significantly reduced if the previous job had the same "color". The whole set of jobs is typically executed many thousand times, so if one can find an not too expensive way to improve the order of the jobs, that will pay off.

So far I have come up with this algorithm which works well most times, but not always:

**first pass:**

Define the order "\<=" so that x \<= y if y can walk to x in the graph.

find any topological sort of the nodes and put it in the list L (L is sorted from smallest to largest w.r.t the partial ordering "\<=" )

```
W = []
for x in L:
   find the earliest y in W so that color(x)==color(y) && there is no z in W with z > y and x > z
   if y exists:
       insert x in W after y.
   if y does not exist and there is no z in W with x > z:
       place x at the beginning of W
   else:
       place x at the end of W

```

**second pass:**

```
 for each continuous group G of colors in W:
    for x in G in reverse order:
       find the latest y in W so that color(x)==color(y) && there is no z in W with z > x and z < y
       if y exists:
           move x directly before y in W

```

The second pass may seem a little puzzling, but it is just my experience that it tends to improve the results. I.e. some times it will be able to move one whole group of colors past another group and join a third group of the same color.

I think the reason that the first pass is not sufficient is that there can be complicated interdependencies between the nodes that are sorted in L after the current x you are looking at, and so you can't know the optimal placement of x in the first pass, you just have to go with something.

Any help would be great!

# Answer
> 4 votes
Suppose you know the list of colors that appear in contiguous parts of an optimal ordering. Then, you can easily find this optimal ordering: simply put as many nodes of the current color in your list as the parent-child order allows and proceed with the next color in your list. This greedy strategy is optimal, because once you have started a color, you will not 'regret' taking a node of the same color later as it adds no cost and only gives more options. If you put all 'free' nodes that already have their parents processed in separate lists, this can be done in $O(n)$, where $n$ is the number of nodes in your forest.

Of course, we do not know this list, so we should figure out how to find it. The number of color lists you would have to check in an uninformed search is $c(c-1)^{k}$, where $c$ is the number of colors you have and $k$ the minimal number of color switches in the final order. If you're lucky, $c$ and $k$ are sufficiently small for a brute-force search and we are done.

However, this will quickly become unfeasible, so I doubt you can afford to spend the $O(c(c-1)^k n)$ time required to do a brute-force search$^1$. Finding an optimal list 'looks hard'. I have no formal proof of e.g. NP-hardness, but it is clear that decisions made early on depend on the structure of the entire forest, so the most natural approach is to try to create subdivisions of by 'cutting' the forest to get subproblems and use e.g. dynamic programming. However, since the nodes can be ordered in many ways, I do not see how to represent these cuts with only polynomially many states. Another hint is that you can see this as a special case of the scheduling problem with partial order requirements.

So, since I think it likely we cannot find an efficient exact solution, you should try an heuristic approach or can perhaps even find an approximation algorithm. I will finish with some observations that may help you in developing such an approach:

* If we decide on the last color in list first and build the ordering backwards, observe that we can only choose nodes where all descendants have the same color: if not, there is a node of another color that should be later in the list. Since we would select all children of the same color as a parent if we had chosen a front to back order in an optimal ordering, we should select only subtrees of the same color where the root has no parent of the same color. It is possible that for some colors, there are no such subtrees, which means that we have less options for the final color.
* If there is a color for which you can select all remaining nodes, you should select that color. This may occur quite often if the correlation between the color ordering and node ordering is high.
* One idea for an heuristic is to select the color that is 'blocking' the most nodes of other colors: you can look at the total number of 'chains' of nodes of the same color that are accessible after removing the color or at the number for a specific color you would like to remove first or the maximum number over all colors.

---

$^1$: You could be slightly more clever and do recursive backtracking where you can prune some searches, but this has the same worst case running time.

---
Tags: graphs, sorting
---


# Question
Title: Is there a LL(1) grammar for the language with equal number of a's and b's?
Consider the following CFG.

$S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS$

Can we prove formally that an equivalent $LL(1)$ grammar does not exist? I feel that intuitively an equivalent $LL(1)$ grammar doesn't exist, but I'm unable to prove this formally.

# Answer
> 4 votes
The language for the grammar in the question is the set of all words with equal number of $a$'s and $b$'s.

I am afraid your intuition is incorrect. Here is an $LL(1)$ grammar for the language.

$\qquad S \to AS \mid BS \mid \epsilon$
$\qquad A \to aXb$
$\qquad X \to AX \mid \epsilon$
$\qquad B \to bYa$
$\qquad Y \to BY \mid\epsilon$

Here is some statistics about the grammar above . $$\begin{array} {|c|c|c|c|} \hline \text{nonterminal} &\text{first set} &\text{follow set} &\text{nullable} &\text{endable}\\\hline S &a\ b &\emptyset &\text{yes} &\text{yes}\\\hline A &a &a\ \ b &\text{no} &\text{yes}\\\hline X &a &b &\text{yes} &\text{no} \\\hline B &b &b\ \ a &\text{no} &\text{yes}\\\hline Y &b &a &\text{yes} &\text{no} \\\hline \end{array}$$

Here is the parsing table. $$\begin{array} {|c|c|c|c|}\hline &a &b &{\\\\$} \\\hline S &S\to AS &S\to BS &S\to \epsilon\\\hline A &A\to aXb & & \\\hline X &X\to AX &X\to\epsilon & \\\hline B & &B\to bYa &\\\hline Y &Y\to\epsilon &Y\to BY & \\\hline \end{array}$$

**Exercise 1.** Show that both the grammar in the question and the grammar above generate the language of words with equal number of $a$'s and $b$'s.

**Exercise 2.** Consider the following grammar.
$\qquad S \to AS \mid BS \mid \epsilon$
$\qquad A \to aU$
$\qquad U \to AbA \mid b$
$\qquad B \to bV$
$\qquad V \to BaB \mid a$
Show that the grammar above also generate the language of words with equal number of $a$'s and $b$'s. Show that it is $LL(1)$.

**Exercise 3.** The following grammar also generate the language of equal number of $a$'s and $b$'s. Explain why it is not $LL(1)$.
$\qquad S \to AS \mid BS \mid \epsilon$
$\qquad A \to aAbA \mid \epsilon$
$\qquad B \to bBaB \mid \epsilon$

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


# Question
Title: PDA for the language of strings containing the same number of a and b
Need idea for solving the following pushdown automata:

$\mathcal{L}=\\{w\in\sum ^\* | \\#a(w)=\\#b(w),|w|\geqslant 0\\} \\,\\,\\,\\, \sum=\\{a,b\\}$

In the beginning I thought to PUSH *A* for input *a*, and then to POP *A* for input *b*, but it doesn't work well for the word ba for example

# Answer
You have solved half of the task. Now push $B$ for $b$ and pop $B$ for $a$.
To decide which operation to do, handle empty stack, pushing symbol when it is empty and popping otherwise.
> 0 votes

---
Tags: pushdown-automata
---


title: Set cover to Edge cover

text:
# Question
Title: Set cover to Edge cover
I want to find set cover of this problem. I have sets, each of cardinality 3. I want to find set cover. This is what I am doing. Treat each set as an edge, which is incident on each of its element. I am considering each element as a vertex. Now I will find minimum edge cover of this (hyper)graph. Is this the right way to do?

# Answer
Yes. This is a right and possible way to go.

One can also consider the formulation of the set cover problem as an Integer Program, using the LP relaxation of such program you can obtain what is referred as $f$-approximation. Details and analysis can be found in most standard books on approximation algorithms.
> 0 votes

---
Tags: graphs, approximation, set-cover, vertex-cover
---


title: Why is this not recognized by a DFA?

text:
# Question
Title: Why is this not recognized by a DFA?
I am still confused over my professor's explanation on why this problem is not a DFA.

The Problem: Explain why $L = \\{p^kq^k \mid k\>0\\}$ cannot be recognized by a DFA

My professor explained it as that it was because the DFA could not store the $k$ iterations in memory. But I still don't get it. In my mind, you just draw states $k$ number of times for $p$ and then $q$.

What's wrong with my logic?

# Answer
The actual claim is that there is no DFA for the language $\\{p^kq^k\mid k\geq 0\\}$. Such an automaton would have to accept *every* string of the form $p^kq^k$ for any $k$, and reject every other string.

For any one fixed value of $k$, you're absolutely right that you can use $2k$ states to count off the $p$'s and the $q$'s. However, to recognize the language, the automaton would have to be able to do this for infinitely many different values of $k$, which would require infinitely many states by this method. Of course, that's not allowed in a deterministic *finite* automaton.

Note that this isn't a formal proof that no DFA can accept this language; rather it's just an intuition about why you should expect there to be no DFA. To formally prove the claim, you'd have to use something like the pumping lemma or Myhill–Nerode; we have a reference question about how to do that.
> 5 votes

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


title: Djikstra algorithm analysis

text:
# Question
Title: Djikstra algorithm analysis
My textbook says that the Dijkstra algorithm's runtime is $O(n) + O(m \log(n)) = O((n+m) \log(n))$. How did they come up with that?

Dijkstra algorithm pseudocode:

```
 1. Dijkstra(V, E, s):
 2.    Create an empty priority queue

 3.    for each v ≠ s:
 4.        d(v) ← ∞
 5.        d(s) ← 0

 6.    for each v ∈ V:
 7.        insert v with key d(v) into priority queue

 8.    while (the priority queue is not empty):
 9.        u ← delete-min from priority queue

10.        For each edge (u,v) ∈ E leaving u:
11.            If d(v) > d(u) + l(u,v):
12.                decrease-key of v to d(u) + l(u,v) in priority queue
13.                d(v) ← d(u) + l(u,v)

```

My runtime analysis:

```
 1.
 2. O(1)

 3. O(n)
 4.     O(1)
 5.     O(1)

 6. O(n)
 7.     O(log(n))

 8. O(n)
 9.     O(log(n))

10.     O(m)
11.         O(1)
12.             O(log(n))
13.             O(1)

```

From my analysis, the largest runtime would be from lines 8, 10, 11, and 12, resulting in $O(nm\log(n)) \ne O((n+m) \log(n))$.

# Answer
> 1 votes
```
 8.    while (the priority queue is not empty):
 9.        u ← delete-min from priority queue

10.        For each edge (u,v) ∈ E leaving u:
11.            If d(v) > d(u) + l(u,v):
12.                decrease-key of v to d(u) + l(u,v) in priority queue
13.                d(v) ← d(u) + l(u,v)

```

Consider the multi-set of all edges that appear on line 10, where $u$ goes through all vertices thanks to the line 9 inside the while loop. There are two cases.

* The graph is undirected. Each of those edges must be incident to a vertex $u$. So each edge in the graph appears exactly twice.
* The graph is directed. Each of those edges must have $u$ as its starting endpoint. So each edge in the graph exactly appears once.

So in total, the number of edges that appear on line 10 is either $2|E|$ with undirected graph or $|E|$ with directed graph. So the running time from lines 8, 10, 11, and 12 is $2mO(\log(n))$ or $mO(\log(n))$. That is, $O(m\log(n))$.

Had the line 10 been `For each edge (w,v) ∈ E:`, your analysis might have had a chance to be correct.

---
Tags: graphs, algorithm-analysis, runtime-analysis, shortest-path
---


# Question
Title: Show that any monotone Boolean function is computable by a circuit containing only AND and OR gates
A Boolean function $f : \\{0, 1\\}^n → \\{0, 1\\}$ is called monotone if changing any of the $n$ input bits $x\_1, \ldots , x\_n$ from $0$ to $1$ can only ever change the output $f(x\_1, \ldots ,x\_n)$ from $0$ to $1$, never from $1$ to $0$.

I know how to do a simple proof of exhaustion for $f : \\{0, 1\\}^1$ and $f : \\{0, 1\\}^2$, but I do not know how to prove the following statement for $f:\\{0,1\\}^n$: any monotone Boolean function is computable by a circuit containing only AND and OR gates.

# Answer
Any Boolean function can be written as a DNF. Each clause in the DNF specifies one truth assignment for which the function holds. For example, the DNF form of XOR is $(x \land \lnot y) \lor (\lnot x \land y)$.

The main observation is that if the function is monotone, you can remove all the negated literals (why?). Once you do that, you get a formula for the function which uses only AND and OR. Some clauses in this formula subsume others (for example, $x$ subsumes $x \land y$). If you drop all the subsumed clauses, you arrive at the *minterm* representation of the function. (A minterm is a minimal satisfying assignment.)

It's a bit more confusing, but you can also do everything using CNFs. This way you arrive at the *maxterm* representation.
> 7 votes

# Answer
You can prove this by induction. We will construct a formula with constants, and then you can eliminate the constants (unless the function itself is constant), if you wish, using the simplification rules $x \land 0 = 0$, $x \land 1 = x$, $x \lor 0 = x$, $x \lor 1 = 1$.

When $n = 0$, the function is just a constant. Given a function $f$ of $n$ variables $f(x\_1,\ldots,x\_n)$, we can always construct two functions of the previous consecutive $(n-1)$ variables $f\_0(x\_1,\ldots,x\_{n-1}) = f(x\_1,\ldots,x\_{n-1},0)$ and $f\_1(x\_1,\ldots,x\_{n-1}) = f(x\_1,\ldots,x\_{n-1},1)$, and both $f\_0,f\_1$ are monotone by the inductive hypothesis. Also there must be well-formed formulas representing Boolean functions $f\_0,f\_1$, respectively. I claim that $$ f = f\_0 \lor (x\_n \land f\_1). $$ because substituting $x\_n = 0$ we just get $f\_0$, and substituting $x\_n = 1$ we get $f\_0 \lor f\_1 = f\_1$. Now we can conclude indeed $f$ is monotone since if $f(\vec{x},0)=f\_0$ is true then so is $f(\vec{x},1)=f\_1$ by above stated inductive hypothesis, and this finishes the inductive step.
> 2 votes

# Answer
Assume we operate on $n$ variables $x\_1,...,x\_n$. Take all sets $S\_1,...,S\_n$ of variables where assigning those variables 'true' makes the statement 'true'. Build the expression

$$f = or(and(S\_1), and(S\_2), ..., and(S\_n))$$

Now, whenever all of the variables in one of the $S\_i$ are true, this expression will be true. However, might we have too many true assignments?

No, because if some assignment to the $x\_i$ makes $f$ true, then it makes one of the clauses of the $or$ true (because that's how $or$ works). Let's say it's $and(S\_i)$ for some $i$. Then this means all the variables in $S\_i$ are true (and maybe some others), and as the function is monotone, that means $f$ must be true.
> 0 votes

# Answer
In the expression $OR(x,y)$, if I define x as 0 and y as $f:\\{0,1\\}^{n-1}$, OR(x,y) is monotone and can represent any monotone function. This statement is in $f:\\{0,1\\}^{n}$, which means $f:\\{0,1\\}^{n}$ contains any monotone function.
> -2 votes

---
Tags: proof-techniques, circuits
---


# Question
Title: Prove Halting on all Inputs is not in RE simulation
I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine that the halting problem receives as input) on w(the word received as input) for n steps.

Can somebody explain to me who is n and why do we need to simulate M for n steps? Why not only once?

For proving that halting on all inputs problem is not in RE, the complement of halting problem is used. Supposed we take M(w) as the turing machine used for halting problem, I get the next simulation:

M'= simulate M(w) for n steps; if M(w) halts, make it loop else, stop.

I don't understand why do I have to make M' simulate M(w) for N STEPS. Why can't I just simulate it one and that's it?

N stands for the length of the word. I don't understand the simulation for a number of steps. Why is that?

# Answer
> 1 votes
What is the Halting on all inputs problem? It is the problem about the language $$TOTAL=\\{⟨M⟩\mid M \text{ is a TM and }M\text{ halts on all inputs} \\}.$$

What is the complement of the Halting problem? It is the problem about the language $$\overline{HALT}= \\{⟨M, w⟩\mid M \text{ is a TM and }M\text{ does not halt on input } w\\}.$$

---

Given a word $⟨M, w⟩$ where $M$ is a Turing machine and $w$ is a input word, how can we construct a new Turing machine in a way that is similar to/the same as how a Turing machine is described in $TOTAL$?

> $M'$ = simulate $M(w)$ for $n$ steps; if $M(w)$ halts, make it loop else, stop.

The construction above is not clear as the meaning of $n$ is defined. Let us clarify that $n$ is the length of the input string. Here is a clear construction of $M'$, where $|x|$ is the length of $x$.

> $M' = $ "On input string $x$, simulate $M$ with input $w$ as long as possible but for no more than $|x|$ steps. If the simulation ever halts, continue to loop forever; otherwise, halt."

Now you should be able to check that $$⟨M, w⟩\in\overline{HALT} \Longleftrightarrow M'\in TOTAL.$$

---

> I don't understand why do I have to make M' simulate M(w) for N STEPS. Why can't I just simulate it one and that's it?

The "N" in "N STEPS" depends on the input to $M'$. It is a variable independent of $M'$.

---
Tags: turing-machines, computability, proof-techniques, semi-decidability, simulation
---


# Question
Title: How are words assigned in machine language?
So, if you have an 8-bit computer and it can perform a fetch cycle, meaning it can access its memory, how do you create words the computer understands.

If LDA "load the accumulator" is in the instruction set and its just something we named for humans and the computer understands binary...

How was this idea communicated in binary.

I see it's another language, in logic, two-state system,

literal b/c logic gates are

But how do you say load and add and such

These are the human terms but what would the computer hear?

# Answer
> 3 votes
LDA gets translated by the assembler to bytes that the machine can interpret.

The contents of these bytes are set by the instruction decoder, and often made to make the decoder as simple as possible. For example some bits may get passed straight to the execution unit so add and subtract differ by a single bit which triggers inverting the second operand and sets the carry in bit. The bits that decide which registers to use would be common to all instructions, stuff like that

The 3 letter acronyms are just shorthands set by whoever was in charge of writing the assembler.

---
Tags: computer-architecture, cpu
---


title: Minimal edge cover of the hypergraph

text:
# Question
Title: Minimal edge cover of the hypergraph
We know that minimal edge cover for the normal graph is polynomial time solvable. Is it also true for hypergraph?

# Answer
> 1 votes
The polynomial algorithm for "classical" graph is based on a maximum matching algorithm completed with the isolated nodes. 3-dimensional matching is known to be NP-complete (https://en.wikipedia.org/wiki/3-dimensional\_matching). This is a case of minimal edge cover for hypergraph. Thus the answer is no.

---
Tags: graphs, approximation, matching, set-cover
---


# Question
Title: How can I find the Myhill-Nerode classes for the language A?
I have the following task (no homework).

> Find all equivalence classes of the Myhill-Nerode relation of the language $$ \mathrm{A} \triangleq\\{w \in \Sigma^{\*} | w\text{ does not end with }01\\}\\,. $$

Because I have no Idea how I to find does classes -I know the theory, but I can't use it -. So I build a DFA (what i should not do):

Now I know there has to be 3 different classes (because the DFA is minimized), but again, I have no idea how to find them. I hope you can help me a little bit, because I write a test paper in 5 weeks and this will be a big Troublemaker.

# Answer
> 1 votes
Two strings $x$ and $y$ are in the same Myhill–Nerode class if they can't be distinguished by adding the same string onto the end of them. That is, they're in the same class if, for all strings $z$, either $xz$ and $yz$ are both in the language or neither of them is.

So, for example, the strings $00$ and $01$ are in different classes because we can distinguish then by adding $1$: $001$ is in the language and $011$ is not. In fact, they're already distinguished by the empty string $\epsilon$, since $01$ is in the language but $00$ is not.

In your case, you can shortcut this because the notion of indistinguishability corresponds exactly to minimal automata: the classes are exactly the sets of strings that take you to each state of the automaton.

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


title: Why is LTL Model Checking in PSPACE

text:
# Question
Title: Why is LTL Model Checking in PSPACE
Given a LTL formula $\phi$ and a transition system $T$ we have to do following steps:

1. Build a (non deterministic) Büchi automaton for $T$
2. Build a (non deterministic) Büchi automaton for $\phi$
3. Compute the intersection of these automatons and check for emptyness

Step 1 can be done in $\mathcal{O}(|T|)$ time and space. I also know and understand that step 3 requires $\mathcal{O}(log^2n)$ space. But what about step 2? The size of the resulting Büchi Automaton from a LTL formula can be exponential in $|\phi|$. Writing that down requires more then polynomial space. So what am I missing here?

Do you may have any papers or books I could read on this topic?

# Answer
> 3 votes
It is correct that writing the Buchi automaton to memory takes exponential space.....which is why you don't do that.

The construction for the Buchi automaton is however very regular and can be done in a *forward* manner. This allows you to construct it on-the-fly while you search for an accepting lasso in the product between the Buchi automaton and $T$.

In this way, you can find an accepting lasso in NPSPACE (it is exists): you build a Turing machine that builds the product on-the-fly, searches for a lasso by non-deterministically guessing which transition in the product to take, and non-determinstically guesses the lasso knot to store (which, w.l.o.g., could also be the required accepting state). If it finds a path to such a knot and then a path from the knot back to the knot, you know that there is a word in the product.

To make this algorithm always terminate, you also have a counter to keep track of the number of transitions observed so far. If it exceeds two times the size of the product, then the algorithm aborts with a "no" answer. Such a counter also only needs space polynomial in the size of the LTL formula.

Since PSPACE=NPSPACE, it follows that you only need polynomial space for such a Turing machine.

# Answer
> 1 votes
Check Lichtenstein and Pnueli's 1985 POPL paper.

---
Tags: complexity-theory, linear-temporal-logic
---


# Question
Title: Determine if there exists a line that intersects all horizontal segments. Better than $O(n^2 \lg n)$?
Suppose I have $n$ horizontal segments in the plane (i.e. their end points share the same $y$ value). I want to determine if there exists a line that intersects all such segments.

I think I can assert that (by some argument based on shifting the line), there exists such line iif there exists a line positioned on some end-point of one of the line segments that intersects all line segments (so that I can iterate through all end-points of the line segments (in total $2n$ points) and try to find the line). Then if I fix a point $p$, I can do a $O(n \lg n)$ radial sweep and see if there exists a line positioned at that point that intersects all the segments. I then just iterate through all $2n$ points and that gives me $O(n^2 \lg n)$.

1. Is my reasoning correct enough for me to write an algorithm for this?
2. Is there a better way to do this than $O(n^2 \lg n)?$

# Answer
> 3 votes
WLOG, let's rotate your problem so your segments are vertical. Let's say segment $i$ has $x$-coordinate $x\_i$ and its low endpoint is $l\_i$ and high endpoint $h\_i$ (with $l\_i \< h\_i$).

Then our line through it (assuming it exists) has formula $y = ax + b$. Plugging in $x\_i$ gives us $y\_i = ax\_i + b$. And thus we have $l\_i \leq ax\_i + b \leq h\_i$.

Convince yourself that a solution line can always intersect at least one of two points: the one with the highest $l\_i$ or the one with lowest $h\_i$ (the most extreme requirements).

We try to find a solution line by plugging in one of the two extreme points $p$ (trying the other if the first doesn't work) to find $b = y\_p - ax\_p$. Then we can substitute to change the inequalities to:

$$l\_i \leq a(x\_i - x\_p) + y\_p \leq h\_i$$

Now our only variable is $a$ so we can run through the $n$ inequalities, consistently choosing the strictest bounds for $a$ until we find the range of $a$ that works or that there's no solution.

Total runtime is $O(n)$ since we only have to try the above process twice and finding the extreme points also takes only $O(n)$ time.

# Answer
> 2 votes
**Without words, an $O(n\log n)$ solution:**

---
Tags: algorithms, computational-geometry
---


# Question
Title: What would be the big-o time complexity of this scenario?
I am wondering what the time complexity of a for loop that increments the control variable, but also multiplies it inside the loop. For example

```
for (int k = 0; k < n; k++)
{
    stuff

    k *= 2;
}

```

I am thinking it must be something like O(log n), but I know that is not it. Any help would be appreciated.

# Answer
> 1 votes
It is $O(\log n)$. Simply take a look at the number of iterations your loop produces when $n$ goes up. I know this is not a proof, btw. You can observe that if $n = 2^p$, for some $p \geqslant 0$, the number of iterations inside the loop increases by one. Clearly, this happens only $O(\log n)$ times, and therefore your loop has $O(\log n)$ iterations.

Now a lightly more formal attempt, but still with a few holes here and there.

We observe that at the end of the loop $$k = 2^{\lfloor \log n \rfloor + 1} - 1.$$

Technically, we should prove this using a loop invariant or induction, but I'm a little too lazy for that now. If we let $n = 2^p$, for some integer $p \geqslant 1$, then we get that $\lfloor \log n \rfloor = \lfloor \log(n - 1) \rfloor + 1$. Let $k\_n$ denote the value of $k$ after $n$ iterations. Then

$$k\_n = 2^{p + 1} - 1 = 2^{\lfloor \log(n - 1) \rfloor + 2} - 1 \> 2^{\lfloor \log(n - 1) \rfloor + 1} - 1 = k\_{n - 1}.$$

So we conclude that $k\_n$ has grown over $k\_{n-1}$, but only if $n = 2^p$. Therefore, the number of iterations is $O(\log n)$.

### Edit

A far more intuitive approach is to consider the code

```
int k = 0;
for (int i = 0; k < n; i++) {
  if (i = 1) {
    k = 1;
  }
  k *= 2;
}

```

Clearly, your code causes $k$ to converge more quickly to $n$ than this example, and this loop finishes after $O(\log n)$ iterations. Clearly, your code will also at most use $O(\log n)$ iterations.

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Run-time of Hungarian algorithm - matrix formulation
There are many different explanations of the Hungarian algorithm. My favorite explanation is the one based on matrices, for example here, since it is very intuitive and easy to carry out in a spreadsheet.

The problem is, I could not understand the argument of why this algorithm, in its matrix formalism, is polynomial in $n$. In particular, in the above presentation, I got stuck trying to prove that Step 5 (page 13) is executed $O(n)$ times, or more generally, $O(poly(n))$ times.

In step 5, we subtract a number $x$ from each uncovered row, and then add the same $x$ to each covered column. Since in this step, the size of the covering is less than $n$, there are more uncovered rows than covered columns, so we subtract $x$ more times than we add $x$. Hence, the sum of all elements in the matrix strictly decreases each time. Since the sum always remains positive, the algorithm must eventually end.

However, I could not understand why it must end after $O(poly(n))$ iterations.

What am I missing in the above argument?

# Answer
> 1 votes
> However, I could not understand why it must end after $(n)$ iterations.

Because it is not true.

Check the following matrices, which are the initial matrix, the matrix at the end of step 2, and the matrices at the end of step 5. Here the steps are explained as in the notes mentioned in the question.

```
[[1, 1, 1, 1, 1]
 [1, 2, 11, 11, 11]
 [1, 3, 4, 11, 11]
 [1, 4, 6, 7, 11]
 [1, 5, 8, 10, 11]]

[[0, 0, 0, 0, 0]
 [0, 1, 10, 10, 10]
 [0, 2, 3, 10, 10]
 [0, 3, 5, 6, 10]
 [0, 4, 7, 9, 10]]

[[0, 0, 0, 0, 0]
 [0, 0, 9, 9, 9]
 [0, 1, 2, 9, 9]
 [0, 2, 4, 5, 9]
 [0, 3, 6, 8, 9]]

[[0, 0, 0, 0, 0]
 [0, 0, 9, 9, 9]
 [0, 0, 1, 8, 8]
 [0, 1, 3, 4, 8]
 [0, 2, 5, 7, 8]]

[[0, 0, 0, 0, 0]
 [0, 0, 8, 8, 8]
 [0, 0, 0, 7, 7]
 [0, 1, 2, 3, 7]
 [0, 2, 4, 6, 7]]

[[0, 0, 0, 0, 0]
 [0, 0, 8, 8, 8]
 [0, 0, 0, 7, 7]
 [0, 0, 1, 2, 6]
 [0, 1, 3, 5, 6]]

[[0, 0, 0, 0, 0]
 [0, 0, 7, 7, 7]
 [0, 0, 0, 7, 7]
 [0, 0, 0, 1, 5]
 [0, 1, 2, 4, 5]]

[[0, 0, 0, 0, 0]
 [0, 0, 7, 6, 6]
 [0, 0, 0, 6, 6]
 [0, 0, 0, 0, 4]
 [0, 1, 2, 3, 4]]

```

So, the number of times step 5 can be executed can be as big as $\frac12(n-2)(n-1)$.

# Answer
> 0 votes
It is at least easy to see that it must end after $O(n^2)$ iterations.

Let $r$ be the row containing the smallest uncovered element. Each time you execute step 5, at least one positive element of $r$ becomes zero, while covered zero elements of $r$ remain zero (since you add back what you subtracted). Also, by construction there cannot be uncovered zero elements in $r$. Hence the number of zero elements in $r$ increases by one. This can happen $n$ times for each row.

For the $O(n)$ bound, I think one should be able to prove that the number of minimal lines required to cover the zeros increases by at least one at each step. However the proofs I know are typically based on a different presentation of the algorithm, see for example: Golin, M. Bipartite Matching & the Hungarian Method.

---
Tags: optimization, runtime-analysis, matching
---