# Question
Title: explain ackerman's recursion. how long it takes to execute the following code for an average PC
how does that recursion work

```
#include <stdio.h>

int ack(m,n)
int m,n;
{
int ans;
if (m == 0) ans = n+1;
else if (n == 0) ans = ack(m-1,1);
else ans = ack(m-1, ack(m,n-1));
return (ans);
}

int main (argc, argv)
int argc; char ** argv;

{ int i,j;
for (i=0; i<6; i++)
for (j=0;j<6; j++)

printf ("ackerman (%d,%d) is: %d\n",i,j, ack(i,j));
}

```

# Answer
> 1 votes
The Ackermann–Péter function works as advertised, while not being primitive recursive. There is an abundance of literature on this function and its execution time. Growth in the second parameter depends on the first, it is a bit like going from counting to addition to multiplication to exponentiation ...
The execution time of the code shown is entirely irrelevant, as the values will almost immediately overflow anyways - *googol* is *small* compared to `ack(4,2)`, googolplex dwarfed by `ack(5, 1)`.

---
Tags: algorithms, programming-languages, recursion
---


title: Examples of an I/O interface

text:
# Question
Title: Examples of an I/O interface
In computer architecture class, my lecturer was explaining about I/O interfaces and modules, but somehow neither me nor my classmates understood almost a word he said.. We still don't get which parts of a computer is an I/O interface. For example, which one of these are an I/O interface? A VGA card or PCI Express?

# Answer
> 2 votes
I would use the term *I/O interface* to refer to the set of CPU instructions that one uses to read and write data from or to an I/O device. There are generally two parts to this.

One is the interrupt mechanism, by which I/O devices can communicate asynchronous information to the CPU. Generally there is a pin, or several pins, on the CPU chip package that can be used to trigger an interrupt. Triggering an external interrupt on most CPU architectures will cause the processor to save some (or all) of its register state and jump to a predetermined location to run the interrupt service routine. (On some architectures there is a way of triggering different interrupt routines for different purposes, while on others there is a single external interrupt routine and there needs to be additional communication done in the interrupt service routine to figure out which device needed service.)

The second part is the way that data gets communicated back and forth between the CPU and the I/O device. This is generally done one of two different ways: memory mapped or "port mapped". In *memory mapped I/O* the registers on the I/O device are mapped to particular locations in the CPU's memory space, and the CPU uses normal load and store instructions to read and write those registers. In *port mapped I/O* the registers on the I/O device are mapped to particular locations in something called "port space." The instructions you use to access the I/O device's registers are often called something like `in` and `out`, but they are pretty similar to load and store instructions. There are other possibilities that get more complicated, but I've probably already given you more detail than you want.

For every specific device there is then some set of device registers that need to be read and/or written with specific values in some specific order. The protocols for what you need to read/write in which registers can get exceedingly complex.

To make this clearer let me give you an example. Let's take the PC keyboard (from the old days before we had USB). Here is the first thing that came up when I googled: http://www.oopweb.com/Assembly/Documents/ArtOfAssembly/Volume/Chapter\_20/CH20-2.html#HEADING2-1. The keyboard controller has two 8-bit registers mapped to port addresses 60h and 64h (hexadecmial). You read these registers using `inb` and `outb` instructions which moves data between the ports and the CPU registers.

The keyboard will additionally cause an interrupt to interrupt number 9 (out of 255) every time a key is pressed or released. So the interrupt service routine associated with interrupt 9 reads port 64h and looks at bit 1 to see if there is a data byte ready. If there is it reads the byte out of port 60h and copies it into some memory buffer for software to read later. (The reason you do the test is that several different hardware devices may be sharing the interrupt.)

# Answer
> 1 votes
An I/O interface is any interface that transfers data between the CPU/memory and the rest of the world. Examples include graphics cards (output only), keyboards (input only) and disc drives (input and output).

---
Tags: computer-architecture
---


# Question
Title: Help understanding formal language notation
I am reading this text and it is making absolutely no sense to me. It as if it assumed I will understand. Not to mention the writer apparently had a book made and his grammar is poor. Some of the plain English sentences do not even make sense or have the letter s on the end of words where they should not be. please help me understand this:

Language generators. A language generator is a device that can be used to generate the sentences of a language. A generator seems to be a device of limited usefulness as a language descriptor. Generators can more easily read and understand them. A language generation method constructs a language generator G and capable of generating a string of language by a process called derivation. For example, consider a language L over alphabet

> ∑ = {a, b}
>
> L= {a^n, b^n|n ≥ 1}
>
> G = { s -\> asb s -\> ab s -\> 3(i need to turn this symbol the opposite direction)}

W = aaa bbb

Derivation:

S ⇒ asb ⇒ aasbb ⇒ aaabbb

i.e., S ⇒ aaabbb It means we have derived aaabbb starting from start symbol S using the rules of language generator G in finite number of steps.

# Answer
> 1 votes
The problem seems to be that they assume you have a background in formal language theory. Here's the basics.

1. $\Sigma$ is the symbol which is traditionally used for an alphabet. When you're talking about strings, you always have a finite set of symbols that can be in those strings. Here we use $\Sigma=\\{a,b\\}$ to say that all our strings are binary, that is, they only contain the letters $a$ and $b$. We could have just as easily chosen $0,1$ or $\vee, \wedge$ or any other symbols we like. We just need a finite set of symbols.
2. $\epsilon$ is the empty string, the string of length 0. Sometimes you'll see this as $\lambda$, which is confusing, so be prepared for either. In a programming language like C, you'd see this written as `""`. It has the property that when you append it to the beginning or end of a word, it gives you that same word.
3. This is a description of context-free grammars. It's basically a concise way of defining a set of strings over some alphabet. We say that a string is in the set if there's some set of derivation rules we can apply to get that string.

The derivation rules basically are a way of generating strings. The idea is that, you start with a special start symbol, usually called $S$. We have upper and lowercase letters, called non-terminals and terminals. We keep applying rules until we only have lowercase letters left.

The X -\> Y things you see are the derivation rules. This is saying, in any string, you can replace the symbol on the left with the symbol on the right. The idea is that you keep doing this until you get a word with only lowercase letters.

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


# Question
Title: Show that $0^i$ where $i$ is a power of 2 is not context free
I'm having difficulty trying to use the pumping lemma in order to show that $L= \\{0^i \mid \ i \text{ is a power of 2 }\\} $ is not context free.

I"m starting by stating that $ s = 0^p$ and then $ s = uvxyz $ and that in order for a language to be context free it must follow the 3 conditions: $|vy| \> 0$ , $|vxy|\le p$ and for some $m \ge 0, \\, uv^mxy^mz \in L$.

So I guess I"m struggling on how pumping something $uv^mxy^mz$ will not be in $L$. Would I try and use something along the lines of pumping down $uv^0xy^0z$ for this to not be in $L$. Any help greatly appreciated!

# Answer
> 3 votes
If you're still confused, here's the proof. Let $p$ be the integer of the Pumping Lemma and consider the string $0^{2^p}$. If $L$ was a CFL, then (since $2^p\ge p$) the PL would apply to $0^{2^p}$ we'd have $0^{2^p}=uvxyz$ with

1. $|vxy|\le p$
2. $|vy| \> 0$

So if we let $v=0^k, y = 0^j$, we have from (1), $k + j =|vy| \le |vxy| \le p$ and from (2), $k + j=|vy|\>0$. In other words,

> $0\<k+j\le p$

Now pump up: The PL assures us that $uv^2xy^2z\in L$, and observe $$ |uv^2xy^2z| = 2^p+(k+j)\le 2^p+p\< 2^p+2^p=2^{p+1} $$ as long as $p\>0$, so the pumped string $uv^2xy^2z$ has length strictly between $2^p$ and $2^{p+1}$. No such string can be in $L$, so we have a contradiction to the PL implication that $uv^2xy^2z\in L$ and so our initial assumption, that $L$ was a CFL, must be false.

You could shorten this proof if you knew that (1) any context-free language over a 1-symbol alphabet must be regular and (2) the language $L=\\{0^{2^n}\mid n\ge 0\\}$ is not regular.

# Answer
> 2 votes
Instead of getting bogged down in the details of the pumping lemma, you can use the Myhill–Nerode criterion. For any $a\<b$, the words $0^{2^a},0^{2^b}$ are inequivalent modulo $L$ since $0^{2^a} 0^{2^a} \in L$ while $0^{2^b} 0^{2^a} \notin L$. This gives an infinite number of pairwise inequivalent words, showing that $L$ is not regular.

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


# Question
Title: How do you show that repeatedly dividing $n$ by $2$ takes $\log_2n$ steps to reach $1$?
I don't see why $n, n/2, n/4, n/8, \dots, 1$ takes $\log\_2 n$ steps. Is there a more general statement on this repeated division?

# Answer
> 3 votes
Hint: Prove by induction that after $k$ steps you are at $n/2^k$. If $n/2^k \leq 1$ then $k \geq \log\_2 n$.

(Actually, this works only for $n$ which is a power of $2$. Otherwise you get something like $(1/2)\log\_2 n$.)

---
Tags: discrete-mathematics
---


# Question
Title: Leveling array values with the smallest move
I'm not an expert of the theory of algorithm, so please forgive me if this problem is nonsense, but I want to find good algorithm to solve below problem.

There is a array of integer each of which has been assigned with random initial value such like \[1,5,-3,4\] or \[123, 543, 295, -703, …\]

You move values from one element of the array to another to achieve smaller variance. For \[1,5,-3,4\], the trivial final state is \[2,2,2,1\].

There is a constraint. The total amount of moving distance should be as small as possible. There are many paths to move \[1,5,-3,4\] to \[2,2,2,1\], but the following way should be **worse** one:

1. move 1 from the fourth element to the first one.
    * \[1,5,-3,4\] -\> \[2,5,-3,3\] (distance = 1 * 3)
2. move 3 from the second element to the third one.
    * \[2,5,-3,3\] -\> \[2,2,0,3\] (distance = 3 * 1)
3. move 3 from the fourth element to the third one.
    * \[2,2,0,3\] -\> \[2,2,2,1\] (distance = 2 * 1)

(total distance: 8)

because there is shorter (**better**) way to achieve this:

1. move 3 from the fourth element to the third one.

* \[1,5,-3,4\] -\> \[1,5,-1,2\] (distance = 2 * 1)
2. move 2 from the second element to the third one.

* \[1,5,-1,2\] -\> \[1,3,1,2\] (distance = 2 * 1)
3. move 2 from the fourth element to the third one.
    * \[2,2,0,3\] -\> \[2,2,2,1\] (distance = 2 * 1)

(total distance 6)

What is the algorithm which can find the shortest path to level values of array?

# Answer
Your problem seems to be the same as that of calculating the Earth mover distance between the starting and target distributions. Wikipedia suggests using the Hungarian algorithm to calculate the distance.
> 3 votes

# Answer
The Hungarian algorithm (mentioned in Yuval Filmus's answer) is fine and will get you the exact answer in $O(n^3)$ work.

However, here's a completely different numerical analysis style method that will get you within tolerance $\epsilon$ in $O(\epsilon^{-1} n \log n)$, or even $O(\epsilon^{-1/2} n \log n)$ work.

The basic method is to:

1. Convert the problem to a $l\_1$ minimization problem,
2. Use fast alternating iterative methods to solve it, which will take $O(\frac{1}{\epsilon})$ iterations to converge to within tolerance $\epsilon$
3. Within each iteration, perform the necessary linear solve using graph multigrid, which will take $O(n \log n)$ work per solve.

**The optimization problem**

We start with a graph, where the nodes represent places where mass is (the numbers), and the edges represent the connection between nodes that mass can be moved across. If you are concerned about some numbers being negative, just add a constant to all nodes in the initial and final states to make them positive - this will not change the optimal mass moving.

The problem can be formulated as the following $l\_1$ minimization problem,

\begin{align} \min\_{u} & \quad \sum\_i |u\_i| \\ \text{such that } & \quad D^T u = p-q, \end{align}

where

* $p$ and $q$ are the final and initial distributions of mass, respectively,
* $u\_i$ is the net flow across edge $i$,
* $D$ is the graph finite difference matrix that takes the distribution on nodes and gives the differences on the edges between them.

This is saying, minimize the net total flow across edges subject to the constraint that the flow takes the initial distribution to the final distribution. Edge directions can be chosen any way so long as your direction choice for $u$ is consistent with $D$.

**The method to solve it**

This form of $l\_1$ minimization problem has been intensely studied in the last 10 years since it arises often in large scale statistics, machine learning, seismic inverse problems, sparsity promoting optimization, and a number of other "hot" fields.

You can now use any of the modern iterative methods developed for $l\_1$ minimization problems such the alternating direction method of multipliers (ADMM), or many others. Usually these modern methods will require you to solve sparse linear systems of the form, $$(D^TD + \alpha I)x = b$$ once per iteration. Since $D^TD$ is a graph laplacian, this solve can be done in $O(n \log n)$ time through graph algebraic multigrid, and is parallelizable to $\log n$.

The error for iteration $k$ in these methods usually goes as $\text{error} \sim \frac{1}{k}$. Some accelerated variants exist that can achieve $\text{error} \sim \frac{1}{k^2}$ (albeit with worse constants and more difficult implementation). Reference here. So, you need $k \sim \frac{1}{\epsilon}$ or $k \sim \frac{1}{\epsilon^{1/2}}$ iterations to ensure that your error is less than $\epsilon$.

So there you go, an efficient and thoroughly modern way to solve this problem. Probably way overkill if your problem is small, but a great way to go if it is very large. I don't know if the details of this framework for solving EMD problems have been published anywhere. I learned of the $l\_1$ formulation of the problem from Justin Solomon who has used it in combination with ADMM to solve EMD problems on discrete surfaces.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Is the height of the tree the number of edges or number of nodes?
I'm so confused by some of the theorems online about tree heights. Does tree height mean the number of edges or nodes? if nodes, does it include the node it is counting from? Can the height of a tree start from 0?

# Answer
> 8 votes
As Yuval says, there's no standard definition. This is not because computer scientists are indecisive but because it's sometimes more convenient to use one definition and sometimes more convenient to use the other. For example, a full, balanced binary tree of height $h$ has $2^h$ leaves if you define height as number of edges and $2^h-1$ vertices in total if you define height as number of vertices. Each of these statements becomes less convenient if you use the other definition and have to keep writing $h-1$ or $h+1$.

The situation is exactly the same as the natural numbers: sometimes, it's more convenient to say that zero is a natural number (for example, the natural numbers are a semiring only if zero is included); other times, it's more convenient to omit zero (for example, if you always want to be able to divide by a natural number). In fact, similar things happen throughout mathematics. Another example is that it's common to insist that graphs have at least one edge (or at least one vertex) to avoid having to start all your theorems "If $G$ is not trivial, then..."

# Answer
> 5 votes
There is no single accepted definition. Some authors define it as the number of edges, some as the number of nodes. Some authors even use both definitions in different papers. Because of this confusing state of matters, each paper ought to state which definition it uses.

# Answer
> 0 votes
Height of a tree simply means the total number of nodes in that tree on the path from the root node to the deepest node in the tree.For instance,if the height of a tree is 'h' then the minimum number of nodes in that tree can b 'h' and maximum number of nodes can be 2^h-1.

---
Tags: graphs, terminology, trees
---


title: Help designing a Turing Machine

text:
# Question
Title: Help designing a Turing Machine
I am faced with the following question:

> Design a Turing Machine that recognizes the language $L = \\{1^{2n+1}\mid n \text{ is a non-negative integer}\\}$. Show the state diagram.

I started doing this using $Q \times \Gamma \rightarrow Q \times \Gamma \times \\{L, R\\}$, and setting up a 7 tuple but I cannot come up with the state diagram.

# Answer
> 2 votes
Hint: $L$ is regular. Draw a DFA accepting $L$, and modify it to a full-fledged Turing machine whose operation is essentially equivalent to that of the DFA.

# Answer
> 0 votes
Hint 2: the "state diagram" and the 7-tuple are two representations of the same idea. One as a drawing, the other as a table..

Make sure you understand what a state diagram means. How can you take a 7-tuple (that you said you know how to get) and convert it into a state-diagram?

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


title: Time Complexity $\Theta$ vs. $\Omega$

text:
# Question
Title: Time Complexity $\Theta$ vs. $\Omega$
If an algorithm has running time of $\Theta(n^2)$, is it possible to have a best-case running time of $\Omega(n)$? Or is the fastest running time only $c n^2$ for some constant factor $c$?

# Answer
Normally, it's the worst-case running time that is given but one should never say just "running time" since it could be anything – best-case, worst-case, average case according to some probability distribution, amortized, ...

If the worst-case running time is $\Theta(n^2)$ all you can say about the best case is that it can't be worse than the worst case, so the best case is $O(n^2)$. So, yes, the best case could be $\Omega(n)$.
> 2 votes

# Answer
There are two possible interpretations for "running time of an algorithm". The first interpretation is the worst-case running time, depending on some parameters such as the input length $n$. The second interpretation is that the running time is some bound that holds for *all* inputs with the given parameters. When we give a big $O$ estimate, both interpretations amount to the same thing: if an algorithm has a running time of $O(n^2)$, then this is both a worst-case bound and a bound which is valid for all inputs of length $n$.

What is then the interpretation of $\Theta(n^2)$ in your case? It's hard to say without more details, and could depend on the context. If it's a worst-case bound then the meaning is "there is a family of inputs for which the algorithm runs in $\Omega(n^2)$ time". If it's a global bound then the meaning is "the algorithm runs in $\Omega(n^2)$ time on *all* inputs". Out of these two possible interpretations, the first seems slightly more likely, but others may hold different opinions.
> 3 votes

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


# Question
Title: Is there an algorithm that provably exists although we don't know what it is?
In mathematics, there are many existence proofs that are non-constructive, so we know that a certain object exists although we don't know how to find it.

I am looking for similar results in computer science. In particular: is there a problem that we can prove it is decidable without showing an algorithm for it? I.e. we know that it can be solved by an algorithm, but we don't know what the algorithm looks like?

# Answer
The simplest case I know of an algorithm that exists, though it is not known which algorithm, concerns finite state automata.

The quotient $L\_1/L\_2$ of a language $L\_1$ by a language $L\_2$ is defined as $L\_1/L\_2=\\{x \mid \exists y\in L\_2 \text{ such that } xy\in L\_1\\}$.

It is easily proved that regular set are closed under quotient by an arbitrary set. In other words, if $L\_1$ is regular and $L\_2$ is arbitrary (not necessarily regular), then $L\_1/L\_2$ is regular, too.

The proof is quite simple. Let $M=(Q,\Sigma,\delta,q\_0,F)$ be a FSA accepting the regular set $R$, where $Q$ and $F$ are respectively the set of states and the set of accepting states, and let $L$ be an arbitrary language. Let $F'=\\{q\in Q\mid \exists y\in L \\;\\;\delta(q,y)\in F\\}$ be the set of states from which a final state can be reached by accepting a string from $L$.

The automaton $M'=(Q,\Sigma,\delta,q\_0,F')$, which differs from $M$ only in its set $F'$ of final states recognizes precisely $R/L$. (Or see Hopcroft-Ullman 1979, page 62 for a proof of this fact.)

However, when the set $L$ is not decidable, there may be no algorithm to decide which states have the property that defines $F'$. So, while we know that the set $F'$ is a subset of $Q$, we have no algorithm to determine which subset. Consequently, while we know that $R$ is accepted by one of $2^{|Q|}$ possible FSA, we do not know which it is. Though I must confess we know to a large extent what it looks like.

This is an example of what is sometimes called an *almost constructive* proof, that is a proof that one of a finite number of answers is the right one.

I suppose an extension of that could be a proof that one of an enumerable set of answers is the right one. But I do not know any. Nor do I know a purely non-constructive proof that some problem is decidable, for example using only contradiction.
> 15 votes

# Answer
To expand on Hendrick's original comment, consider this problem

> Given an integer $n\ge 0$ is there a run of $n$ or more consecutive 7s in the decimal expansion of $\pi$?

This problem is decidable, since one of two cases may obtain:

1. There is an integer $N$ for which the decimal expansion of $\pi$ contains a run of $N$ consecutive 7s, but no longer run.
2. For any $n$, the expansion of $\pi$ has a run of $n$ consecutive 7s.

In case (1) a decision algorithm for the problem would be one of

> If $n \> N$ answer "no" else answer "yes".

and in case (2) the algorithm would be

> Answer "yes".

Clearly each of these is a decision algorithm; we just don't know which. That suffices, though, since decidability only requires the *existence* of an algorithm, not the specification of *which* algorithm to use.
> 12 votes

# Answer
Here is a non-answer. I'm posting because I believe it's instructive, because I originally claimed the opposite and eight people agreed enough to upvote before @sdcwc pointed out the mistake. I didn't want to just edit my first answer because I'm not sure as many people would have upvoted it if they knew it was wrong.

I originally claimed that it sufficed to take any set $S$ that we know to be finite but for which we don't know the members. Since $S$ is finite, it is recursive, so there is an algorithm but I claimed that we don't know what it is.

However, this is incorrect. For example, by the Robertson–Seymour theorem, we know that the class of graphs of treewidth at most 10 has a finite set of forbidden minors. We don't know what this set is so I claimed we don't have an algorithm to decide if a graph $H$ is a forbidden minor of the class of graphs of treewidth at most 10. But @sdcwc points out that there *is* an algorithm: just check that $H$ has treewidth more than 10 and all its proper minors have treewidth at most 10.
> 2 votes

---
Tags: algorithms, proof-techniques
---


# Question
Title: Randomized agorithm for selecting a $m$-subset out of a $n$-set
The question has been discussed here but unfortunately is closed.

Reference : m-element random sample being equally likely ...(CLRS 5.3-7)?

My question is as follows.

Suppose $n = 5, m = 3$. This implies that we need to randomly select a $3$-subset out of $5$ elements. The algorithm makes $3$ recursive calls. The probability of obtaining the set $S\_1 = \\{1,2,3\\}$ is more than that of $S\_2 = \\{3,4,5\\}$ since we can obtain $S\_2$ in only one way as follows.

$$ 3 = RANDOM(1,3) \\4 = RANDOM(1,4)\\ 5 = RANDOM(1,5) $$

But in case of $S\_1$ we have $3! = 6$ ways of obtaining it, two of them being as follows.

$$ 3 = RANDOM(1,3) \\2 = RANDOM(1,4)\\ 1 = RANDOM(1,5) $$ $$ 2 = RANDOM(1,3) \\3 = RANDOM(1,4)\\ 1 = RANDOM(1,5) $$

Now, how can the output of each $3$-subset is equally likely as claimed in the question?

# Answer
There are actually only two random steps in this case:

1. Start with $\\{1,2,3\\}$.
2. With probability $3/4$, replace a random element with $4$.
3. With probability $3/5$, replace a random element with $5$.

You get $\\{1,2,3\\}$ if you don't insert $4$ or $5$, which happens with probability $$\left(1-\frac{3}{4}\right)\left(1-\frac{3}{5}\right) = \frac{1}{4} \cdot \frac{2}{5} = \frac{1}{10}.$$

You get $\\{3,4,5\\}$ in two cases:

1. You replace $1$ with $4$ and then $2$ with $5$.
2. You replace $2$ with $4$ and then $1$ with $5$.

The probability that you replace a specific element with $4$ is $(3/4)(1/3)=1/4$, and the probability that you replace a specific element with $5$ is $(3/5)(1/3)=1/5$. In total, the probability that we get $\\{3,4,5\\}$ is

$$ \frac{1}{4}\cdot \frac{1}{5} + \frac{1}{4}\cdot \frac{1}{5} = \frac{1}{10}. $$

So both probabilities are the same.
> 1 votes

---
Tags: randomized-algorithms
---


# Question
Title: Fixed size set to contain the maximum number of given sets
I asked this question in SO here

I have about 1000 sets of size \<=5 containing numbers 1 to 100.

```
{1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ...

```

Is it possible to find a set of size 20 that contains the maximum number of given sets?

In other words, let $U = \\{1, 2, ..., 100\\}$ and $S \subseteq \\{Z \in 2^U \mid |Z| \leq 5\\}$. How can I find $X \subseteq U$ with $|X| = 20$ such that $|\\{Y \in S \mid Y \subseteq X\\}|$ is maximized?

Checking each of `100!/(80!*20!)` sets or bulding all set combinations with size \<=20 is inefficient.

Is there any (semi)efficient solution or is it np-complete?

The set {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20} contains 5 sets.

# Answer
The decision version of the problem can be formulated as follows:

* Given a collection of sets of numbers $S$. Each number is drawn from a set $U$. You want to know if there is a way to pick $k$ numbers from $U$ to form a set $X$ which is the superset of $s$ sets in $S$.

The following is a reduction from k-clique which is an NP-complete problem.

The k-clique problem has an input as a graph and asks if there is a way to pick $k$ nodes so that there is an edge between any two of the $k$ nodes.

We turn each node into a number. These numbers form the set $U$. We turn each edge into a set containing two numbers representing the corresponding two nodes of the edge. These sets form the set $S$.

The question to the original problem is: Is there a way to pick $k$ numbers from $U$ to form a set $X$ such that $X$ is the superset of $C\_{2}^k$ sets in $S$

The proof has two directions.

1. If there is a k-clique in the graph, then we can pick the $k$ numbers corresponding to $k$ nodes in the clique to form $X$. Because of the way we transform the graph, we know there will be $C\_{2}^k$ sets in $S$ each corresponds to an edge in the original graph and thus is a subset of $X$. So the answer to the original problem is positive.
2. If there is no clique of size $k$, then for any set of $k$ nodes chosen from the graph one can only have less than $C\_{2}^k$ undirected edges between any two picked nodes. Otherwise, we will have a clique of size $k$. This means that there can only be less than $C\_{2}^k$ subsets of $S$ which is a subset of the set $X$ formed by any $k$ chosen numbers. So the answer to the original problem is not positive.

The transformation is in poly-time. The reduction is proven, so the problem is NP-hard. The problem is clearly in NP because we check how many sets covered by $k$ numbers in poly time. This means the original problem is NP-complete.
> 4 votes

---
Tags: algorithms, optimization
---


# Question
Title: Why can the alphabet be represented in numbers in base 256
This is in context of hashing of strings. I'm not sure why a string like, CS, could be represented as CS = 'c'\*256 + 's'

Does anyone know about this?

# Answer
> 6 votes
A number in base ten is just a sequence of digits 0–9, with the string $d\_n\dots d\_2 d\_1 d\_0$ representing the number $10^nd\_n + \dots + 10^2d\_2 + 10^1d\_1 + 10^0d\_0$. Similarly, a character in an 8-bit character set can be considered to be a "digit" between 0 and 255, so a sequence $d\_n\dots d\_1d\_0$ of these "digits" represents the number $256^nd\_n + \dots + 256^2d\_2 + 256^1d\_1 + 256^0d\_0$.

Another way to see this is to write the number out in binary. For example, a 32-bit binary number can be considered as having 32 binary digits (bits) or 4 256-ary digits by collecting the bits into groups of 8. In the same way, an 8-digit decimal number can be considered as a 4-digit number in base-100. For example

$$38572856$$

can be considered as

$$38\\,57\\,28\\,56 = 38\times 100^3 + 57\times 100^2 + 28\times 100^1 + 56\times 100^0 = 38572856\\,.$$

For the Latin alphabet, base 26 would be the most natural representation, since the letters can be treated as 26 different "digits". You may also have heard of Base-64 encoding which uses the 64 characters `A...Za...z0...9+/` in that order as 64 "digits". The advantage there is that all 64 of the characters can easily be included in a text file and, by using Base-64, you can code three bytes of binary data (24 bits) into four characters (4x6 bits), which is a acceptably inefficient.

---
Tags: hash
---


# Question
Title: When is splitting a collection coins two ways NP-complete?
Suppose we have a set $D$ of denominations of coins and a our input is a "tip jar" containing some finite number of these coins (e.g., five nickels, a dime and three quarters). In the first two problems, we want to know whether it is possible to divide the money in the jar equally between two people; in the third one, we're satisfied if the money can be divided almost equally. What is the complexity of these problems?

1. $D = \\{1, 2, 4, 8, \dots\\}$.
2. $D = \\{1, 2, 3, 4, \dots\\}$.
3. $D = \\{1, 2, 3, 4, \dots\\}$ but we only require the two people to be given amounts $x$ and $y$, respectively, satisfying $|x-y|\< 10$.

My main question is what sets $D$ lead to the problem being in **P** and what makes it **NP**-complete.

# Answer
Problem 2 is the same as the NP-complete problem PARTITION. Problem 3 is also NP-complete, since we can always arrange all denominations to be multiples of 10 cents.

The most interesting case is Problem 1. If the jar contains in total $2S$ cents, then we are looking for a subset of the jar summing to $S$. If $S$ is odd then there is no solution unless the jar contains a 1 cent coin, in which case we take one such coin and put it aside (it forms part of the solution), and update the target sum to $S-1$. Is $S$ is even we do nothing. In both cases, the new target sum is even. The number of 1 cent coins which appear in a solution must be even, and so we can group the 1 cent coins in pairs, replacing them with 2 cent coins (if there is an odd number, we just throws the odd one out). Now we repeat the same procedure with the 2 cent coins, the 4 cent coins, and so on, until we either reach the target sum or find out that the target sum is not reachable. This algorithm runs in polynomial time.
> 1 votes

---
Tags: complexity-theory, np-complete, decision-problem
---


# Question
Title: How can finite sets be represented as a type?
*Manually self-migrated from stack overflow.*

A set of objects of a type T is often represented using its indicator function (`set T` = `T -> bool`). However, for practical purposes this representation isn't necessarily very useful. For instance, if T is the natural numbers, there's no way to print0 out all of the numbers in a given set, since it would require checking all of the natural numbers, which is an infinite task.1

However, say I'm only interested in finite sets, and I want to be able to print out all the members of a set. (Obviously I also want to easily test membership, construct unions and intersections, etc.) Is there a good way to do this using inductive types?

Edit:
To clarify, I need the `set` type to encapsulate all of the set invariants (no duplicates, unordered, etc) so that all members of that type automatically satisfy those properties. The indicator function representation does this, but is impractical to use as a data structure for the above reasons. Using sorted lists (`set T` = `list T`) is possible, but not all lists are valid (sorted without duplicates) representation of a set—I need the type system to enforce that all members of `set T` are actually sets.

---

0: Let's assume we're using some monad to encapsulate printing, etc.
1: In exchange, we do of course get the ability to represent infinite sets.

# Answer
If you want a type system for finite sets that enforces the validity and unicity of all representations, then your type system must be able to model equality of elements. (Informal proof: `insert x (insert y empty)` has differently-shaped representations depending on whether `x` and `y` are equal.) This is impossible with algebraic datatypes alone, unless you're willing to restrict the domain of the sets to sufficiently simple sets (for example, you can use a bit vector to represent a finite subset of a finite set; you can use finite lists of positive integers to get a unique representation of finite sets of positive integers: store $\\{x\_1, \ldots, x\_n\\}$ as $\[x\_1, x\_2-x\_1, \ldots, x\_n-x\_{n-1}\]$ where the $x\_i$ are numbered in increasing order).

A sophisticated type system can of course represent anything you want. Basically, you need:

* dependent types, so that the type definition can contain equality assertions;
* induction, to build a data structure containing any number of elements.

For example, the calculus of inductive constructions admits representations of finite sets. You can look for examples in the Coq library and contributions.

If you're willing to relinquish either the requirement for unicity or for validity, you can make do with algebraic datatypes. Representing finite sets as finite lists yields a set representation where every datum is valid, but each set admits multiple representation ($n!$ representations for an $n$-element set if the elements have unique representations). Something like a sorted list or search tree can give a unique representation (assuming that the elements have a unique representation). For search trees, to have representation unicity, you need a balancing function that guarantees unicity (which may impact performance).

In the type systems found in typical programming languages, it is typical to implement sets with an underlying representation that may or may not be valid. The type system thus does not enforce that all representations are valid. It does, however, help to maintain this property: a finite set can be implemented as an abstract type. The type is implemented as a module which is *sealed*, ensuring that all elements of the finite set type have been built from constructors provided by the module. The correctness of the finite set modle code ensures the validity of set representations, and the type system helps by maintaining this invariant.
> 5 votes

---
Tags: type-theory, sets, inductive-datatypes
---


# Question
Title: Wouldn't a Red-Black tree fix up after insertion mess up the BST ordering?
I've been reading about fixing up after an insertion into a red black tree. (http://web.cse.ohio-state.edu/~lai/2331/0.Red-Black%20Trees.pdf)

The most surprising part is not that there are 6 things that we need to do after inserting into a red black tree. i.e. if both parent, uncle red, then parent, uncle black, grandparents red, replace inserted value with grandparent. The most surprising part is that wouldn't this blatantly mess up the BST ordering such that a node x is always greater than the left side and less than the right side?

In above link, page 10, the author just replaced grandparent with the newly inserted node x. Wouldn't this completely mess up the BST ordering? Can someone explain if BST ordering should be preserved in a red-black tree and why rotation/fix up after insertion will not have any affect on this ordering?

# Answer
A correct implementation of red-black trees will maintain the BST ordering property. Whenever you add a node to the tree or delete a node from the tree you very carefully maintain this property. If you have to modify the structure of the tree then you do so in such a way that maintains the BST property.

I suggest you go carefully through the insertion and deletion pseudocode and verify that both operations maintain the BST property.
> 1 votes

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


title: Big O Notation Explained

text:
# Question
Title: Big O Notation Explained
Our teacher gave us the following definition of Big O notation:

O(f(n)): A function g(n) is in O(f(n)) (“big O of f(n)”) if there exist constants c \> 0 and N such that |g(n)| ≤ c |f(n)| for all n \> N. I'm trying to tease apart the various components of this definition. First of all, I'm confused by what it means for g(n) to be in O(f(n)). What does in mean?

Next, I'm confused by the overall second portion of the statement. Why does saying that the absolute value of g(n) less than or equal f(n) for all n \> N mean anything about Big O Notation?

My general intuition for what Big O Notation means is that it is a way to describe the runtime of an algorithm. For example, if bubble sort runs in O(n^2) in the worst case, this means that it takes the time of n^2 operations (in this case comparisons) to complete the algorithm. I don't see how this intuition follows from the above definition.

# Answer
O(f(n)) means the family of function of f(n), a family of function for example could be {n^2, 3\*n^2, 6\*n^2, ...k\*n^2}, for g(n) to be in the O(f(n)), it means that g(n) is less than all elements of f(n) in the long run. In the above example, it could be g(n) = n, versus O(f(n)) = O(n^2), obviously, n^2 is bigger than n for all n in the long run.

Absolute value sign compares the absolute values of these two functions so that even if g(n) is negative, we can compare which negative grows faster i.e. -n^2 grows faster than -n is equivalent to n^2 grows faster than n

n\>N means in the long run

Bubble sort runs O(n^2) in the worst case means that Bubble sort can run much faster than O(n^2), but it does not exceed O(n^2). For example, we want to sort two elements {2,1} using bubble sort, obviously this takes 1 operation and that's it, 1 is smaller than n^2.
> 1 votes

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


# Question
Title: Count positive subsequences in a sequence of numbers faster than $\Theta(n^{1.5})$
Find the total number of positive subsequences in a sequence of numbers with an algorithm that is faster than $O(n^{1.5})$. For example, {-2 3} is a positive subsequence of {1 -2 3} since -2+3 = 1 is positive. The following is my code:

```
import java.util.*;

class PSIv3
{

public static int mergeSort(int[] a, int i, int j){
    int count = 0;

    if ( i < j ){
        int mid = (i+j)/2;
        count += mergeSort(a, i, mid);
        count += mergeSort(a, mid+1, j);
        count += merge(a, i, mid, j);
    } else {

        if ( a[i] > 0 ){
            count++;
            return count;
        }

    }

    return count;
}

public static int merge(int[] a, int i, int mid, int j){

    int sum = a[mid] + a[mid+1];
    int count = 0;
    int tempsum;

    if (sum > 0)
        count++;

    for ( int l = mid + 2; l <= j; l++ ){
        sum = sum + a[l];
        if ( sum > 0 ){
            count++;
        }
    }

    sum = a[mid] + a[mid+1];

    for ( int k = mid - 1; k >= i; k-- ){
        sum = sum + a[k];

        if ( sum > 0 )
            count++;

        tempsum = sum;

        for ( int l = mid + 2; l <= j; l++ ){
            tempsum = tempsum + a[l];
            if ( tempsum > 0 ){
                count++;
            }
        }

    }

    return count;
}

public static void main(String [] args)
{
    Scanner sc = new Scanner(System.in);
    int numberOfElements = sc.nextInt();
    int[] intArray = new int[numberOfElements];

    for ( int i = 0; i < numberOfElements; i++ ){
        intArray[i] = sc.nextInt();
    }

    int count = PSIv3.mergeSort(intArray, 0, numberOfElements-1);

    System.out.println(count);

}
}

```

My algorithm is to modify the mergeSort algorithm with the aim of getting an $O(N log N)$ algorithm. Instead of sorting, I increment the count when I encounter a positive subsequence. When two portions, say A and B merge together, there are 3 possibilities to consider: 1) the subsequence is in A 2) the subsequence is in B or 3)the subsequence is not in A and not in B. Since 1) and 2) are already counted. I only have to consider 3. Every subsequence in 3 must contain a\[mid\] and a\[mid+1\]. Else it will be in 1) or 2). Therefore, I start from this subsequence and expand to the left and expand to the right, incrementing the count if the subsequence is positive.

My algorithm works, but it is not fast enough to pass the test. Hence, I am wondering if anyone has a faster algorithm or can tell me how to optimise the existing algorithm. Thanks.

# Answer
The running time for `merge` procedure is $O(n^2)$ instead of $O(n)$, so your running time $T(n) = 2T(n/2) + O(n^2) = O(n^2)$. The $O(n^2)$ time is caused by your second half of the 'merge' procedure, where you compute the sum including the right subarray for each left subarray. If you could find a way to make your 'merge' linear time, then the algorithm will be $O(n \lg{n})$.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Regular expression for a binary number that includes "10" and has an odd number of 0's
I have been struggling trying to write a regular expression for a binary number that includes "10" and has an odd number of 0's, so far I have (1) * (00) * 10(1010) * (00) * (1) * but it doesn't accept 0100 for example or 010101 etc, also if I write a finite automata for this how do I prove its correctness ?

# Answer
You can write a regular expression directly:

* First ignore the odd number of zeroes. You can easily write an expression for this modified language, based on the fact that you can choose to particularize the first occurence of $10$ (namely $0^\*1^\*10(0+1)^\*$ is a valid expression).
* Now you want to modify the first part ($0^\*1^\*$) and the second part $(0+1)^\*$ to take into account the odd number of zeroes. Since these two parts have to agree (have the same parity of zeroes) there are two disjoint cases: either you have even numbers of $0$'s before and after the $10$ pattern, or an odd numbers:

1. To have an even number of $0$'s before the pattern, simply write $(00)^\*1^\*$. For an even number after the pattern, this is simply an expression for a word with an even number of zeroes: $1^\*(01^\*0)^\*1^\*$ (each $0$ has a friend). Together, this gives you the expression: $(00)^\*1^\*\ 10\ 1^\*(01^\*0)^\*1^\*$.
    2. To have odd numbers, you can re-use modified versions of the expressions in 1.: Before the pattern, you add a first $0$ in front: $0(00)^\*1^\*$; After the pattern, you need a first $0$ but also $1$'s in the middle: $1^\*01^\*(01^\*0)^\*1^\*$. Together: $ 0(00)^\*1^\*\ 10\ 1^\*01^\*(01^\*0)^\*1^\*$.

Globally, you have the disjunction of the two cases:

$$(00)^\*1^\*\ 10\ 1^\*(01^\*0)^\*1^\* + 0(00)^\*1^\*\ 10\ 1^\*01^\*(01^\*0)^\*1^\*$$

This is not meant to be the smallest possible expression, but at least it shows how you can construct one. For instance, you can factorize the common parts to obtain $$ (00)^\*(1^\*10+01^\*101^\*0)1^\*(01^\*0)^\*1^\*.$$
> 1 votes

---
Tags: formal-languages, regular-expressions
---


# Question
Title: Integer Linear Programs: An instance or not?
Given a set of integers $\\{x\_0, x\_1, ... , x\_{n-1}, x\_n\\} \subseteq \mathbb{Z}$, a set of integer variables $\\{y\_0, y\_1, ... ,y\_{n-1}, y\_n\\} \subseteq \mathbb{Z}$ and an integer $m \in \mathbb{Z}$ is the following equation an instance of an integer linear program (ILP):

$ (x\_1\cdot y\_1) + (x\_1\cdot y\_1) + \cdots + (x\_{n-1}\cdot y\_{n-1}) + (x\_n\cdot y\_n) = m $ i.e. is there an assignment of variables $y\_i$ such that the equation is true? After googling around I noticed that ILPs usually involve maximising or minimising a variable, but that is not what is needed here. If not, could anyone tell me what type of problem this is and if there are any known complexity results?

# Answer
> 3 votes
Your problem has a solution if and only if $m$ is a multiple of the greatest common divisor of $x\_1,\ldots,x\_n$. You can compute the GCD in polynomial time using the Euclidean algorithm (the version where you divide in each step rather than subtract) applied $n-1$ times.

---
Tags: decision-problem, integer-programming
---


# Question
Title: Recurrence relation with a number value (not n)
I'm learning how to use recursion trees to solve recurrence relations and while I know how to solve it for the form

$$T(n) = aT\big(\frac{n}{4}\big) + n$$

I'm stuck when the equation has a numerical term, like

$$T(n) = aT\big(\frac{n}{4}\big) + 3$$

Using a recursion tree, what gets multiplied at the first, second, third level? And what is the sum of the work done?

# Answer
> 2 votes
The recursion tree corresponds to repeated expansion of the recurrence: $$ \begin{align\*} T(n) &= 3 + aT(n/4) \\ &= 3 + 3a + a^2T(n/16) \\ &= 3 + 3a + 3a^2 + a^3T(n/64) \\ &= \cdots \\ &= 3 + 3a + \cdots + 3a^{k-1} + a^kT(n/4^k) \\ &= 3\frac{a^k-1}{a-1} + a^kT(n/4^k). \end{align\*} $$ This is the result if you stop the recursion after $k$ steps. If, for example, you define $T(1) = 3$ then for $n = 4^k$ you will get $T(n) = 3+3a+\cdots+3a^k = 3\frac{a^{k+1}-1}{a-1} = \Theta(a^{\log\_4 n})$.

---
Tags: recurrence-relation
---


# Question
Title: Can anyone explain why this is an inadmissible recurrence case that cannot be solved by the master theorem?
Wikipedia says that the following recurrence is *inadmissible* since there is a non-polynomial difference between $f(n) = \frac{n}{\log n}$ and $n^{\log\_b a}$:

$$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n} $$

In human language, what does non-polynomial difference mean? Why was $n/\log n$ compared to $n^{\log\_ba}$ in the first place?

In addition, what happens if I replaced $n/\log n$ with $n/\log^\*n$, where $\log^\*n$ is the log-star function. Would a similar type of analysis take place?

# Answer
> 3 votes
A non-polynomial difference just means that the quotient $\frac{n/\log n}{n^{\log\_b a}} = \frac{1}{\log n}$ is not a polynomial, where here $a=b=2$. To see why this is a problem, let's try to apply the master theorem.

Case 2 states that if $f(n) = O(n^{\log\_b a} \log^k n)$ for some $k \geq 0$ then $T(n) = O(n^{\log\_b a} \log^{k+1} n)$. In our case we can choose $k = 0$ and obtain the bound $T(n) = O(n\log n)$. If we also had $f(n) = \Omega(n^{\log\_b a} \log^k n)$ then $T(n) = \Omega(n^{\log\_b a} \log^{k+1} n)$, but this doesn't hold in our case.

Case 1 states that if $f(n) = O(n^c)$ for $c \< \log\_b a$ then $T(n) = O(n^{\log\_b a})$. In our case $c = 1$ so this case doesn't apply.

Case 3 states that if $f(n) = \Omega(n^c)$ for some $c \> \log\_b a$ then $T(n) = \Omega(n^c)$. In our case $c \< 1$ so this case also doesn't apply.

Summarizing, the master theorem only gives the upper bound $T(n) = O(n\log n)$. We trivially have $T(n) = \Omega(n/\log n)$, but this doesn't match the upper bound.

We can determine the exact asymptotics using the Akra–Bazzi method. In our case $p = 1$ and $g(x) = x/\log x$, so $T(n) = \Theta(n(1+G(n))$ where $$ G(x) = \int\_1^x \frac{g(u)}{u^2} \\, du = \int\_1^x \frac{du}{u\log u} = \log\log x. $$ (Formally, we have to change the lower bound of the integration from $1$ to $e$.) We conclude that $T(n) = \Theta(n\log\log n)$.

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: books on algorithms for beginners in Ruby or Python or C. Not too math heavy
I am currently at student at Turing and I would like to learn more about algorithmic design while studying programming. Our school mainly deals more with web software, Ruby, and Rails, but I would like to gain an education in algorithms and data structure while here.

Do you have any books for beginners on algorithms or data structure? I only know Ruby and a little Python. Is there anything that you recommend that isn't the CLRS book... it's a tad over my head right now.

How much mathematics do I need to know? My guess is that I also need a book on discrete mathematics?

# Answer
To be honest, it doesn't really matter what languages you use to learn an algorithm (it's only the syntax that changes, the logic is the same).

However, if you want a Python specific one check out:

A more generic one is by the O'Reilly series (they make wonderful books!):

There are also a number of youtube tutorials, so check out this, although it is in Java, it is very good!
> 4 votes

---
Tags: algorithms, books
---


# Question
Title: What does an NFA do if there's no transition with the correct symbol?
So I am learning about DFA and NFA, and I need some clarification for it.

DFA

* accept empty set
* transition for every element in the alphabet
* path are deterministic

NFA

* accept the empty set and empty string
* path are not deterministic

My question is does NFA need a transition for every element in the alphabet? If not, then let say the alphabet is {0. 1} and I am at a state without the transition for 1, do I go to the empty state or something?

# Answer
In a DFA, if you are in state $p$ and see an input character $c$, one of three things may happen:

1. You can consume that character (i.e., read it) and change to state $q$ ($q$ may be $p$ or not).
2. There may not be a move defined for the pair $(p, c)$ in which case the DFA halts and rejects the input string.
3. If the DFA is in a final state after having read all the input, it accepts the input, otherwise it rejects the input.

For an NFA, you have more possibilities:

1. In state $p$ with input $c$ you can consume the input and change to *several* states $q\_1, q\_2, \dotsc$ .
2. In state $p$ you can elect not to consume the input and change to several states $q\_1, q\_2, \dotsc$. This is called an *epsilon move*. In essence, your machine may change state without reading any input.
3. As with a DFA, there may not be any move defined for the pair $(p, c)$ or $(p, \epsilon)$ in which case the NFA halts that branch of execution.
4. If the NFA is in a final state in any particular branch of its execution and has consumed all the input, it accepts the input. If it hasn't reached any accept state after having read all the input, it rejects.

In either a DFA or an NFA, you don't need to have moves defined for all possible (state, character) pairs. If you're in state $p$ and there is no move defined for an input character, the machine (or that branch) halts and rejects.

Some people don't like this behavior and complete the automaton by creating what you apparently call an empty state and defining transitions to that state on those missing inputs. Once you're in that state (also known as a dead or error state), you never leave, no matter what the input is.
> 11 votes

# Answer
No, NFAs can have any number of transitions for a given symbol1 from a state. If the NFA gets into the situation where the current symbol from the input has no transition from the current state, then the current path fails. If every possible path fails (in this way, or if it fails to reach an accept state at the end of the input) the NFA rejects the input.

1. Any *sensible* number of course; being an integer in the range 0 to the number of states inclusive.
> 3 votes

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


# Question
Title: Is Binary Search Related to Binary Search Tree?
I was reading binary search and suddenly realized that it would be very difficult for a binary search tree to find the middle value and then split in two. Are these related at all?

# Answer
> 2 votes
A balanced binary search tree describes the working of the binary search algorithm on a sorted list. The root should contain the middle element, the left subtree the left half, the right subtree the right half, and so on recursively. The tree also has to be balanced, that is, to reflect the fact that we chose the middle element as the root. In this sense, a binary search tree is a generalization of binary search on a sorted list.

---
Tags: search-algorithms
---


# Question
Title: In computer science how is using passive voice regarded?
A soft question, when I was in high school and in University I took scientific writing classes and people told me I should use passive voice as much as possible to sound objective, but when I entered grad school people told me I should not use passive voice unless I work in Chemistry. So Which one should I follow?

# Answer
> 6 votes
The bottom line advice is: Use whichever voice best aids understanding.

Many people over-use the passive voice, thinking that it makes them sound more scientific. In practice, it's more common for the passive voice to make sentences harder to follow.

Therefore, as a rough guideline, it's helpful to use the following principle: use the active voice whereever possible. If you find yourself writing in passive voice, check whether your sentence would be clearer, simpler, or easier to understand if written in the active voice.

I recommend you read style guides on clear writing. You'll find they tend to warn against over-use of passive voice: active voice often makes sentences simpler, more direct, more forceful, more vivid, and thus both more concise and more memorable. Strunk & White have some good examples of this guideline; see, e.g., Rule 11 and Rule 12.

There are some special cases where there are conventions or norms within the field that are worth following. See, e.g.,

# Answer
> 1 votes
There is some discussion of passive voice in CS papers in this comprehensive but no-so-well publicized "insider" reference (which apparently hasn't been officially published even by the authors except recorded electronically as class notes) by a leading authority in the field Knuth & teaching cohorts. Generally both passive and nonpassive ("active" or "imperative") forms of writing are used in CS with some major examples of each. They discuss use of style analysis programs which also automatically score the passive versus imperative sentence constructions, and can be used for guidance, different uses in the abstract versus the body, and so on. Overall, it comes down to style preferences and guidelines. Overuse of either form is generally to be avoided.

Mathematical writing by Donald E. Knuth, Tracy Larrabee, and Paul M. Roberts.

See page 110, and also search for "passive" and "imperative" keywords in the document.

> Paul now moved on to the final area of discussion: Style. Rule #6 in § 1 suggests that we use 'we' to avoid passive voice. This use of 'we' is equivalent to "the reader and 1" . Paul says that even better is to avoid both passive voice and the use of 'we' through judicial use of imperative and indicative moods along with an outlying kind of non-sentential phrase.

---
Tags: research
---


title: Pumping lemma for 0^n and n>0

text:
# Question
Title: Pumping lemma for 0^n and n>0
When applying the pumping lemma to $L = \\{ 0^n \mid n\>0\\}$ I do the following:

$S = 0^p$
$x = \varepsilon$
$y = 0^p$
$z = \varepsilon$

so $S = xyz = (\varepsilon)0^p(\varepsilon)$

For $x y^i z$ if i choose $i = 0$ (pumping down) i get $S = \varepsilon$, which is not an element of $L$.

Therefore according to the pumping lemma this language is not regular. But since I am able to draw a DFA for $L$, I know it *is* regular.

I would like to know what rules I am violating by trying to apply the pumping lemma to $L$ in this manner.

# Answer
The pumping lemma says that you **can** split the word into $xyz$. It doesn't say that *every* such split works. For instance, if you take $|x|=1$ in your example, the pumping works up and down. This would be a "correct split" that makes the pumping lemma hold.

As a reference, recall the definition of the pumping language for regular languages (from Wikipedia):

> Let $L$ be a regular language. Then there exists an integer $p\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = xyz$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:
>
> 1. $|y| \ge 1$
> 2. $|xy| \le p$ and
> 3. for all $i \ge 0$, $xy^iz \in L$.
> $y$ is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in $L$).
> 1 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Explanation of Summations for Algorithm Analysis
I do not have a background in Computer Science, work as a Software Engineer, and am attending college for my Master's degree in Computer Science. I have a data structures and algorithms course that I am taking currently with the "Introduction to Algorithms" text book by Cormen, Leiserson, Rivest, and Stein (CLRS). This is not one of my homework problems, but rather extra effort for me to try and understand algorithm analysis as it relates to using summations.

For instance, consider the example of $T(n) = T(n-2) + n^2$. An answer I saw floating around had $\sum\limits\_{i=0}^{n/2} (n-2i)^2$. I can understand how to get the $(n-2i)^2$ part, but am not sure how to get the upper and lower boundary conditions, as well as what to do after this point. I guess the total answer for this is $\Theta(n^3)$, but am not making the connection between the summation and the final answer.

I have had calculus in the past, and do remember some of the series chapter that dealt with harmonic, Taylor, geometric, telescoping, and power series. But as it relates to CS, I'm not quite sure where it is going.

So, my questions are:

1. Why are the lower and upper bounds 0 and n/2, respectively?
2. What do I do with the summation notation to get a final answer?

I'm sure this is easily answered and that I'm just overlooking something. I know that a series that looks like the harmonic series, which is $\sum\_{i=1}^n (1/i)$, will give $\ln(n) + O(1)$. But most of it I don't understand how to get the values associated with Big-O, Omega, or Theta.

I appreciate the help, guidance, and any examples/tutorials you can point me to.

# Answer
I will answer each of your questions as follows

1. Why are the lower and upper bounds 0 and n/2, respectively?

* For the lower bound: we can see that at the first recursive call, the running time is $n^2$ so $n^2 = (n - 2i)^2$ when $i = 0$
    * For the upper bound: we can see that when a base case is given say $T(1) = a$, ($a$ can be some constant that for the purpose of calculating the upper bound, we don't really care) then to reach to the base case, you will need to apply the recurrence formula $x$ times which means you need to solve for $x$ the equation $((n - 2) - 2) .. -2) = 1$. This equation is $n - 2x = 1$ which will give you $x = \frac{n-1}{2}$. To make things easier for readers, someone might consider the base case is $T(0)$. In this case you will instead solve $n-2x=0$ giving $x=\frac{n}{2}$. This is your convenient upper bound $\frac{n}{2}$.
2. What do I do with the summation notation to get a final answer?

A good way to solve summation like the one you give for the purpose of asymptotic bounding (such as $O$, $\Omega$, $\Theta$) is using integration. Let's look at the following graph, so you can easily visualize the approach and main idea.

Let's look at the interval where the terms in your summation are monotonic. In your particular case, the terms in your summation decreases as $i$ increases in the interval of $\[0, \frac{n}{2})$. This is because the each of the terms is a parabola on variable $i$, and this parabola has a single minima at $i = n/2$. As $i$ increases, the parabola decreases until $i$ reaches $n/2$ then the parabola start increasing.

Let's not worry too much about the actual value on the y-axis, but focus on the fact that your summation can be view as the summation of all the cyan blocks having width 1. As the terms monotonically decrease, you have $(n - 2i)^2 \< (n - 2(i-1))^2$. Then you choose the function $f(x)$ using the right hand side replacing the variable $i$ with the variable $x$ which is the red line in the graph. $f(x)= (n - 2(x-1))^2$ thus you have $\sum\limits\_{i=0}^{n/2} (n - 2i)^2 \< \int\limits\_{0}^{n/2} (n - 2(x-1))^2dx$

Now you solve the right hand side of the above inequality. This will give you $-\frac{1}{2}\frac{1}{3} (n - 2(x-1))^3 \Big|\_{0}^{n/2} = -\frac{8}{6} - (- \frac{1}{2}\frac{1}{3}(n+2)^3) = \frac{(n+2)^3 - 8}{6} \in O(n^3)$. So you have $T(n) \in O(n^3)$

If you want to find the bound for $\Omega$, then you will do similarly. The difference now is that you choose $f(x) = (n - 2(x+1))^2$ because the terms in the summation are greater than the next term $(n - 2i)^2 \> (n - 2(i+1))^2$. Your summation now can be seen as the bigger cyan plus blue (and purple) blocks. In other words, $\sum\limits\_{i=0}^{n/2} (n - 2i)^2 \> \int\limits\_{0}^{\frac{n}{2}-1} (n - 2(x+1))^2dx$. Note that I have changed the upper bound on integration because getting over $\frac{n}{2}-1$ the terms change direction. But that is ok, because we still have the bound on $\>$ sign

Solving the integration will give you a polynomial of degree 3 so you have $T(n) \in \Omega(n^3)$.

So now you can conclude that $T(n) \in \Theta(n^3)$

*Extra:* Back up image in case the graph above is no longer viewable: Summation bound
> 3 votes

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


# Question
Title: Is it possible to obtain a total function by composition of partial functions?
This statement is Theorem 1.1 (page 39) of *Computability, Complexity and languages* by Martin Davis:

> If function $h$ is obtained from the (partially) computable functions $f$, $g\_1$, $g\_2$, ..., $g\_k$ by composition then $h$ is (partially) computable.

What I understand from this theorem is if there is at least one partial function among the composed function then $h$ is partial function. Am I right?

Here is an example, the functions $x$ and $x+y$ and $x.y$ are total but $x-y$ is a partial function. it is possible to obtain $4x^2-2x$ by composition of these functions in the following way, this function is total but it is obtained from an non-total function ($x-y$).

$2x = x+x$

$4x^2 = (2x)(2x)$

$4x^2-2x$ *composition of $x-y$*

This is an example from the book, is this example a contradiction of the theorem?

# Answer
> 8 votes
The theorem should be read as "If you compose computable functions, you get a computable function; if you compose partial computable functions, you get a partial computable function."

Note that, perhaps confusingly, partial computable is a larger class of functions: every computable function is partial computable. One could reduce the confusion at the cost of verbiage by calling them total computable functions and partial-or-total computable functions. If you compose total computable functions, the result is a total computable function. If you compose partial-or-total computable functions, the result is a partial-or-total computable function.

Your example in the question shows that it's possible to combine a total function and a non-total function to get a total function. Notice that both examples actually only apply total functions directly to the inputs and at least one of the inputs to the non-total function is the output of a total function. In those circumstances, it's still possible to get a total function as the result of the composition. Conversely, if you apply a non-total function directly to your inputs (and none of its inputs is the output of some total function), your composition is guaranteed to be non-total.

# Answer
> 6 votes
This is a confusion about terminology:

* A function $f : A \to B$ is **total** if it is defined everywhere on $A$.
* A function $g : A \to B$ is **partial** if it is defined on a subset $A' \subseteq A$, called the **domain** of $g$.

Cruicially, there is **no requirement** that $A'$ be a proper subset of $A$. Thus, **every total function is also a partial function**.

This is common practice in mathematics. For instance, a square is also a rectangle, an equilateral triangle is also an isosceles triangle, a smooth function is also continuous, etc.

---
Tags: terminology, computability, semi-decidability
---


# Question
Title: Find a 3-colouring using the 3-colourability decision problem
I was learning about NP problems. I read that for many problems, like Clique, we can easily convert its decision problem to derive a solution of search problem. (For Clique problem, you only need to enumerate the vertices of $G$ and delete any vertex that if your decision function tells you is not in the clique) But for 3-COLOR problem, I have no idea of how to link decision problem to search problem. Can anybody help me?

# Answer
Let the vertices of the input graph $G$ be $\\{v\_1, \dots, v\_n\\}$. First, check if $G$ is 3-colourable: if not, output "No 3-colourings" and quit.

Otherwise, add new vertices called $r$, $g$ and $b$ to $G$ and add the edges $rb$, $bg$ and $br$. Call this graph $G\_0$. Note that $G\_0$ is 3-colourable and, in any 3-colouring of $G\_0$, the three new vertices must receive different colours. Since the names of the colours are arbitrary, we will call the colour that $r$ gets, red; call $g$&'s colour, green; and call $b$'s colour blue.

We'll now create a sequence of graphs $G\_1, \dots, G\_n$, each of which will be 3-colourable, creating $G\_i$ from $G\_{i-1}$ as follows.

* Set $G\_i = G\_{i-1} + \\{rv\_i, gv\_i\\}$ (i.e., the graph made by adding edges $rv\_i$ and $gv\_i$ to $G\_{i-1}$) if this graph is is 3-colourable. Since $v\_i$ is adjacent to both $r$, which is red, and $g$, which is green, $v\_i$ must be blue.
* Otherwise, set $G\_i = G\_{i-1} + \\{gv\_i, bv\_i\\}$, if this graph is 3-colourable. In this case, $v\_i$ must be red.
* Otherwise, set $G\_i = G\_{i-1} + \\{bv\_i, rv\_i\\}$. Since $G\_{i-1}$ was 3-colourable (you can prove this by induction), and we couldn't find a colouring with $v\_i$ blue or red, $v\_i$ must be green.

The above procedure produces a 3-colouring of the $n$-vertex graph $G$ with $2n+1$ calls to the oracle (procedure) for checking 3-colourability.
> 6 votes

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


# Question
Title: Difference between a lambda term and a lambda expression
Is there any difference between a $\lambda$-term and a $\lambda$-expression?

Looking at the recursive definitions on Wikipedia of $\lambda$-term and $\lambda$-expression, they are equivalent. But I am confused as they are slightly different and refer to what they define by a different name.

# Answer
Books on lambda calculus define only lambda terms. Some programming languages may call anonymous function lambda expressions.
> 2 votes

---
Tags: terminology, lambda-calculus
---


title: Proving approximation ratio

text:
# Question
Title: Proving approximation ratio
We recently in computational complexity class dealt with approximation algorithms and I was wondering how one would prove a heuristic having a certain ratio in regards to the optimal version. Looking at some notes it seems that one has to relate the approximation to an intermediate algorithm, right?

# Answer
> 3 votes
It's not necessary to compare to an intermediate algorithm, just to the best possible.

For example, consider the following terrible algorithm for approximating the distance between two vertices in a graph: if the vertices are adjacent, return $1$; otherwise, return $n$, the number of vertices. This gives an $n/2$ approximation: in the worse case, the true distance is $2$ but the algorithm returns $n$.

But perhaps you're concerned that we might not know the true optimal value – after all, it's probably hard to analyze and compute. That's why we're using an approximation algorithm, right? So let's imagine that the distance between vertices is really difficult to calculate so we don't actually know what the worst case of our approximation algorithm is. At that point, you can start using approximations or, rather, bounds on the optimal value. So, for example, somebody might say, "Hey, I've no idea what the greatest possible distance between two vertices in a graph is but I know it's the length of the shortest path. A path has to use some set of edges, and use them once each. I know there can't be more than $n^2$ different edges in a graph, so the worst-case distance can't be more than $n^2\\!$. Therefore, the approximation ratio can't be any worse than $n^2/2$." And they'd be right: the approximation ratio isn't any worse than that. The "more sophisticated" analysis in the previous paragraph gave a better bound on the approximation ratio.

---
Tags: algorithm-analysis, approximation
---


# Question
Title: Comparing coefficients of boolean functions
Let a real polynomial representing a boolean function be $P(x\_1,\dots,x\_n) = \sum\_{a\in\\{0,1\\}^n}c\_ax^a = \sum\_{a\in\\{0,1\\}^n}p(a)\prod\_{i\in 1\_a}x\_i\prod\_{j\in \bar{1}\_a}(1-x\_j)$ where $1\_a$ is the set of $i$ such that $a\_i=1$ and $\bar{1}\_a$ is the complement of $1\_a$. How do you represent $c\_a$ in terms of $p(a)$?

Is for all $b\in\\{0,1\\}^n$, $c\_{b} = \sum\_{a\in\\{0,1\\}^n}(-1)^{\<b,a\>}p(a)$?

# Answer
Consider the function $P(x\_1) = x\_1$. Then $P(0) = 0$, $P(1) = 1$, and the polynomial representation is $x\_1$, but your formula gives $c\_0 = 1$ and $c\_1 = -1$. However, if we define $\hat{P}(b) = 2^{-n} \sum\_{a \in \\{0,1\\}^n} (-1)^{\langle a,b \rangle} P(a)$ then $$ P(x) = \sum\_{b \in \\{0,1\\}^n} \hat{P}(b) (-1)^{\langle x,b \rangle}. $$ This is known as the *Fourier expansion* of $P$. To relate this to your expansion, notice that $$ (-1)^{\langle x,b \rangle} = \prod\_{i\colon b\_i=1} (-1)^{x\_i} = \prod\_{i\colon b\_i=1} (1-2x\_i). $$ It is now an exercise to relate the coefficients $\hat{P}(b)$ to the coefficients $c\_b$ you are interested in.
> 1 votes

---
Tags: boolean-algebra, polynomials
---


# Question
Title: compressing a set of binary strings with fixed length
I'm looking for a data structure / algorithm to store an unordered set `S` of binary strings of a fixed length `n` (i.e. all matching the following regular expression: `[01]{n}`).

Insertion and lookup ("Is element `x` in the `S`?") should maximally take polynomial time to `|S|`.

The space complexity should be logarithmic to `|S|` for large sets. In other words, the space should not be exponential to `n` if for example `2^n / 2` random and unique strings are inserted, but polynomial to `n`.

Is such a thing known to exist?

# Answer
> 4 votes
Suppose $S$ consists of $m$ strings in $\\{0,1\\}^n$ and we don't allow query arrows. Any two different sets $S\_1,S\_2 \subseteq \\{0,1\\}^n$ of size $m$ respond differently to some lookup query: there must be some $x \in S\_1\setminus S\_2$, for example, and the lookup of $x$ should succeed in $S\_1$ and fail in $S\_2$. For this reason, the contents of your data structure should be different for $S\_1,S\_2$. Since there are $\binom{2^n}{m}$ different choices for $S$, any data structure supporting all of them should have at least $\binom{2^n}{m}$ different settings. In particular, if you use $M$ bits to store it then $2^M \geq \binom{2^n}{m}$. When $m = 2^n/2$, for example, this forces $M \geq 2^n - O(n) = 2m - O(\log m)$.

---
Tags: data-structures, strings, sets
---


# Question
Title: Interactive example of Dynamic scoping and evaluation order of expressions
Given the following (arbitrary language, although I think it is close to Algol 60) program:

```
program main;                               // A main parent level
  var i : integer;                          // A 'global' variable

  (* Note that all parameters are passed by value here *)

  function f1 (j : integer) : integer;      // A Child function
  begin { f1 }
    i := i + 3;
    f1 := 2 * j - i;
  end; { f1 }

  function f2 (k : integer) : integer;      // Another Child function, same level as f1
    var i : integer;                        // Here, there is a variable that is declared
  begin { f2 }                                 // but no value assigned
    i := k / 2;
    f2 := f1(i) + f1(k);
  end; { f2 }

begin { main }                              // Running/Calling/Executing the code
  i := 8;
  i := i + f2(i);
  writeln(i);
end. { main }

```

How would you trace the values of variables throughout the program when it is interpreted using Dynamic scoping of free variables, when the arguments appearing in expressions are evaluated left to right, and when they are evaluated right to left, so that the user can watch what happens

I have created a JS plnkr for Static Scoping with Left to Right evaluation and another for Static Scoping with Right to Left evaluation. Feel free to adapt these answers (if possible) for Dynamic Scoping, with L-\>R and R-\>L evaluation.

I chose plnkrs because I knew I could get the Static/lexical side using JS, but am unsure of how to make it happen *dynamically* or in another interactive environment (preferably not one I have to install).

I learn a bit slower on some problems like this where the values are asked of the output, but don't show the value states throughout the program, and trying to get a better understanding, especially in an example I can play around with interactively, as the book examples are really bad. In the code above, it also gets challenging, because it appears that the variable `i` in line 2 is allocated, but would be `undefined`. But that may be my imperative/functional brain making it more complicated than it is...

# Answer
> 1 votes
I do not know other environments in existing languages, whether statically or dynamically scoped. Also, that would be language specific, hence off topic here.

Without a system environment, the way I would do this would be to insert print statement in my program, either by hand if I am poor, or with a some programmable program transformation system. I actually did it often a very long time ago for debugging purposes, applying program transformations I had developed in such a program transformation system.

Your example is rather simple as the formal parameters `j` and `k` are never modified, so that everything can be assumed to be call by value. But things can get very hairy when formal parameters get modified in the function, depending on the parameter passing mode.

I am also a bit surprised that your system gives you the post value of `i` in `f2` at the beginning rather than at the end of the trace.

You may try to trace the values of variable that are not visible in the function currently executed, for example by printing them with a function defined at the right place. But that can only work when the function uses static scoping.

My basic philosophy is that dynamic scoping is an endless source of problems because you cannot know what a free variable stands for, as it may vary from call to call. I know that some people like it and say it is useful. I will not comment.

Dynamic scoping was invented as a bug in the first Lisp interpreter, in the late fifties. When they realized what they had done, the beast was out. Scheme corrected that, but much later.

I am not sure I answered you. But I now realize this question is borderline on this site.

---
Tags: programming-languages, programming-paradigms, variable-binding
---


# Question
Title: Which algorithm to use to find all common substring (LCS case) with really big strings
I'm looking for a particular case of longest common substring (LCS) problem. In my case I have two really big strings (tens or hundreds of milions byte characters) and need to find the LCS and other long strings.

A simplified example

$S\_0$ = ABBCADGGHEEASSSCC

$S\_1$ = ABDCADGGHMEASSSAC

the LCS = CADGGH (6 chars) and other long strings with 5 chars are CADGG, ADGGH and EASSS.

Which is the fastest algorithm to get all substrings with its length? (list all substrigs and legths) And in my case (very big byte substrings) which is the fastest LCS algorithm? (only get longest common substrings).

**NOTE**: In particular I don't have any space limit now, but this algorithm may be implemented in a mobile device in a future and is possible to have a very limited RAM/disk space (but always, at least, I have the same disk space available as the sum of file lengths).

# Answer
I came across this problem before. I compressed the strings and applied dynamic programming on the compressed strings.

For compression techniques, I followed the methods described in this paper: http://pdf.aminer.org/000/145/966/data\_compression\_using\_long\_common\_strings.pdf

The speed was decent. But, it consumed some space though.
> 1 votes

---
Tags: algorithms, strings, substrings, longest-common-substring
---


# Question
Title: Are conditionals necessary in computation?
I know this question might seem weird, maybe I'm just overthinking, but this is really troubling me because I've been a computer engineer for some time now and conditionals (if statements for instance) always seemed pretty clear and intuitive!

I mean, let's assume that I have a program which starts at

```
int main(int argc, char** argv) // in C

```

How am I supposed to know what is inside argv and argc? My old, intuitive answer: if statements. Using if statements, I would decide based on the input how to execute my program... I never considered any possibility other than having the input provided under this way, and I, as a programmer, could only mess with what is after the call to the program, with the input already defined. Hence I had no doubt that I needed to use conditionals.

I have ONLY 1 PROGRAM that needs to execute for ANY input and provide the right answers, hence I can't avoid if statements. It all seemed alright, for years now... until I started to think... Could there be other ways?

What if I had a different version of my program for each possible input? The operating system or the hardware could then call a different version according to the input. Then I thought – this would simply delegate the if statements to either the operating system or the hardware, respectively.

Then I even thought, what if the user had a different computer for each different input? I know this might seem really stupid, but I'm just trying to understand the "law" behind the need for conditionals in our physical world!

Also, in this last example it could be argued that the conditional would simply have to be executed in the user's brain (when he decides which computer to use based on the intended input).

Can someone give me some light in this subject? This is really troubling me :( maybe I've overthought things and now I'm paying the price for it...

# Answer
One argument that conditionals are not fundamental to computation is that there are turing complete models of computation that don't use anything resembling conditionals. For example, you can think of the lambda calculus as an untyped programming language where the only operation is function application. There is no branching involved: all the computation is just taking the function's arguments, and substituting it in for all uses of that argument inside the function itself.

But, another way of looking at this is that any turing complete model of computation can *simulate* conditionals in some way. For example, a simple idea for branching in the lambda calculus is that "true" is a function that takes 2 inputs, an if branch and an else branch, and then returns the if branch $(\lambda x. \lambda y . x)$. Meanwhile "false" is a function that takes 2 inputs, an if branch and an else branch, and returns the else branch $(\lambda x. \lambda y . y)$.

Then, in the lambda calculus, a program like "if T then foo else bar" would be encoded like $(T)(foo)(bar)$, which is to say applying foo and bar as arguments to the function T.

Or, more trivially, every turing complete model can simulate the turing machine, which is a state machine (and thus evaluates based on a conditional at every time step).

Anyways, as for the more realistic models of computation that you are used to, one reason you need conditionals is because if you didn't have conditionals, every program you write would either loop forever or execute in O(1) ((where we consider the size of your program to be constant)). Think about it: no conditionals means no loops (unless you use an unconditional jump, but then you will just loop forever). But, without loops, each line of your program will be executed exactly once. Thus, every program runs in O(1). This essentially means you can't solve any interesting problems.

However, I would argue that the more fundamental issue here is that loops (or some equivalent, such as combinators) are fundamental for computation. If you remove the ability to make a "goto", then even with conditionals your language will not be turing complete (by the same argument: your code will simply execute along some control flow path exactly once then terminate in O(1), and not every problem can be solved in O(1)).
> 4 votes

---
Tags: algorithms, turing-machines, computation-models, turing-completeness, church-turing-thesis
---


title: Resolving ambiguity in dangling else

text:
# Question
Title: Resolving ambiguity in dangling else
Initially the ambiguous grammar is as follows (with some cropped production rules):

```
<STMT>         -->  <IF-THEN> | <IF-THEN-ELSE>
<IF-THEN>      -->  if condition then <STMT>
<IF-THEN-ELSE> -->  if condition then <STMT> else <STMT>

```

To resolve the ambiguity, the previous grammar is transformed into the following one in the book I study:

```
<STMT>           -->  <IF-THEN> | <IF-THEN-ELSE>
<IF-THEN>        -->  if condition then <STMT>
<IF-THEN-ELSE>   -->  if condition then <E-STMT> else <STMT>
<E-STMT>         -->  <E-IF-THEN-ELSE>
<E-IF-THEN-ELSE> -->  if condition then <E-STMT> else <E-STMT>

```

What I cannot get is that why the following rule is necessary.

```
<E-IF-THEN-ELSE> -->  if condition then <E-STMT> else <E-STMT>

```

As far as I think about, the update on `<IF-THEN-ELSE>` and introduction of `<E-STMT>` is sufficient to resolve the ambiguity. Could you please give an example refuting my argument? Thanks..

# Answer
> 1 votes
I assume that one can also derive some atomic statements from `<STMT>` and `<E-STMT>`, otherwise the language of both grammars would be empty and all would be quite trivial. :-) But that aside:

The new grammar should do two things: it should be unambiguous and it should generate the same language.

The variables `<E-STMT>` and `<E-IF-THEN-ELSE>` are introduced to remember part of the context in which the variable occurs. What you want to accomplish, is that the variables `<STMT>`, `<IF-THEN>` and `<IF-THEN-ELSE>` cannot occur in a position directly preceeding an `else` symbol, and also that the variables `<E-STMT>` and `<E-IF-THEN-ELSE>` *must* occur in a position directly preceeding an `else` symbol. So, if we see a `<E-STMT>` or `<E-IF-THEN-ELSE>` somewhere, we know that the next symbol must be `else`, and if we see an other variable we know that the next symbol cannot be an `else`. This way we have some week form of "context-awareness".

If we remove the rule for `<E-IF-THEN-ELSE>` and replace the rule for `<E-STMT>` by

```
<E-STMT> -> <IF-THEN-ELSE>

```

then we can derive the following:

> `<STMT>` $\to$
> `<IF-THEN-ELSE>` $\to$
> `if condition then <E-STMT> else <STMT>` $\to$
> `if condition then <E-IF-THEN-ELSE> else <STMT>` $\to$
> `if condition then if condition then <E-STMT> else <STMT> else <STMT>`

and here a `<STMT>` variable which directly preceeds an `else` symbol. This will lead to ambiguities.

If we try to fix this and additionally change the if-then-else rule to

```
<IF-THEN-ELSE> --> if condition then <E-STMT> else <E-STMT>

```

then we can perform the derivation

> `<STMT>` $\to$ `<IF-THEN-ELSE>` $\to$ `if condition then <E-STMT> else <E-STMT>`

and here we have an `<E-STMT>` variable without a following `else` symbol. Since the `<E-STMT>` generates no if statements without else clause, the language of the new grammar is not the same.

The grammar which was proposed in the book solves both these problems.

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


# Question
Title: Given two sequences of the same size, how many longest common subsequences can they have?
For simplicity assume that both have the same size N.

the lengh of this subsequence can be at most N, so maybe it's

`max(C(N,1), C(N,2), ... , C(N,N))`?

# Answer
> 1 votes
I understand the question as follows:

Given $n$. How many different longest common consecutive subsequences might two strings of length $n$ have at most?

If this is your question, than consider for example the string $a\_1a\_2...a\_n$ with $a\_i\ne a\_j$ for $i\ne j$ and the reverse string $a\_na\_{n-1}...a\_1$. The longest common subsequences of those strings are all subsequences of length $1$ $(a\_1,a\_2,...,a\_n)$. Therefore, in your unrestricted question, the maximal number of different longest common subsequences of two strings of length $n$ is equal to the the maximal number of different subsequences with same length, which is $n$ for subsequences of length $1$.

If you restrict the question to strings over a given alphabet of fixed size, lets say $k$, the answer is much more difficult.

---
Tags: combinatorics
---


# Question
Title: Finite number of Turing machines running concurrently on multi-tapes Turing-machine-equivalent?
So basically, there are several (finite number of) Turing machines being able to read off and write to the same set of tapes (the number of tapes is finite, but each tape may have infinite tape spaces). And then we consider a group/machine of these machines to solve a problem. Would this machine be Turing machine-equivalent?

# Answer
> 4 votes
A roung, informal sketch of how I would prove this:

1. We can simulate multiple threads running concurrently in a programming language like C. (Note that this is without hardware support! There are some cool ways to do this, my favorite is using continuations in Scheme, inserting a call to a thread scheduler whenever a function returns).
2. We can simulate a multi-tape TM with a single-tape TM.
3. We can simulate a single-tape TM in a programming language like C.

From this, we get that we can simulate a multi-tape TM in our programming language. Since we can simulate threads, we can now simulate multiple multi-tape TM's running concurrently. And, since we can simulate C with a single-tape TM, we can simulate the whole thing with a single-tape TM.

The transitivity of turing-completeness is a useful tool. That is, if A simulates B, and B simulates C, then A simulates C.

# Answer
> 2 votes
In order to show formally that your model only computes computable functions, you need to prove a simulation result: given a set of Turing machines communicating according to some protocol, show how to simulate them on a single Turing machine. Such simulation results show, for example, that multitape Turing machines are no stronger than single tape Turing machines.

The first step in a formal proof would be to formally define your model of computation. Then, given an instance of your model, you have to show how it can be simulated on a Turing machine, or on any other equivalent model. This is going to be very messy, but probably doable.

We usually rely on the Church-Turing thesis and our intuition instead of proving things formally. The reason is that usually such extended computation models are given in order to simplify some proof - to present it in a more comprehensible manner. It would defeat the purpose if each time we would have had to spend many pages proving simulation results.

In the same way, proofs in mathematics are usually not formal in the sense that they are given in some formal axiom system, but rather they rely on the mathematical judgment of the reader. This is part of what is sometimes called mathematical maturity - presenting things using the correct amount of detail.

---
Tags: computability, turing-machines, computation-models, turing-completeness
---


# Question
Title: Linear congruential generator with uniform distribution
I am currently studying linear congruential generators, and there was an example in which I didn't get the code:

```
public class Random {

static final int a = 48271;
static final int p = 2147483647; //2^31 - 1
static final int q = p/a;
static final int r = p%a;
int state;

public Random() {
    this ( (int)(System.currentTimeMillis()%Integer.MAX_VALUE ));
}

public Random(int initialValue) {
    if (initialValue < 0)
        initialValue += p;
    state = initialValue;
    if (state == 0)
        state = 1;
}

public int randomInt() {
    int tmp = a * (state % q) - r * (state/q);  //line I don't get
    if (tmp < 0)
        state = tmp+p;
    else
        state = tmp;
    return state;
}
}

```

The teacher said that it was so that all numbers can be expressed in 32 bits (or somethig like that). The thing is that a LCG should have a period of exactly $p-1$ and I don't get why it should be the case with this line.

Could you also explain why the following code would not work?

```
public int randomInt() {
    int tmp = (a*state)%p;
    if (tmp <= 0) state = tmp+p;
    else state = tmp;
    return state;
}

```

Thanks in advance for any answer.

**Edit:** I compared both generators by generating numbers in the interval $\]0,1\[$ with the following codes:

```
    //Generators
    public int randomInt() {
        int tmp = (a*state)%p;
        if (tmp <= 0) state = tmp+p;
        else state = tmp;
        return state;
    }

    public int randomInt2() {
        int tmp = a * (state % q) - r * (state/q);
        if (tmp < 0) state = tmp+p;
        else state = tmp;
        return state;
    }

    public double randomReal() {
        return randomInt()/(double)p;
    }

    public double randomReal2() {
        return randomInt2()/(double)p;
    }

```

And the Main method:

```
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;

public class Main {

public static void main(String[] args) {

    File file = new File("resultatsGC.xls");
    FileWriter fw = null;
    Random rand = new Random();
    Random rand2 = new Random();
    double x, y;
    int[] tab = {0,0,0,0,0,0,0,0,0,0};
    int[] taby = {0,0,0,0,0,0,0,0,0,0};

    try {

         for (int i = 1 ; i < Math.pow(2, 31)-1 ; i++) {
            x = rand.randomReal();
            y = rand2.randomReal2();
            for (int j = 0 ; j < 10 ; j++) {
                if (x > j/(double)10 && x < (j+1)/(double)10) {
                    tab[j]++;
                }
                if (y > j/(double)10 && y < (j+1)/(double)10) {
                    taby[j]++;
                }
            }
            if (i%100000000 == 0)
                System.out.println(i+") "+x);
        }

        fw = new FileWriter(file, false);

        //Write in file the results
        for (int i = 0 ; i < 10 ; i++) {
            double a = ((double)i)/10;
            double b = ((double)(i+1))/10;
            String str = "["+a+";"+b+"]\t";
            fw.write(str);
            fw.write(tab[i]+"\t");
            fw.write(taby[i]+"\n");
        }

        fw.close();

    } catch (FileNotFoundException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    } finally {
        try {
            if (fw != null)
                fw.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
        System.out.println("DONE!");
    }
}
}

```

And here is what it graphically gives:

Orange columns are the results of the algorithm that I had a question about. Clearly, it is better (much more uniform), but my question remains: why is it correct (even more correct than the other)?

# Answer
> 1 votes
One issue with your generator is that when computing `tmp = (a*state)%p`, you are actually taking modulo twice: first modulo $2^{32}$ (with sign), then modulo $2^{31}-1$. So you aren't really computing $a^t \pmod{p}$ like you might have expected. To test this hypothesis, you can ask Java to use `long` for the multiplication `a*state` – the results should improve. There is also a difference between using signed and unsigned arithmetic, though you can't test this in Java.

The other generator is more careful - it's only multiplying small numbers (the result is below $2^{31}$), which is why the truncation issue doesn't effect it.

The other generator computes the function $$ y\lfloor \tfrac{p}{a} \rfloor + z \mapsto az - (p\pmod{a}) y. $$ (The comparison to $0$ just ensures that the result is in $\[0,p)$ without affecting the value modulo $p$.)

The idea is that $$ a(y\lfloor \tfrac{p}{a} \rfloor + z) \equiv az + y(a\lfloor \tfrac{p}{a}\rfloor-p) \pmod{p}. $$ Now $a\lfloor\frac{p}{a}\rfloor-p = -(p\pmod{a})$, and so the other generator really computes $x \mapsto ax \pmod{p}$.

---
Tags: pseudo-random-generators
---


# Question
Title: Is a secondary TM sufficient to detect all loops?
Procedure: Start a secondary TM in parallel with the first, but have the second perform exactly 1 step each 2 steps the first TM performs (i.e. it runs at half speed). If the second machine ever reaches the same configuration as the first, a loop was detected (obviously).

Claim: *All* infinite local loops in a TM can be detected in the above manner.

Local loop, in this context, refers to a machine running within a certain tape interval without ever stopping. To clarify, in particular this excludes any machines which extend the tape in any direction without bounds.

Has this been proven? I'm pretty sure I found this claim in a paper, I believe one of Marxen's, though I can't seem to find it.

# Answer
> 7 votes
This is Floyd's cycle finding algorithm, which is an efficient procedure for finding cycles. If you don't care about efficiency, you can use a big table which stores the different states the Turing machine has reached. If it reaches the same state twice, then it's in an infinite loop. What you are describing is just a more efficient way of detecting the same event, which is a particular type of infinite loop.

Turing machines can fail to halt – enter an infinite loop – in other ways. For example, a machine can keep going to the right indefinitely. The machine never halts, yet it doesn't reach the same state twice. A cycle finding algorithm won't detect this situation. Of course, there is no general way of detecting infinite loops, since the halting problem is undecidable.

---
Tags: computability, turing-machines, busy-beaver
---