# Question
Title: Using coloring optimization or coloring decision to solve coloring search
How can you show that **coloring search** can be solved by making a polynomial number of calls to the solution for **coloring optimization** or **coloring decision**? (**Coloring search** is the algorithm to color the vertices of a graph such that adjacent vertices have a different color.)

I wasn't sure how to solve it, but here is what I attempted (I chose to use **coloring optimization**):

> **Coloring search** can be solved by calling **coloring optimization** and finding the value $m$, which is the amount of colors needed so that no two adjacent vertices have the same color. Once $m$ is found, **coloring search** can color the vertices of the graph by rotating through the $m$ different colors for each vertex.

Am I on the right track?

# Answer
> 6 votes
Given a graph $G$, we want to do two things:

1. Find the smallest $k$ such that $G$ is $k$-colourable,
2. Given such a $k$, find a colouring of $G$ with $k$ colours.

If we have an oracle for the decision version of the colouring problem, we can do both.

For the first part we can perform a search to find the optimal $k$. Even the naive approach here is okay, we can just sequentially ask if $G$ is $k$-colourable for $k=1,2,\ldots,n$. Then we make at most $n$ calls to the oracle. Of course we can perform a binary search and cut this down to $\log n$ calls. (Note that this is also how we solve the optimization version with the decision version).

Then given that we've worked out what $k$ is optimal, we can find a $k$-colouring of $G$ using the decision oracle. The only wrinkle is that the oracle doesn't take partial colourings, so we need a way of encoding in the graph that a particular vertex has been coloured a particular colour.

To do this we actually use the oracle on an auxilliary graph, which we will call $G^{+}$, that is $G$ plus a $K\_{k}$ with some additional edges. Of course the $K\_{k}$ needs exactly $k$ colours, so we can use its vertices to indicate which colours are available for a vertex. Let the vertices $\\{k\_{1},\ldots,k\_{k}\\}$ of the $K\_{k}$ correspond to the colours $\\{c\_{1},\ldots,c\_{k}\\}$. Then we will indicate that a vertex $v$ in $G$ *cannot* be coloured with colour $c\_{i}$ by making it adjacent to $k\_{i}$. Furthermore if we colour a vertex with colour $c\_{j}$ we will make it adjacent to *every* $k\_{i}$ with $i\neq j$ (and *not* adjacent to $k\_{j}$).

Then we repeatedly do the following:

1. Pick an 'uncoloured' vertex $v \in V(G)$.
2. For every vertex $u \in N(v)$, if $u$ has been coloured, then there is one $k\_{i}$ such that $uk\_{i} \notin E(G)$. Add the edge $vk\_{i}$ to $E$.
3. For the remaining vertices $k\_{j}$ such that $vk\_{j}$ is not yet in $E$, we add all *other* edges between $v$ and the $K\_{k}$ and ask the oracle if the new graph is $k$-colourable. If it is, we keep this graph and move on to the next vertex, if the answer is No, we undo step 3 and try with the next $k\_{j}$.

Note that as $G$ is $k$-colourable, there is some $k\_{j}$ that step three will work with. Then when we have processed every vertex, each vertex in $G$ is *not* adjacent to exactly one vertex in the $K\_{k}$, this indicates which colour the vertex can be coloured with to obtain the colouring. From step 2, we see that this cannot be the same colour as any of its neighbours.

At step three we make at most $k$ calls to the oracle, and we do this for each vertex in $G$, so in total we make at most $(k+1)n$ calls to the oracle (including the search for $k$).

---
Tags: graphs, np
---


# Question
Title: How does this non-deterministic algorithm to find if a Hamiltonian path exists work?
I have read of an algorithm that a non-deterministic Turing machine $N$ can run to determine whether a given graph $G$ has a Hamiltonian path from the start node $s$ to a certain node $n$:

1. Write a list of $x$ numbers $p\_1, p\_2, p\_3 ... p\_x$, where $x$ is the number of nodes in $G$. Each number in this list is non-deterministically selected to be from 1 to $x$.
2. Check for repetitions in this list. If a repetition exists, reject.
3. Check whether both $s = p\_1$ and $n = p\_x$. If either do not hold, reject.
4. For each $i \in \[1, x - 1\]$, check whether $(p\_i, p\_{i + 1})$ is an edge of $G$. If any are not, reject.
5. Accept.

I do not understand how this algorithm works. Specifically, in step 1, why am I making a list of random (potentially repeating) numbers from 1 to $x$ (What does this list have to do with the nodes of $G$?)?

Likewise, in step 4, why does $(p\_i, p\_{i + 1})$ represent a potential edge in $G$?

# Answer
> 2 votes
There's a couple of bits of information that are key to making this make sense:

1. Each $p\_{i}$ should be a label for a vertex in $G$. Typically $p\_{i} \in \[1,x\]$, but it's not compulsory that you have to label the vertices from 1 to $x$. So the first step is effectively producing a putative list of vertices that could be a path. The rest just checks that it is actually a path (a hence why $(p\_{i},p\_{i+1})$ could be an edge).
2. The list is not random. It is selected non-deterministically. This is most definitely not the same as randomly selected. Non-determinism is a special theoretical property where a non-deterministic machine can "guess" a correct answer if it exists, however correct also has a special meaning, in that it selects an answer that will lead to an accepting state if such an answer exists. This may not be the right answer, just one that will make the Turing Machine say Yes - so we still have to check it.

So the algorithm guesses really cleverly a list (in fact an ordering) of all the vertices of the graph, and then checks that it actually makes a Hamiltonian Path from $s$ to $n$.

---
Tags: turing-machines, nondeterminism
---


# Question
Title: How to determine the polynomial runtime of an NP reduction?
To show that a NP problem is NP-complete, we also have to show that $L \leq\_{p} L'$ , where $L$ is proven NP-complete and you have to prove $L'$ also is. The thing I am confused is how in all NP-complete problems in CLRS they just state the reduction algorithm for $L$ to convert to $L'$ is polynomial. How can one prove it's polynomial time, provided an example such a clique or ham cycle kind of problem?

# Answer
The problem here is a misunderstanding of the point of the reduction. NP-complete problems are not known to have polynomial time algorithms. If they do, then P $=$ NP, if they don't then P $\neq$ NP - this is the **BIG** question of theoretical computer science.

The point of the reductions you're looking at is to show that the problem $L'$ is NP-complete, and thus at least as hard as anything else in NP. It does this by demonstrating that if you could solve $L'$ in polynomial time, then using the reduction you could solve $L$ in polynomial time too (take the instance of $L$, convert it to an instance of $L'$, solve that, then use that solution to get the solution to the original instance).

As $L$ is NP-complete, this also means that if we could solve it in polynomial time, we could solve *every* problem in NP in polynomial time (hence the intuition that NP-complete problems are in some sense the "hardest" problems in NP).

Just to add some technical bits on top of that, a problem $\Pi$ is NP-complete if:

1. $\Pi \in$ NP, and
2. $\Pi$ is NP-hard.

A problem $\Pi$ is in NP if there is an non-deterministic algorithm that solves $\Pi$ in polynomial time in the size of the input or equivalently we can check an answer to an instance of $\Pi$ in *deterministic* polynomial time.

A problem $\Pi$ is NP-hard if for *every* problem $\Phi \in$ NP, there exists a polynomial time reduction such that $\Phi \leq\_{p} \Pi$ (this can be a different reduction for each $\Phi$). In practice what we do is actually chain these reductions together, so say we have an NP-hard problem $\Pi'$, then we know that there's reductions from everything in NP to it, so if we can show that $\Pi' \leq\_{p} \Pi$ then by composing the reductions, we can show that there's a reduction from everything to $\Pi$ (we just go via $\Pi'$).

So just to come back to the original question, we don't know if there's a polynomial time algorithm for $L'$ - most(?) people would probably suspect that there isn't, as lots of people have spent lots of time trying to find even one polynomial time algorithm for any NP-complete problem and there's been no luck so far (of course such an algorithm for any of them means a polynomial time algorithm for *everything* in NP). The reduction 'just' shows that $L'$ is one of these hard problems.
> 1 votes

---
Tags: complexity-theory, np-complete, reductions, proof-techniques
---


# Question
Title: Is the complement of $ww^R$ context-free?
Identify the language given by $L = \\{ x \in (0,1)^\* : x \neq ww^R, w \in (0,1)^\*\\}$. Note: $w^R$ is the reverse of the string $w$.

Closure property can/should be applied only in the cases when the actual language is not specified. Otherwise, you may arrive at wrong conclusions. The language in question is fully specified, so I doubt whether one can directly apply closure property on $ww^R$, which you say, is its complement or vice versa. The given answer is CFL. But I don't seem to have arrived at it satisfactorily.

# Answer
> 2 votes
If you want to show that $L$ is context-free, you can proceed as follows:

Build a push-down automaton $P$ that accepts $L$. $P$ will read the input and put all the read characters on its stack. At some point it guesses (non-deterministically!) that half of the input has been read. Then it reads the remaining input and checks it a against its stack. If $P$ finds a mismatching character it accepts, if it does find not a mismatch, or the guess for the middle of the word was wrong, it rejects.

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


title: A puzzle in Permutation

text:
# Question
Title: A puzzle in Permutation
There are two stacks A and B.

```
A :  a,b,c,d   ('a' is on top and 'd' is at the bottom of the stack)
B :  (empty)

```

There are two rules.

```
If an element of A is popped, it must be printed immediately or pushed into B.
If an element of B is popped, it can only be printed.

```

So, how many permutations of a,b,c,d are possible? (continue reading)

P.S. Well, I did calculations manually(didn't use any formula) and got 14 as the answer. However, it took around 10 minutes to do the lengthy steps. So, is there an easy way to do this?

# Answer
> 2 votes
This problem looks like the problem of single stack sorting. "Single" because onle your stack B is used to sort, the stack A is only for input. Donald Knuth has analysed this, and characterized it as the 231-avoiding permutations, and has shown their number equals the Catalan numbers.

Now if my observation is correct, you must have counted wrong (original number you gave was 28). The Catalan numbers are 1, 2, 5, 14, 42, 132,

(added, after you recomputed) Thus, we get a formula, the number of "single-stack sortable permutations of length n" is the $n$-th Catalan number $C\_n = \frac 1{n+1}{2n \choose n}$. That does not yet explain the connection. There is a lot to learn about Catalan numbers, see the wiki-page for a lot of situations where they arise! Also the page to the online encyclopedia of integer sequence I referred to has more than enough links to keep you busy for a long time.

---
Tags: stacks, permutations
---


# Question
Title: Computational power of nondeterministic type-1 min-heap automata with multiple heaps
I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called *min-heap automata*; the original question, and links to others, can be found here.

This question concerns the power of type-1 min-heap automata, which represent my initial idea for how these machines would operate. The class of languages which can be accepted by such automata is incomparable (i.e., neither a proper subset nor a proper superset) of the set of context-free languages.

Push down automata, which possess a single stack for data storage, accept the set of context-free languages, in the same way that min-heap automata, which possess a single heap for data storage, accept the set $HAL\_1$ of languages accepted by nondeterministic type-1 min-heap automata. Push-down automata with two stacks are equivalent to Turing machines in computational power; they can simulate Turing machines, and vice versa; which leads me to my question:

> Does adding another heap to non-deterministic type-1 min-heap automata make them equivalent in terms of computing ability to Turing machines, in the sense that they are able to simulate Turing machines? If not, does it increase their computational power at all, in the sense that nondeterministic type-1 min-heap automata can accept a set of languages which is a proper subset of $HAL\_1$? If so, does adding additional heaps increase computational power, i.e., can nondeterministic min-heap automata with $k+1$ heaps accept more languages than automata with $k$ heaps, for any $k$?

This is one of the last questions I plan to ask about these automata; if good answers can be had for these (and other) questions, my curiosity will be completely satisfied. Thanks in advance and for all the hard work so far.

# Answer
Although the first answer has already been accepted, I understand that the power of the multiple heap automata described here have not been resolved.

With two heaps, and just a single heap symbol each (apart from the bottom-of-heap), it seems one can simulate a *two-counter automaton*. Such an automaton keeps two natural numbers, that can be incremented, decremented, and tested for zero. You can push and pop, and also test for bottom-of-stack, which is equivalent for zero test. Only two of these are sufficient to simulate a Turing Machine! The proof of this fact is in the first edition of the Hopcroft Ulmann book, Theorem 7.9, but seems originally from Minsky (1961). The many-counter automaton (with zero tests) is equivalent to the notion of register machine.

Thus, if I understand your definition well, the two min-heap version of your $\mathrm{ HAL}$ models are equivalent to $RE$.
> 2 votes

# Answer
Let $\mathrm{SDL}\_k$ the *shuffled Dyck language with $k$ types of parentheses*, i.e.

$\qquad \displaystyle \mathrm{SDL}\_k = \mathrm{DL}(\[\_1,\]\_1) \\, ш\\, \dots \\, ш\\, \mathrm{DL}(\[\_k,\]\_k)$

with $ш$ the shuffle of languages and $\mathrm{DL}(\\\_,\\\_)$ the Dyck language with matching parenthesis as specified. Intuitively, any word in $\mathrm{SDL}\_k$ contains of $k$ properly nested words of parentheses interleaved arbitrarily; for instance, $\[\_3 \[\_1 \[\_1 \[\_3 \[\_2 \]\_1 \]\_3 \]\_2 \[\_1 \]\_1 \[\_2 \]\_1 \]\_3 \]\_2\in \mathrm{SDL}\_3$.

**Fact 0:** $\mathrm{HAL}\_1^{(k)} \subseteq \mathrm{HAL}\_1^{(k+1)}$ for $k\geq 1$

**Claim 1:** $\mathrm{SDL}\_k \in \mathrm{HAL}\_1^{(k)}$ for $k\geq 1$

**Claim 2:** $\mathrm{SDL}\_{k+1} \notin \mathrm{HAL}\_1^{(k)}$ for $k\geq 1$ *(the claim is wrong; see below)*

Together, fact and claims show that $\mathrm{HAL}\_1^{(k)} \subset \mathrm{HAL}\_1^{(k+1)}$ and $\mathrm{HAL}\_1^{(k)} \subset \mathrm{RE}$ for for $k\geq 1$.

---

**Ad Claim 1:** It is clear that $\mathrm{DL}(\[,\]) \in \mathrm{HAL}\_1$; min-heaps can implement a counter that is increased by one on $\[$ and decreased by one on $\]$. A word is accepted if and only if the counter never becomes negative and is zero at the end.

The same principle is used for $\mathrm{SDL}\_k$ on a $k$-heap automaton; we maintain one counter per parenthesis type on a dedicated heap each and accept if and only if no counter becomes negative and all counters are zero at the end.

**Ad Claim 2:** This is more a sketch. In order to accept $\mathrm{SDL}\_{k+1}$ an automaton has to be able to check at any time wether $\]\_i$ is allowed next for any $i=1,\dots,k+1$. As nesting depth and "shuffle depth" are unbounded, finite control can not do this (not even for one parenthesis type). Since a $k$-heap automaton can only access $k$ bits of (heap) information at any time, it has no way of doing the necessary checks.

---

---

Claim 2 is in fact false. We have to be remember that type-1 heap automata can essentially store a *finite* amount of counters but can only access the top most. With two heaps, we can access *all* counters of the first heap: if we want to access counter $i$, move the symbols encoding counters $1,\dots,i-1$ to the second heap, access counter $i$ and move everything back. That leads us to the following claims:

**Claim I:** $\mathrm{HAL}\_1 \subset \mathrm{HAL}\_1^{(2)}$

**Claim II:** $\mathrm{HAL}\_1^{(2)} = \mathrm{HAL}\_1^{(3)} = \dots$

Claim I follows from above reasoning with $\mathrm{SDL}\_2$. Claim II holds because $k$-heap automata can only manage finitely many counters, no matter the $k$, which can be simulated by a $2$-heap automata as outlined above.

This train of thought leads us to

**Claim III:** $\mathrm{HAL}\_1^{(2)} \subset RE$

as Turing machines can handle unbounded numbers of counters, outclassing $2$-heap automata. As a concrete example, consider

$\qquad \displaystyle \mathrm{SDL} = \bigcup\limits\_{k\geq 1} \mathrm{SDL}\_k.$

Note that $\mathrm{SDL}$ can be expressed using a finite alphabet by encoding $\[\_i$ as e.g. $\[\\{\overline{i}\\}$ with $\overline{i}$ the binary representation of $i$ and $\]\_i$ similarly.
> 2 votes

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


title: Is 1-in-k SAT NP-complete for k > 3

text:
# Question
Title: Is 1-in-k SAT NP-complete for k > 3
It is well-known that 1-in-k SAT is NP-complete for k=3. What about for k \> 3?

# Answer
It's still in NP by using a truth assignment as a proof.

You can reduce 1-in-3 SAT to 1-in-$k$ SAT to show hardness as follows. Let $\phi$ be an instance of 1-in-3 SAT with clauses $C\_i$ for $1 \le i \le m$. For each $C\_i$ we define $C\_i'$ by adding $k - 3$ instances of the literal $y$ (where $y$ is a new variable that does not appear in any $C\_i$). We also construct the new clause $C\_{m+1}'$ which has $k-1$ occurences of the literal $y$, and one occurence of the literal $\neg y$. Let $\phi'$ be the instance of 1-in-$k$ SAT with clauses $C\_i'$ for $1 \le i \le m+1$. I claim $\phi'$ is a YES-instance of 1-in-$k$ sat if and only if $\phi$ is a YES-instance of 1-in-3 SAT.

First, assume $\phi'$ is a YES-instance, and choose a satisfying assignment. $C\_{m+1}'$ is satisfied only when $y$ is false, so this assignment has $y$ false. Therefore, the literals $x$ are not satisfied, and so exactly one of the first 3 literals of $C\_i'$ is satisfied for each $i$. These are exactly the literals of $C\_i$, so exactly one of the literals of $C\_i$ is satisfied for each $C\_i$ and so $\phi$ is a YES-instance.

In the other direction, suppose $\phi$ is a YES-instance, and choose a satisfying assignment. Extend this assignment to give $y$ the value falsehood. This assignment shows that $\phi'$ is a YES-instance.

To illustrate the reduction, here is an example (going to 1-in-5 SAT):

$\phi = (x\_1 \vee \neg x\_1 \vee x\_2) \wedge (x\_3 \vee \neg x\_2 \vee \neg x\_2)$

$\phi' = (x\_1 \vee \neg x\_1 \vee x\_2 \vee y \vee y) \wedge (x\_3 \vee \neg x\_2 \vee \neg x\_2 \vee y \vee y) \wedge (y \vee y \vee y \vee y \vee \neg y) $
> 5 votes

---
Tags: complexity-theory, reference-request, np-complete
---


title: Radix sort exercise

text:
# Question
Title: Radix sort exercise
I'm trying to understand a proof regarding radix-sort but to no avail.

I'll first write down a brief summary of the proof and then assign some questions which I hope will be clarified enough.

> Suppose you have an array of integer numbers in the range $\\{0,1,2,\ldots n \log n\\}$. Show and explain an effective algorithm in the worst case which finds out if there are two elements with the same value. note - You can use an extra memory in order of magnitude equals to $O(n)$.

I don't really care about how the algorithm will look like. The idea to this proof is using radix-sort in $O(n)$ and then looking for two elements with the same value as the array is sorted.

**The proof outline:**

Let's suppose we are examining a larger domain which is $\\{0,1,2 ,\ldots n^2 - 1\\}$. Now we'll treat each number according to its binary representation using radix-sort bit by bit.

Right after this, comes the part I can't understand at all....

As we know the order of magnitude of radix-sort is $\Theta(d(n+k))$ and therefore all we have to decide is which a to choose to have order of magnitude equals to $O(n)$.

using the formula $\frac{2\log n}{a} (n + 2^a)$.

After this step, you just choose $a = \log n$ and you are done.

**My questions are:**

1. How did the writer concluded the following formula: $\frac{2\log n}{a} (n + 2^a)$?
2. Also, why do the writer prefer to work on the domain of $\\{0,1,2 ,\ldots n^2 - 1\\}$ instead the one given in the question?

# Answer
1. In the formula $\Theta(d(n+k))$, $d$ is the number of digits (iterations in the sort) and $k$ is the size of the buckets (the base you are working in). So, if you were sorting the numbers 0 through 999 with 10 buckets, there would be $d=3$ iterations (since the numbers have length 3 in base 10) and we would have $k=10$, which is the base.

If we leave the base, $2^a$ to be determined later (I guess by using a power of two we can read a bits and let that determine the bucket), there are $\log\_{2^a}(n^2) = \frac{\log\_2 n^2}{\log\_2(2^a)} = \frac{2 \log n}{a}$ iterations. $k= 2^a$ is just the base. So $d(n+k) = \frac{2 \log n}{a}(n + 2^a)$.
2. The expanded range is to make the math prettier. Above we took $\log n^2$, which worked out nicely to give a constant factor 2 in our assymptotic. If we instead had $\log (n \log n)$, things would not be as nice. It should still work (possibly for a different choice of $a$), and if you're comfortable with big-O work you can do it as an exercise, but the proof is much cleaner when you don't have to argue that $O(\log n + \log \log n) = O(\log n)$.
> 1 votes

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


title: Reducing recursive languages

text:
# Question
Title: Reducing recursive languages
I need a clarification related to the following situation.

Consider a Turing machine $T\_1$ that halts for every input. In other words $J\_1 = L(T\_1) \subseteq \Sigma^\*$ is recursive. Suppose we are given a function $f:\Sigma^\* \mapsto \Sigma^\*$ and a language $J\_2 \in \Sigma^\*$ such that $$ x \in J\_2 \iff f(x) \in J\_1.$$

I would assume this readily implies $J\_2$ is recursive as well since one can create a Turing machine $T\_2$ that on given input $x$ evaluates $y = f(x)$ and simulates $T\_2$ on the given input $y.$ Clearly $L(T\_2) = J\_2.$

What now confuses me is the following.

> Are there any restrictions on $f$ for this ''reduction'' to work?

What is the usual approach here? Is $f$ assumed to be given as a black box that always evaluates $f(x)?$ If so could someone explain the motivation behind this, because it appears to me that it could as well be that $f(x)$ cannot be computed effectively and hence $T\_2$ cannot be constructed in a "feasible" way.

As for the motivation for the question, I would like to show that given $f:\Sigma^\* \mapsto \Sigma^\*$ and a recursive language $L,$ the language $f^{-1}(L)$ is recursive as well.

# Answer
> 4 votes
Reductions are about translating one problem to another. In our case, we *reduce* the question "$x \in J\_2$" to the question "$f(x) \in J\_1$". Naturally, for this to make any sense $f$ has to be computable (otherwise we can reduce anything to anything). But it is also important to pay attention to the totality of $f$.

We normally require that $f$ be total because we do not want to be in a position when the reduction itself never ends. In this case, if $f$ is computable and total, and $J\_1$ is computable, then $J\_2 = f^{-1}(J\_1)$ is computable as well.

Allowing $f$ to be partial might make sense when we are interested in *semi*-deciding whether $x \in J\_2$ because then we might as well allow $f(x)$ to diverge when $x \not\in J\_2$. But this is not usualy done.

# Answer
> 3 votes
The answer is already in your question. One must assume that $f$ is effectively computable, i.e., there is a Turing Machine that, given $x$ (on one tape) computes $f(x)$ (on another tape). It should also halt on every input, but that is implicit in 'computes'.

We need this in order to avoid that $f$ indeed computes an undecidable property of $x$; e.g., when $J\_1 = \Sigma^\*$ and $f:\Sigma^\* \to \\{0,1\\}$ computes the halting problem.

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


title: Show the Language is Recursive

text:
# Question
Title: Show the Language is Recursive
I have devised the following TM for the language EQUAL.

EQUAL accepts all strings with the same number of a's and b's. It is context free but non regular.

Using the TM I devised, how can I show that EQUAL is recursive? How can I show that it crashes when the input is not in EQUAL.

# Answer
> 1 votes
A language is recursive if a Turing Machine decides it: On input *w*, the TM always halts, and accepts if *w* is in the language, and rejects if *w* is not in the language.

So to show that the language is recursive, you just need to show that your Turing Machine gives the correct answer on every input string (accepts if # of a's equals # of b's, rejects otherwise). That will also show that it halts on all inputs, so you're done.

As Hendrik says in the comment, a Turing Machine should have both an accept state and a reject state. (That's what it means to accept/reject -- to enter the appropriate state.)

So first, you'll need to make this change.

Then, to prove your construction correct, you use the following type of proof. First, suppose I have a string $w$ that does have an equal number of a's and b's. Then I will show that, when I feed $w$ into my TM, it halts in the accept state. Second, suppose I have a string $x$ that does *not* have an equal number of a's and b's. Then I will show that, when I feed $x$ into my TM, it halts in the reject state.

You should convince yourself that this proof accomplishes what I said is required above!

**But note** your TM is not quite there yet: Consider what will happen on input string "bbb"!

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


# Question
Title: Computational complexity of the clique problem
What is the best known approximation for the computational complexity of the clique problem? Is it accurate to consider it $O(2^n)$?

# Answer
Wikipedia is usually a good starting reference to well-known problems as the clique. There is a list of the fastest known algorithms for CLIQUE including references.

Apparently, the fastest algorithm we know runs in time $O(1.1888^n)$, so that's the best upper bound on the complexity of CLIQUE we have. As for lower bounds, we don't have a super-polynomial one, or otherwise P=NP? would have been solved.
> 5 votes

---
Tags: complexity-theory, time-complexity, algorithm-analysis
---


title: Why is $3^n = 2^{O(n)}$ true?

text:
# Question
Title: Why is $3^n = 2^{O(n)}$ true?
$3^n = 2^{O(n)}$ is apparently true. I thought that it was false though because $3^n$ grows faster than any exponential function with a base of 2.

How is $3^n = 2^{O(n)}$ true?

# Answer
> 12 votes
With some algebra (and changing the constant in the $O(n)$), we can actually change the bases.

$$3^n = (2^{\log\_2 3})^n = 2^{n\log\_2 3}$$

Since $\log\_2 3$ is a constant, $n\log\_2 3 = O(n)$. So $3^n = 2^{O(n)}$.

I'm not sure what you mean by "$3^n$ grows faster than any exponential function with a base of 2." $2^n = o(3^n)$ of course but it seems you mean something more general. My guess is that your statement applies to something like $O(3^n)$, where you multiply the base by a constant, as opposed to $2^{O(n)}$ where you multiply the number in the exponent by a constant.

# Answer
> 8 votes
> $3^n$ grows faster than any exponential function with a base of $2$.

True. This implies that $3^n = O(2^n)$ cannot be true. But what you have here is $2^{O(n)}$.

Recall that $O(f(n))$ is really a set of functions, and strictly speaking we should be writing $3^n \in 2^{O(n)}$ (or even $(n \mapsto 3^n) \in 2^{O(n \mapsto n)}$). The right-hand side is not the exponential of a function, but the exponential of a set of functions. Expanding the definition of big oh:

$$ 2^{O(n)} = 2^{\\{f \\;\mid\\; \exists N, \exists p, \forall n \ge N, f(n) \le p n\\}} = \\{(n \mapsto 2^{f(n)}) \mid \exists N, \exists p, \forall n \ge N, f(n) \le p n\\} $$

Since the exponential function $n \mapsto 2^n$ is increasing, we can lift the inequality out of the exponential:

$$ 2^{O(n)} = \\{g \mid \exists N, \exists p, \forall n \ge N, g(n) \le 2^{p \\, n}\\} $$

Contrast with $$ O(2^n) = \\{g \mid \exists N, \exists k, \forall n \ge N, g(n) \le k \\, 2^{n}\\} $$

In $2^{O(n)}$, the multiplicative constant is inside the exponential. In $O(2^n)$, it is multiplied by the exponential. $2^{p \\, n} = 2^p 2^n$, so we have (for any $n \ge 0$) $3^n \le 2^{\log\_2 3} 2^n$, i.e. we can take $N = 0$ and $p = \log\_2 3$, showing that $3^n \in 2^{O(n)}$.

# Answer
> 4 votes
$3^n=2^{O(n)}$ is in fact true because if you recall $O(n)$ definition you will see that you can add/multiply by any constant. So:

$3^n \< 2^{kn}$ // $ \log\_2 $

$n\log\_2(3^n) \< kn\log\_2(2)$

$k \> \log\_2(3) $

So as you can see $2^{kn}$ is bigger then $3^n \iff k \> \log\_2(3)$

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


title: String similarity problem

text:
# Question
Title: String similarity problem
> We are given two strings $x=x\_1,x\_2,x\_3,\ldots,x\_m$ and $y=y\_1,y\_2,y\_3,\ldots,y\_n$ over some finite alphabet. We consider the problem of converting $x$ to $y$. Using the following operations:
>
> 1.Substitution: replace one symbol by another one.
>
> 2.Insertion: inserts one symbol
>
> 3.Deletion: delete one symbol.

For example, if $x$="logarithm" and $y$="algorithm", we convert $x$ to $y$ in the following way:

1. start with "logarithm"
2. inserting "a"at the front gives "alogarithm".
3. deleting "o"gives "algarithm"
4. replacing the second "a"by "o"gives "algorithm".

The similarity problem between the string $x$ and $y$ is defined to be the minimum number of operations needed to convert $x$ to $y$.

For example, the similarity between $x$="logarithm" and $y$="algorithm" is 3, because $x$ can be converted to $y$ using three operations. If the string $x$ has length $m$ and the string $y$ is empty, then the similarity between $x$ and $y$ is similar to $m$.

Give a dynamic programming algorithm (in pseudocode) that computes, in $\mathcal o(mn)$ time, the similarity between the string $x$ and $y$.

It is as the edit distance problem but there is the corresponding minimization problem problem where we measure similarity instead of distance .

# Answer
Just like @Hendrik mention all you need to do is calculate Levenshtein distance which does exactly what you need.

Levenshtein distance can be expressed in following formulae $$ \mbox{lev}\_{a,b}(i, j) = \begin{cases} \max(i,j) &, \mbox{if } \min(i,j) = 0 \\ \min \begin{cases} \mbox{lev}\_{a,b}(i-1,j) +1 \\ \mbox{lev}\_{a,b}(i, j-1)+1 \\ \mbox{lev}\_{a,b}(i-1,j-1) +\[a\_i \neq b\_i\] \end{cases} &, \mbox{else} \end{cases} $$ Where $a, b$ are compared strings, $i, j$ are strings length and $\[a\_i \neq b\_i\]$ is $1$ iff $a\_i \neq b\_i$ and $0$ otherwise.

From this formula it can be easy translated to pseudocode.

```
Lev(a, b)
  len_a = len(a)
  len_b = len(b)
  cost = 0

  if(a[0] != b[0])
    cost = 1

  if (len_a == 0 or len_b == 0)
    return max(len_a, len_b)
  return min(Lev(a[1..len_a-1], b) + 1,
             Lev(a, b[1..len_b-1]) + 1,
             Lev(a[1..len_a-1], b[1..len_b-1]) + cost)

```

However there is small problem with this solution, its running time is $\mathcal O(nm)$ and you requested $\mathcal o(nm)$ so I hope you just made a typo.

You can also calculate this distance online using this website.
> 2 votes

---
Tags: algorithms, reference-request, dynamic-programming, strings
---


# Question
Title: Prove the following problem is NL-complete
Suppose $$A = \left\\{\langle G, d, s, t\rangle \\;\Bigg|\\; \begin{array}{l} \text{\\(G\\) undirected}, \\ \text{\\(s\\) and \\(t\\) are nodes in \\(G\\)}, \\ \text{there is a path of length \\(d\\) from \\(s\\) to \\(t\\) and no path of shorter length} \end{array}\right\\}$$ I can easily see that this language is in NL, but I am having trouble proving that this is NL-complete.

# Answer
Let $G'$ be the graph with self-loops added to every vertex. Take $n$ copies $G'\_1,G'\_2,\ldots,G'\_n$ (without the edges) and connect $x \in G'\_i$ to $y \in G'\_{i+1}$ if $(x,y) \in G'$. The shortest path between $s \in G'\_1$ and $t \in G'\_n$, if any exists, is now of length exactly $n-1$.
> 3 votes

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


title: Closure properties of languages

text:
# Question
Title: Closure properties of languages
> Let $P$ be a regular language and $Q$ be a context-free language such that $Q \subseteq P$(For example, let $P = a^\*b^\*$ and $Q = \\{ a^nb^n | n \ge 0\\}$). Then which of the following is always regular?
>
> 1. $P \cap Q$
> 2. $P - Q$
> 3. $\Sigma^\* - Q$
> 4. $\Sigma^\* - P$

**Option 1**
$P \cap Q = Q$ as $P \subseteq Q$. Thus $P \cap Q$ is context-free.

**Option 2**
I was not able to generally reason here. I used the example mentioned in the question.
Let $P = a^\*b^\* $ and $Q = \\{ a^nb^n | n \ge 0\\}$.
$P - Q = \\{a^nb^m | n \neq m\\}$ which is not regular but only context-free.

**Option - 3**
Let $\Sigma = \\{ a, b\\}$ and $Q = \\{ a^nb^n | n \ge 0\\}$.
Again $\Sigma^\* - Q = \\{a^nb^m | n \neq m\\} $ which is not regular but only context-free.

Thus, the 4th option must be right, $\Sigma^\* - P$ is regular. I am however unable to understand this result intuitively. Could somebody explain?

# Answer
I got it on further thought. It is trivial. $\Sigma^\* - P$ is $P'$, the complement of P and this is regular. I was unnecessarily concentrating on how $Q \subseteq P$ would play a role. It doesn't actually.
> 3 votes

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


title: Finding nested intervals efficiently

text:
# Question
Title: Finding nested intervals efficiently
The intervals are represented as two numbers, e.g. $(4.3, 5.6)$. The intervals are unique.

If for $(x,y)$ and $(u,v)$, $x≤u$ and $v≤y$, $(u,v)$ is nested in $(x,y)$

How do I find out which intervals are nested in others efficiently?

The hint is to use two induction hypotheses: one to assume you can solve the problem for $n-1$ intervals, another that you can find the largest right endpoint for the $n-1$ intervals.

How do I use this information to do the inductive step in constant time?

# Answer
> 2 votes
A solution must look like this: we have list of intervals and we must tell for a new interval which of the intervals contain it and which of the list are contained in the new interval.

A logical start will be that the list of intervals are sorted in some data structure and we need to add the new interval in its proper place. In the general case an insertion into some sorted list can be done in time complexity $O(log n)$, when using self-balancing binary search tree for example.

I am not sure if for the general case it is possible to reach $O(1)$ time. However to beat the logarithmic time you may need to add some limitations. It is clear that for the insertion we **must not use comparison**. One limited solution can be done by using modified counting sort. This however will work only if we know that the interval's points are limited to positive integer values in some interval(you can enhance the solution to work for sets that are countable and finite, if you assume that you don't have infinite memory).

Example: If we have $n=4$ the following list $(1, 8), (3, 6), (2, 3)$ and you want to add a new interval $(4, 5)$

We can order them in **array with size $n$ X largest right endpoint**: in the first row we place interval's IDs in the cell with the number of the start/end point. If this cell already has an ID we are using the cell in the bottom row. We can keep a counter to the fullness level of each column.

We can add the same way the new interval in $O(1)$ time and have the intervals ordered by their nesting again in **constant time**.

Here is some pseudo code of the operaion in the n-th step:

```
Input:new_interval = (x,y)
    array[x][x_column_counter] = new_interval_id
    array[y][y_column_counter] = new_interval_id
    y_column_counter++
    x_column_counter++

```

# Answer
> 4 votes
This problem is as hard as comparison sorting, given `n` input number sort them.

You can make interval set from input number set $S$ (w.l.o.g suppose input numbers are in $Z^+$) as follow:

$ \Gamma = \\{(a,b) \mid a\in S \wedge b=\max\_{t\in S} \\{2\cdot t - a + 1 \\} \\}$

Above transformation can be done in $O(n)$.

But if you find a nesting relation in this interval set in $o(n \log n)$, you can sort input array in $o(n \log n)$, But comparison sorting barrier is $\Omega(n \log n)$, So the algorithm which finds interval nesting cannot be better than $\Omega(n \log n)$ with respect to comparision sorting barrier, But also $O(n \log n)$ algorithm is trivial.

---
Tags: algorithms, induction
---


# Question
Title: Efficient algorithm for a modified stack to pop the smallest element
I was practicing the following problem :

> There are a total of $N$ operations. At each operation, you can either add an element to the top or remove several elements as described below.
>
> Inputs are integers. An input other than $-1$ indicates that we have to add the elements in last in first out fashion (LIFO). If the input is $-1$, then we have to remove (pop) all the elements that lie above the current minimum element of the stack, and then pop that minimum element.
>
> For each $-1$ in the inputs, print $(m,p)$ where $m$ is the minimum element on the stack and $p$ counts how many total elements we popped from the stack.

Example :

```
N=14 (Total 4 operations)
9
6
8
-1
2
0
6
-1
3
1
2
10
5
-1

In above example : First three operation is inserting operation ,
that is we need to insert them in LIFO Fashion.
So the stack after third operation is : [9  6   8*]
    PLEASE NOTE * represent the element at the top  of the stack.
Fourth Operation is -1 , that is we have to remove all elements
(including the minimum ) , that lie above the minimun elements.
The Minimum Element is 6 ,so we remove 8 and 6 and Hence the stack now is :
[9*]
So answer for fourth operation is (6,2)
6 - the minimum element in the stack and 2 ,as we removed
total 2 elements from the stack.

Operation 5 th ,6 th and 7th are Inserting operations.
After 4 th operation , the stack was [9*]
After 7th operation , the stack looks like [9 2 0 6*]
8th operation is -1 . Minimum element is 0 ,so we should remove 0,6
    from the stack
Hence Answer is (0,2)
As the minimum element is "0" and we removed total "2" elements from
    the stack.

The  stack at the end of eighth operation is:
[9 2]

Operation 9 ,10 ,11 12,13  are inserting operations
So Stack after 13th operation is:
[9 2 3 1 2 10 5* ]
operation 14 is -1.
The minimum element  in the stack is 2. However 2 lies at two
    different positions in the stack .
But we should remove that  2 , which is nearest to the top of the stack
(In order word ,if the minimum lies at more than two positions in the
    stack ,then the one which is closer to the top of the
stack is considered).
So remove 2 at Index 5 (as it is closer to the top of stack) and element
that lies above it in stack.
So after removing 2(the minimum element ) and 10,5 (the elements above
    the min element)
The stack looks like:
[9 2 3 1*]
    Answer is (2,3) //As 2 is the min element and we popped "3" elements

PLEASE NOTE * represent the element at the top  of the stack.

```

## My approach

I am using a simple stack for the above problem. But the constraint is high: $1 \le N \le 10^6$. There are many $-1$'s in the input, so a simple stack will work very slowly. The time limit for the problem is just 1 second.

# Answer
You can simply push elements to the stack only if they are smaller than the element on the top of the stack.If they are bigger you will count them in different counter in order to know how much elements were pushed and keep those counters in another stack. When you have to pop you will pop only the top element.

Here is sample pseudo code (some check for empty stacks and initial values are omitted):

```
    input: element
    // stack.peak() - gets top element without popping it
    if (element == -1)
        top = stack.pop()
        print(top, (counter_stack.pop() +1))

    if (element > stack.peak())
        count = counter_stack.pop()
        counter_stack.push(count+1)
    else
        stack.push(element)
        counter_stack.push(0)

```

Here is what should this look for your example:

```
9
stack: [9*]
counter_stack: [0]
6
stack: [9 6*]
counter_stack: [0 0]
8
stack: [9 6*]
counter_stack: [0 1*]
-1
stack: [9 6*]
counter_stack: [0]

print : 6(the popped value), 2 (counter_stack popped +1)

2
stack: [9*]
counter_stack: [0 0]
0
stack: [9 2 0*]
counter_stack: [0 0 0]
6
stack: [9 2 0*]
counter_stack: [0 0 1]
-1
stack: [9 2*]
counter_stack: [0 0]
print : 0(the popped value), 2 (counter_stack popped +1)

3
stack: [9 2*]
counter_stack: [0 0 1*]
1
stack: [9 2 1*]
counter_stack: [0 1 0*]
2
stack: [9 2 1*]
counter_stack: [0 1 1*]
10
stack: [9 2 1*]
counter_stack: [0 1 2*]
5
stack: [9 2 1*]
counter_stack: [0 1 3*]

-1
stack: [9 2*]
counter_stack: [0 1]
print : 1(the popped value), 4 (counter_stack popped +1)

and so on.

```
> 4 votes

---
Tags: algorithms, arrays, stacks
---


# Question
Title: How to find contour lines for Appel's Hidden Line Removal Algorithm
For fun I am trying to make a wire-frame viewer for the DCPU-16. I understand how do do everything except how to hide the lines that are hidden in the wire frame. All of the questions here on SO all assume you have access to OpenGL, unfortunately I do not have access to anything like that for the DCPU-16 (or any kind of hardware acceleration).

I found a fairly good description of Appel's algorithm on Google Books. However there is one issue I am having trouble figuring out.

> Appel defined contour line as an edge shared by a front-facing and a back-facing polygon, or unshared edge of a front facing polygon that is not part of a closed polyhedron. An edge shared by two front-facing polygons causes no change in visibility and therefore is not a contour line. In Fig. 8.4, edges AB, EF, PC, GK and CH are contour lines, whereas edges ED, DC and GI are not.

I understand the rules of the algorithm and how it works once you have your contour lines, however I do not understand is what I need to do to determine if a edge is "*shared by a front-facing and a back-facing polygon, or unshared edge of a front facing polygon that is not part of a closed polyhedron*" from a coding point of view. I can look at a shape and I can know what lines are contour lines in my head but I don't have a clue on how to transfer that "understanding" in to a coded algorithm.

---

## Update

I have made some progress in determining contour lines. I found these two lecture notes from a University of Buffalo class on computer graphics.

> Consider the edges. These fall into three categories.
>
> 1. An edge joining two invisible faces is itself invisible. This will be deleted from the list and ignored.
> 2. An edge joining two potentially-visible faces is called a 'material edge' and will require further processing.
> 3. An edge joining a potentially-visible face and an invisible face is a special case of a 'material edge' and is also called a 'contour edge'.

Using the above two pieces of information I am able to get closer to being able to write this out as code, but I still have a long way to go.

# Answer
For the "-facing" rule to hold, you must make sure that all faces are properly oriented. Use the right-hand rule for instance, that means that the vertices of a face should be numbered in such a way that a positive rotation in the plane of the face corresponds to a normal pointing outside of the polyhedron. (Got it ?) Or more simply, every face must come with its outward-pointing normal.

Dangling faces, i.e. not belonging to a closed polyhedron can be seen as having an undeterminate orientation.

Now computing the parts of an edge which are hidden by a contour polygon is the main course. This problem is very close to that of clipping a line segment by a polygonal window in 2D. First consider the line of support of the line segment and find intersections with the polygon. By using a parity rule, you can easily determine the parts inside and outside the polygon.
> 3 votes

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


title: Reducing Clique to Independent Set

text:
# Question
Title: Reducing Clique to Independent Set
The Clique problem takes a graph $G = (V,E)$ and an integer $k$ and asks if $G$ contains a clique of size $k$. (A clique is a set of vertices such that every pair of vertices in the set is adjacent.) The Independent-Set problem takes a graph $G’ = (V’,E’)$ and an integer $k’$ and asks if $G’$ contains an independent set of size $k’$. (An independent set is a set of vertices such that no pair of vertices in the set is adjacent.)

1. Give a polynomial time algorithm that, given a graph $G$ and an integer $k$ produces a graph $G’$ and an integer $k’$ such that $G$ has a clique of size $k$ if and only if $G’$ has an independent set of size $k’$. Justify your answer.
2. Use 1. to prove that the Independent-Set problem is NP-Complete given that the Clique problem is NP-Complete.

# Answer
The trick is to realize that if a graph has a clique of size $k$, the inverse graph has an independent set of size $k$. A clique of size $k$ means that $k$ nodes all have edges in between them. In the inverse graph these $k$ nodes are not (directly) connected and can be used to create an independent set of size $k$

Hence, the polynomial time algorithm you are looking for is merely the one that inverts the graph.

You will find a youtube explanation here.

I suspect that if you try to draw some very simple graphs with cliques and the inverses of said graphs you will realize why this is true.

As for (2), you need to show that an algorithm to the independent set problem can be used to solve the clique problem. Furthermore you need to show that using the solution to the independent set problem can be used to find the solution to the clique problem in polynomial time. This proves the following:

You can now reduce the clique problem to independent set. As all problems in NP can be reduced to the clique problem (the definition of clique being in NPC) all problems in NP can be reduced to independent set too and so it is in NPC. And since you reduced clique to independent set in polynomial time it cannot be harder than the clique problem either.

So (2) is equivalent to the following: If you were given a polynomial time algorithm for the independent set problem, how would you use it to find out whether a graph had a clique of size $k$?
> 13 votes

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


title: How is this grammar LL(1)?

text:
# Question
Title: How is this grammar LL(1)?
This is a question from the Dragon Book. This is the grammar:

> $S \to AaAb \mid BbBa $
> $A \to \varepsilon$
> $B \to \varepsilon$

The question asks how to show that it is LL(1) but not SLR(1).

To prove that it is LL(1), I tried constructing its parsing table, but I am getting multiple productions in a cell, which is contradiction.

Please tell how is this LL(1), and how to prove it?

# Answer
First, let's give your productions a number.

> 1 $S \to AaAb$
> 2 $S \to BbBa$
> 3 $A \to \varepsilon$
> 4 $B \to \varepsilon$

Let's compute the first and follow sets first. For small examples such as these, using intuition about these sets is enough.

$$\mathsf{FIRST}(S) = \\{a, b\\}\\ \mathsf{FIRST}(A) = \\{\\}\\ \mathsf{FIRST}(B) = \\{\\}\\ \mathsf{FOLLOW}(A) = \\{a, b\\}\\ \mathsf{FOLLOW}(B) = \\{a, b\\}$$

Now let's compute the $LL(1)$ table. By definition, if we don't get conflicts, the grammar is $LL(1)$.

```
    a | b |
-----------
S | 1 | 2 |
A | 3 | 3 |
B | 4 | 4 |

```

As there are no conflicts, the grammar is $LL(1)$.

Now for the $SLR(1)$ table. First, the $LR(0)$ automaton.

$$\mbox{state 0}\\ S \to \bullet AaAb\\ S \to \bullet BbBa\\ A \to \bullet\\ B \to \bullet\\ A \implies 1\\ B \implies 5\\ $$$$\mbox{state 1}\\ S \to A \bullet aAb\\ a \implies 2\\ $$$$\mbox{state 2}\\ S \to Aa \bullet Ab\\ A \to \bullet\\ A \implies 3\\ $$$$\mbox{state 3}\\ S \to AaA \bullet b\\ b \implies 4\\ $$$$\mbox{state 4}\\ S \to AaAb \bullet b\\ $$$$\mbox{state 5}\\ S \to B \bullet bBa\\ b \implies 6\\ $$$$\mbox{state 6}\\ S \to Bb \bullet Ba\\ B \to \bullet\\ B \implies 7\\ $$$$\mbox{state 7}\\ S \to BbB \bullet a \\ a \implies 8\\ $$$$\mbox{state 8}\\ S \to BbBa \bullet \\ $$

And then the $SLR(1)$ table (I assume $S$ can be followed by anything).

```
    a     | b     | A | B |
---------------------------
0 | R3/R4 | R3/R4 | 1 | 5 |
1 | S2    |       |   |   |
2 | R3    | R3    | 3 |   |
3 |       | S4    |   |   |
4 | R1    | R1    |   |   |
5 |       | S4    |   |   |
6 | R4    | R4    |   | 7 |
7 | S8    |       |   |   |
8 | R2    | R2    |   |   |

```

There are conflicts in state 0, so the grammar is not $SLR(1)$. Note that if $LALR(1)$ was used instead, then both conflicts would be resolved correctly: in state 0 on lookahead $a$ $LALR(1)$ would take R3 and on lookahead $b$ it would take R4.

This gives rise to the interesting question whether there is a grammar that is $LL(1)$ but not $LALR(1)$, which is the case but not easy to find an example of.
> 11 votes

# Answer
If you are not asked, you don't have to construct the LL(1) table to prove that it is an LL(1) grammar. You just compute the FIRST/FOLLOW sets as Alex did:

$\qquad \begin{align} \operatorname{FIRST}(S)&={a,b} \\ \operatorname{FIRST}(A)&={ε} \\ \operatorname{FIRST}(B)&={ε} \\ \operatorname{FOLLOW}(A)&={a,b} \\ \operatorname{FOLLOW}(B)&={a,b} \end{align}$

And then, by definition an LL(1) grammar has to:

1. If $A \Rightarrow a$ and $A \Rightarrow b$ are two different rules of the grammar, then it should be that $\operatorname{FIRST}(a) \cap \operatorname{FIRST}(b) = \emptyset$. Hence, the two sets haven't any common element.
2. If for any non-terminal symbol $A$ you have $Α \Rightarrow^\* ε$, then it should be that $\operatorname{FIRST}(A) \cap \operatorname{FOLLOW}(A) = \emptyset$. Hence, if there is a zero production for a non-terminal symbol, then the FIRST and FOLLOW sets can't have any common element.

So, for the given grammar:

1. We have $\operatorname{FIRST}(AaAb) \cap \operatorname{FIRST}(BbBa) = \emptyset$ since $\operatorname{FIRST}(AaAb) = \\{a\\}$ while $\operatorname{FIRST}(BbBa) = \\{b\\}$ and they don't have any common elements.
2. $\operatorname{FIRST}(A) \cap \operatorname{FOLLOW}A) = \emptyset$ since $\operatorname{FIRST}(A) = \\{a,b\\}$ while $\operatorname{FOLLOW}(A) = \emptyset$, and now $\operatorname{FIRST}(B) \cap \operatorname{FOLLOW}(B) = \emptyset$ since $\operatorname{FIRST}(B) = \\{ε\\}$ while $\operatorname{FOLLOW}(B) = \\{a,b\\}$.

As for the SLR(1) analysis I think it is flawless!
> 10 votes

# Answer
Search for a sufficient condition which makes a grammar LL(1) (hint: look at the FIRST sets).

Search for a needed condition which all SLR(1) grammars must meet (hint: look at the FOLLOW sets).
> 0 votes

---
Tags: formal-grammars, compilers, parsers
---


title: What is a linearization point?

text:
# Question
Title: What is a linearization point?
With respect concurrent programming, what is a linearization point?

They seem to occur at a compare-and-swap instruction apparently. The best definition I could find is here.

> All function calls have a linearization point at some instant between their invocation and their response.

Okay that's fine, they occur somewhere within a function call, but what are they?

> All functions appear to occur instantly at their linearization point, behaving as specified by the sequential definition.

Occur instantly at their LP's??? I don't understand this.

I also read through this which attempts to prove LP's. I am having trouble finding any solid definitions. Could anyone help?

# Answer
> 11 votes
Sounds like you are reading The Art of Multiprocessor Programming.

> "All function calls have a linearization point at some instant between their invocation and their response"
>
> > Okay that's fine, they occur somewhere within a function call, but what are they?

Side effects of the functions. http://en.wikipedia.org/wiki/Side\_effect\_(computer\_science):

> A function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world.

In C/C++ side effects are basically writing to memory that is not on the function stack.

> "All functions appear to occur instantly at their linearization point, behaving as specified by the sequential definition"
>
> > Occur instantly at their LP's??? I don't understand this.

It means that memory writes become visible to other CPUs in the system at that point. Imagine a function of 100 instructions. Instruction 90 is CAS which is a linearization point. Once the instruction has completed the effects of preceding memory writes become visible to other CPUs instantly (release semantics). This happens some time after the function has been called but before it returned (on instruction 90 of 100).

Note, that memory writes may not always be visible to other CPUs in the system if linearization points are not employed.

---
Tags: semantics, concurrency, synchronization
---


# Question
Title: How is verifying whether an assignment satisfies a boolean formula possible in polynomial time?
How can I prove that I can verify whether a boolean assignment of variables $a$ satisfies some boolean formmula $\phi$ in polynomial time?

I know that we can just plug the boolean assignment into the formula, but this seems to be a very high-level description, and I am not sure that it is a reliable one since we must simplify the formula.

# Answer
There is no need to simplify the formula, you just evaluate it recursively according to the definition of the boolean operators in use.

Let $\varphi$ a boolean formula and $a : X\_\varphi \to \\{0,1\\}$ an assignment of all variables that occur in $\varphi$. Now we define the evaluation function $\operatorname{eval}\_a$ on variable-free boolean expressions in the following way:

$\qquad \begin{align} \operatorname{eval}\_a(\text{true}) &= 1 \\ \operatorname{eval}\_a(\text{false}) &= 0 \\ \operatorname{eval}\_a(x) &= a(x) \\ \operatorname{eval}\_a(\lnot \varphi) &= 1 - \operatorname{eval}\_a(\varphi) \\ \operatorname{eval}\_a(\varphi \land \psi) &= \operatorname{eval}\_a(\varphi) \cdot \operatorname{eval}\_a(\psi) \\ \operatorname{eval}\_a(\varphi \lor \psi) &= \max(\operatorname{eval}\_a(\varphi), \operatorname{eval}\_a(\psi)) \\ & \vdots \end{align}$

Clearly, $\operatorname{eval}\_a(\varphi) = 1$ if and only if $a(\varphi) \mathop{|\\!\\!\\!==\\!\\!\\!|} \text{true}$ (here, $a$ is continued on $\varphi$ in a syntactical manner: it replaces all variable occurrences $x$ in $\varphi$ with $a(x)$). If in doubt, perform a structural induction along the inductive definition of boolean formulae. Furthermore, $\operatorname{eval}\_a$ performs about one operation per operator and literal; thus it runs in time $O(|\langle \varphi \rangle|)$.
> 11 votes

---
Tags: complexity-theory, logic, satisfiability
---


# Question
Title: Static access pattern in Distributed Databases
> The access patterns of user requests may be **static**, so that they do not change over time, or dynamic. It is obviously considerably easier to plan for and manage the **static** environments than would be the case for dynamic distributed systems. Unfortunately, it is difficult to find many real-life distributed applications that would be classified as **static**. The significant question, then, is not whether a system is static or dynamic, but how dynamic it is. Incidentally, it is along this dimension that the relationship between the distributed database design and query processing is established.

What does it mean for an access pattern to be “static”? Could you show a practical example of a static access pattern?

# Answer
> 0 votes
I found what you copied in the following text

The idea is that users access (querying, updating or etc ..) of the database changes with time. It may be at its peaks in sale seasons for example if the database belongs to a commercial applications. etc .. - if it is always fixed and predicted then it is static.

From your copied text: it says that: "it is difficult to find many real-life distributed applications that would be classified as static. The significant question, then, is not whether a system is static or dynamic, but how dynamic it is." --

perhaps, a static access pattern is a collection of sensor nodes that update the database with their readings in a periodic time, with equal size updates always. -- or a set of servers that get a synchronization clock in a periodic manner (quite theoritical i guess)

---
Tags: distributed-systems, databases
---


# Question
Title: Calculating Binet's formula for Fibonacci numbers with arbitrary precision
Binet's formula for the nth Fibonacci numbers is remarkable because the equation "converts" via a few arithmetic operations an irrational number $\phi$ into an integer sequence. However, using finite precision arithmetic, one would always have some (small) roundoff error.

> Is there a discussion/description somewhere of how to calculate the Fibonacci sequence using Binet's formula (ie *not* the recurrence relation) and floating point arithmetic which results in no roundoff error?

# Answer
As the comments show, roundig is a respected method for Fibonacci computations. See also "Computation by rounding" in the wiki-lemma.

You avoid roundoff by computing exactly, but using numbers of the form $a+b\sqrt5$: $(a+b\sqrt5)(c+d\sqrt5) = (ac+5bd)+(ad+bc)\sqrt5$. Technically that is $Z\[\sqrt5\]$ I believe. But I now realise that you also have to take into account that $a,b$ are fractions.

But the recursion is so nice, why not use it? Based on the matrix form you can get the $n$-th Fibo number in a logarithmic number of steps.
> 4 votes

---
Tags: algorithms, discrete-mathematics, floating-point, arithmetic, mathematical-programming
---


# Question
Title: Doubt regarding cache hit ratios and access time
**Question 1:** What is the average access time for a 3-level memory system with access time $T\_1$, $2T\_1$ and $3T\_1$? (Hit ratio $h\_1$ = $h\_2$ = 0.9)

The solution given is: $0.9\[T\_1\] + 0.1(0.9\[2\*T\_1\] + 0.1\[3\*T\_1\]) = 1.11\[T\_1\]$ **(Method 1)**

Here, they have considered the page won't be copied to the lower level. Otherwise, it would have been like the following

`If a page is not there in cache, it would be copied from main memory to cache and then accessed.` $T\_1 + 2T\_1$

`If a page is not there even in main memory, it would be brought to main memory, then cache and then accessed.` $T\_1 + 2T\_1 + 3T\_1$

$0.9\[T\_1\] + 0.1(0.9\[T\_1+2\*T\_1\] + 0.1\[T\_1 + 2\*T\_2 + 3\*T\_1\]) = 1.23\[T\_1\]$ **(Method 2)**

I went through another similar problem.

**Question 2**

```
Cache Access Time = 20ns
Memory Access Time = 120ns
Hit Ratio = 0.8
Some other useless information below...
Cache Block size = 16 words
Set size = 2 blocks
Number of sets = 128
Size of main memory address = 21bits
What is the hit ratio if the average access time is increased by 40ns?
(A) Remains same      (B) 0.921     (C) 0.467      (D) 0.592

```

I simply calculated it using **Method 1** as follows

```
Effective access time = 0.8*20 + 0.2*(120) = 40ns
Increase by 40ns, so new time = 80ns
80 = h*20 + (1-h)*120
Hit ratio = 0.4

```

But this is not in the options

But when I calculated it using **Method 2**

```
Effective access time = 0.8*20 + 0.2*(20 + 120) = 44ns
Increase by 40ns, so new time = 84ns
84 = h*20 + (1-h)*120
Hit ratio = 0.467

```

That is option (C)

Here, the answer is coming using Method 2 but in the above question they are using Method 1.

**How do I know which method to take while solving such problems? Whether would the missed page be brought into the lower memory (cache) or not?**

# Answer
> 2 votes
I think, that the part `with some other useless information...` in your problem specification must contain some information on solving your problem. As I was trying to calculate the numbers that you got I found some errors, and I thought there must be some more input. Let me first explain:

Your formulas are incorrect for both `Method 1` and `Method 2`. When accessing some memory level you ALWAYS access this level, not with probability! Explanation goes something like this: You ACCESS $L1$, if you MISS (some probability), you go to $L2$. On $L2$ you again make an ACCESS, and if you MISS (with some probability), you move to $L3)...

So `Method 1` with your first problem would be: $$\[T1\]+0.1(\[2\*T1\]+0.1\*\[3\*T1\])=1.23\[T1\]$$

And `Method 2` for first problem: $$\[T1\]+0.1(\[T1+2\*T1\]+0.1\[T1+2∗T1+3∗T1\])=1.36\[T1\]$$

So now looking at your second problem, you can solve it by using `Method 1`:

**New Method 1**

```
Effective access time = 20 + 0.2*(120) = 44ns
Increase by 40ns, so new time = 84ns
84 = 20 + (1-h)*120
Hit ratio = 0.467

```

Note that here I assumed you made a mistake with answer $(C)$ in your problem description (it is not $0.4467$, but it is $0.467$).

Now if you would have miss penalties defined in your problem statement, then you would use `Method 2`. Miss penalty just says, that if you do not get a result in your current level, then you have to copy it from the upper level. Now let us assume, that miss penalty on second level is 300ns (that means copying the contents to level 1 and accessing it). Everything else stays the same. The calculations would go:

**New Method 2**

```
Effective access time = 20 + 0.2*(120+0.2*300) = 56ns
Increase by 40ns, so new time = 96ns
96 = 20 + (1-h)*(120+(1-h)*300)
Hit ratio = 0.65840

```

One other caution... You need to use the same formula for calculating the average access time if you chose one method. (In your `Method 2` you calculated access time by `Method 2` and then calculated the new hit ratio with `Method 1`)

So how do you know which method to choose? From the problem description! If you have miss penalty given, then you take the second approach. If you do not have miss penalty, then you use the first approach.

# Answer
> 0 votes
It's a design choice for the cache. So if you are designing a cache, do both and examine the consequence in term of performance, complexity of the design and other impacts in order to make your choice.

If you are trying predicting for a given cache, look at its spec.

And note anyway that cache have often a more complex behavior than that so whatever is your result, don't take it for an absolute truth, there are factors you aren't taking into account with such a simple minded computation (grace buffers, prefetch, bus contention, ...)

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


title: What exactly is a clique cover problem?

text:
# Question
Title: What exactly is a clique cover problem?
I am really confused about clique problem and clique cover problem. I tried googling it,but I don't see to be able to visualise the clique cover problem.

# Answer
> 6 votes
A clique is a simple undirected graph with all of the possible edges. It is also known as a complete graph, but clique is more often used to referring to subgraphs that are complete graphs.

The clique cover problem asks whether a graph's vertices can be partitioned into $k$ or fewer sets such that each set of vertices induces a clique. That is, $V = V\_1 \cup V\_2 \cdots \cup V\_k$ such that if $u, v \in V\_i$ then $uv \in E$. For example, $C\_4$ (a cycle of 4 vertices) can be partitioned into 2 cliques by choosing two non-adjacent edges. If the vertices were 1, 2, 3, 4 and the edges 12, 23, 34, 14, then we could write $V = \\{1,2\\} \cup \\{3,4\\}$, and check that $12$ and $34$ were edges as required.

This is different from the clique problem, which asks whether there is a clique in the graph of size at least $k$ (and does not care about the structure of the rest of the graph. For example, in $C\_4$, there is a clique of size 2.

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


title: How partitioning in map-reduce work?

text:
# Question
Title: How partitioning in map-reduce work?
Assume a map-reduce program has $m$ mappers and $n$ reducers ($m \> n$). The output of each mapper is partitioned according to the key value and all records having the same key value go into the same partition (within each mapper), and then each partition is sent to a reducer. Thus there might be a case in which there are two partitions with the same key from two different mappers going to 2 different reducers. How to prevent this from occurring? That is, how to send all partitions (from different mappers) with the same key to the same reducer?

# Answer
Let's take a simple example, Counting word into a distributed set of documents:

each mapper takes in input a list of document, and returns a list of pairs word and how many times this word occurs. There is an intermediate layer that takes the outputs of all the mapper and groups values by key. After that the reducer will sum each of this value. This is a practical example:

Output of 3 mappers

1. **Mapper1** (house,4) (dog,2) (cat,1)
2. **Mapper2** (dog,3)
3. **Mapper3** (cat,5) (house,6)

before give these data to the reducer the intermediate layer will group them by key. obtaining :

* (house, (6,4))
* (dog,(3,2))
* (cat,(5,1))

After that reducers take in input these pairs and sum values:

1. **Reducer 1** (house ,(6,4))-\> (house,10)
2. **Reducer 2** (dog,(3,2)) -\> (dog,5) (cat,(5,1)) -\> (cat,6)

The MapReduce idea comes from a paper by google that you can find here: http://research.google.com/archive/mapreduce.html

---

reading this article you will notice that the mapper gives in output a list of pairs, but the reducer takes in input a pair of (key , list(value)) this implies that there is something in between that "lists" all values with the same keys. This task is done on the output of ALL the mappers, this task is optimized , sorting values ecc.. but as i say is in practice done on all the mapper.

If you know a little of java i suggest you to try something using the Hadoop framework by Apache

as you can see in the linked example the CombinerFunction(the intermediate layer that i've mentioned) works on the same input of the reducers.
> 1 votes

---
Tags: distributed-systems, parallel-computing, algorithm-design
---


# Question
Title: What will i obtain if i apply a xor-ing a one way function and it's input?
I know that a one-way function is informally a function that it's easy to compute but hard to invert.
If f(x) is a one way function the function $g(x) = x\oplus f(x)$ is a one-way function? My intuition is that it's but i not really sure.

# Answer
> 6 votes
Let $h$ be any one-way function, and define $f(x) = 0^{|x|} h(x)$. Note that $f$ is also one-way: it is easy to compute, and if you can invert $f$ you can invert $h$ (so since $h$ is hard to invert, so is $f$). But $g(x) = xh(x)$ is easy to invert.

---
Tags: cryptography, one-way-functions
---


# Question
Title: Does forcing TMs to change all symbols they read change their power?
If we limit a turing machine so that it is not allowed to write the symbol that it reads would it reduce its power?

For example: $( State, A, State, Z, DIRECTION)$

$A$ cannot be the same symbol as $Z$.

# Answer
If you give me a standard Turing Machine, I can build a must-write-different Turing Machine that does the same thing.

I'll take the original alphabet and double it -- so for symbol $a$, I create two symbols $a\_1$ and $a\_2$, and for symbol $b$, I create $b\_1$ and $b\_2$.

Now I treat both $a\_1$ and $a\_2$ in the exact same way as the old TM treated $a$, except when I'm supposed to write an $a$ back onto an $a$, I check if the current symbol is $a\_1$ or $a\_2$ and write the other one.

We could verify that this construction will indeed mimic the behavior of the original TM (no matter what it was), so must-write-different TMs are equally powerful.

(If this is not clear, please let me know so I can explain further!)
> 15 votes

---
Tags: computability, turing-machines, machine-models
---


# Question
Title: Where to find published research papers?
Coming from the POV of someone who is thinking about pursuing a PhD in Computer science.

I am having trouble deciding what I would focus my research on when I go for my PhD. See also this question on academia.SE.

So I am thinking that reading/keeping current on what research is being done and what research papers are being released is a good source of....inspiration? Plus good knowledge to know.

Is there central place/database of/good starting place to see recently published CS research papers, or are they all hidden deep within the websites of the University they were written at?

# Answer
As AJed mentioned, ACM digital library and IEEE xplorer would be near the top of list.

Additionally Goggling with advanced search for the name of the reference with the option to search for PDF or PS increases the change of a hit.

Sometimes limiting the search to `cs.xyz` or `xyz.edu` increases the quality of results.

If you are just starting out on a subject, try adding the word `survey` as a search term because many researchers write survey papers so that someone new to the subject has an informed person guiding the way.

I also like to hit CitSeerX, WorldCat and Google Scholar

Don't forget to look at the patents in Google Scholar, I don't usually but every now and then companies have to give out something good they may not publish anywhere else.

If you don't attend school, you can see if a school provides access to their library for outside third parties. I found out that I can do this for Princeton University for $300 a year.

Added 3/2/2013

Microsoft Academic Search

This can also visualize publication trends in computer

Added 1/1/20016

arxiv.org \- Open access to 1,106,143 e-prints in Physics, Mathematics, Computer Science, Quantitative Biology, Quantitative Finance and Statistics.

semanticscholar.org

This has a nice feature that list survey papers which is useful when you are starting on something new.
> 15 votes

# Answer
See the ACM digital library, IEEE xplorer. These are the top in my opinion. Look as well in ScienceDirect (Elsevier) and Springer (for theoretical computer science, I believe these two libraries are better).

Usually, googling your research problem would lead you to papers. The journals in which these papers are published is what you are looking. Of course, use the references and citations of the paper you read. In the long term, you will restrict yourself with the journals of your field.
> 9 votes

# Answer
A very large fraction of new computer science papers come up on arxiv: http://arxiv.org/corr/home.

If you are interested in complexity theory give ECCC a look: http://eccc.hpi-web.de/.

If you are interested in crypto, there is the IACR eprint archive: http://eprint.iacr.org/.

All of these are free and frankly should suffice for most of recent papers.

EDIT: Maybe I was being too positive there. I mostly know about US-type theoretical computer science.
> 9 votes

# Answer
Microsoft Academic search is very good. You can select a list of conferences in your area and get RSS feeds of the latest papers.
> 2 votes

# Answer
If I'm looking for a particular topic or research problem, I usually start with Google scholar. To search for recent work by a particular author, title, or conference, sometimes DBLP is the way to go.

If you just want to browse recent work, then as others have said sometimes arxiv.org is a good way to go, but take care that the authors are reputable because arxiv is not peer reviewed. Another even better way to go is to follow what's been recently published in conferences in your field. I like confSearch for finding upcoming or recent conferences. You can usually find a list of accepted papers from a conference even before those papers are printed in the proceedings, and then locate the papers on authors Web pages or on arxiv.
> 2 votes

# Answer
In the other answers good sources are given. What I like to add is that not only you should try to locate single papers in a field, but also to find in what conferences they have been published. Then you can take some volumes of recent years and browse a little what has been happening there. Conference series might be from ACM, IEEE, or Springer LNCS.

Also, Google is a good help, but single papers in the arxiv do not tell about the "status" of the research. Research must have been accepted/presented elsewhere in order to count.
> 1 votes

# Answer
In my opinion, since as you said you haven't decided yet the field of your research,starting from papers for inspiration is a bit odd. Firstly, if I were you I would search the Web for the general idea of "the state of the art" for each sector of Computer Science. Then you should go deeper reading papers, provided that you will have decided which path you would like to take.
Specifically now on which is the best way to browse a paper online, you should check IEEExplore, CiteSeerX (as the others mentioned) and CoRR and then if you can't find it for free, google the author and/or title to check if it is available on a non-charging repository. Good Luck!
> 1 votes

---
Tags: reference-request
---


title: Generate the word using this grammar

text:
# Question
Title: Generate the word using this grammar
Using this grammar, over the alphabet $\Sigma=\\{a\\}$ $$ S \rightarrow a \\ S\rightarrow CD \\ C\rightarrow ACB \\ C\rightarrow AB \\ AB\rightarrow aBA \\ Aa\rightarrow aA \\ Ba\rightarrow aB \\ AD\rightarrow Da \\ BD\rightarrow Ea \\ BE\rightarrow Ea \\ E\rightarrow a \\ $$ Im trying to show that the working string $aaaaaaaaaBBBAAAD$ or $a^{n^2} B^nA^nD$ generates the word $a^{(n+1)^2}$

# Answer
> 2 votes
Start at the end! There is only one applicable production: #8. $D$ moves backward over the $A$'s turning them into $a$'s. Then use #9, and repeatedly #10.

Please take a piece of paper and count the $a$'s generated. Probably the expression $(n+1)^2 = n^2+2n+1$ is useful.

# Answer
> 2 votes
Firstly, let's see step by step a sequence of production usage in order to draw the general conclusion:
$$aaaaaaaaaBBBAA\mathbf{AD}\underset{prod8}{\rightarrow}~a...aBBBA\mathbf{AD}a\underset{prod8}{\rightarrow}~a...aBBB\mathbf{AD}aa\underset{prod8}{\rightarrow}$$ $$\underset{prod8}{\rightarrow}a...aBB\mathbf{BD}aaa\underset{prod9}{\rightarrow}a...aB\mathbf{BE}aaaa\underset{prod10}{\rightarrow}a...a\mathbf{BE}aaaaa\underset{prod10}{\rightarrow}$$ $$\underset{prod10}{\rightarrow}a...a\mathbf{E}aaaaaa\underset{prod11}{\rightarrow}a...a\boldsymbol{aaaaaaa}$$

Finally, we have 16 'a's in our word, which verifies the general formula: $a^{{(n+1)}^2}$.
I guess you have to prove it parametrically, not just show the application of the productions on the given string. So you could say that:

* **n 'a's** are generated by consuming the 'A's with the production #8, as we have 'D' repeated only once and combined with the 'A's before it we take "Da" n times.
* **1 'a'** is generated by using the production #9 once, which consumes one 'B' at a time and replaces 'D' with 'E'.
* **2 'a's (or better n-1 'a's)** are generated by using the production #10, which consumes one 'B' at a time.
* Finally, **1 'a'** is generated, as E is consumed with production #11

To sum up, we have: $n^2$ 'a's from the given word, $n$ from the 1st step, $1+(n-1)=n$ from steps 2 & 3 and at last $1$ 'a'as described in step 4 $\Rightarrow n^2+2n+1=(n+1)^2$ 'a's.

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


# Question
Title: Algorithm to find all 2-hop neighbors lists in a graph
Given a graph $G = (V,E)$, where $|V| = n$. What is a fast algorithm for generating the collection of all 2-hop neighborhood lists of all nodes in $V$.

Naively, you can do that in $O(n^3)$. With power of matrices, you can do that with $O(n^{2.8})$ using Strassen algorithm. You can do better than this using another matrix multiplication algorithm. Any better method ? Any Las Vegas algorithm ?

# Answer
> 16 votes
The question really depends on what is the precise definition of a 2-hop. If by a 2-hop you mean the set $$hp(v) = \\{ u \mid \mbox{there is a path of length 2 between u and v}\\},$$ then the current answer is no, you cannot do it faster than $O(n^{\omega})$ where $\omega$ is the usual constant associated with the complexity of performing the matrix product.

Why? For every vertex $v$ check if $v$ is adjacent to vertex in $hp(v).$ If this is the case then you have found a triangle in your graph. Moreover the graph is triangle free if you do not find a vertex $v$ with this property.

The currently best known algorithm for testing if a graph is triangle-free has time complexity $O(n^{\omega}).$

---
Tags: algorithms, algorithm-analysis, graphs, randomized-algorithms
---


# Question
Title: Construct a PDA for the complement of $a^nb^nc^n$
I am wondering if this is even possible, since $\\{a^n b^n c^n \mid n \geq 0\\} \not\in \mathrm{CFL}$. Therefore a PDA that can distinguish a word $w\in\\{a^n b^n c^n \mid n \geq 0\\}$ from the rest of $\\{a^\*b^\*c^\*\\}$ might as well accept it, which sounds contradictory to me.

I guess I need to take advantage of the non-deterministic nature of PDAs but I'm out of ideas. If you could offer some advice I would very much appreciate it.

# Answer
No, this is context-free. To accept $a^nb^nc^n$, you need to make sure that three numbers are equal. To accept $a^\*b^\*c^\* \setminus a^nb^nc^n$, you just need to make sure that you're in one of the following three cases:

1. The number of $a$s is different from the number of $b$s; or
2. The number of $a$s is different from the number of $c$s; or
3. The number of $b$s is different from the number of $c$s.

Write a PDA for each of these cases, then combine them by jumping nondeterministically to each one from the start state.
> 17 votes

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


# Question
Title: Is $L=\{ xyx^Ry^R \mid x,y \text{ is an element of }\{0,1\}^*\}$ context-free?
Is the language $L=\\{ xyx^Ry^R \mid x,y \text{ is an element of }\\{0,1\\}^\*\\}$ context-free?

Note: $x^R$ is the reverse of $x$.

**My Work:** I think this is a context free language. Since a pushdown automaton (PDA) accepts context-free languages, I am trying to draw a PDA for this language. When I draw a PDA, how does the PDA tell $x$ and $y$ apart? Or is this not a context-free language? (then I can use pumping length to prove this)

# Answer
No, it is not a context-free language. From my original SO answer: consider the string $0^n1^n0^n1^n \in L$, where $n$ is the pumping length from the pumping lemma for context-free languages. This fails the pumping lemma for context-free languages; in particular, we have seven cases for $vxy$:

1. $vxy$ consists entirely of 0s from the first part of the string. Pumping this up or down will cause the numbers of 0s in the first and third parts of the strings to be different, so we're no longer in $L$.
2. $vxy$ consists entirely of 1s from the second part of the string. Same problem between the second and fourth parts as between the first and third parts mentioned in case 1.
3. $vxy$ consists entirely of 0s from the third part of the string. Same but opposite problem as in case 1.
4. $vxy$ consists entirely of 0s from the fourth part of the string. Same but opposite problem as in case 2.
5. $vxy$ straddles the first and second parts of the string, beginning with 0s and ending with 1s. Pumping will change the the numbers of 0s and 1s in the first and second parts of the string, and they won't match the third and fourth parts of the string anymore, so we're not in $L$ anymore.
6. $vxy$ straddles the second and third parts of the string, beginning with 1s and ending with 0s. We have the same problem as in case 5.
7. $vxy$ straddles the third and fourth parts of the string, beginning with 0s and ending with 1s. We have the same but opposite problem as in case 5.
> 4 votes

# Answer
The language is not context-free. This can be shown with help of the the context-free pumping lemma. Let $p$ be the pump width, then show that is not possible to "pump" the word $w=1^p0^p1^p0^p$.

You are left with showing the following. No matter how one subdivides $w$ into 5 parts $u,v,x,y,z$ with $|vy|\>0$ and $|uxy|\le p$, there exists for every such subdivision some $i$, such that $uv^ixy^iz\not\in L$. Use a case distinction.
> 3 votes

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


# Question
Title: Input to make worst case on big O not possible?
Sorry if this question is very simplistic; I'm just starting out and I'm trying to wrap my head around all this asymptotic bound stuff. When trying to find the upper bound for the worst case of a function does it need to take into account what the meat of the code actually does? I have some code that would (in the worst case) iterate through a while loop n times, but when you consider what that code actually does, it would always make it so that the condition for the while loop becomes false on the next iteration.

Some people say that it doesn't matter what is actually happening within the code; just that if it has the ability to iterate n times (even though it's virtually impossible because of the body of the loop) then that would be the worst case vs. however many steps the code ACTUALLY runs.

If anyone has any insight it would be greatly appreciated! Thanks!

# Answer
It matters what is actually happening in the code. The following pseudocode is O(1)

```
loop_factor = input()

for x between 0 and loop_factor():
    for y between 0 and loop_factor():
        terminate

```

However, it doesn't matter what is *likely* or *reasonable* to happen. If the body of your loop makes it "virtually" guaranteed that the loop will terminate next iteration, that means nothing; you need an actual hard **proof** that the loop will exit early for **all** input, no matter how absurd.

Essentially if you can rewrite your algorithm so that the loop clearly can't iterate n times without changing the meaning (i.e. replace the loop with just a few copies of the loop body in if statements, or something), then you are justified in saying that the loop isn't going to do n iterations. If you really need the loop to be there in the code as a loop that can iterate up to n times, then the big-oh complexity of the loop almost certainly does have to be n times the complexity of the loop body.
> 2 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis
---


title: NP-complete reductions

text:
# Question
Title: NP-complete reductions
I've read that "Every problem in NP can be reduced to every NP-complete problem".

My question is on the choice of the word "reduce". If I were to "reduce" a polynomial problem in NP to an exponential problem in NP, I just plain feel weird about using the word "reduce" because I feel like I've increased the problem, not reduced it. So, why do we use the word reduce?

Also, why do we write "reduce A to B" as $A\le\_{p} B$. It seems backwards.

# Answer
A reduction from A to B shows that A is "no harder" than B in some sense. We call it a reduction because it reduces the problem of solving A to the problem of solving B. This is a usage of the word "reduce" that is more mathematical and less about "size"; you can think of it as meaning that we've reduced the amount of work the world has to do, because even though we haven't solved A or B with the reduction we've made it so that a solution to B will automatically also be a solution to A.

Where A was a problem we didn't have any efficient solutions for, and where we already have an efficient solution for B, this does result in A getting "smaller" in a sense. For example, say we'd already come up with an exponential solution to A, and B is an NP-complete problem. Previously, the best we knew was that A was an exponential problem. After someone comes up with the A -\> B reduction, now we know it's actually an NP problem.

Yes, you can use a reduction argument to show that an already-known-to-be-easy problem is "no harder" than a hard problem. You can in fact use a polynomial-time reduction from **ANY** problem in P to **ANY** other problem whatsoever (that has at least one "yes" instance and at least one "no" instance), because you can "solve" the P problem in the reduction but simply encode the answer as an instance of another problem. Yes, this is pointless. But it's not "wrong" or inconsistent.

The problem you're having is purely in the analogy you're using, namely that a reduction is a "way of making a problem smaller". That is a reasonable metaphor for one of the usual **aims** of reduction proofs, which is to show that a problem is "easier" than previously suspected by finding a way to reduce it to another problem already known to be "easier".

But that doesn't help you with the other extremely common use of reduction arguments, which is to show that a problem C is *impossible* to solve, by finding a reduction *from* another problem D which is already known to be impossible. Here the reduction argument isn't "making D smaller", it's showing that C is "big".

Try to think of a reduction argument from A -\> B as a way of showing that A is "no harder" than B. When you think of it that way, it's not at all surprising that you can often reduce easy problems to hard ones; we already knew that they were easier! This account also easily explains the incomputability proofs by reduction; if the Halting Problem is no harder than X, then X can't be solvable.
> 4 votes

# Answer
Mostly from Vor's comment:

$A \le\_pB$ can be taken to mean that the problem $A$ is at least as easy as $B$ (or less hard). The $\_p$ subscript stands for *polynomial-time* and indicates that "easy" is relative term here, and the difficulty of the actual problems must consider the *polynomial-time* reduction as inconsequential (such as when solving $B$ requires super-polynomial time).
> 1 votes

---
Tags: complexity-theory, terminology, np-complete, reductions
---


# Question
Title: Show that the language of strings not in the union of two regular languages is regular
Given languages $L\_1,L\_2$, defines $X(L\_1,L\_2)$ by

$\qquad X(L\_1,L\_2) = \\{w \mid w \not\in L\_1 \cup L\_2 \\}$

If $L\_1$ and $L\_2$ are regular, how can we show that $X(L\_1,L2)$ is also regular?

# Answer
There are several ways to show that a language is regular (check the question How to prove a language is regular?)

Specifically for the language in your question, start with DFAs for $L\_1$ and $L\_2$ and try to construct an NFA for $X(L\_1,L\_2)$ using them. More details below:

> Note that $X(L\_1,L\_2) = \overline{L\_1} \cap \overline{L\_2}$.
> From the DFA of $L\_1$ construct the DFA of $\overline {L\_1}$ (making any final state not-final, and vice-versa). Do the same for $L\_2$. Intersection of regular languages can be constructed via product machine (see this question).
> \[Of course, if you already know that a complement of a regular language is also regular, and so the intersection of two regular languages – you are done without constructing those DFAs..\]
> 3 votes

# Answer
Expanding on Zach's comment, you (*should*) know the following things:

1. If $L\_{1}$ and $L\_{2}$ are regular languages, then $L\_{1} \cup L\_{2}$ is a regular language.
2. If $L\_{1}$ and $L\_{2}$ are regular languages, then $L\_{1} \cap L\_{2}$ is a regular language.
3. If $L\_{1}$ and $L\_{2}$ are regular languages, then $L\_{1} \cdot L\_{2}$ is a regular language.
4. If $L$ is a regular language, then $L^{\ast}$ is a regular language.
5. If $L$ is a regular language, then $\bar{L}$ is a regular language.

Now you should be able to pick a few of these that combined make up your $X$ language function/operator/whatever you call something like that (well, it's just a language defined in terms of others).

Just for some background, proofs for these properties can be found (IN A REALLY LARGE FONT) here.

Give this a go, if you're really stuck, I'll put a bit more in the spoilers below (but with little explanation).

> $X(A\_{1},A\_{2}) = \overline{A\_{1}\cup A\_{2}} = \bar{A\_{1}}\cap\bar{A\_{2}}$.
> 2 votes

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


# Question
Title: Find maximum distance between elements given constraints on some
I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements:

* The element 1 is in position 1, and element N must be at a position \>= the position of element N-1. (i.e. element 2 could be at position 1, element 3 at position 7, and element 4 at position 8 (but not position 5))
* Some elements must be within a certain distance from each other on the line.
* Some elements must be at least a certain distance from other on the line.

My objective is to return an integer that represents the maximum span between element 1 and element N. If no lineup is possible, return -1, and if the elements can be any distance apart, return -2.

I am given:

* The number of elements
* A withinArray\[\]\[\] where withinArray\[x\]\[y\] = the distance elements x and y must be within on the line. Any zero values represent no constraints.
* An atLeastArray\[\]\[\] where atLeastArray\[x\]\[y\] = the distance elements x and y must be apart on the line. Any zero values represent no constraints.

An example input would be: 4 elements, withinArray\[3\] = 10, withinArray\[2\]\[4\] = 20, and atLeastArray\[2\]\[3\] = 3. (all other array values are zero).

The return value for this input would be 27. (element 1 at position 1, element 2 at position 8, element 3 at position 11, and element 4 at position 28)

The problem was first posted here by someone else. I'd like to figure out an elegant solution to it programmatically. Though I've been working on it for a whole day, I still have no luck coming up with a good solution. I feel that I need to use dynamic programming techniques, but have a hard time finding a good substructure.

I am not able to locate the same example on the web. Any pointer to such materials online would be appreciated. It's even better if you are an expert for such kind of question and can outline the solution in detail. Executable code is a plus.

# Answer
What you describe is a linear program. You can use the following formulation:

Let $x\_i$ be the $i$th element. The variables are $d\_1,\ldots, d\_{n-1}$, where $d\_i$ denotes difference between $x\_{i+1}$ and $x\_i$. You require $d\_i\ge 0$.

If two elements $x\_i,x\_j$ should be at least within some distance $\ell^-\_{ij}$, then you set $$ d\_i+d\_{i+1}+\cdots +d\_{j-1} \le \ell^-\_{ij}.$$ If they should be at least $\ell^+\_{ij}$ away from each other you set $$ d\_i+d\_{i+1}+\cdots +d\_{j-1} \ge \ell^+\_{ij}.$$ Then maximize the objective function $\sum\_{i=1}^{n-1} d\_i$. An LP solver can also tell you if the problem is infeasible or unbounded. Of course you could look for a faster solution for this special class of LPs.
> 7 votes

---
Tags: algorithms, optimization, dynamic-programming, linear-programming
---


# Question
Title: Find the Simple Cycles in a Directed Graph
This problem, for me, looks very interesting. It was about to find a simple cycle (i.e. cycle where are not repeat nodes) in a directed graph.

My solution is going like this, i.e, this graph is a case problem:

I know that there is a cycle in a graph, when you can find "back edges" in a depth-first-search (dashed in my picture in DFSTree), and for a moment I can sure for a few cycles, but not for all, simple cycles. Because, the directed egdes so important to from a cycle, i.e (0123) != (0321)

I'm thinking in make a dfs for each node with back-edges, but I'm not sure, and it's not clear. So, I ask you, if you guide me. Thanks!.

Here is my count of simple loops for my case problem.

# Answer
> 15 votes
You may be interested in the algorithm presented in this paper:

Finding all the elementary circuits of a directed graph. Donald B. Johnson. SIAM J. COMPUT. Vol. 4, No. 1, March 1975

> **Abstract.** An algorithm is presented which finds all the elementary circuits-of a directed graph in time bounded by `O((n + e)(c + 1))` and space bounded by `O(n + e)`, where there are `n` vertices, `e` edges and `c` elementary circuits in the graph. The algorithm resembles algorithms by Tiernan and Tarjan, but is faster because it considers each edge at most twice between any one circuit and the next in the output sequence.

The paper contains a complete algorithm.

---
Tags: algorithms, graphs, enumeration
---


title: Cell walls in Conway's Game of Life?

text:
# Question
Title: Cell walls in Conway's Game of Life?
Do there exist robust structures in Conway's Game of Life? For instance, has anyone constructed a spaceship with a shield that absorbs all small oscillators and gliders it collides with?

# Answer
See "eaters" category.

They can absorbe gliders and spaceships, but I'm not an expert and I don't know if there are "walls" capable of absorbing everything. Perhaps it is a nice subject to investigate! (see the references at the bottom of Wikipedia pages for modern approaches using constraint solvers).

From the lexicon:

**:eater** Any still life that has the ability to interact with certain patterns without suffering any permanent damage. (If it doesn't suffer even temporary damage then it may be referred to as a rock.) The eater1 is a very common eater, and the term "eater" is often used specifically for this object. Other eaters include eater2, eater3, eater4 and even the humble block. (In fact the block was the first known eater, being found capable of eating beehives from a queen bee.) Another useful eater is shown below, feasting on a glider.
> 4 votes

---
Tags: cellular-automata
---


title: Modified paths Counting in a Rectangle

text:
# Question
Title: Modified paths Counting in a Rectangle
I was solving the following problem. But I am not able to think of an efficient algorithm for this modified version of problem. The problem statement is:

> We are given **K Rectangles**. The dimensions of $x$-th Rectangle is ($N\_x \times M\_x$), where $1\leq x \leq K$. From each rectangle $x$ , Alice Cuts a rect. of dimension ($P\_x \times Q\_x$), where $1 \leq x \leq K$ , from the **Top-Right Corner** and trashes the cut portion.
>
> Initially Alice placed a robot, at the **top left corner** of **each** rectangle. He is very interested to find the *number of ways, each robot* can reach the bottom-right corner (target) using the following rules:
>
> * The robot can only move 1 unit *right** or the robot can only move 1 unit *downward*.
> * The robot **cannot** move upward, **can't** move even *left* and **can't** move even *diagonally*.
> * The robot can move on rectangle boundary.
>
> The number of ways can be very large. Thus, Answer = (Number of ways) mod 10^9+7.

Constraints is very large:

```
1<=K<=10
2<=(Nx,Mx)<=5*10^5
1<=Px<Nx
1<=Qx<Mx

```

The Time Limit is just 1 second.

Example:

```
K=1

N1=2 M1=2

P1=1 Q1=1

```

Answer: 5 ways

I had **solved the easier version** of this problem (Using Pascal triangle + Combinatorics), when no portion of rectangle is cut/removed. But I don't know how to solve the above modified problem, where a small rectangle is cut from top-right Corner of the original rectangle.

# Answer
> 2 votes
As mentioned in the comments, DP is a perfectly valid solution to the problem. If the numbers are too large to calculate directly the number of solutions, then you can take things mod 10^9 + 7 during intermediate steps, too. This will work out because $(a \\% b + c \\% b) \\% b = (a + c) \\% b$ (for positive numbers or programming languages that implement negative mod correctly such as Python.

For a more elegant approach, you can calculate directly using more combinatorics. You know the total number of paths in the rectangle before part of it was removed, so it suffices to count the number of paths that went through the removed portion. To do this, take a diagonal from the bottom left of each removed rectangle up and to the right until you reach the border, Any path that goes in the removed portion must hit this diagonal, so if you sum the number of paths there are through each spot on the diagonal, you know how many paths to remove from your total. To count the number of paths that go through a square, count the number of paths to that square and multiply by the number of paths from there to the finish.

A fancier version of this approach is to count directly the paths that avoid the removed portion. To do this, take a diagonal from the corner of the removed rectangle (but not including it) down and to the left until you reach the border. A path avoids the removed rectangle if and only if it goes through this diagonal, so you can sum the number of paths through each location on this diagonal. Again, multiply the number of paths *to* a point by the number of paths *from* that point.

# Answer
> 0 votes
We start from the common corner grid (B,N-A) of the rectangle and the cut part. Now, we start from grid (0,0) and find path till that corner multiplied by paths from that corner till grid (N+1,M+1) , i.e the first term of above expression. Now further we move one grid back and calculate path from grid (0,0) till that grid multiplied by paths from there to grid (N+1,M+1) but removing the cases where common grid is used. Similarly , following above process till grid (B,N-A-1) to (B,0) we get the result.

Thus,You may use the formula I have derived:

$${N-A+B \choose B} {M-B+A \choose A} + \sum\_{r=0}^{N-A-1} {B+r \choose r} {N-r+M-B-1 \choose N-r}$$

where $A=P$ and $B=Q$.

You need to simplify it further to convert into $O(n \log n)$ solution.

---
Tags: algorithms, combinatorics, dynamic-programming
---


title: Is this a Context Free Language?

text:
# Question
Title: Is this a Context Free Language?
I got this question on my final exam: Is the following language context-free?

$$ L = \\{w\bar w^R \mid w\in \\{0,1\\}^\* \\}$$

**Notation**: The string $\bar w$ is obtained from $w$ by replacing all 0s with 1's and all 1's with 0's. The string $\bar w^R$ is $\bar w$ in reverse order.

---

> I've thought about it being a context-free language, but I notice that when you pump the string in the middle, the string will still be in the language. (using pumping lemma)

I think it's context free. This is the context free grammar:

$$ S \to 0S1 \mid 1S0 \mid \varepsilon $$ (It's basically a palindrome, but both sides are exact opposites.)

# Answer
> 2 votes
A Context free grammer is one in which LHS of atleast one of the productions is free from any terminal symbols (context). According to your production rule,it is clearly CFG.

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