# Question
Title: Isomorphisms between regular graphs of same degree
Are all $n$-vertex regular graphs of degree $d$ isomorphic?

Can someone provide an example of two non-isomorphic graphs $G\_1$ and $G\_2$ which are both regular with degree $d$ and have the same number of vertices (i.e., $|G\_1| = |G\_2|$)?

# Answer
> 5 votes
Playing around with a pencil and paper for a few minutes, it should be easy to come up with non-isomorphic $d$-regular graphs with the same number of vertices, for small $d$. For example, take two cycles of length $2n$ and connect chords across them in different ways.

However, there is a polynomial-time isomorphism algorithm for any class of graphs of bounded degree, which includes the $d$-regular graphs for any fixed $d$. It's due to Luks (*Isomorphism of graphs of bounded valence can be tested in polynomial time*, *Journal of Computer and System Sciences* 25(1):42–65, 1982) and uses a bunch of group theory.

# Answer
> 5 votes
**Of course not.**

Consider, for example, the cycle $C\_6$ with six vertices and the graph obtained by the union of two copies of $C\_3$. Then both are 2-regular, but they are obviously not isomorphic.

This is also the case if we restrict the question to connected graphs. Consider, for instance, the following two 3-regular graphs:

You can see they are not isomorphic because the second one contains cycles with six vertices that have chords; this is impossible in the first graph since it has precisely four six-cycles and you can see none of them have chords. (Or even easier: The second one has a five cycle, whereas the first one has only cycles with three, four, six, or more vertices.)

What you might be able to prove is that all *2-regular and connected* graphs are isomorphic (see, e.g., this), but this is a big restriction compared to the original question.

---
Tags: graphs, graph-isomorphism
---


# Question
Title: Get all factors of a word in linear time or constant time
I have the following problem :

I have an algorithm which takes a word $w$ as entry. The problem is that my algorithm is doing a lot of things on the factors of $w$ and I am representing $w$ as an array of char. So if I want to get the factor $w\_i...w\_j$ of $w$ I need to do a loop that begin at $i$ all the way to up $j$., so it basically takes$O(j-i)$ times. Yet I am doing this operation on a lot of couples $(i,j)$ so at the end it becomes heavy in time complexity.

So one idea is to first calculate all factors of $w$ and put them in a double array of size $\mid w \mid^2$, I guess it takes $O(\mid w \mid^2)$ to fill this array.

Now I am wondering if we can improve this complexity ? Like for example get all factors of $w$ in linear time ? Maybe it's possible to use at first a different data structures to stack $w$ (so not array) that will allowed me to get any factors of $w$ in constant time ?

Thank you !

# Answer
> 1 votes
No, there's no faster way to calculate all the "factors" (substrings) of $w$. It takes $\Theta(|w|^2)$ space even to write down the list of all factors. Any algorithm has to spend at least 1 unit of time per character of output. So, any algorithm will have to take $\Omega(|w|^2)$ time; you can't do better than $O(|w|^2)$ time.

If you want to look for a faster algorithm, you'll need to look for a way to do it that doesn't involve calculating and storing all possible factors. You might want to think about what operations you need to perform on these factors, and whether there's any data structure that can help you perform those operations faster (maybe a Merkle hash tree? maybe a rolling hash? hard to know, without knowing what you're trying to do with the factors).

---
Tags: algorithms, word-combinatorics
---


# Question
Title: optimal flow for index multiple source and destination in directed graph
I am facing the similar problem to max flow in multiple source-destination directed graph (which has a familiar solution of connecting all the sources to one source and the same for the destination, and solving it with some algorithms like Ford-Fulkerson), but the difference in my problem is that :

1. all edges has capacity of 1 (the flow is discrete so once an edge is used - it can't be used again)
2. each source need to flow to a specific destination (e.g. $v\_1$ needs to flow to sink $u\_1$ \- other sinks can't consume $v\_1$ flow).

I need to find the max sources that can reach to their destination on a given graph. Is there a solution for this or I have to compute all the possiblities ?

# Answer
> 1 votes
This is an instance of a multi-commodity flow problem. Unfortunately the problem is NP-hard (even when all edge capacities are 1).

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


# Question
Title: Measuring the Probability of Error for a Potential BPP Algorithm
# Problem

Given a search algorithm that can be used to query a *k-dimensional space*, produced from an *input array of N data*, has a time complexity of $O(klog^2N)$. This algorithm partitions the space into four regions then selects three of those regions due to some condition. From there it selects at random one of the three spaces as the next space to check for the answer. If this algorithm produces a value it is 100% the correct solution, else it states it cannot find the solution which is always wrong because the item being searched is always there. Therein, the theory is to run it a bunch of times until it produces the solution.

# Question

I created this algorithm which is to be utilized as an experiment to create a *BPP* algorithm for a data analysis problem. But, I am uncertain if it qualifies as a *BPP* algorithm. From my understanding it is not, because it has a one in three chance of selecting the correct partition at each time it partitions the space. This means the probability of selecting the correct solution is $(1/3)^{klogN}$ making the probability of selecting the incorrect solution one minus the probability of the correct solution.

So, my question is A) Is my interpretation correct for measuring the probability? B) Does this algorithm qualify as a *BPP* algorithm or some other class?

# Answer
> 2 votes
The class BPP (and related classes such as RP, coRP, and ZPP) deal with *decision problems*. This means the algorithms corresponding to these classes may only produce "yes" or "no" answers. This notion does not quite match your algorithm, which is actually solving a *search problem* (i.e., the solution set is a subset of some arbitrary set of outputs).

At any rate, what you are actually trying to refer to as a "BPP algorithm" is a randomized algorithm with *two-sided error*. Such an algorithm produces correct and incorrect answers for both instances that have and do not have a solution, and, usually, it is also required that the algorithm be correct "most of the time" (where this is defined by bounding the error by some probability constant).

However, your algorithm has not actually two-sided nor one-sided error. This is because your problem instances *all* have solutions (and your algorithm does not claim otherwise). Thus, your algorithm only really *fails to find* solutions with some probability, which makes it have *zero-sided error*, that is, it always outputs correct answers, but may also output a "could not find" or "don't know" answer (with some bounded probability). As a result, what you have is a Las Vegas algorithm, which is a type of probabilistic algorithm with applications well beyond complexity theory. Incidentally, the alternative definition for a Las Vegas algorithm (i.e., a probabilistic algorithm with *expected* polynomial time complexity) is quite consistent with your remark that you need to run your algorithm "a bunch of times until it produces the solution."

On a side note, the complexity class associated with decision problems solvable with zero-sided error probabilistic TMs is the class ZPP (though this is only tangential to your question since, as I have explained above, you are not working in the realm of decision problems anyway).

# Answer
> 1 votes
The definition of BPP is that the algorithm always runs and finishes in polynomial time, and the probability it makes an error is $\le 1/3$. So, apply that to your algorithm. You told us it completes in polynomial time, so it meets that condition. Next you must figure out if the error probability is at most $1/3$. If your algorithm runs the search process once, the answer is no: the error probability is $2/3$, which is too large. However, if your algorithm repeats the search process three times and output the first value it finds, then the probability it makes an error is $(2/3)^3 \approx 0.296 \le 1/3$, so repeating it three times gives you an algorithm that *is* in BPP. (Of course, if you repeat three times, the running time will still be polynomial.)

Strictly speaking BPP only applies to decision problems, that check whether the input is a member of a language or not, and your problem isn't phrased in those terms. However your situation is close enough that if you said "my algorithm is in BPP" theorists would understand what you meant.

---
Tags: time-complexity, search-algorithms, randomized-algorithms
---


# Question
Title: Doing matrix multiplication with $\lceil n^3 / \log n \rceil$ processors in $2\log n$ steps by Brent's principle
On a parallel machine with $n$ processors we can compute the sum (or product, or the result of any associative operation) on $n$ numbers in $\log n$ steps. In the first step combine neighbors to get $n/2$ numbers left, then combine them so that $n/4$ numbers are left and so on until a single number, the result, is left which happens after $\lceil \log n \rceil$ steps. With this is it obvious that we can compute the matrix product of two $n \times n$ matrices $A = (A\_{ij}), B = (B\_{ij})$ with $n^3$ processors in $\log n + 1$ steps, in a first step compute all the $n^3$ products of the entries $A\_{ik} \cdot B\_{kj}$ for $i,j,k \in \\{1,\ldots, n\\}$. Then with $n^2$ processors compute the $n^2$ sums of the $n$ numbers $A\_{i1}\cdot B\_{1j} + \ldots + A\_{ik}\cdot B\_{kj}$. Hence we get by with $1 + \log n$ parallel steps.

Now the following argument is from C. Papadimitriou, *Computational Complexity*, page 361, to show that we get time $2\log n$ using just $n^2 / \log n$ processors (the argument used is called *Brent's principle* according to the book).

> We compute the $n^3$ products not in a single step as before, but rather in $\log n$ ''shifts'' using $\lceil n^3 / \log \rceil$ processors at each shift. We use shifts of the same $\lceil n^3 / \log n \rceil$ processors to compute the first $\log \log n$ parallel addition steps, where more than $\frac{n^3}{\log n}$ processors would be ordinary needed. The total number of parallel steps is now no more than $2\log n$, with $\frac{n^3}{\log n}$ processors \[...\].

(those arguments could also be found on these slides).

But I get more parallel steps as $2\log n$.

1) First we compute the $n^3$ products $A\_{ik}\cdot B\_{kj}$ with $\log n$ shifts, hence we need $\log n$ parallel steps for this.

2) If we combine the results as written in the introduction, then in the $k$-th step we have $n/2^k$ numbers to combine. Hence if $2^k \< \log n$ we do not have enough processors to do this in a single step, hence we have to ''shift'' again, this time $\lceil \log n / 2^k \rceil$ times. If $2^k \ge \log n$ we can use a single parallel step as we have enough processors at hand.

Combining the above reasoning we get the following equation (I omit the rounding) for the number of parallel steps: $$ \log n + \sum\_{k=1}^{\log \log n} \frac{\log n}{2^k} + \log n - \log \log n. $$ The first summand commes from the shift over the $n^3$ numbers, the second summand for the shifts needed if in the combination/summation of the product we still have to many numbers for our processors, and the last for the number of steps if we do have enough processors. This equals \begin{align\*} & \log n + \log n \left( 1 - \frac{1}{2^{\log \log n}} \right) + \log n - \log \log n \\ & = \log n + \log n - 1 + \log n - \log \log n \\ & = 3 \log n - \log \log n - 1 \end{align\*} The last is in general more than $2\log n$, so what am I missing. Why does they argue they get by with $2\log n$ steps. Do I miss anything here?

# Answer
Yes, you are correct while all textbooks and lecture notes you and I have found so far are wrong in claiming "doing matrix multiplication with $\lceil n^3 / \log n \rceil$ processors in at most $2\log n$ steps by Brent's principle"

There is hardly anything valuable to add to your meticulous calculation. Anyway, here is an example that specializes your calculation.

### An example

Let $n=16$. We have two $16\times16$ matrices, $(A\_{ij})$ and $(B\_{ij})$ with $\left\lceil \dfrac{n^3}{\log\_2n}\right\rceil=\left\lceil\dfrac{16^3}{\log\_2 16}\right\rceil=1024$ processors.

It takes 4 parallel steps to compute all the $n^3=4096$ products of the entries $P\_{ijk}=A\_{ik} \cdot B\_{kj}$ for $i,j,k \in \\{1,2,\cdots,16\\}$ with $1024$ processors.

How to compute $n^2=256$ sums of the $n=16$ numbers $P\_{i1j}+ \ldots + P\_{i16j}$ for $i,j\in\\{1,2,\cdots,16\\}$?

We first compute $256\times 8=2024$ sums of two neighbors $S\_{ikj}=P\_{i(2k-1)j}+P\_{i(2k)j}$ for $i,j\in\\{1,2,\cdots,16\\}$, $k\in\\{1,2,\cdots, 8\\}$. It takes 2 parallel steps for 1024 processors, where $2$ is $\dfrac{\dfrac{n^3}2}{\dfrac{n^3}{\log\_2n}}=\dfrac{\log\_2n}2\>1$.

There are $256 \times 4 = 1024$, $256 \times 2 = 512$, $256 \times 1 = 256$ sums of two numbers to calculate, respectively. Each of them will take one parallel step because of the serial dependency. We need $3 =\log\_2n-1$ parallel steps.

So we need $4 + 2 + 3 = 9$ parallel steps in total, which is bigger than $\lceil 2\log\_2 n\rceil = 8$.

### Corrected statement

Multiplication of two $n\times n$ matrices can be done in no more than $3\log\_2 n+1$ parallel steps with $\lceil n^3 / \log\_2 n \rceil$ processors by Brent's principle.

### Brent's principle

Here is one version of Brent's principle that applies to current situation.

**(Brent’s principle)**: An algorithm involving $t$ time steps and performing a total of $m$ operations can be executed by $p$ processors in no more than $t + \lceil(m – t) / p\rceil$ time steps in PRAM.

In particular, we have $m=n^3+ n^2(n-1)$ operations and $t=1+\lceil \log\_2n\rceil$ time steps for matrix multiplication. If we have $p=\lceil n^3 / \log\_2 n \rceil$ processors, the upper limit of parallel steps given by Brent's principle, $t + \lceil(m – t) / p\rceil$ is $3\lceil\log\_2 n\rceil-1$ or $3\lceil\log\_2 n\rceil$ or $3\lceil\log\_2 n\rceil+1$.
> 2 votes

---
Tags: complexity-theory, computation-models, parallel-computing
---


title: Short Fibonacci Heap

text:
# Question
Title: Short Fibonacci Heap
Is it possible to create a Fibonacci Heap that has exactly 5 nodes: one root node and 4 children of that root?. If yes please explain the sequence of operations to do so. If it is not possible then why?

I faced this question in an interview but couldn't answer it. Hopefully can learn it from here.

# Answer
> 1 votes
Corollary 1 in Fredman & Tarjan's paper states:

> A node of rank $k$ in an F-heap has at least $F\_{k+2} \ge \phi^k$ descendants, including itself; where $F\_k$ is the $k$th Fibonacci number ($F\_0 = 0$, $F\_1 = 1$, $F\_k = F\_{k-2} + F\_{k-1}$ for $k \ge 2$), and $\phi = (1 + \sqrt{5})/2$ is the golden ratio.

Any node of rank 4 must have at least $F\_{4+2} = 8$ descendants including itself, but the root node in the example has only 5. Therefore it could not have been created using Fibonacci heap operations.

---
Tags: data-structures, heaps, priority-queues
---


# Question
Title: How many iterations does the Bellman-Ford algorithm need for directed and undirected graphs
The Bellman-Ford algorithm on a graph with $n$ vertices, normally includes a loop executed $n-1$ times. Each time through the loop we iterate over the list of edges $(u,v)$ and relax $v$. Note that we don't relax $u$ and $v$ on each iteration through the edges.

What I don't understand is that if $G$ is an undirected graph with $n$ vertices, then it is equivalent to a directed graph with $2n$ vertices. We simply think of the edge between $u$ and $v$ as a set $\\{u,v\\}$ for an undirected graph, and as the ordered pair $(u,v)$ for a directed graph.

I don't understand why the Bellman-Ford algorithm needs only $n-1$ repetitions for both a directed and undirected graph. It seems like it should take $n-1$ repetitions for directed graph, and $2n-1$ repetitions for undirected graphs or we should relax both vertices of an edge on each iteration.

Otherwise stated, why does running Bellman-Ford on a directed graph, also find the shortest paths of the undirected graphs?

# Answer
The Bellman-Ford algorithm only needs $n-1$ iterations, regardless of the number of edges. The number of iterations needed depends only on the number of vertices, not on the number of edges.

When you talk about converting a directed graph to an undirected graph, that conversion increases the number of edges but does not change the number of vertices. Thus, it doesn't change the number of iterations needed for the Bellman-Ford algorithm.
> 2 votes

# Answer
The Bellman-Ford algorithm does not work on undirected graphs with negative weights, because $(u,v)$ and $(v,u)$ are not allowed on the same path, but the Bellman-Ford algorithm does not handle this constraint. In fact, if the weight of $(u,v)$ is negative, $(u,v)$ and $(v,u)$ form a negative cycle.

If your weights are all non-negative (which is possibly your case according to your comment), the Bellman-Ford algorithm can work on undirected graph. The reason why it requires only $n-1$ iterations is explained in D.W.'s answer. However, you may want to take the advantage of non-negative weights and use some more efficient algorithm (like Dijkstra's algorithm).

Otherwise you can use the technique of T-joins or perfect matching.
> 3 votes

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


# Question
Title: In-place algorithm for interleaving an array
You are given an array of $2n$ elements

$$a\_1, a\_2, \dots, a\_n, b\_1, b\_2, \dots b\_n$$

The task is to interleave the array, using an in-place algorithm such that the resulting array looks like

$$b\_1, a\_1, b\_2, a\_2, \dots , b\_n, a\_n$$

If the in-place requirement wasn't there, we could easily create a new array and copy elements giving an $\mathcal{O}(n)$ time algorithm.

With the in-place requirement, a divide and conquer algorithm bumps up the algorithm to be $\theta(n \log n)$.

So the question is:

> Is there an $\mathcal{O}(n)$ time algorithm, which is also in-place?

(Note: You can assume the uniform cost WORD RAM model, so in-place translates to $\mathcal{O}(1)$ space restriction).

# Answer
> 48 votes
Here is the answer which elaborates upon the algorithm from the paper linked by Joe: http://arxiv.org/abs/0805.1598

First let us consider a $\Theta(n \log n)$ algorithm which uses divide and conquer.

**1) Divide and Conquer**

We are given

$$a\_1, a\_2, \dots , b\_1, b\_2, \dots b\_n$$

Now to use divide and conquer, for some $m = \Theta(n)$, we try to get the array

$$ \[a\_1, a\_2, \dots , a\_m, b\_1, b\_2, \dots, b\_m\], \[a\_{m+1}, \dots, a\_n, b\_{m+1}, \dots b\_n\]$$

and recurse.

Notice that the portion $$ b\_1 , b\_2, \dots b\_m, a\_{m+1}, \dots a\_n$$ is a cyclic shift of

$$ a\_{m+1}, \dots a\_n, b\_1 , \dots b\_m$$

by $m$ places.

This is a classic and can be done in-place by three reversals and in $\mathcal{O}(n)$ time.

Thus the divide and conquer gives you a $\Theta(n \log n)$ algorithm, with a recursion similar to $T(n) = 2T(n/2) + \Theta(n)$.

**2) Permutation Cycles**

Now, another approach to the problem is the consider the permutation as a set of disjoint cycles.

The permutation is given by (assuming starting at $1$)

$$ j \mapsto 2j \mod 2n+1$$

If we somehow knew exactly what the cycles were, using constant extra space, we could realize the permutation by picking an element $A$, determine where that element goes (using the above formula), put the element in the target location into temporary space, put the element $A$ into that target location and continue along the cycle. Once we are done with one cycle we move onto an element of the next cycle and follow that cycle and so on.

This would give us an $\mathcal{O}(n)$ time algorithm, but it assumes that we "somehow knew what the exact cycles were" and trying to do this book-keeping within the $\mathcal{O}(1)$ space limitation is what makes this problem hard.

This is where the paper uses number theory.

It can be shown that, in the case when $2n + 1 = 3^k$, the elements at positions $1$, $3, 3^2, \dots, 3^{k-1}$ are in different cycles and every cycle contains an element at the position $3^m, m \ge 0$.

This uses the fact that $2$ is a generator of $(\mathbb{Z}/3^k)^\*$.

Thus when $2n+1 = 3^k$, the follow the cycle approach gives us an $\mathcal{O}(n)$ time algorithm, as for each cycle, we know exactly where to begin: powers of $3$ (including $1$) (those can be computed in $\mathcal{O}(1)$ space).

**3) Final Algorithm**

Now we combine the above two: Divide and Conquer + Permutation Cycles.

We do a divide and conquer, but pick $m$ so that $2m+1$ is a power of $3$ and $m = \Theta(n)$.

So instead on recursing on both "halves", we recurse on only one and do $\Theta(n)$ extra work.

This gives us the recurrence $T(n) = T(cn) + \Theta(n)$ (for some $0 \lt c \lt 1$) and thus gives us an $\mathcal{O}(n)$ time, $\mathcal{O}(1)$ space algorithm!

# Answer
> 18 votes
I'm pretty sure I've found an algorithm that does not rely on number theory or cycle theory. Note that there are a few details to work out (possibly tomorrow), but I'm quite confident they will work out. I handwave as I'm supposed to be sleeping, not because I'm trying to hide problems :)

Let `A` be the first array, `B` the second, `|A| = |B| = N` and assume `N=2^k` for some `k`, for simplicity. Let `A[i..j]` be the subarray of `A` with indices `i` through to `j`, inclusive. Arrays are 0-based. Let `RightmostBitPos(i)` return the (0-based) position of the rightmost bit that is '1' of `i`, counting from the right. The algorithm works as follows.

```
GetIndex(i) {
    int rightPos = RightmostBitPos(i) + 1;
    return i >> rightPos;
}

Interleave(A, B, N) {
    if (n == 1) {
        swap(a[0], b[0]);
    }
    else {
        for (i = 0; i < N; i++)
            swap(A[i], B[GetIndex(i+1)]);

        for (i = 1; i <= N/2; i*=2)
            Interleave(B[0..i/2-1], B[i/2..i-1], i/2);

        Interleave(B[0..N/2], B[N/2+1..N], n/2);
    }
}

```

Let's take an array of 16 numbers, and let's just start interleaving them using swaps, and see what happens:

```
1 2 3 4 5 6 7 8    | 9 10 11 12 13 14 15 16
9 2 3 4 5 6 7 8    | 1 10 11 12 13 14 15 16
9 1 3 4 5 6 7 8    | 2 10 11 12 13 14 15 16
9 1 10 4 5 6 7 8   | 2 3 11 12 13 14 15 16
9 1 10 2 5 6 7 8   | 4 3 11 12 13 14 15 16
9 1 10 2 11 6 7 8  | 4 3 5 12 13 14 15 16
9 1 10 2 11 3 7 8  | 4 6 5 12 13 14 15 16
9 1 10 2 11 3 12 8 | 4 6 5 7 13 14 15 16
9 1 10 2 11 3 12 4 | 8 6 5 7 13 14 15 16

```

Of particular interest is the first part of the second array:

```
|
| 1
| 2
| 2 3
| 4 3
| 4 3 5
| 4 6 5
| 4 6 5 7
| 8 6 5 7

```

The pattern should be clear: we alternately add a number to the end and replace the lowest number by a high number. Note that we always add a number that is one higher than the highest number we already have. If we were somehow able to figure out exactly which number is the lowest at any given time, we can do that easily.

Now, we go for bigger examples to see if we can see a pattern. Note that we don't need to fix the size of the array to construct the above example. At some point, we get this configuration (the second line subtracts 16 from every number):

```
16 24 20 28 18 22 26 30 17 19 21 23 25 27 29 31
0   8  4 12  2  6 10 14  1  3  5  7  9 11 13 15

```

Now this clearly shows a pattern: "1 3 5 7 9 11 13 15" are all 2 apart, "2 6 10 14" are all 4 apart and "4 12" are 8 apart. We can therefore devise an algorithm that tells us what the next smallest number will be: the mechanism is pretty much exactly how binary numbers work. You have a bit for the last half of the array, a bit for the second quarter, and so on.

If we are therefore allowed enough space to store these bits (we need $\log n$ bits, but our computational model allows this - a pointer into the array also needs $\log n$ bits), we can figure out which number to swap in $O(1)$ time amortized.

We can therefore get the first half of the array into its interleaved state in $O(n)$ time and $O(n)$ swaps. However, we do have to fix the second half of our array, which seems all messed up ("8 6 5 7 13 14 15 16").

Now, if we can 'sort' the first half of this second part, we end up with "5 6 7 8 13 14 15 16", and recursively interleaving this half will do the trick: we interleave the array in $O(n)$ time ($O(\log n)$ recursive calls each of which halve the input size). Note we don't need a stack as these calls are tail recursive, so our space usage remains $O(1)$.

Now, the question is: is there some pattern in the part we need to sort? Trying 32 numbers gives us "16 12 10 14 9 11 13 15" to fix up. Note that we have the exact same pattern here! "9 11 13 15", "10 14" and "12" are grouped together in the same fashion we saw earlier.

Now, the trick is to recursively interleave these subparts. We interleave "16" and "12" to "12 16". We interleave "12 16" and "10 14" to "10 12 14 16". We interleave "10 12 14 16" and "9 11 13 15" to "9 10 11 12 13 14 15 16". This sorts the first part.

Just like above, the total cost of this operation is $O(n)$. Adding all of these up, we still manage to get a total running time of $O(n)$.

An example:

```
Interleave the first half:
1 2 3 4 5 6 7 8    | 9 10 11 12 13 14 15 16
9 2 3 4 5 6 7 8    | 1 10 11 12 13 14 15 16
9 1 3 4 5 6 7 8    | 2 10 11 12 13 14 15 16
9 1 10 4 5 6 7 8   | 2 3 11 12 13 14 15 16
9 1 10 2 5 6 7 8   | 4 3 11 12 13 14 15 16
9 1 10 2 11 6 7 8  | 4 3 5 12 13 14 15 16
9 1 10 2 11 3 7 8  | 4 6 5 12 13 14 15 16
9 1 10 2 11 3 12 8 | 4 6 5 7 13 14 15 16
9 1 10 2 11 3 12 4 | 8 6 5 7 13 14 15 16
Sort out the first part of the second array (recursion not explicit):
8 6 5 7 13 14 15 16
6 8 5 7 13 14 15 16
5 8 6 7 13 14 15 16
5 6 8 7 13 14 15 16
5 6 7 8 13 14 15 16
Interleave again:
5 6 7 8   | 13 14 15 16
13 6 7 8  | 5 14 15 16
13 5 7 8  | 6 14 15 16
13 5 14 8 | 6 7 15 16
13 5 14 6 | 8 7 15 16
Sort out the first part of the second array:
8 7 15 16
7 8 15 16
Interleave again:
7 8 | 15 16
15 8 | 7 16
15 7 | 8 16
Interleave again:
8 16
16 8
Merge all the above:
9 1 10 2 11 3 12 4 | 13 5 14 6 | 15 7 | 16 8

```

# Answer
> 3 votes
Here is a non-recursive in-place in linear time algorithm to interleave two halves of an array with no extra storage.

The general idea is simple: Walk through the first half of the array from left to right, swapping the correct values into place. As you advance, the yet to be used left values get swapped into the space vacated by the right values. The only trick is figuring out how to pull them out again.

We start with an array of size N split into 2 nearly equal halves.
`[ left_items | right_items ]`
As we process it, it becomes
`[ placed_items | remaining_left_items| swapped_left_items | remaining_right_items]`

The swap space grows with the following pattern: A) grow the space by removing the adjacent right item and swapping in a new item from the left; B) swap the oldest item with a new item from the left. If the left items are numbered 1..N, this pattern looks like

```
step swapspace index changed
1    A: 1         0
2    B: 2         0
3    A: 2 3       1
4    B: 4 3       0
5    A: 4 3 5     2
6    B: 4 6 5     1
7    A: 4 6 5 7   3
...

```

The sequence of which index changed is exactly OEIS A025480, which can be calculated with a simple process. This allows the swap location to be found given only the number of items added so far, which is also the index of the current item being placed.

That's all the info we need to populate the 1st half of the sequence in linear time.

When we get to the midpoint, the array will have three parts: `[ placed_items | swapped_left_items | remaining_right_items]` If we can unscramble the swapped items, we have reduced the problem to half the size, and can repeat.

To unscramble the swap space, we use the following property: A sequence built by `N` alternating append and swap\_oldest operations will contain `N/2` items where their ages are given by `A025480(N/2)..A025480(N-1)`. *(Integer division, smaller values are older).*

For example, if the left half originally held the values 1..19, then the swap space would contain `[16, 12, 10, 14, 18, 11, 13, 15, 17, 19]`. A025480(9..18) is `[2, 5, 1, 6, 3, 7, 0, 8, 4, 9]`, which is exactly the list of indexes of the items from oldest to newest.

So we can unscramble our swap space by advancing through it and swapping `S[i]` with `S[ A(N/2 + i)]`. This is also linear time.

The remaining complication is that eventually you will reach a position where the correct value should be at a lower index, but it has already been swapped out. It is easy to find the new location: just do the index calculation again to discover where the item was swapped to. It may be necessary to follow the chain a few steps until you find an unswapped location.

At this point, we have merged half the array, and maintained the order of the unmerged parts in the other half, with exactly `N/2 + N/4` swaps. We can continue through the rest of the array for a total of `N + N/4 + N/8 + ....` swaps which is strictly less than `3N/2`.

*How to calculate A025480:*
This is defined in OEIS as `a(2n) = n, a(2n+1) = a(n).` An alternate formulation is`a(n) = isEven(n)? n/2 : a((n-1)/2)`. This leads to a simple algorithm using bitwise operations:

```
index_t a025480(index_t n){
    while (n&1) n=n>>1;
    return n>>1;
}

```

This is an amortized O(1) operation over all possible values for N. *(1/2 need 1 shift, 1/4 need 2, 1/8 need 3, ...)*. There is an even faster method which uses a small lookup table to find the position of the least significant zero bit.

Given that, here's an implementation in C:

```
static inline index_t larger_half(index_t sz) {return sz - (sz / 2); }
static inline bool is_even(index_t i) { return ((i & 1) ^ 1); }

index_t unshuffle_item(index_t j, index_t sz)
{
  index_t i = j;
  do {
    i = a025480(sz / 2 + i);
  }
  while (i < j);
  return i;
}

void interleave(value_t a[], index_t n_items)
{
  index_t i = 0;
  index_t midpt = larger_half(n_items);
  while (i < n_items - 1) {

    //for out-shuffle, the left item is at an even index
    if (is_even(i)) { i++; }
    index_t base = i;

    //emplace left half.
    for (; i < midpt; i++) {
      index_t j = a025480(i - base);
      SWAP(a + i, a + midpt + j);
    }

    //unscramble swapped items
    index_t swap_ct  = larger_half(i - base);
    for (index_t j = 0; j + 1 < swap_ct ; j++) {
      index_t k = unshuffle_item(j, i - base);
      if (j != k) {
        SWAP(a + midpt + j, a + midpt + k);
      }
    }
    midpt += swap_ct;
  }
}

```

This should be a fairly cache-friendly algorithm, since 2 of the 3 data locations are accessed sequentially and the amount of data being processed is strictly decreasing. This method can be turned from an out-shuffle to an in-shuffle by negating the `is_even` test at the start of the loop.

---
Tags: algorithms, arrays, permutations, in-place
---


title: Counter Machine (Halting Problem)

text:
# Question
Title: Counter Machine (Halting Problem)
How can we show that Halting Problem for one-counter additive machines is decidable ?

# Answer
A simple way is the following:

Suppose that the increments are $+1, -1$; the number of states of the machine is $m$ and the current value of the counter is $n$.

You can notice that if the counter reaches $n+m+1$ without hitting the $0$, then by the pigeonhole principle the machine from value $n$ to $n+m+1$ has entered the same state $s\_i$ two times ($s\_i \to ... \to s\_i$), and the difference in the counter value is positive; so it will continue to repeat the same loop and increase the counter.

After hitting the $0$ \- for the same reason - if the counter reaches $m+1$ then the machine will never halt.

So it's enough to simulate the machine up to $m(n+m+1)$ steps; if it doesn't halt in that time it will never halt: it will loop forever on the same values $(s\_i,c\_j) \to ... \to (s\_i,c\_j)$ or increase forever the counter: $(s\_i,c\_j) \to ...\to (s\_i,c\_k) \to ...;\\; c\_k \> c\_j+m$ .

If the increments are $\pm v, v \in \[1,h\]$ then the machine can be reduced to an equivalent one with $\pm 1$ increments.
> 2 votes

---
Tags: turing-machines, automata, halting-problem
---


# Question
Title: Can we create recursive functions only by using if-else statements?
I have to show whether a program containing only *if-else* statements but no loops is able to calculate the following type of functions: $f^n(x)$. The function $f$ is applied $n$ times to $x$, so I guess this is a recursive function.

How can I prove that formally?

# Answer
If a program doesn't include any loop, recursion or equivalent construct, then it cannot express recursive computations.

In order to write a formal proof, you'd need to define your language formally. “Equivalent construct” can include some exotic things such as parallel execution, exception handlers, higher-order functions (leading to fixpoint combinators), meta-execution facilities (`eval`), etc. that let recursion in through a backdoor.

Suppose that a language contains only the following constructs: constants, assignments, sequence (do a then do b), functions operating on base types (but not functions taking functions as arguments), conditionals (`if (x == y)`), some primitives on base types (e.g. `+`, `*`). Then the execution of the program takes a time that is at most exponential, and in particular bounded, in the size of the program (the unit of time is an elementary expression, e.g. `x := y` takes one unit, `x := y + z` takes two units). In a nutshell, function application at most multiplies the complexity of the function by the complexity of the program, and the rest is linear.

Since this language can only express bounded-time computations, it cannot express all recursive programs (and in fact it cannot even express all primitive recursive programs).
> 5 votes

# Answer
IMHO the cleanest way to have a recursive calculation function is to ONLY use a if-else. Since there are usually only two main conditions in a recursive function( 1 - base case met, 2 - base case not met) it is only logical to only have two condition checks. The **if** checks for the base case, if the base case has not been reached **else** does calculations and sends the new recursive call. Below is some pseudo code for a recursive function for the example you provided.

```
int recursiveFunction(int n,int x)
{
    if(n==1)
    {
       return x;
    }
    else
    {
       x=x*x//or whatever work is being done
       return (n-1,x);
    }
}

```
> 2 votes

# Answer
I'm not sure entirely what you mean. Are you allowed method invocations? If so you can provide this example:

```
def apply_multiple(f, x, n):
  if n == 0:
    return x
  else:
    return f(apply_multiple(f, x, n-1))

```

If you're talking about writing that particular function without ANY flow control other than if statements, you can't. Consider the line number you're currently on. This can only increase, so for a finite program there are only a finite number of states it can be in. This isn't going to work if n can be an arbitrary number.
> 2 votes

# Answer
In Elixir, this would be as easy as

```
def nthApply(f, x, n) do
  if n < 1 do
    x
  else
    nthApply(f, f.(x), n-1)
  end
end

```
> -2 votes

---
Tags: recursion, semantics
---


# Question
Title: Create a grammar that generate the language a^n . b^m . c^q . d^p such that n + p = q + m
I'm stuck on this question. I'm struggling on how to keep track of the number of a and d I have generated.

The professor hasn't given the correction.

I have seen similar questions but the condition is different, I can't find the grammar. Is it possible to prove that it is not context free?

EDIT: taking inspiration from other slightly similar solved question, here's my solution, but I think it could be factorized/improved

```
S -> S1 | S2
// S1 is the case where I will try to pair a with c (i.e when there more c than d), S2 is the case where I will try to pair d with b (i.e when there are more b than a)
S1 -> XY
X -> aXc | Z // for each a generate a c
Z -> aZb | epsilon // for each a generate a b
Y -> cYd | epsilon // for each d generate c
// since all the b's have been generated along with a's, i did not find a way to pair d's with b's
S2 -> UV
U -> aUb | epsilon
V -> bVd | W
W -> cWd | epislon

```

# Answer
> 4 votes
Note if $n\<m$, we can write $a^nb^mc^qd^p$ as $a^nb^nb^xc^qd^{x+q}$ where $n,x,q$ are independent of each other. Otherwise, we can write $a^nb^mc^qd^p$ as $a^{m+y}b^mc^yc^pd^p$ where $m,y,p$ are independent of each other.

So the grammar can be $S\rightarrow S\_1S\_2\mid S\_3S\_4$, where $S\_1$ generates $a^nb^n$, $S\_2$ generates $b^xc^qd^{x+q}$, $S\_3$ generates $a^{m+y}b^mc^y$, and $S\_4$ generates $c^pd^p$. They are all easy to construct.

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


# Question
Title: DFA which accepts all strings starting and ending with 'aa'
I have to construct a DFA which accepts set of all strings over {a,b} which start and end with 'aa'. I have constructed the following DFA, but it does not accept 'aa' and 'aaa'. How can I make it accept all strings in the language.

# Answer
> 2 votes
One solution could be putting the final state right after the first two states. From there, if an $a$ is read you stay in the final state, otherwise you move to a state analogous to $q\_2$; from there, with two $a$s you return to the final state and with a $b$ you go back to $q\_2$.

In short, just picture ($q\_1, a$) going to $q\_4$ instead of $q\_2$. The rest should go unchanged.

This way, the automata should accept strings such as 'aa', 'aaa' and so on. And of course if it reads a 'b' it'll need two more 'a's to return to the final state.

# Answer
> 1 votes
It will accept all string starting and ending with aa including aa and aaa. First , it should start with aa.So,we want the machine to remember 'aa'.Anything other than this should go to trap state (qt). That we have done in first two states. If nothing is there after this,the string is in accepted state.

After two consecutive a, if another a comes ,it should remain in final state and if b comes it should come out of final state(q2--\>b=q3).

Now if another b encounters ,it should loop in same state that is not final state(since we need string ending with aa only).

And if 'a' comes ,again we want the machine to remember 'a'(for this we need new state) so that we can check for next alphabet and if another 'a' comes,it should go back to final state and if not go to q3.

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


# Question
Title: Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time
In this proof of the Space Hierarchy Theorem the following language is defined $$ L = \\{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\langle M \rangle, 10^k|) \\}. $$ And then stated:

> Now, for any machine $M$ that decides a language in space $o(f(n))$, $L$ will differ in at least one spot from the language of $M$. Namely, for some large enough $k$, $M$ will use space $\le f(|\langle M \rangle|, 10^k|)$ on $(\langle M \rangle, 10^k)$ and will therefore differ at its value.

I get the diagonalization argument, but what makes me wonder according to the linear speed up theorem for space we have \[see for example Hopcroft/Ullman, 71\]:

> If $L$ is accepted by an $S(n)$ space-bounded Turing machine with $k$ storage tapes, then for any $c \> 0$, $L$ is accepted by a $cS(n)$ space-bounded Turing machine.

As shown in the linked wikipedia article $L$ is accepted by a Turing machine using $f(n)$-bounded space, then by linear speed up $L$ is also accepted by some machine $M'$ using at most $\frac{f(n)}{2}$ tape cells. But then we get a contradiction on the inputs $(\langle M' \rangle, 10^k)$, as $M'$ accepts $L$ if $(\langle M' \rangle, 10^k)$ is accepted, then $(\langle M' \rangle, 10^k) \notin L$, contradiction, and similar for the case if it is not accepted. If $(\langle M' \rangle, 10^k)$ is not accepted by $M'$ then $(\langle M' \rangle, 10^k) \in L$ by definition of $L$, but $(\langle M' \rangle, 10^k) \notin L(M') = L$, a contradiction.

My reasoning seems to be fine, but it should not be... what am I missing here? In my argument, the problem is with the speed up and essentially it derives that if speed up is possible, then we can separate $f$ and $cf$ for $0 \< c \< 1$, i.e., speed up is not possible. The only valid conclusion would be that linear speed up is not possible, but that is certainly not true...

# Answer
> 5 votes
**The Wikipedia proof is bogus.**

As you have proven, the description for $L$ is incomplete. It should read: $$ L = \\{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } x = (\langle M \rangle, 10^k) \mbox{ using space } \le f(|x|) \\; \textbf{and time} \\; \le 2^{f(|x|)} \\} $$

This corrects the proof because now $M$ (or $M'$) can still accept $x = (\langle M \rangle, 10^k)$ and take space $\le f(|x|)$. Actually, $(\langle M \rangle, 10^k) \in L$ has a quite reasonable explanation in that $M$ attempts to simulate $M$, which (as a subroutine) attempts to simulate $M$ again, and so forth and so on, until eventually $2^{f(|x|)}$ steps elapse and the whole procedure is interrupted. Hence, $M$ does not accept $x$ using space $\le f(|x|)$ and time $\le 2^{f(|x|)}$, *although it does accept it taking space* $\le f(|x|)$ (well, perhaps actually $O(f(|x|))$) *and time $\> 2^{f(|x|)}$*.

As a matter of fact, the purported algorithm for $L$ in the article explicitly states it runs its simulation with a $2^{f(|x|)}$ stopwatch. This is precisely the detail that is missing from the definition of $L$.

# Answer
> 4 votes
First the other answer by dkaeae seems to be perfectly fine regarding that every machine using $o(f)$ space also can get by with $o(2^{o(f)})$ time in the limit (by assumption the machines considered are deciders, hence halt, hence by counting configurations we have no configuration twice). And as we have an infinite of inputs $10^k$ for each machine, we can conclude that no such machine could accept the thus modified $L$. Also the modifications seems to suggest that if $M$ accepts $L$, on input $(\langle M \rangle, 10^k)$ it will need more than $2^{f(|(\langle M \rangle, 10^k)|)}$ time, or even for the machine $M'$ we got by the speed up theorem.

But still this seems somehow nebulous in the sense that why we surely need this blow up in time. The intuition "M applied to itself, applied to itself ..." seems to suggest this time blow up, and that the machine stops and reject inputs $(\langle M \rangle, 10^k)$ as written by dkaeae.

In this post I try to give a more formal reason by employing how machines simulate each other. It helped me in understanding the problem apart from the abstract reasoning as given above and so it might be worthwile to share it here.

Essentially it boilds down to the fact that Turing machines have no restriction on the working tape alphabet, and from this essentially the speed up theorem is derived. But in simulating other machines we always have a logarithmic blow up in the working size alphabet, and as we always have bigger working alphabet by the blank symbol as the input alphabet, if we code machines to be processed by other machines (or simulated) we have to code also the blank symbol by input symbols. This is inherent in the definition of machines we cannot get by with. For example also if we just restrict to the working tape symbols $\\{0,1,b\\}$ and input $\\{0,1\\}$ then we have to code the blank symbol $b$ by $\\{0,1\\}$ to code a machine as input for another. Note that if we restrict our machines to $\\{0,1,b\\}$ we do not have a speed up theorem anymore.

I might help to look at other proof's. I took one from the classic Ullmann/Hopcroft (1979).

> **Theorem** If $S\_2(n)$ is a fully space-constructible function, $$ \inf\_{n\to \infty} \frac{S\_1(n)}{S\_2(n)} = 0, $$
> and $S\_1(n)$ and $S\_2(n)$ are each at least $\log\_2 n$ then there is a language in $DSPACE(S\_2(n))$ not in $DPSACE(S\_1(n))$.
>
> *Proof* The theorem is proved by diagonalization. Consider an enumeration of off-line Turing machinees with input alphabet $\\{0,1\\}$ and one storage tape, based on the binary encoding of Section 8.3, but with a prefix of $1$'s permitted, so each TM has arbitrary long encodings. We contruct a TM $M$ that uses $S\_2(n)$ space and disagrees on at least one input with any $S\_1(n)$ space bounded TM. On input $w$, $M$ begins by marking $S\_2(n)$ cells on a tape, where $n$ is the length of $w$. Since $S\_2(n)$ is fully space-constructible, this can be done by simulating a TM that uses exactly $S\_2(n)$ cells on each input of length $n$. In what follows, if $M$ attempts to leave the marked cells, $M$ halts and rejects $w$ This guarantees that $M$ is $S\_2(n)$ space bounded. Next $M$ begins a simulation on input $w$ of TM $M\_w$, the TM encoded by binary string $w$. **If $M\_w$ is $S\_1(n)$ space bounded and has $t$ tape symbols, then the simulation requires space $\lceil \log t \rceil S\_1(n)$**. $M$ accepts $w$ only if $M$ can complete the simulation in $S\_2(n)$ space and $M\_w$ halts without accepting $x$. Since $M$ is $S\_2(n)$ space bounded, $L(M)$ is in $DPSACE(S\_2(n))$. $L(M)$ is not in $DSPACE(S\_1(n))$. For suppse there were an $S\_1(n)$ space-bounded $TM \hat M$ with $t$ tape symbols accepting $L(M)$. By Lemma 12.1 we may assume that $\hat M$ halts on all inputs. Since $\hat M$ appears infinitely often in the enumeration, and $$ \inf\_{n\to \infty} \frac{S\_1(n)}{S\_2(n)} = 0, $$ there exists a sufficiently long $w$, $|w| = n$, such that $\lceil \log t \rceil S\_1(n) \< S\_2(n)$ and $M\_w$ is $\hat M$, $M$ has sufficient space to simulate $M\_w$ and accept if and only if $M\_w$ rejects. Thus $L(M\_w) \ne L(M)$, a contradiction.

The bold part tells everything. Even to simulate $M$ on itself we have a blowup in space, and just for $S\_1 \in o(S\_2)$ we can compensate this blowup in the limit, but we cannot compensate for running times of $c\cdot \dot S\_2(n)$, $c \> 1$ in particular not for $M$ itself. More space can also lead to more time (or at least the time bound is bigger, this is the base $2^{\ldots}$), hence this is where the time blow up mentioned by dkaeae might come from. Also if we apply space compression, in the simulation we have more tape symbols, hence the compression effect is ''reversed'' by the factor $\lceil \log t\rceil$ in the simulation and the reasoning in the question breaks down; same for $M$ simulating itself.

---
Tags: complexity-theory, turing-machines, computability, space-complexity
---


title: The instructions a Stack Machine has

text:
# Question
Title: The instructions a Stack Machine has
Trying to figure out which instructions a stack machine has, and wanted to clarify / reassure that these are in fact all of them.

* `push` onto stack
* `pop` off stack
* `call` a system function like `add`

Then you can implement `jump`, for example, by pushing the address of the instruction in memory, and calling `call`. You can implement `add` by pushing twice and popping twice, etc. You can implement everything from just these 3 instructions. Wondering if this is correct, or if there is anything I am missing.

# Answer
There are dozens and dozens of stack machines out there in the wild, and they all have different instruction sets. So there's no single correct answer.

Some people might consider using `CALL` like that cheating: after all, it relies on things like `ADD` and `CMP` and `JMP` and `DUP` and such all being implemented in the machine, so why don't you call them instructions? But if you're going that route, you can get rid of `POP` too, and implement that with `CALL`. The only reason you can't get rid of `PUSH` too is you need some way to get opcodes and arguments onto the stack.

If you don't want to use `CALL` like that, the minimum for Turing-completeness would be something like `PUSH`, `ROT` (rotate the stack in some controllable way), `DUP` (duplicate the top of the stack), `CMP` (compare two values), `JMP` (some sort of conditional GOTO), and `SUB` (subtract one number from another). An actually useful machine would have more, things like `ADD` and `AND` and such.
> 3 votes

---
Tags: computer-architecture, assembly
---


title: Order Mistake Definition in CLRS

text:
# Question
Title: Order Mistake Definition in CLRS
On page 53 or CLRS it has said :

> We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function $g(n,m)$, we denote by $O(g(n,m))$ the set of functions $$\begin{align} O(g(n,m)) = \\{ f(n,m) : &\text{there exist positive constants }c, n\_0,\text{ and } m\_0 \\ &\text{ such that } 0 \le f(n,m) \le cg(n,m)\\ &\text{ for all } n\ge n\_0\text{ or } m \ge m\_0 \\} \end{align}$$

I think this definition has a problem cause if $n \ge n\_0$ for some constant $n$ then we don't need to grow $m$! I feel something is Wrong! It must be the word "and" instead of "or" for example : $f(x , y ) = x^2 + y^2$
$g\_2(x,y) = x^2 + y$
$g\_1(x,y) = x^2 + x\*y$

by the definition $f(x,y)$ is $O(g\_1(x,y))$ ! or even $f(x,y)$ is $O(g\_2(x,y))$ ?

please guide me .

# Answer
Well, there is not really a completely satisfying way to have the big-O Notation with multiple variables. Therefore CLRS present one way of a generalization. Putting an *and* instead of the *or* would give a new definition with other problems.

See this article for a discussion on the subject.
> 2 votes

# Answer
It looks like you misunderstood the definition.

---

To be more precise, the definition is read as the following.

> $$\begin{align} O(g(n,m)) = \\{ f(n,m) : &\text{there exist positive constants }c, n\_0,\text{ and } m\_0 \\ &\text{ such that } 0 \le f(n,m) \le cg(n,m)\\ &\text{ for all } (n,m)\text{ such that }n\ge n\_0\text{ or } m \ge m\_0 \\} \end{align}$$

---

### $f(x,y)\not\in O(g\_1(x,y))$

For the sake of contradiction, suppose $f(x,y)\in O(g\_1(x,y))$. Then there exist positive constants $c$, $n\_0$, and $m\_0$ such that $0 \le f(n,m) \le cg(n,m)$ for all $n\ge n\_0$ or $m \ge m\_0$.

$$ \lim\_{m\to\infty}\frac{f(n\_0,m)}{g\_1(n\_0,m)}=\lim\_{m\to\infty}\frac{n\_0^2 + m^2}{n\_0^2 + m}=\lim\_{m\to\infty}\frac{\frac{n\_0^2}m + m}{\frac{n\_0^2}m + 1}=\lim\_{m\to\infty}\frac{m}{1}=\infty$$

So, there exists $m\_1\ge m\_0$, such that $f(n\_0,m\_1) \> cg\_1(n\_0,m\_1)$. This contradicts to the condition that $f(n,m) \le cg\_1(n,m)$ for all $n\ge n\_0$. Q.E.D.

---

There is no way to define the big-$O$ notation for functions on more than one variable in a way that implies all properties commonly used in algorithm analysis. You can read this long paper by Kalle Rutanen, March 15, 2018, *O-notation in Algorithm Analysis (updated)* for details. So one has to be somewhat wary using the big-O notation in the case of multiple variables.

On the other hand, if the functions inside the notation are nondecreasing in each variable, then most properties used in algorithm analysis do hold for some natural definitions of the big $O$-notation for multivariate functions. This is the case in the question, when we can be more comfortable. In fact, that paper claims that "computer scientists have used the O-notation correctly intuitively" by providing "a solid mathematical foundation" (quoted from its chapter 7, conclusion).

---

**Exercise 1.** Show that $g\_1(x,y)\in O(f(x,y))$ and $g\_2(x,y)\in O(f(x,y))$

**Exercise 2.** Show that $f(x,y)\not\in O(g\_2(x,y))$.

**Exercise 3.** Show that $f(x,y)\in O(2x^2+3y^4)$ and $f(x,y)\in O(\max(x^2,y^2))$.
> 2 votes

---
Tags: asymptotics
---


title: Is λ allowed in Deterministic CFG?

text:
# Question
Title: Is λ allowed in Deterministic CFG?
I have a non-deterministic CFG that says

> S-\> aS | aB | bB | λ;
> B-\> bB | λ

And I'm asked to create a deterministic CFG from that. I understand why the given CFG is non-deterministic because it contains

> S-\> aS | aB | \[...\]

But I think what I'm confused is why in my book does it say that A-\>λ productions are not allowed? I can't think of any other way to keep the solution a deterministic CFG if λ is not allowed.

\[EDIT\] The book defines deterministic CFG

> *"To recognize the full set of context-free languages, we require a non-deterministic stack automaton. We saw that any NFA could be replaced by an equivalent DFA but we cannot do this in the case of non-deterministic stack automaton. It is our good fortune that practical programming languages can be adequately described by deterministic CFG"*
>
> *"We said that in Type 1 grammars, the nonterminal on the left-hand side could be replaced by ε. Since these restrictions are cumulative as we go from one level of the hierarchy to the next, this implies that Type 2 grammars may not have productions of the form A-\> ε. In fact, we will see many CFGs have such productions, we must allow such productions as exceptions to the Type-1 restriction."* \- Introduction to Compiler Construction by Thomas W. Parsons

# Answer
Oh. That's a disappointing explanation in the book. I suggest that you don't rely on that explanation for precise details about deterministic CFGs; it looks like it is trying to give intuition, but it is not the place to look for formal definitions, rigor, or precision. I'd suggest looking at a well-regarded automata theory textbook. (Hopcroft, Motwani, and Ullman's book is well-regarded, though I haven't checked specifically whether it has a definition of deterministic CFG. Sipser is also good.)

As Yuval says, the definition of a deterministic CFG is not completely standard. I think I've seen multiple slightly different definitions. Here are the basic concepts:

* The definition of a deterministic pushdown automaton is standard. (There *are* two variants, acceptance by final state and acceptance by empty stack; normally we use acceptance by final state, unless otherwise specified.)
* The definition of a deterministic context-free language is standard: $L$ is a deterministic context-free language if it is accepted by any deterministic pushdown automaton.
* The definition of a deterministic context-free grammar is not completely standard. If I remember correctly, I think it can be defined in a few slightly different ways. The one thing everyone agrees on is that, no matter what definition of deterministic CFGs you pick, the languages that can be accepted by such grammars should be exactly the deterministic context-free languages. But there are a few different ways to place restrictions on a CFG, while achieving this property. In particular, you can define deterministic CFGs in a way that allows it to include $A \to \lambda$ rule. Perhaps there is another definition that doesn't allow such rules, and perhaps your textbook has that definition in mind. Since your book doesn't state a precise definition, one can only guess. Perhaps the author decided that the exact specifics aren't too important, for the book's purposes.

The bottom line is: your question seems perfectly reasonable. I don't think the problem is that you lack understanding of something important. I think the problem is that the textbook is just written in a confusing way, on this particular point.
> 2 votes

---
Tags: context-free
---


title: Number of final states in a minimal DFA

text:
# Question
Title: Number of final states in a minimal DFA
Is the number of final states in a DFA at least the number of final states in its minimal DFA?

Is the answer even yes? Any help would be appreciated.

# Answer
> 0 votes
No. An easy counterexample to think about is a line of states that are all final states and they transition to the right on 0 or 1. So like A -\>(0,1) B -\> (0,1) -\> C -\> (0,1) C where the final node simply loops on itself for 0 and 1. Using Myhill-Nerode this would simplify down to a single start state that loops on itself. So the number of final states isn't necessarily a construction on the number of states after minimizing.

# Answer
> 4 votes
Yes, the number of final states in a DFA is at least the number of final states in its minimal DFA. Your proof is correct at some level of formality.

---

Intuitively, as you have noticed, any DFA for $L$ can be reduced to the minimal DFA for $L$ by merging states, which must merge any final states to a final state.

---

Here is how to make your proof mathematically more formal. Let $L$ be a language over $\Sigma$ and $D=(Q,\Sigma,\delta,s,F)$ be a DFA that accepts $L$. Let $M$ be the set of Myhill-Nerode equivalence classes with respect to $L$.

Define a map $m:Q\to M$ such that $m(q)=\[w\]$, where $w$ is any input that will drive $D$ to state $q$ and $\[w\]$ is the Myhill-Nerode equivalence class that contains $w$. We can verify that $m$ is well-defined, i.e., $\[w\_1\]=\[w\_2\]$ if both $w\_1$ and $w\_2$ drive $D$ to $q$.

We can verify or recall the following claims, thus completing this proof.

* $m$ maps a final state in $D$ to a Myhill-Nerode equivalence class that contains a word in $L$.
* all final states in the minimal DFA of $L$ are in one-to-one correspondence to all Myhill-Nerode equivalence classes that contain a word in $L$.

---

Here is a simple related exercise.

**Exercise.** The number of non-final states in a DFA is at least the number of non-final states in its minimal DFA.

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


# Question
Title: Check if knapsack problem instance is unsolvable
Is it possible to easily check if an instance of the 0-1 knapsack problem is unsolvable? Example: Assign 10 40-min tasks to 8 employees that have 60 minutes available each. Clearly, this instance is unsolvable as a 0-1 knapsack problem (but solvable as a fractional knapsack problem). I don't want to solve the 01-knapsack problem, but just detect if it is NOT solvable. Thanks in advance!

**EDITED PROBLEM 1 - THOROUGH PROBLEM DESCRIPTION**

Below is a more thorough problem description.

*Tasks*

I have a set of tasks with a given duration and a given time window each task has to be performed within (e.g the task duration for a given task could be 20 minutes and it has to be performed in the time interval 08:00-09:00). In addition, each task has a required skill, meaning that the employee carrying out the task needs to have a certain competence level (e.g tasks with required skill equal to 2 can only be carried out by employees with a competence level greater than or equal to 2).

*Employees*

I have a set of employees that work shifts. E.g an employee work from 08:00 to 13:00. Each employee has a given competence level, described above. The tasks are supposed to be allocated to the employees, and an employee cannot perform more than one task at the same time. E.g the same employee cannot perform BOTH task 1 (duration 10 minutes and time window 08:10-08:20) and task 2 (duration 30 minutes and time window 08:10-08:45). In addition, there are some tasks that a given employee cannot perform due to other reasons.

*Problem*

I want to check (preferably in polynomial time) a given problem instance (with tasks and employees) is not solvable, meaning that there exists some conflict such that it is impossible to allocate all tasks (see example above in original question formulation). **To my understanding, it is NP-hard to solve the problem, but I just want to prove/detect that a given instance is unsolvable. Is it possible to easily check if there does not exist a possible assignment of tasks to employees?**

**EDIT 2 - BETTER DEFINITION OF THE GOAL**

To be clear, I don't want an algorithm that ALLWAYS finds out if an instance is unsolvable or not. I am just looking for a way (an algorithm) that as OFTEN AS POSSIBLE finds out if the instance is unsolvable, and if the algorithm is uncertain (some efficient test did not detect that the instance was unsolvable) then I am fine with the problem instance being either solvable or unsolvable. So the algorithm I am looking for should detect as many "unsolvable instances" as possible, but not all.

Thanks in advance for your answers and contributions!

# Answer
This is a complex set of constraints. The standard way to solve this kind of problem is using integer linear programming (ILP). Solving ILP instances is NP-hard -- so there is unlikely to be any polynomial-time algorithm -- but in practice, on real-world scheduling problems, solvers can often find a solution in a reasonable amount of time. For your parameters (10 employees, 75 tasks, a few dozen time slots), I would expect that ILP might be very effective. This kind of approach is widely used in operations research for scheduling.

So, use an ILP solver. You can even set a time limit, and then it will return either "solution found", "no solution exists", or "time exceeded". That will meet your requirement of identifying some instances that are unsolvable, efficiently.
> 1 votes

# Answer
Your problem is a bin packing decision problem with the possibility of additional constraints on which items each bin can hold. To be clear, the decision problem is simply *deciding* whether a given set of items fits in a given set of bins. This problem is a superset of the regular bin packing decision problem, which is NP-complete, so your problem is NP-complete.

Therefore an efficient solution exists iff P = NP.
> 0 votes

# Answer
The problem you are talking about is NP-Hard (as you have stated). But, I think there is a *"simple"* way to get a pseudo-polynomial time complexity algorithm to detect for a possible solution.

First let us simplify the problem to a single employee and their list of $N$ tasks that they could potentially complete where said employee has $F$ time to complete tasks. For this algorithm, we are going to ignore any priorities of the tasks. Therein, we are looking at an example of the Subset Sum Problem. This problem, although NP-Hard as well, has a pseudo-polynomial time dynamic programming solution with the time complexity of $O(FN)$. Since for your problem $F$ is constant for that day, the algorithm should essentially be $O(N)$.

Given that there are $E$ employees, we just apply the same algorithm to each of their assigned tasks to see if every employee ends up with a solution. Therein, the total time to check whether or not there is a solution comes out to $O(EN)$. Of course there might be some extra costs involved, such as producing the tasks that each employee can work, but it should still essentially be polynomial.

Now, this algorithm does not take into account priorities and dependencies of tasks. But, it should at least help in quickly determining there is not a solution. If it does indicate there might be a solution, you at least have a potential solution to work from.

# TL;DR

There is an algorithm that has at least $O(EN)$ time complexity, where $E$ is number of employees and $N$ the number of tasks, that if indicates there is not a solution there is no solution. But, if it indicates there is a solution there still might not be a solution because of task priorities/dependencies/etc...
> 0 votes

---
Tags: np-complete, knapsack-problems
---


# Question
Title: Optimal scalability of a distributed algorithm
What's the optimal scalability of some algorithm when I implement it in a distributed manner?

Intuitively, it seems to me that any algorithm can scale at most linearly with number of computing nodes. I.e, if algorithm A takes **T** units of time with **1 computing node** on input I, it can't run faster than **T/n** units of time with **n computing nodes** on the same input I.

Is my intuition correct or are there some weird counter-examples to it?

# Answer
Yes, your intuition is correct, for all the reasonable models of computation that I'm familiar with. If it weren't, then we could take a single machine and have it simulate a cluster of n nodes, increasing the cost by only a factor of n. So, if you had an algorithm that ran on a cluster of n nodes faster than T/n, you'd get an algorithm that runs on a single node faster than T.

Note that the single node might need to have n times as much memory as each node in the cluster.
> 1 votes

---
Tags: runtime-analysis, distributed-systems
---


title: Quantum NAND gate

text:
# Question
Title: Quantum NAND gate
Wondering how a quantum NAND gate would be implemented, and if it would be considered universal. I saw for quantum computing the Hadamard, phase, CNOT and π/8 gates are universal, but didn't see NAND in there. Wondering why it's not universal in quantum computing, and if/how you can construct a quantum NAND gate.

# Answer
The trick is, unlike classical gates, quantum gates have to be *reversible* (aka *invertible*). In other words, for every possible output, there must be one and only one possible input producing that output.

This means the classical NAND gate can't possibly work in quantum computing: there are more inputs than outputs, so by the pigeonhole principle there must be some inputs that map to the same output. In particular, the inputs $(1,0)$, $(0,1)$, and $(0,0)$ all produce the output $1$.

So first, let's focus on *reversible classical computing*: we force all gates to be reversible, but don't worry about qubits yet. By the pigeonhole principle, we see that each gate must have at least as many output bits as it has input bits.

For one input bit and one output bit, there are only two reversible gates: `ID` (return the input unchanged) and `NOT` (return the opposite of the input). Neither of these are universal, as we can't build a `NAND` out of them.

For two input bits and two output bits, there are a few different trivial gates (such as "return both inputs unchanged", "return the first one unchanged and flip the second one", etc). But the most interesting one is `CNOT`, defined something like this:

$$CNOT(x, y) = (x, x \oplus y)$$

In other words, it flips $y$ if $x$ is true, and also outputs $x$ unchanged. Now we have an equivalent to `XOR`! But unfortunately, this still isn't universal: you can't build `NAND` out of `CNOT`, just like you can't build `NAND` out of `XOR`. (The proof works the same way, too.)

Well, what about three inputs and three outputs? Once we've got three bits to work with, we can build `CCNOT`, which works like this:

$$CCNOT(x, y, z) = (x, y, (x \wedge y) \oplus z)$$

And using this, you *can* build a reversible `NAND`!

$$NAND(x, y) = CCNOT(x, y, 1)$$

So it turns out that `CCNOT` is indeed universal, for reversible classical computation. It's better-known as the *Toffoli gate*, after its discoverer. But you could certainly think of it as "reversible `NAND`".

But once we bring in quantum computing, things get more complicated. `CCNOT` can implement all *classical* computations, but it can never create superpositions: you need something like a Hadamard gate for that. It turns out *no single gate can ever be universal* for quantum computing. So while "reversible `NAND`" is an important part of quantum computing, it can't stand alone: you need other operators too.
> 3 votes

# Answer
The NAND gate is not reversible, you can't recover its inputs using its outputs, so it's not a well defined quantum gate. Or, at the very least, it must contain some sort of internal measurement mechanism that would cause decoherence. This would prevent it from being universal for quantum computation.

A simple way to fix the reversibility problem is to have the gate work like a Toffoli. Instead of having two inputs `a, b` and producing one output `a nand b`, have three inputs `a, b, c` and toggle `c` based on `a nand b` thus producing the output `a, b, c xor (a nand c)`. This gate is just a minor variation on the Toffoli gate, so it has the same universality properties as the Toffoli. It is universal for classical reversible computation, but not universal for quantum computation unless you add some sort of superposing gate such as the Hadamard.
> 3 votes

---
Tags: quantum-computing, circuits
---


# Question
Title: Program to check whether a string is accepted by an unrestricted grammar
How can I write a program to find out whether a given string is generated using a type 0 grammar (unrestricted grammar)?

# Answer
Unfortunately, you cannot.

Nobody can since the membership problem for unrestricted grammar is undecidable. Here is a reference in Wikipedia.

On the other hand, the membership problem for context-sensitive grammar or, what is equivalent, noncontracting grammar is decidable.

Just in case it is not clear to you, a collection of decision problems (a.k.a, yes/no questions) is decidable if there is a program which will solve any given one of them correctly within finitely many steps. It is undecidable if there is not such a program. The existence of undecidable problems could be the best technical backdrop for this story.

You will learn its formal definition in your study of computer science (or you might have). There will be **lots of undecidable problems** coming to you; so if you suspect one, you should probably wait until you have studied the chapter about undecidability and somewhat more before you raise a similar question. Or you could just search around using the keyword "decidable" or "undecidable"
> 1 votes

# Answer
Short answer: **no, it's proven impossible**.

Slightly longer answer: unrestricted grammars are equivalent in power to Turing machines. That is, you can convert any Turing machine to an unrestricted grammar without loss of generality.

It's famously impossible to decide whether an arbitrary Turing machine accepts an arbitrary string (see the Halting Problem and Rice's Theorem). If you could decide whether an unrestricted grammar produced a given string, you could convert any Turing machine into an unrestricted grammar, and decide whether it accepted—and that's impossible. Therefore, you can't decide whether an unrestricted grammar produces a given string, in the general case.
> 1 votes

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


title: Prove PSPACE is closed under union?

text:
# Question
Title: Prove PSPACE is closed under union?
How would you prove PSPACE is closed under union? So far, my thought process is that we can create an algorithm to show that P is closed under union. I'm struggling with how I can connect that to PSPACE...

# Answer
(First, I'm assuming you mean finite union, not infinite union. As dkaeae points out in the comments, this is an important distinction!)

Let's say you have languages $P\_0, P\_1, \cdots P\_n$, which are all in `PSPACE`. In other words, there exist Turing machines $T\_0, T\_1, \cdots T\_n$ which decide (using polynomial space) whether a given input is in $P\_0, P\_1, \cdots P\_n$ respectively.

Now you have an input $x$ and want to decide if it's in $P\_0 \cup P\_1 \cup \cdots \cup P\_n$. The algorithm for this is straightforward: run $T\_0(x), T\_1(x),$ and so on, in order. If any of these machines accepts, then $x$ is in the union. If none of them accepts, $x$ is not in the union.

The space required is the maximum of the space taken by each Turing machine. Since each Turing machine takes polynomial space, the largest must be polynomial. Therefore the union is in `PSPACE`.
> 2 votes

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


# Question
Title: Prove PSPACE is closed under complement?
How would you prove PSPACE is closed under complement? So far, my thought process is that we can create an algorithm to show that P is closed under complement. I'm struggling with how I can connect that to PSPACE...

# Answer
> 2 votes
Let $P$ be an arbitrary language in `PSPACE`. In other words, there exists a Turing machine $T$ that decides (using polynomial space) whether an arbitrary input $x$ is in $P$.

Now we can write an algorithm to decide whether $x$ is in $\neg P$:

* Run $T$ on $x$
* If $T$ accepts, reject
* If $T$ rejects, accept

This takes however much space $T$ takes, plus a constant. A polynomial plus a constant is still a polynomial. Therefore, $\neg P$ is in `PSPACE`.

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


# Question
Title: Calculate the number of distinct permutations of length n in the closure of a language
I am studying a distance CS course, but there is no tutor available, so I would appreciate your help...

Consider the language $S = \\{a, aa, ab\\}$ How many distinct words of length $n$ will appear in $S^\*$?

Is there a way to do this without having to "enumerate" $S^\*$ until the answer is found?

# Answer
> 1 votes
D.W. has shown how to solve the problem in a general setting. Let me show the simplest way for this particular problem.

### What is $S^\*$?

$S^\*=\\{w\in\\{a,b\\}^\*: w\text{ does not contain }bb\text{ and }w \text{ does not start with } b\\}$.

The description above can be shown, for example, by demonstrating that the right hand side contains $\epsilon, a, aa, ab$ and its concatenation with itself.

### Recurrence relation

Let $f\_n$ be the number of words of length $n$ in $S^\*$. Then $f\_0=1$ and $f\_1=1$.

Let $w$ be a word of length $n+1$, $n\ge1$.

* $w$ ends with $a$. Then $w=xa$ for $x\in S^\*$ of length $n$.
* Otherwise, $w$ ends with $b$. Then $w=yab$ for $y\in S^\*$ of length $n-1$.

The above shows that $f\_{n+1}=f\_n+f\_{n-1}$. So $f\_n$ is the famous Fibonacci sequence.

### Final formula

$$f\_n=\frac{\left(\dfrac{1+\sqrt5}2\right)^n-\left(\dfrac{1-\sqrt5}2\right)^n}{\sqrt5}$$

---

**Exercise.** (One minute or less if you find the shortcut.) How many distinct words of length $n$ appear in $\\{a,bb\\}^\*$?

# Answer
> 1 votes
The language $S^\*$ is regular. Therefore, it can be expressed by a DFA. Now use Why isn't it simple to count the number of words in a regular language? or https://cstheory.stackexchange.com/q/8200/5038.

---
Tags: algorithms, closure-properties
---


# Question
Title: Is it possible to interpret some Martin-Löf types as abelian monoids in such a way that any abelian monoid can be represented as a type?
For instance, I can interpret the unit type as the trivial monoid with one element. Non-dependent pairs $A \times B$ can be interpreted as the direct sum $A ⊕ B$ when $A$ and $B$ can both be interpreted as abelian monoids. For the sum type $A + B$, you can define the monoid operation as: $$inj\_L(a\_0) \cdot inj\_L(a\_1) = inj\_L(a\_0 \cdot a\_1)$$ $$inj\_L(a) \cdot inj\_R(b) = inj\_R(b)$$ $$inj\_R(b) \cdot inj\_L(a) = inj\_R(b)$$ $$inj\_R(b\_0) \cdot inj\_R(b\_1) = inj\_R(b\_0 \cdot b\_1)$$ (Although this does mean that the interpretations of $A+B$ and $B+A$ are different).

So far though this scheme only lets me represent finite monoids where $\forall x: G, x \cdot x = x$. I'd like a way to extend it to infinite and more interesting monoids. That will at least require a way to interpret W-types but I can't see what that interpretation could be. Does such an interpretation exist? Or is there a simple proof that what I'm trying to do is impossible?

# Answer
> 1 votes
Fortunately you gave us some context in the comments (always a good idea to include it in your question). Rather than doing what you're trying to do, I believe quantitative type theory is what you're looking for.

---
Tags: type-theory, dependent-types, group-theory
---


# Question
Title: Is it decidable whether a Turing machine M will reach state q on input s?
> Given a turing machine $M$, one of its states $q$ and an input word $w$, will $M$ ever reach $q$ on $w$?

As we are not given anything about the word length, I assume that we have a finite length word. Then I believe this problem is decidable. After all, we only have to check whether we come across state $q$ when we feed $w$ to $M$.

But my solution manual claims that it is an undecidable problem.

Am I correct or is the manual correct? Do we ever take into consideration a word with infinite length during such analysis?

# Answer
> 5 votes
> Do we ever take into consideration a word with infinite length during such analysis?

Never say never. However, it is a safe bet that in the course of your undergraduate or even graduate study you can assume that all inputs to Turing machines are finite.

---

Here is a more formal restatement/understanding of the problem in the question.

> $$\begin{align}\text{TRIPLE }=&\\{\langle M, q, w\rangle: M\text{ is a Turing machine. }\\ &q\text{ is one of the states of }M. \\ &w\text{ is a word over the input alphabet of }M.\\}\\ \text{REACH }=&\\{\langle M, q, w\rangle\in\text{TRIPLE}: M\text{ will reach }q\text{ on input }w. \\}\end{align}$$ Is $\text{REACH}$ decidable? (the problem of state reachability)

Assume $\text{REACH}$ is decidable. By definition, there is a Turing machine $T$, which, given a Turing machine $M$, its state $q$ and an input word $w$ as its input, it will accept the input if and only if $M$ will reach state $q$ on input $w$.

Recall that $A\_{\text{TM}} = \\{\langle M,w\rangle : M \text{ is a TM and }M\text{ accepts }w\\}$. Construct a new Turing machine $T'$ such that given input $\langle M, w\rangle$ where $M$ is a TM and $w$ is an input for $M$, $T'$ will change the input to $w'=\langle M, q\_{\text{accept}}, w\rangle$ where $q\_{\text{accept}}$ is the unique accept state of $M$, and then simulate $T$ on input $w'$. We see that $T'$ is a decider for $A\_{\text{TM}}$.

I would believe you have learned that $A\_{\text{TM}}$ is not decidable. That contradiction shows that our assumption must be wrong, which means this problem of state reachability cannot be decidable.

(In case that the Turing machines defined for you could have multiple accept states, $T'$ could replace all accept states in $M$ with a unique accept state at first.)

Reader can also take a look at a more intuitive and less notation-cluttered but less rigorous version of this answer here, which is just the first version of this answer.

---
Tags: turing-machines, computability, undecidability, semi-decidability
---


# Question
Title: Find total count of all paths starting from a fixed vertex to all other vertexes of the graph
Given an directed graph (may contain cycles) we have to find total number of simple paths from a fixed source vertex to all other vertices of the graph, i.e.

$$ \text{#(paths from 1 to 2)}+\text{#(paths from 1 to 3)}+\cdots+\text{#(paths from 1 to $n$)}. $$

We have to find this in linear time, as number of vertexes can be as large as 100000. I tried using DFS in this question to generate all the paths and keeping up count of these but this is not fast enough.

Is there any mathematical formula for this?

P.S. I am only interested in total number of paths, not generating all the paths. Each vertex has up to 4 or 5 edges.

For example, if the adjacency matrix of a 4 nodes graph is like this:

```
  A B C D
A 0 1 0 0
B 1 0 1 1
C 0 1 0 1
D 0 0 1 0

```

Then the number of paths are

```
from A to B: 1
from A to C: 2
from A to D: 2
therefore 5 paths

```

So I want the answer to be 5.

The edges may be unidirectional or bidirectional and I want to find only simple paths.

# Answer
Suppose you have a polynomial-time algorithm $\mathcal{A}$ to solve this problem, then consider a graph $G$ and arbitrary two vertices $s$ and $t$. We construct a new graph $G'$ by add a new vertex $t'$ into $G$, as well as an edge $(t,t')$. Now we have

\begin{align} \text{#(paths from $s$ to $t$ in $G$)} =&\ \text{#(paths from $s$ to all other vertices in $G'$)}\\ &-\text{#(paths from $s$ to all other vertices in $G$)}. \end{align}

That means, we can use $\mathcal{A}$ to count the number of paths between two vertices in polynomial time. However, the latter problem is #P-hard. So such an algorithm $\mathcal{A}$ does not exist unless $\mathbf{P}=\mathbf{NP}$.
> 1 votes

---
Tags: algorithms, graphs, counting
---


title: On propositional formula satisfiablitiy

text:
# Question
Title: On propositional formula satisfiablitiy
I know that there is no algorithm for converting any logical formula to DNF so even though we have an efficient algorithm to solve DNFSAT we can't solve formulaSAT in deterministic polynomial time. But what makes the finding of an efficient CNF algorithm solve formulaSAT in polynomial time? Because I'm guessing that the complexity of converting a logical formula to a DNF would be the same as the complexity of converting a formula to CNF so even if we find an efficient algorithm for CNFSAT we won't be able to convert any formula into CNF and therefore we can't solve formulaSAT also! Or am I wrong and the problem of formulaSAT is not in NP?! An example of what I mean by a formula: (¬A∨B)∧¬((A∧¬C∧(B∨D))∨(C∧D))

# Answer
> 1 votes
When converting an arbitrary formula into a CNF, you are introducing *extension variables*. These are new variables that represent subformulas of your formula.

Let us take the following simple formula as an example:

$$ A \lor (B \land C). $$

In order to convert this into a CNF, we need to replace $B \land C$ with an extension variable $\alpha$ which has the same truth value of $B \land C$. We can easily express "$\alpha = B \land C$" as a CNF (or as a DNF). After replacing $B \land C$ with $\alpha$, we obtain the formula $$ (A \lor \alpha) \land \text{"$\alpha = B \land C$"}. $$ (You need to replace "$\alpha = B \land C$" with a CNF.) This formula is *equisatisfiable* with the original formula: the original formula is satisfiable iff the new formula is satisfiable. Therefore if we are interested in knowing whether the original formula is satisfiable, we can instead ask whether the new one is.

In the transformation outlined above, we used the fact that the class of CNFs is closed under conjunction. That is, we could express add the condition "$\alpha = B \land C$" to our formula while retaining its CNF form. The same is not the case for DNFs, which are closed under disjunction but not under conjunction.

Indeed, consider the opposite situation, in which we want to convert $A \land (B \lor C)$ into an equisatisfiable DNF. We can easily express $\alpha = B \lor C$ as a DNF; the problem is that $(A \land \alpha) \land \text{"$\alpha = B \lor C$"}$ is not a DNF, since we joined $A \land \alpha$ and $\alpha = B \lor C$ with the wrong connective.

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


# Question
Title: How is the literal meaning of "rendezvous" related to its usage in distributed computing?
I am trying to figure out the difference between RPC and Rendezvous. Is it correct that they differ only on their implementation on server side: RPC will involve creating a new process/thread to handle a request, and Rendezvous will pick an existing process/thread to handle a request?

The word "rendezvous" simply means a bunch of people meeting together. How is it related to its usage in computing?

Thanks.

# Answer
> 2 votes
In this context, the rendezvous would mean "a bunch of threads meeting together" instead of people. Rendezvous is a method of synchronisation in which at least two threads "meet". In other words, each thread that reaches the rendezvous point waits until all other threads have reached the same point before proceeding.

In the context of Distributed Algorithms the Rendezvous Problem is the task of devising an algorithm that will ensure that at least two entities (e.g., mobile agents) starting from different positions will meet after a finite amount of time in a specific environment (e.g., in a graph).

---
Tags: distributed-systems, communication-protocols
---


# Question
Title: DFA & RE from descriptive definition of given regular language
I am trying to make the **DFA** and **RE** of a regular language which is define on the **alphabet = {1,0}** and all the strings present in these languages have **exactly one 010 substring** in them.

Some strings which are accepted by the above regular language are;

**{010, 0100, 0101, 1010, 0010 .......0101110.....}**

In the above strings there is only one 010 substring. If there is more than one 010 substring in a string such as.

**{01010, 01011010... }**

then the DFA of the above language should not accept that string.

If someone provide me ony DFA of the above lang. then i would be able to make the RE by **state elimination**. Or if someone provide me the RE of the above lang. then i could make the DFA by other **kleene theorem**.

**My work:** I made the following DFA for that language;

This DFA is `accepting` all the strings like `010, 0100, 0101, 1010, 0010....` and its also `rejecting` the string with more than 010 like `01010`. But with that its rejecting `0101110` string which is part of the language.

**Note:** I go through the **question** which is already on the CS stackexchange as previously my question was marked duplicate. This question is about "How we can prove that a given language is regular or not". But in my question i have provided the descriptive definition of a regular language. And i am trying to get its RE or DFA.

# Answer
You can always use the current state of the automaton to remember the last three characters you've seen. Now, you can implement two phases. In the first phase, you're happy if you're ever in the situation where the last three characters were $010$. In the second phase, you become unhappy if you ever see $010$ again.
> 3 votes

# Answer
Here's a hint; your language is, more or less, the concatenation of three languages: the strings not containing 010, the language consisting of the single string 010, and the strings not containing 010.

1. Can you make a DFA which accepts all and only those strings not containing 010, perhaps as the complement of something?
2. When I said "more or less" above, I was referring to the fact that the concatenation of the languages is a bit more complicated than vanilla concatenation. You have to deal with that.
> 2 votes

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


title: The heaviest induced subgraph problem

text:
# Question
Title: The heaviest induced subgraph problem
I am interested in such a combinatorial problem: given a graph $G=(V, E)$ and a weight functions $w\_v: V \mapsto R$, and $w\_e: E \mapsto R$ we are asking about such a induced subgraph $G' = (V', E')$ of $G$ that maximizes the sum: $ \sum\_{e \in E'} w\_e(e) + \sum\_{v \in V'} w\_v(v) $.

The problem is **NP-H**ard (by the reduction from maximum clique problem) so any suggestions for approximation solutions (even greedy) and links to the literature would be appreciated.

# Answer
> 1 votes
$\newcommand{\R}{\mathbb{R}}$ Let's consider a special case of the problem where vertex has negative weight and edges have positive weight. So $w\_v: V\to \R^-$ and $w\_e: E\to \R^+$.

Finding the heaviest induced subgraph is equivalent to a min-$st$-cut computation on a suitable graph. We will refer to the slides about densest subgraph in this presentation.

Indeed, minimizing $w\_e(E(V'))+w\_v(V')$ is equivalent to minimizing $(-w\_v(V')) + \frac{1}{2} w\_e(E(V',\bar{V'})) + \frac{1}{2} \sum\_{v\in \bar{V'}} \deg(v)$. (Note the degree here are weighted degree, that is $\deg(v) =\sum\_{e:v\in e} w\_e(e)$) The derivation of the above fact is similar to slide 21. Then, this can be solved easily by modeling it as a min-$st$-cut in some other graph (see slide 22). It is crucial to have negative vertex weights and positive edge weights for the reduction to work.

---
Tags: graphs, optimization, approximation, greedy-algorithms
---


# Question
Title: In which order to solve subproblems when using memoization?
I am currently trying to solve a task with memoization. I have following recursion:

A (i, j) = f( A (i, j-1), A (i-1, j-1), A (i-1, j + 1) )

I am not sure in which order the sub-problems should be solved best, so that multiple calculations are avoided.

Does someone have an idea which order is best?

# Answer
> 2 votes
Let me show you the general approach to figuring this out. Then I'll let you apply that technique to your specific situation.

Well, it's clear that you need to solve $A(i,j-1)$, $A(i-1,j-1)$, and $A(i-1,j+1)$ before solving $A(i,j)$. So, you need to pick an order that ensures all three of those are solved before you try to solve $A(i,j)$. What order would work for that?

I suggest you try drawing a picture. Draw a grid, with one dot for each $(i,j)$. Draw an arrow from $(i,j-1)$ to $(i,j)$, an arrow from $(i-1,j-1)$ to $(i,j)$ and an arrow from $(i-1,j+1)$ to $(i,j)$ for each $(i,j)$. You might do this for, say, a 4x4 grid. Look at the resulting picture. Can you find an order of traversing the dots, so that is consistent with all of the arrows? Hint: try topological sorting that graph. What order does that give you? Can you generalize? What would work for a 5x5 grid?

If you're not sure, just write a recursive program and apply memoization. Then you won't need to explicitly pick an order to build things out bottom-up; the computer will take care of that for you. See When can I use dynamic programming to reduce the time complexity of my recursive algorithm? and https://en.wikipedia.org/wiki/Memoization.

---
Tags: dynamic-programming, efficiency, memoization
---


title: Deustch algorithm using one qubit

text:
# Question
Title: Deustch algorithm using one qubit
Deutsch algorithm uses two qubits to determine the type of function. But what if we have only one qubit? How the algorithm would be implemented? And especially, how $U\_f = |x\rangle |y \oplus f(x)\rangle$ would look like?

# Answer
> 3 votes
Unfortunately, as D.W. says, it's not possible to do Deutsch's Algorithm with only a single qubit.

The key is the line you quoted in your question: the quantum oracle for the function $f$ returns $\mid x\rangle \mid y \oplus f(x)\rangle$. This only works with two qubits.

Why can't we just make the oracle return $\mid f(x) \rangle$? Well, in quantum computing, all functions must be reversible (you can reconstruct the input from the output), and we have no guarantee that $f(x)$ is reversible. And if we force $f(x)$ to be reversible, then we know it's balanced, and the problem becomes trivial (return "balanced" every time).

The only way to make a reversible function out of a function that may not be reversible is to add "ancillary" or "garbage" qubits; this is how the Toffoli gate implements the non-reversible `AND` function. That's basically what the second qubit is doing here: without it, we can't even necessarily call the function.

# Answer
> 1 votes
You can't. If the algorithm needs two qubits, you can't implement it with just one qubit.

---
Tags: quantum-computing
---


# Question
Title: Is this language is Context-free language or not?
Is anybody can help me please to determine is this language is Context-free language or not?

L={wvw | w,v∈{a,b,c}+}

for example:

part of the language: acbac, abcab, bbcbb

not part of the language: abab, aa, abcc

I tried to prove using pumping lemma for context-free languages like that:

I take this word from language w=**aacbbaa**. I split the word to 5 parts uvxyz and if I can pump u and y and the word stays inside language the language is context-free:

```
u-aa, v-cc, x-b, y=bb, z=aa
after I pump v and y the word is still in language->
u-aa, v-cccc, x-b, y=bbbb, z=aa ->
aaccccbbbbbaa

```

But the answer inside answers section is that the language is not context-free.

What wrong with my prof?

# Answer
> 2 votes
You can't use the pumping lemma to prove that a language is context-free (see, e.g., here). The pumping lemma is only useful to prove that the language is *not* context-free. See our reference questions for details on how to prove that a language is or isn't context-free: How to prove that a language is context-free?, How to prove that a language is not context-free?.

So, one thing wrong with your proof is where you say "if... the word stays inside language the language is context-free" -- that's not correct.

---
Tags: computability, automata, context-free
---


# Question
Title: Role of weak entities in avoiding inconsistencies
My material on database claims that:

> Weak entities help to avoid data duplication and inconsistencies arising due to duplicating the key of the strong entity.

My question is how can a strong entity key even be duplicated? This would make the key lose its uniqueness property.

Can anyone please help? How is the statement provided in the material justified?

Thanks in advance!

# Answer
> 0 votes
Definition and example of weak entity

The diagram shows a strong entity (Order, key Order number) linked to multiple weak entities (Order Line, key Order number+Order linenumnber). There's a foreign key from the weak entity to the strong (Order number).

So the Order number is duplicated in the sense a given Order number appears in many entities: one strong (Order number is the whole key); many weak (Order number is part of the key).

---
Tags: database-theory
---


# Question
Title: Why aren't P and P/poly trivially the same?
The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see http://pages.cs.wisc.edu/~jyc/02-810notes/lecture09.pdf). Now, why can't a polynomial-sized circuit be simulated in polynomial time?

# Answer
The point about circuits is that a circuit has a fixed number of inputs. This means that, to define a language, we need a family of circuits $C\_0, C\_1, C\_2, \dots$ such that the circuit $C\_i$ tells you which strings of length $i$ are in the language, for each $i$. This doesn't require that there should be any relationship between the circuits $C\_i$ and $C\_{i+1}$: they could be completely different. In particular, for any set $S\subseteq\mathbb{N}$, you could set declare $C\_i=\mathrm{true}$ if $i\in S$ and $C\_i=\mathrm{false}$ for $i\notin S$. Even if $S$ is undecidable!

In contrast, a language is in $\mathrm{P}$ if there is a single Turing machine that tells you whether every possible input of every possible length is in the language. Now, you can't play any funny games about inputs of different lengths.

You're correct that we can evaluate any fixed circuit in $\mathrm{P}$. But that's not necessarily enough to decide a language in $\mathrm{P/poly}$. To do that, we would first need to compute the length of the input, then use that to determine which circuit $C\_i$ we need to evaluate, and then evaluate the circuit. As the example above shows, the "determine which circuit" part might not even be computable, let alone computable in polynomial time.
> 25 votes

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


# Question
Title: How to find First in a left recursive grammar?
> One of the basic requirements for a grammar to be LL(1) is : For every pai r of productions A -\> X | Y, First(X) and First(Y) should be disjointed.
>
> If a grammar is left-recursive, then the set of productions will contain at least one pair of the form A -\> AX|B; and hence, First(AX) and First(Y) will not be disjoint sets, because everything in the First(Y) will also be in the First(AX).
>
> Source : Compiler Design by Dr. O.G. Kakde

How can I calculate the First of (AX) because First(A) = First(AX) U First(Y) goes recursively forever ?

# Answer
Here is how to apply the production rule $ A\to AX$ to compute $\text{first}(A)$.

> When $\epsilon\in\text{first}(A)$, add all (non-$\epsilon$) members of $\text{first}(X)$ to $A$.

More generally, if there is a rule $A\to AX\_1X\_2\cdots X\_n$,

> When $\epsilon\in\text{first}(A)$, add all non-$\epsilon$ members of $\text{first}(X\_1)$ to $A$. When $\epsilon\in\text{first}(A)$ and $\epsilon\in\text{first}(X\_1)$, add all non-$\epsilon$ members of $\text{first}(X\_2)$ to $A$. When $\epsilon\in\text{first}(A)$ and $\epsilon\in\text{first}(X\_1), \text{first}(X\_2)$, add all non-$\epsilon$ members of $\text{first}(X\_3)$ to $A$, and so on.

The rules above are just specializations of the general rules. What is particular in this situation is that there is no effect when you add all members of $\text{first}(A)$ to $\text{first}(A)$. There is no concern about infinite recursion.

---

Here is a left-recursive grammar.
$\quad S \to SX\mid Y$
$\quad X \to x$
$\quad Y \to y$
We compute as the following.

* $\text{first}(X)=\\{x\\}$ by the rule $X\to x$.
* $\text{first}(Y)=\\{y\\}$ by the rule $Y\to y$.
* $\text{first}(S)=\\{y\\}$ by the rule $S\to Y$.
* Since $\epsilon\not\in\text{first}(S)$, ignore rule $S\to SX$.

---

Here is another left-recursive grammar.
$\quad S \to SX\mid Y$
$\quad X \to x \mid \epsilon$
$\quad Y \to y \mid \epsilon$
We compute as the following.

* $\text{first}(X)=\\{\epsilon, x\\}$ by the rules $X\to x \mid \epsilon$.
* $\text{first}(Y)=\\{\epsilon, y\\}$ by the rules $Y\to y\mid\epsilon$.
* add $\epsilon, y$ to $\text{first}(S)$ by the rule $S\to Y$.
* Since $\epsilon\in\text{first}(S)$, add $x$ to $\text{first}(S)$ by the rule $S\to SX$. So $\text{first}(S)=\\{\epsilon, x, y\\}$

---

**Exercise.** Compute the first set of the following grammar.
$\quad E\to E - T \mid T$
$\quad T\to T * F \mid F$
$\quad F\to (\ E\ ) \mid I$
> 5 votes

---
Tags: context-free, compilers, parsers
---