# Question
Title: Testing whether the language of one automaton is a subset of another
Is there an algorithm to solve following problem?

Given two finite automata $A$ and $B$. Determine whether the language recognized by automaton $A$ is a subset of language recognized by automaton $B$ or otherwise.

# Answer
> 12 votes
Recall some closure properties of regular languages, namely that they are closed under complementation and intersection. Now, $L(A)\subseteq L(B)$ whenever $L(A)\cap\overline{L(B)}$ is empty. So you need to construct the automaton that accepts the intersection of $A$ and the complement of $B$ – these are standard constructions – and test whether the resulting automaton accepts the empty language. This can be checked by inspecting the automaton to see whether any accepting states are reachable from the initial state. If not, then the language accepted is empty.

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


# Question
Title: A Formula For Generalized Josephus problem
There is a formula in wikipedia for the general case of josepus problem

Josephus Problem

But there is no reference for it, I don't know where it came from and I need too find out... Maybe Donald Knuth's Art of Programming?

# Answer
In "Concrete Mathematics" by Graham, Knuth, Patashnik. Look in Chapter 3: Integer functions.
> 1 votes

---
Tags: reference-request, recursion
---


# Question
Title: What is meant by "give pattern of a regular expression"
I have an alphabet $A = \\{b,B\\}$ and I'm asked to write down the **pattern** of the regular expression $(\epsilon|bb|b)(B|bb)(b|\epsilon|b)$. What does the question actually want me to do? I'm not sure. Does it want me to give the possible patterns that can be formed with $b$ and $B$? But then surely the question would not have been phrased the way it is.

I'm just confused about what I need to do here and what is expected of the answer. If anyone could give an example it would be very helpful.

Note: This is not the original question, I changed and simplified it.

# Answer
A **pattern** (in the context of languages and automata) is a way of defining a set of strings. A string matches a pattern if it belongs in the set defined by that pattern. So, your regular expression is actually a pattern. The question, I think, would be to find the pattern given a set of strings!
> 1 votes

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


# Question
Title: Why not relax only edges in Q in Dijkstra's algorithm?
Can someone tell me why almost in every book/website/paper authors use the following:

```
foreach vertex v in Adjacent(u)
    relax(u,v)

```

when relaxing the edges, instead of:

```
foreach vertex v in Adjacent(u)
    if (v is in Q)
        relax(u,v)

```

This is extremely confusing for someone when learning the algorithm. Is there any reason why the people are omitting the IF ?

Anyway I wrote a semi-Javascript (I changed it here to a readable syntax) implementation of Dijkstra and I wanted to be sure if it is correct because of this IF case. Here is my code excluding the initialising:

```
while (queue.length != 0)
    min = queue.getMinAndRemoveItFromQ()
    foreach v in min.adjacentVertices
        // inspect edge from "min" to "v"
        if ( queue.contains(v) AND min.priority + weight(min,v) < v.priority )
            v.priority = min.priority + weight(min,v)
            v.pre = min

```

Is this implementation correct or am I missing something ?

# Answer
The condition

> min.priority + weight(min,v) \< v.priority

can only be true if $v$ is in the queue. If a vertex $v$ has been removed from $Q$ the invariant of Dijkstra's algorithm guarantees we've already found the shortest path to $v$.

**Edit: Proof Sketch** Suppose v isn't in Q. Then we must have already found the shortest path to v. Now if we later examine a vertex u connected to v, the condition min.priority + weight(min,v) \< v.priority must be false, otherwise we would have found a shorter path to v which is a contradiction.
> 7 votes

# Answer
It depends on how they define what is in the queue ($Q$). There are two options:

1. Initially all vertices are added in the queue, the source with distance $0$, all the other with distance $\infty$.
2. Initially only source is added with distance $0$, other vertices are added when discovered.

Now in the first case, the condition might be added, but *is redundant*. If $v \not\in Q$, than we already know $d(v)$ and we know that $d(v) \le d(u)$ ($u$ being current vertex), so $d(u) + d(u,v) \ge d(v)$ given the precondition of Dijkstra's algorithm that $d(u,v) \ge 0$.

But in the second case, the condition is *wrong*, because $Q$ only contains discovered vertices, but we need to process undiscovered vertices as well.

Given that a heap structure does not allow efficient membership check nobody wants to confuse newbies into performing this check when comparing the tentative distances is only slightly slower than checking "settled" flag and need to keep a "settled" flag around might easily offset it's possible benefits anyway. I know at least one practical implementation that keeps and uses such flag. It does so mainly to reuse code from breadth-first search and is accompanied by an alternate implementation that does not.

Also note that many applications of Dijkstra's algorithm stop it when specific vertex is settled, specific diameter reached, two parallel runs meet or some other stopping condition is met long before the whole graph is even discovered, in which case the second definition is more efficient (you don't add the vertices that won't be needed) and I don't see any case where the first would actually be more efficient. And as established above, in the second case, the condition *can't* be added.
> 4 votes

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


# Question
Title: Regarding programming languages, what is meant by "hook"?
My professor gave this assignment question, where he asks us to compare the expressive ease and the expressive range of Low Level and High Level theoretical programming languages.

While in context, I could understand that "hook" seems to refer to the opposite of an abstraction, I don't understand precisely what it means. Is it a real term, or did my professor (who isn't being helpful) make it up?

This is the question, cut from the assignment:

# Answer
> 1 votes
Typically, a hook is an non-abstract method defined in an abstract class, that can be optionally implemented and overridden in subclasses to modify behaviour. I think this is best exemplified in the template method pattern, where the (abstract) superclass defines the overall semantics for a process, but leaves primitive operations to be implemented by sublasses:

A template method is defined inside an abstract class:

```
public abstract class AbstractLogger {

    /*
     * Template method, made final to make
     * sure the flow is not modified by subclasses
     */
    public final void logMessage(String msg) {
        msg = preProcess(msg);
        writeToLog(msg);
    }

    /*
     * Abstract primitive operation that must be
     * implemented by subclasses
     */
    protected abstract void writeToLog(String str);

    /*
     * Hook method that can be optionally overriden to
     * modify the template method's behaviour
     */
    protected String preProcess(String str) {
        return str; // default behaviour: do nothing
    }

}

```

Concrete subclasses make use of the hook-method to augment behaviour:

```
public abstract class TerminalLogger extends AbstractLogger {

    /*
     * This primitive operation must be implemented
     */
    protected void writeToLog(String str) {
        System.out.println(str);
    }

    /*
     * Override super.preProcess() to modify behaviour
     * of the template method
     */
    protected String preProcess(String str) {
        return str.toLowerCase();
    }
}

```

Pardon the contrived example - I hope it illustrates the point clearly enough. For more info on hook methods and template methods see:

http://en.wikipedia.org/wiki/Hook\_method#Hook\_methods

http://en.wikipedia.org/wiki/Template\_method\_pattern

The template method pattern wiki presents a fuller example than mine - you might want to check it out.

---
Tags: terminology, programming-languages
---


title: Regular vs LALR(1): what is faster

text:
# Question
Title: Regular vs LALR(1): what is faster
Supposing we have two grammars which define the same languge: regular one and LALR(1) one.

Both regular and LALR(1) algorithms are O(n) where n is input length.

Regexps are usually preferred for parsing regular languages. Why? Is there a formal proof (or maybe that's obvious) that they are faster?

# Answer
> 1 votes
I believe the reason for favoring regular expressions over LALR(1) grammars for accepting simple grammars stems from the time needed to *build* an LALR(1) automaton. Let $m$ denote the size of the grammar which is used to build the automata for accepting the language defined by said grammar. If you need to build up the accepting automaton during runtime you will probably want to use regular expressions because building up an LALR(1) automaton will take $O(m\cdot 2^m)$ which does not include the necessary testing if the input grammar even is LALR(1) ($O(m^3)$). Regular expressions instead can be build up quite easily, the check can occur during conversion (see \[1\] , re2post).

Adding to the speed gained when building up different regular expressions during different program runs modern regular expressions, mostly PCRE, are NP-Complete, thus very powerful (see for instance \[2\]). Additionally, with most languages supporting regular expressions there also is an interactive environment to check if the regular expression really expresses your intention, which is more efficient from a programmer's perspective than to write the grammar, generate the parser and do a test and then reiterate the process. I believe this to be the main reason for using regular expressions over LALR(1) grammars.

If you are interested in the implementation and runtime aspects of grammars \[3\] might also be of interest to you.

\[1\] http://swtch.com/~rsc/regexp/

\[2\] http://nikic.github.com/2012/06/15/The-true-power-of-regular-expressions.html

\[3\] Gerhard Goos, William Waite, Compiler Construction, Springer, Jan 1984 ( symbolaris.com/course/Compilers/waitegoos.pdf)

---
Tags: regular-languages, efficiency, parsers
---


# Question
Title: Example for the analysis of a recursive function
```
l is a matrix of size [1...n, 1...n]

function: rec(i,j)
  if (i*j == 0)
    return 1
  else
    if (l[i,j] == 0)
      l[i,j] = 1 * rec(i-1,j) + 2 * rec(i,j-1) + 3 * rec(i-1,j-1)
    return l[i,j]
end_function

for i=1 to n
  for j=1 to n
    l[i,j] = 0

rec(n,n)

```

The nested for's are O(n2). But i have difficulties to analyse the recursive part. There is another variation of this example with l as 3d. And the essential part of 3drec function is defined as:

```
if (l[i,j,k] == 0)
  l[i,j,k] = 2 * rec(i-1,j,k) + 2 * rec(i,j-1,k) + 2 * rec(i,j,k-1)

```

Anyway let's think about the 2d version again. I thought something like that (that's the running time for the whole code including the nested loops):

T(n) = T(n-1, n2) + T(n, n-12) + T(n-12, n-12)

And i'm stuck here. Besides i don't know if i did right till this point.

# Answer
The running time is exponential. As Yuval showed in his answer, we have

$$f(i,j) = \begin{cases} O(1), & i = 0 \text{ or } j = 0, \\ f(i-1,j) + f(i,j-1) + f(i-1,j-1) + O(1), & \text{otherwise}. \end{cases}$$

Let's look at a $g = O(f)$ defined by $g(i,0)=g(0,i)=1$ and $g(i,j)= g(i,j-1) + g(i-1,j)$.

This gives the array $$ \begin{array}{ccccc} 1&1&1&1&1\cr 1&2&3&4&5\cr 1&3&6&10&15\cr 1&4&10&20&35\\1&5&15&35&70 \end{array}$$ which you should recognize as binomial coefficients. The term $g(i,i) = {2i \choose i},$ which grows as $\Theta(\frac{1}{i^{1/2}}4^i)$. This shows that the growth of $f$ is exponential.

The easiest way I know to find the exact growth formula is to compute the first few terms of the sequence and look it up on the Online Encyclopedia of Integer Sequences. Using 1 for all the $O(1)$ terms, computing them using a spreadsheet takes less than a minute, and we find that the sequence is in the OEIS. The page for the sequence tells us that the growth rate is $\Theta(\frac{1}{i^{1/2}}(3+2\sqrt{2})^i)$.
> 5 votes

# Answer
Here's the correct recurrence for the running time of rec: $$ f(i,j) = \begin{cases} O(1), & i = 0 \text{ or } j = 0, \\ f(i-1,j) + f(i,j-1) + f(i-1,j-1) + O(1), & \text{otherwise}. \end{cases} $$ The running time of the entire program is $f(n,n) + O(n^2)$. Now it remains to solve the recurrence for $f$, which I leave to you.
> 6 votes

# Answer
You are interested in the time `rec(i, j)` takes. If you look at the code, it doesn't depend on the contents of the `l` array, just on `i` and `j`. Just take each call to take time 1. Then, by the recursion, for the time $t\_{i j}$ you have the recurrence: $$ t\_{i + 1, j + 1} = t\_{i + 1, j} + t\_{i, j + 1} + t\_{i, j} \quad t\_{i, 0} = t\_{0, j} = 1 $$ Use generating functions to solve this. Define: $$ T(x, y) = \sum\_{\substack{i \ge 0 \\ j \ge 0}} t\_{i j} x^i y^j $$ Then $T(x, 0) = \frac{1}{1 -x}$, $T(0, y) = \frac{1}{1 - y}$. Using the properties of generating functions: $$ \frac{T(x, y) - y / (1 - x) - x / (1 - y) + 1}{x y} = \frac{T(x, y) - x / (1 - y)}{x} + \frac{T(x, y) - y / (1 - x)}{y} + T(x, y) $$ This gives $T(x, y) = \frac{1 - x - y}{1 - x - y - x y}$. Luckily we aren't interested in $t\_{i j}$, just in $t\_{n n}$: $$ \begin{align\*} \[x^n y^n\] T(x, y) &= \[x^n y^n\] \left(1 + \frac{x y}{1 - x - y - x y}\right) \end{align\*} $$ Let's tackle the second term: $$ \begin{align\*} \[x^n y^n\] \frac{x y}{1 - x - y - x y} &= \[x^{n - 1} y^{n - 1}\] \frac{1}{1 - x - y - x y} \end{align\*} $$ Expanding each term of the geometric series by the multinomial theorem: $$ \begin{align\*} \[x^{n - 1} y^{n - 1}\] \frac{1}{1 - x - y - x y} &= \[x^{n - 1} y^{n - 1}\] \sum\_{k \ge 0} \sum\_{\substack{r \ge 0 \\ s \ge 0}} \binom{k}{r \\, s \\, k - r - s} x^r y^s (x y)^{k - r - s} \\ &= \[x^{n - 1} y^{n - 1}\] \sum\_{k \ge 0} \sum\_{\substack{r \ge 0 \\ s \ge 0}} \binom{k}{r \\, s \\, k - r - s} x^k y^k \\ &= \sum\_{\substack{r \ge 0 \\ s \ge 0}} \binom{n - 1}{r \\; s \\; n - 1 - r - s} \\ &= 3^{n - 1} \end{align\*} $$ This gives a complexity of $O(3^n)$.

**Edits:** I had messed up badly, I hope it is fixed now.
> 1 votes

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


# Question
Title: Is there a single valid definition for a Turing Machine, or is it mutable?
I'm just learning about Turing Machines, and I'm a bit confused by the difference in formal description between Wikipedia and my textbook.

My textbook says the following:

$$M=\langle Q,\Sigma,\Gamma,\delta,q\_{0},q\_{accept}, q\_{reject} \rangle$$

where:

1. $Q$ is the set of states,
2. $\Sigma$ is the input alphabet not containing the blank symbol $\sqcup$,
3. $\Gamma$ is the tape alphabet, where $\sqcup\in\Gamma$ and $\Sigma\subseteq\Gamma$,
4. $\delta: Q\times\Gamma\to Q\times\Gamma\times\\{L,R\\}$ is the transition function,
5. $q\_0\in Q$ is the start state,
6. $q\_{accept},q\_{reject}\in Q$ are the accepting and rejecting states, respectively, and $q\_{accept}\neq q\_{reject}$

While Wikipedia states

> Hopcroft and Ullman (1979, p. 148) formally define a (one-tape) Turing machine as a 7-tuple $M= \langle Q, \Gamma, b, \Sigma, \delta, q\_0, F \rangle$ where
>
> * $Q$ is a finite, non-empty set of states
> * $\Gamma$ is a finite, non-empty set of the tape alphabet/symbols
> * $b \in \Gamma$ is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation)
> * $\Sigma\subseteq\Gamma\setminus\\{b\\}$ is the set of input symbols
> * $q\_0 \in Q$ is the initial state
> * $F \subseteq Q$ is the set of final or accepting states.
> * $\delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \\{L,R\\}$ is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.)

There are obviously a few similarities, but there are a few differences as well. Namely the ordering of the items in the 7-tuple $M$. Also, my textbook has three entries for separate special states, and the Wikipedia entry has only two - My book doesn't have a special element just for the blank character.

# Answer
> 11 votes
The ordering of the items in the 7-tuple M is completely immaterial to the behavior of the Turing machine. There is no "correct" or "incorrect" ordering; but I would say that both orderings are essentially the same definition. And I don't see that the blank character is treated any differently in the two definitions. In both, it's part of the tape alphabet but not the input alphabet.

For the two definitions to be effectively different, you would need to find a difference that does not correspond to a re-ordering of the 7-tuple, or is just in the wording of how the blank symbol is treated.

The only **actual** difference between the two definitions seems to be that your book has $q\_{\mathrm{accept}}$ and $q\_{\mathrm{reject}}$ as the halting states, while Wikipedia permits a general set $F$ of halting states. This is because your book only deals with Turing machines that compute languages (so for every string $x$, either $x \in L$ or $x \not\in L$) while Wikipedia also wants to handle Turing machines that compute functions. For a Turing machine that computes a function, you can assume that there is only one final state, $q\_{\mathrm{halt}}$; the value of the function will be written on the tape when the Turing machine halts.

# Answer
> 3 votes
There are several valid definition of a Turing machine but they (the TM's) are all equivalent in power (they all compute the same functions). You could use the original definition (coined by Alan Turing himself in his paper "Computing Machinery and Intelligence". He describes the Turing machine in English. It's what a Turing machine consists of that matters not how the pieces are ordered.

# Answer
> 1 votes
As mentioned before by other people the are variety of Turing machines with a little bit different definitions like two-way infinite tapes, arbitrary numbers of read-write heads, multiple tapes, ... See this link. The point is that all of them are "equivalent" in theory. It's up to you which is better for your problem.

---
Tags: terminology, turing-machines
---


# Question
Title: Overlap between computer science and analytic geometry?
I would like to know if there are some topics that could be covered in an undergraduate first-term course about analytic geometry, but related to Computer Science.

I know that, for example, the simple equation for the line can be used for explaining linear regression or other topics in elliptic cryptography (too advanced for an initial course).

Any suggestion of topics?

# Answer
Computer graphics is applied analytic geometry, and showing how games do their computations might be exactly the kind of motivating subject matter you are looking for.
> 3 votes

# Answer
One other topic that could be covered is numerical methods and algorithms. Efficient way of visualizing the multidimensional graphs, functions,....
> 1 votes

---
Tags: education
---


# Question
Title: How come {ww} isn't regular when {uv | |u|=|v|} is?
As we know, using the pumping lemma, we can easily prove the language $L = \\{ w w \mid w \in \\{a,b\\}^\* \\}$ is not a regular language.

However, the language $L\_1 = \\{ w\_1 w\_2 \mid |w\_1| = |w\_2| \\}$ is a regular language. Because we can get the DFA like below,

```
DFA:

--►((even))------a,b---------►(odd)
      ▲                         |
      |--------a,b--------------|

```

My question is, $L = \\{ w w \mid w \in \\{a,b\\}^\* \\}$ also has the even length of strings ($|w|=|w|$, definitely), so $L$ still can have some DFA like the one above. How come is it not a regular language?

# Answer
well, there are things that a DFA can do, and things that DFA cannot do. A DFA is quite a simple machine, and it has no access to "memory". The only "memory" it has is its current state, i.e., a very limited memory. A DFA can do tasks that require *finite* amount of memory, but nothing more than that.

To check if the input is of even length - is very simple task. It requires only 1 bit of memory (odd/even). therefore, it can be done by a DFA.

However, for the second language $\\{ ww \mid w\in\Sigma^\*\\}$ the DFA needs to check that the first $w$ is *identical* to the second $w$. How can you do that with no memory? In fact, since $w$ can be of any length, a (one-pass) machine that checks that the two copies of $w$ are the same must have *infinite* memory (to accommodate any $w$..). But a DFA has only limited memory, and thus cannot solve this task.

at least, this is the intuitive explanation.
> 8 votes

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


# Question
Title: Languages that satisfy the pumping lemma but aren't regular?
Given a regular language $L$, then it is easy to prove that there is a constant $N$ such that is $\sigma \in L$, with $\lvert \sigma \rvert \ge N$ there exist strings $\alpha$, $\beta$ and $\gamma$ such that $\lvert \alpha \beta \rvert \le N$ and $\lvert \beta \rvert \ne \epsilon$, and for all $k$ it is $\alpha \beta^k \gamma \in L$. It is widely stated that the converse isn't true, but I haven't seen any clear example. Any suggestions? Clearly the proof that the offending language isn't regular has to use stronger methods than the typical "doesn't satisfy the pumping lemma". I'd be interested in simple examples, to present in introductory formal languages classes.

# Answer
The language $\\{ \\$ a^nb^n \mid n \ge 1 \\} \cup \\{ \\$^kw \mid k\neq 1, w\in \\{a,b\\}^\* \\}$ seems to be simple. The second part is regular (and can be pumped). The first part is nonregular, but can be pumped "into" the second part by choosing $\\$$ to pump.

(added) Of course, this can be generalized to $\\$L \cup \\{ \\$^k \mid k\neq 1 \\} \cdot \\{a,b\\}^\*$ for *any* $L\subseteq \\{a,b\\}^\*$. Sometimes the formulation is in the "if ... then ..." style: if $w$ starts with a single $\\$$ then it is of the form. That I personally find less intuitive.

As noted by @vonbrand the (possibly) non-regular part of the language is isolated by intersecting with $\\$\\{a,b\\}^\*$. This can be separately tested using the pumping lemma if needed.
> 19 votes

---
Tags: formal-languages, proof-techniques
---


# Question
Title: Optimal algorithm for finding all ngrams from a pre-defined set in a text
I'm thinking about the optimal algorithm for the following problem:

Input data:

* a **text**, say it's an article about 5-50 pages.
* a set of **ngrams** (ngram strings, n\>2), of arbitrary length, could be more than 20k n-grams.

The algorithm should output the following:

* a dictionary of all ngrams that were found in the text with the corresponding quantities, it should also take into account that ngrams could partially intersect or consist of each other (like *'probability density', 'probability density function', 'probability density distribution'*)

So **the question is** what would be the most time-efficient algorithm to compute this?

Both all words in a text and all words in ngrams are reduced to the canonical forms.

# Answer
What you want to solve is a string matching problem. Wikipedia (and any textbook on the matter) contains a rich list of algorithms with their respective runtimes.

Be aware that they give *worst-case* runtimes. Different algorithms behave differently on natural text; some perform better because of the large alphabet and some worst because of its repetitive nature. Therefore, you should benchmark the respective algorithms with data similar to which you expect to get.
> 5 votes

# Answer
You could construct a DFA that recognizes the given set of ngrams. Some of the states signify that a certain ngram has just been read, so if you keep track of all the states the DFA is in, you know all occurrences of the ngrams in the text.
> 2 votes

# Answer
Following up on Yuval, I would build a tree structure so that you can find the $n$-grams. Store the number of matches of each $n$-gram in the corresponding leaf. (It is similar to a DFA, but does not store links for 'missing' letters.)

In general my method for looking at multiple strings with overlap would be **Aho-Corasick**. It has "failure links" that tell where to continue when the next letter read from the input is not in the tree. It also handles the fact that if you reach a leaf (found an $n$-gram) then the maximal overlap with possible next match is known.

A problem with storing trees is the alphabet size. In the lower level of the trees a node will have many children, in upper levels the children are sparse. Done in the wrong way this leads to a waste of space.
> 2 votes

# Answer
The standard answer to this was given by Bentley in "Programming Pearls": Sort this way \[horizontal hand wave\] then this way \[vertical wave\].

In more detail:

* For each word in your dictionary, set up a signature computed by sorting its letters
* Sort the dictionary by signatures

The set of anagrams are those with the same signature, it is now a simple matter to collect them.
> 0 votes

---
Tags: algorithms, time-complexity, strings, natural-language-processing
---


title: If set of TM's is not countable?

text:
# Question
Title: If set of TM's is not countable?
I was reading about counting principle related to TOC. I understand that the set of TMs are countable infinity. I couldn't understand the significance of it. What is its not countable?

# Answer
> 5 votes
To expand a bit Luke's answer - the main question is what problems (=languages) can be solved by a computer (=TM).

One might think that **any** problem can be solved by a computer. But this is not true. The reason is that there are such and such different Turing Machines, and **way more** different languages. Therefore, there must be a language that no TM can recognize. This language is *undecidable*, and the "problem" this language represents cannot be solved by any computer. In fact, the vast part of languages are undecidable.

The number of different Turing machines is infinite, but countable ($\aleph\_0$), while the number of different languages is infinite of a larger magnitude ($\aleph$, and not countable). See more details on the wiki page for Cantor's diagonal argument, or search this site for related questions.

# Answer
> 4 votes
The set of all languages is uncountable, hence there can't be a TM for every language, and there must be languages that aren't recursively enumerable.

# Answer
> 1 votes
Each TM can be described by a finite string of symbols (the examples of TMs described in textbooks or elsewhere should give a good idea of how to do it with a limited supply of symbols). Any set of finite-length strings made of a finite set of symbols is countable. To get some non-countable set of machines would require that their description isn't finite, and that defeats the whole purpose.

---
Tags: computability, turing-machines, uncountability, church-turing-thesis
---


# Question
Title: Cache strategies, what reference article could I study?
So as to optimize an application, I must implement data caching: not to recompute some data - those heavy on cpu but that don't change often.

When playing with the idea, I imagined something like the way win32/MFC manages the windows screen i.e.:

* While a part is valid, it is not repainted.
* When a rectangle or a region is invalidated, this part is repainted during the next painting session - launched by the OS.

I was imagining a way to validate and invalidate my cached value, so as to recompute only what is necessary when it is necessary.

Then I read this wikipedia page about Cache Algorithms, and none of the listed algorithm was using the technique I explained above. So I feel ill at ease, and I need to read some work about caching.

Do you know of some resources that I could rely on before I start implementing my own cache process ?

# Answer
The best strategy to find the best suitable algorithms for caching is to read survey papers in this area. I recommend the paper A survey of Web cache replacement strategies by Podlipnig and Böszörmenyi (2003) which reviews many general techniques for caching.
> 4 votes

# Answer
The best overall view on optimization I've seen is Bentley's "Writing efficient programs" (sadly out of print), the medular part of its rules are in his "Programming pearls". For analysis of the algorithms I'd dig into Cormen et al "Introduction to Algorithms" (don't let the "introduction" fool you, it is more an encyclopaedia).
> 2 votes

---
Tags: reference-request, efficiency, cpu-cache
---


# Question
Title: Could anyone prove that this is a context free language or not?
> **Possible Duplicate:**
> Show that $\\{xy \mid |x| = |y|, x\neq y\\}$ is context-free

Can anyone prove that the following is a CFL? or not? why?

$$L=\\{w=w\_1w\_2 \mid len(w\_1)=len(w\_2) \mbox{ and $w\_1$ does not equal $w\_2$}\\}$$

# Answer
This must be a classic in formal language theory. The Pumping Lemma will not help, because, unexpectedly, it *is* context-free. (I did not see the answer here, but it might be overlooked)

The $w\_1$ and $w\_2$ parts must have a position where they differ. Unfortunately, we cannot distinguish the middle *and* the two matching positions at the same time. However, we can find matching positions *without* knowing the middle.

With some effort you can convince yourself that your language $L$ equals $$\\{ x\_1 a x\_2 b x\_3 \mid a,b \in \Sigma, a\neq b, |x\_1|+|x\_3| = |x\_2| \\}.$$ Once you have shown that, write a grammar using that formulation.
> 2 votes

---
Tags: context-free
---


# Question
Title: Where can I find a short and 'easy' peer reviewed paper on something from computability, decidability or complexity?
It's a homework assignment, we were asked to read, understand, and present to our colleagues a short paper/article (suggested 4-6 pages) for our Computability, Decidability or Complexity class.

The articles I was able to find in the past couple days using google scholar a way over what we were taught, plus, 50-100+ pages is way over the scope of my assignment. In class, we were provided with an introduction to the three topics, complexity classes, relations between them, and (mostly informal) proofs for the most representative problems from each class by modelling them using all kinds of Turing Machines.

Any possible solutions? It's the first time in my life I'm touching anything related to research, I can barely understand even the scope of most papers I find.. I guess any advice would be welcome.

# Answer
> 7 votes
"By definition" recent research papers usually contain non-trivial results and they often (always?) require a deep knowledge of the argument in order to be well understood, so if you pick a paper at random you'll probably find a bunch of obscure signs in your hands :-)

So my suggestion is to look at "old" research papers (but not *"too old"*):

1. pick a particular argument/theorem that you think you have understood informally (or an argument that intrigues you);
2. read more about it on a theory of computation book or on Internet (for example start from Wikipedia and look at the references at the bottom, or search it on Google adding the keywords "introduction" or "lecture notes");
3. finally search the paper in which that argument/theorem was originally published and read it;

For example one of the fundamental basic results in computational complexity is the (deterministic) Time Hierarchy theorem. *Very informally* the theorem says that given more time, a Turing machine can solve more problems. You can start reading the Wikipedia article, then pick a lecture note with a more formal proof Googling around (for example pick this one by Arora). Finally when you think that you've understood the proof well download and read the original paper R. Stearns and J. "Hartmanis paper On the computational complexity of algorithms", 1965. You'll find that it contains even more details and is more formal.

# Answer
> 4 votes
Assuming "older" papers are ok, what about Stephen Cook's well known *The Complexity of Theorem-Proving Procedures* \[1\]? It is 8 pages long, and if for the most part you have been able to keep up in your computability class, you can likely keep up with this paper as well. A copy is freely available from the author's website, or alternatively you can get a "nicer" re-typed version here.

\[1\] Stephen A. Cook. 1971. The complexity of theorem-proving procedures. In Proceedings of the third annual ACM symposium on Theory of computing (STOC '71). ACM, New York, NY, USA, 151-158.

# Answer
> 3 votes
I'd look at the "further reading" suggestions in your textbook. If the author made some effort here, the papers listed should be on-topic, important, and probably accessible.

# Answer
> 2 votes
Alan Turing's paper *On computable numbers, with an application to the Entscheidungsproblem*, 1936 is an extremely important paper (it started the entire field, one could say), and it's also a pleasant read. Highly recommended reading.

Claude Shannon's paper *A mathematical theory of Communication*, 1948 is beautiful, though it might fall outside of the category of complexity theory, it is the paper that initiated *information theory* and might therefor be relevant.

# Answer
> 1 votes
This is an interesting history article titled "A Short History of Computational Complexity" which will give you a big picture in this area.

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


title: Finding all cliques of a graph

text:
# Question
Title: Finding all cliques of a graph
Given a graph with $n \leq 50 $ vertices. Count all $k$-cliques of this graph, where $k = 1, \ldots , n$.

I need the most efficient algorithm.

# Answer
> 9 votes
Your problem (assuming I understand your English correctly) is counting the number of cliques in a graph of size $n = 50$. Counting the number of cliques in a graph is #P-complete (see this paper, which shows that counting the number of independent sets in a graph is #P-complete even for bipartite graphs).

Several efficient exponential time algorithms for the problem (efficient in the sense that their running time is $O(c^n)$ for $c\<2$) are described in Jeff Erickson's lecture notes \- see section 4.2 on page 4. The simplest algorithm, whose running time is $O(\phi^n)$ (where $\phi$ is the golden ratio), is as follows. For an arbitrary vertex $v \in G$ with neighborhood $N(v)$, we have the following recurrence for the number $I(G)$ of independent sets in $G$ (to get the number of cliques, complement $G$): $$ I(G) = \begin{cases} 2I(G-v), & N(v) = \emptyset, \\ I(G-v) + I(G\setminus(N(v)+v)), & \text{otherwise}. \end{cases} $$

This algorithm might be practical for $n=50$. If it isn't, you can try the other algorithms described in the lecture notes. Some of them require some modification for your case, and therefore the running times listed there might not hold in your case.

---
Tags: algorithms, graphs
---


title: Proof of the Stable Matching Problem

text:
# Question
Title: Proof of the Stable Matching Problem
Looking at the document *Fundamentals of Computing Series*, The Stable Marriage Problem.

Theorem 1.2.3 - page 12:

> In a man-optimal version of stable matching, each woman has worst partner that she can have in any stable matching.

Proof:

> Suppose not. Let $M\_0$ be the man-optimal stable matching, and suppose there is a stable matching $M’$ and a woman $w$ such that $w$ prefers $m = p\_{M\_0}(w)$ to $m' = p\_{M'}(w)$ . But then $(m,w)$ blocks $M'$ unless $m$ prefers $p\_{M'}(m)$ to $w = p\_{M\_0}(m)$, in contradiction of the fact that $m$ has no stable partner better than his partner in $M\_0$.

I'm having trouble visualizing the definition of the problem and the proof (what is the contradiction?).

First, what is the question implying? From what I read and the fact that in most stable matching examples, all the women do not end up with the completely last person on their list ... So I'm a bit confused.

In the proof, here is what I am getting: in $M'$ we suppose $w$ prefers $m$ to $m'$. But then if there is a stable matching containing $(m,w)$ this would leave $w$ with her worst partner and that is a contradiction. Is this correct?

In addition, if $m$ did prefer $w'$ it would contradict that it is not his first pick ?

I'm new to computer science concepts so any help is appreciated.

# Answer
> 3 votes
The claim is not that every woman ends with the last man on her list. Rather, consider *all* stable matchings, and all partners of some woman $w$ in these stable matchings. Among them, pick the worst one (according to her view) $m$. Then in the man-optimal matching, $w$ is matched to $m$.

Now that you understand what they're trying to prove, read the proof again. (It couldn't have made sense before, because the claim as you stated it just isn't true.)

# Answer
> 1 votes
There is a very nice lecture video on Youtube which describes all properties. I recommend you to watch is if you are new to the concept.

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


# Question
Title: Building functionally complete boolean circuits out of trinary logic
There are some not-very-commonly considered forms of trinary logic using 3 truth values. Even entire (unusual/rare) ternary computers have been built from it.

> Is there some knowledge or reference of how to convert some trinary logic systems into functionally complete boolean circuits/logic?

"Functionally complete" means all boolean functions can be computed. I am asking the more general question above in case the following more specific question does not have an answer. The motivation is more this specific following case. Consider the following "trinary truth table" for a single trinary operator.

```
   a b c

a  a c a
b  c b b
c  a b c

```

> Is it possible to somehow create functionally complete boolean circuits out of the single above trinary truth table operator? Or, maybe it can be definitively proven it's not possible?

I am also looking for any reference to that or something similar.

# Answer
It is not possible to "invert" a value. Here is a list (computed in Python) of all unary functions achievable using your gate (the order of inputs is abc):

```
aaa
aba
abb
abc
aca
acc
bbb
cbb
cbc
ccc

```

An inverter would have one of the patterns ba?, c?a, ?cb (depending on which two values you choose to encode True and False), which none of these functions have.

On the other hand, it is possible to compute all monotone functions. Use a for True and c for False. The Or gate is realized as $x \lor y = (xy)$. The And gate is realized as $x \land y = ((((xb)y)b)a)$. (Note that your gate is symmetric but not associative.) There might be other solutions, e.g. using b and c.

Edit: Here is how to extend this to a complete simulation using double wires, according to vzn's suggestion. We represent True by (a,c) and False by (c,a). Negation is accomplished by swapping the two wires. The Or gate is formed by applying the Or gate described above for the first wire, and the And gate for the second wire. The And gate is defined analogously.

Further edit for the curious: here is how to compute all unary functions. We start with the list abc,aaa,bbb,ccc corresponding to the identity function and all constants. We now repeatedly choose two members and compose them, i.e. given functions $f,g$, we compute the function $(fg)$. Eventually the process stabilizes, that is generates no new functions, and we get the ten functions listed above.
> 3 votes

---
Tags: reference-request, logic, reductions, circuits
---


# Question
Title: Computational complexity of coefficients
I have some recurrence relationships I use to compute some coefficients of a series. I want to know what the time complexity of computing these is. Suppose I know the coefficients $a\_0,...,a\_n$, and I want to compute $c\_0,...,c\_n$ as follows

$ c\_{n}=\begin{cases} e^{b\_{0}}, & n=0\\ \frac{1}{n}\sum\_{k=1}^{n}kb\_{k}c\_{n-k}, & n\geq1 \end{cases}$

where

$b\_{n}=\begin{cases} \frac{1}{a\_{0}}, & n=0\\ -\frac{1}{a\_{0}}\sum\_{i=1}^{n}a\_{i}b\_{n-i}, & n\geq1 \end{cases}$

So far this is what I have. If we know $b\_0,...,b\_{k-1}$ then $b\_k$ can be computed in $O(k)$ time, so to compute $b\_0,...,b\_{n}$ takes $\sum\_{k=0}^{n}O(k)=O(n^2)$ time.

Now suppose that we know $b\_0,...,b\_{k}$ and $c\_0,...,c\_{k-1}$ then it takes $O(k)$ time to compute $c\_k$. Thus to compute $c\_0,...,c\_{n}$ it takes $\sum\_{k=0}^{n}O(k)=O(n^2)$. Ofcourse we have to take into account the time it takes to compute $b\_0,...,b\_{n}$ which is $O(n^2)$.

So can I conclude that the time it takes to compute $c\_0,...,c\_{n}$ is

$O(n^2)+O(n^2)=O(n^2)$??

# Answer
> 2 votes
You also need to take into account the size of the coefficients. Adding integer coefficients of bit-length $\ell$ takes time $O(\ell)$, and multiplying them takes time $\tilde{O}(\ell)$, i.e. $O(\ell (\log \ell)^k)$ for some $k$ (any $k \> 1$ will do). Your case is slightly more complicated, since the answer is rational and uses the "indefinite" value $e^{1/a\_0}$, so in general it is going to be a polynomial in $e^{1/a\_0}$ with rational coefficients. This further increases the running time.

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


title: MGU and Variable Standardization - CNF

text:
# Question
Title: MGU and Variable Standardization - CNF
I have been reading on converting first order logic sentences to conjunctive normal form, and then performing resolution.

One of the steps of converting to CNF, is to Standardize variables: rename all variables so that each quantifier has its own unique variable name.

Most general Unifier is the least specialized unification of two clauses.

Question 1: I have been searching to find an example that shows what are the potential problems if I don't standardize variables, but all the online resources I found only explain the "How" and not the "Why". Could you provide me with an example of a potential problem?

Question 2: The same problem as the first question. What if we don't use MGU, and use a more specialized unifier? What are the potential problems? Could you provide me with an example?

My sincere thanks. Felipe

# Answer
> 0 votes
1. See this answer \- it's an example of a contradictory set of clauses where we cannot derive a contradiction without renaming variables. Note that it's not sufficient to only rename variables after the conversion to CNF, we have to rename variables to be distinct before *every* application of the resolution rule. You can view it as follows: A variable appearing in two distinct clauses has different meaning in each of them as they're implicitly universally quantified. If we don't rename the variable in one of the clauses, we make a false assumption that the variable means the same in both clauses.
2. By using MGU, we derive the most general clause in a resolution step. If we use any unifier that is more specialized than their MGU, the resulting clause is weaker. This means, that we didn't infer all the knowledge we could, and we can miss a derivation of an empty clause even if it exists. For example: \begin{array}{c} P(x,y) \lor Q(y) \\ \lnot Q(d) \\ \lnot P(c,d) \end{array} If we make a resolvent from the first two clauses using MGU which sends $y\to d$, we get $P(x,d)$ and we can proceed with the third clause. If we take a weaker unifier, like one that also sends $x\to d$, we get $P(d,d)$ and we're not able to make a resolvent with the third clause. This means the method is no longer complete.

---
Tags: logic, artificial-intelligence, knowledge-representation, first-order-logic
---


# Question
Title: Fuzzy string matching algorithm with allowed events?
I want to be able to locate a substring in a string allowing for a specified number of mismatches, insertions and deletions - and at the same time know how many mismatches, insertions and deletions were used for any match.

Using brute force backtrack I can find the matches, but I cannot guarantee that the match was produced using the fewest permutations possible.

Using dynamic programming I can find the matches and guarantee that the match was produced using the fewest permutations possible, but I cannot specify a number of allowed mismatches, insertion and deletions - only a total edit distance.

# Answer
> 2 votes
What you want is the so-called (optimal) local alignment of two strings. You can use the standard local alignment algorithm but allow insertions/deletions at the beginning and end (of the the shorter string) for free.

In the classic dynamic programming algorithm, this corresponds to initialising the first row (resp. column) with zero, removing the penalty for steps along the last row (resp. column) and finally looking for the minimum cost in the last row (resp. column) and backtrack from there. You can find alternatives in the Wikipedia article.

Restricting the number of deletions or insertions used can be implemented by adding counters to the cell values; if adding one would take one over the respective limit (stored globally), assign cost $\infty$ to the respective operation.

# Answer
> 1 votes
You should be able to modify the dynamic program for global alignment to return a 3-vector $\langle m, i, d \rangle$ that contains the number of mismatches, insertions, and deletions. It is straightforward to see that edit distance is simply the $\ell\_1$ (i.e. sum) of this vector.

If any of these individual values are greater than their allowed amount, you can return $\langle \infty, \infty, \infty \rangle$. If no alignment has less than the number of allowed mismatches, insertions, or deletions, this answer will propogate upward.

---
Tags: algorithms, dynamic-programming, strings, substrings
---


# Question
Title: Exponential input and poly-time algorithm
For a list of integers, of size n, where n is exponential, will merge-sort(n), run in poly-time or psuedo poly-time?

# Answer
First, the question is not well defined. If the input is of size $n$, the algorithm is measured with respect to $n$. However, the question suggests that $n$ is already exponential (in what?!)

Lets assume each number takes $k$ bits, and we have $n$ different numbers to sort, where $n$ is exponential in $k$.

Then, merge sort takes $O(n \log n)$ *comparisons*. Each comparison takes $O(\log k)$ time (unless we use some gates that compare two numbers in $O(1)$).
> 1 votes

---
Tags: algorithms, terminology, time-complexity, polynomial-time
---


# Question
Title: What precisely is infinite ambiguity in a grammar?
From what I've read, an example of infinite ambiguity is usually given in a form of a loop:

$S \rightarrow aA \\ A \rightarrow B \\ B \rightarrow A \\ B \rightarrow b$

But a grammar is called *ambiguous* if there's more than 1 way to derive the input string ω. What if I then take this well-known ambiguous grammar:

$S \rightarrow SSS \\ S \rightarrow SS \\ S \rightarrow b$

and extend it with $S \rightarrow \epsilon$ so that for any member of $\left\\{ b^n \middle| n \geq 0\right\\}$ there's infinitely many ways to derive it? Does this make the grammar *infinitely* ambiguous?

# Answer
> 2 votes
From a comment by Sylvain:

A grammar is infinitely ambiguous iff there is a productive and accessible nonterminal $A$ s.t. $A \Rightarrow^+ A$. Nonterminals $A$ and $B$ fulfill this characterization in your first example, and so does $S$ in the second example when you add the rule $S \to \varepsilon$. I'll leave the proof of the characterization as an exercise.

> Consider that a parse tree of infinite size for a finite input sentence must repeat a nonterminal spanning the same interval in the input.

---
Tags: terminology, formal-grammars, ambiguity
---


# Question
Title: Implications of truncation of numbers when converted into binary
I have been posed with a question whereby a computer truncates numbers to x number of digits. Due to this, if this computer is trying to store a decimal number which has a binary equivalent greater than x, it truncates the remaining digits producing a different binary number. However, this binary number is still an 'approximation' of what it should be, but of course is the equivalent of a different decimal number (close to what we were trying to store initially).

What problems can occur due to this incorrect storage of data?

# Answer
> 1 votes
This is specifically about real numbers — integers can be represented exactly. Actually, real numbers can be represented exactly too, at least the one that matter, but this is very inefficient, so for most applications real numbers are represented by a floating point approximation.

By the way, this isn't specific to decimal numbers (numbers that can be represented in base 10 with a finite number of digits after the decimal point). No matter what base you choose, you can only represent a tiny subset of the real numbers (you can't even represent all rationals).

When computing with approximations, it's important to keep in mind that each step of computation may make the approximation worse, so that after many steps it's not always obvious how precise the result is — in some cases, the result is meaningless because the magnitude of the uncertainty is larger than the result. Numerical algorithms need to be constructed carefully to minimize errors due to approximations.

There is a whole subfield of computer science devoted to floating point calculations. To start with, read the classic paper What Every Computer Scientist Should Know About Floating-Point Arithmetic by David Goldberg.

# Answer
> 0 votes
The question of finding a binary fraction which can be transformed back to the same decimal fraction was analized at great length by Knuth in his "A Simple Program Whose Proof Isn't", see

```
@InCollection{Knuth:1990:SPW:119872.119899,
  language =     {english},
  author =       {Knuth, Donald E.},
  title =        {A Simple Program Whose Proof Isn't},
  booktitle =    {Beauty is Our Business},
  editor =       {Gries, David},
  year =         {1990},
  isbn =         {0-387-97299-4},
  pages =        {233--242},
  numpages =     {10},
  url =          {http://dl.acm.org/citation.cfm?id=119872.119899},
  acmid =        {119899},
  publisher =    {Springer-Verlag New York, Inc.},
  address =      {New York, NY, USA},
}

```

---
Tags: approximation, numerical-analysis, floating-point
---


# Question
Title: Acquiring the necessary background for research
I'm starting my mater's thesis in computer science. I'm interested in computational Origami (algorithms mainly); I've read a little about the subject and I'm worried because I lack some of the knowledge that I think is necessary to do research in that area. But still I'd like to start and want to ask: which is better an approach: learn the necessary background as I go and wheneve a necessity pops up or learn it first and then start. I have 4 to 5 months to finish my thesis.

# Answer
In my experience, it is better to learn stuff as you need it. Otherwise, you don't have the motivation to *really* "get" it, and there is always the risk of getting lost in the forest of interesting stuff out there (that in the end is of no use). Be at the lookout for results that could help you (Google or citeseerx or ..., or even this site, are your friends).

Another piece of advise: Start writing right now. Editing your ramblings into something coherent later on is easy, sitting in front of a blank screen with writer's block when the deadline approaches is extremely painful. Write down what you do right now; if it works out it stays for later, if not it gets erased (and you don't get embarassed by your dumb attempts ;-). That way it doesn't happen to you that you *know* something is right, but don't remember why... and have to redo lots of work (happened to me!).

Make a short (3-4 line) summary of each paper or other reference that looks relevant, add it to your bibliography. Reading the stuff so you are able to extract what is relevant to you helps understanding the stuff, the summaries help in locating material later. And the collection of summaries will be your chapter on state of the art (after cleanup).

As a final comment, use LaTeX (it looks much nicer, has very good handling of bibliographies ;-), and perhaps asymptote for figures (it is a bit hard to learn, but has C++-like syntax to manipulate points and define lines, and produces excelent results). Put the whole stuff under version control (my favorite is git, but use whatever you are confortable with). That way you'll be able to have an up-to-date backup (preferrably on some other machine!), and go back if you *really* mess up (Murphy's lat assures us you will).
> 11 votes

# Answer
I agree that you will be more motivated for deep understanding once you have already begun working. At the same time, you want to make sure that you have covered enough background that you don't "reinvent the wheel". I suggest alternating your background reading and more focused work. Once you've started working, it will help focus your reading. Your reading may in turn spark new ideas for your work.

I find it helpful to read first for breadth, and then for depth. A good survey paper can save a lot of time here, but if not, I like to take a very brief look at a whole range of papers to determine what's important, then take a deeper look at the papers which have had the most impact or are most important to my particular interest. I read just the introductions of a few of the most recent papers. It helps orient me to what have been the seminal papers over time. Then I take a look at those papers. Going in historical order can help, since later papers build on earlier papers, but also be aware that later papers may refine or simplify earlier ideas as well.
> 4 votes

# Answer
In addition to all useful mentioned recomendations, I recommend you to find good "**survey paper**" in your area. It will help you to get the big picture of the research topics and some open and hot questions. They also contain the well known references.
> 2 votes

---
Tags: research
---


# Question
Title: How to show composition of one way function is not such?
I was wondering how should I proceed in order to show that the composition of (say) two one-way functions (either weak or strong or both together) is not a one-way function?

Specifically: Say $f$ and $g$ are one-way functions (either weak or strong). How do I prove that their composition $g(f(x))$ is not necessarily a one-way function?

# Answer
> 6 votes
You come up with an example: two functions $f,g$ which are one-way functions, but $f \circ g$ is not. To show that the latter is not a one-way function, you come up with an algorithm breaking it.

Here is an example. Choose some genuine one-way function $h$. Let $f(x) = h(x) 0^{|x|}$, and let $g(x,y) = h(x)$ if $y \neq 0^{|x|}$, and $g(x,y) = 0^{|x|}$ if $y = 0^{|x|}$ (we break the input in such a way that $|x|=|y|$). Note that the composition is just the zero function.

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


# Question
Title: Description of resolution algorithm as it applies to SAT
SAT \[5\] can be solved with resolution definitively, i.e. if the formula has a true assignment, resolution can find it, and if it cant be satisfied, resolution can show that no assignment exists (at least in exponential time/space.). \[4\]

> Is there a good fully-self contained description somewhere of solving SAT with resolution?

The descriptions on Wikipedia of resolution are focused on a single logical operation, not how to use it in an algorithm to solve SAT, and the Davis Putnam algorithm is described mostly in terms of 1st order logic. I am looking for a description of solving SAT with resolution that does not refer to 1st order logic, just in terms of boolean input variables. Online description is preferred if possible. The connection with DPLL would be helpful also.

---

\[1\] Davis Putnam algorithm, Wikipedia

\[2\] Resolution in logic, Wikipedia

\[3\] Davis Putnam Logemann Loveland algorithm, Wikipedia

\[4\] Is resolution complete or only refutation-complete?

\[5\] The boolean satisfiability problem

# Answer
What you are looking for is a proof of the completeness of resolution. Here is one example. The relation to DPLL is that a run of DPLL which terminates in failure can be converted to a resolution proof that the formula is unsatisfiable.
> 4 votes

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


title: Dangerous interrupts

text:
# Question
Title: Dangerous interrupts
Let's say we have a fictional operating system in the user mode. Whenever an interrupt or a trap occurs, the os would switch to the Kernel mode jumping to the address determined from the interrupt vector. A malicious user could take advantage of the loophole by executing a malicious program in the kernel mode.

Why is it dangerous ? What could have the user possibly done to achieve this and what kind of remedy would you suggest for the loop hole ?

# Answer
The malicious user has to first get the malicious code into kernel space somehow. User and kernel address spaces often look contiguous under linux and various unixes, but user space isn't mapped into kernel space, and vice versa. Some variations of Unix (the Masscomp system, as I recall) made this more explicit by having user space and kernel space start at 0x00000000. So, that's the first problem: code at 0x0804890c (or where ever) writeable by the user doesn't exist in the kernel's address space.

Secondly, the malicious user would have to have the ability to change the interrupt vector. This vector conceptually could live in either kernel or user space, but probably resides in kernel space. If the interrupt vector resides in kernel space, the user doesn't have write access. If the interrupt vector resides in user space, it's marked read-only, and the addresses in it point to code in kernel space. Which is why problem (1) above for the malicious user exists.
> 5 votes

# Answer
The details depend on the processor architecture, but generally speaking, when an interrupt is raised:

* The CPU saves some registers (at least the current program counter and an indication of the current processor mode).
* The CPU switches to a privileged mode.
* The CPU reads a pointer value from virtual memory at a predefined location (the interrupt vector).
* The CPU branches to that address.

It's up to the operating system designer to ensure that use mode code cannot change the interrupt vector and that the interrupt vector points to a location that can only be modified by privileged code. The page containing the interrupt vector, the code page that the interrupt vector points to, and of course the virtual memory tables, must be modifiable only by privileged code. If there was a way for the currently-running user mode code to affect what is executed on an interrupt, that would be a major bug in the kernel.
> 1 votes

---
Tags: operating-systems, security, os-kernel
---


# Question
Title: What is the difference between a TM accepting and deciding a language?
Frankly I'm very uncomfortable with the material right now. There are some things I can understand, but many I still do not.

My first assignment is asking me in one question (which I do know how to do) to give a full description of a TM that accepts a language $L = \\{ x \in \\{0,1\\}^\* \mid x \text{ is divisible by } 4 \\}$. I know that any binary string ending with $00$ is divisible by 4, so $\\{00,100,1100,1000,11100,11000,10100,10000,\dots\\}$ is the language that this TM accepts.

But on the topic of (un)decidability: I know that a language is decidable if there exists a TM that accepts all strings in, and only strings from that language — and that same TM rejects all strings and only strings not in that language.

Which leads to the question: What is the difference between a Turing machine *accepting* and *deciding* a language?

# Answer
In situations like these, where you are wondering about the difference between two phrases, the correct thing to do is to look up some definitions and think about them. You will discover several variations, perhaps something like this:

1. A machine "eats" a language $L$ if on input $x$ it halts and outputs $1$ if $x \in L$, and $0$ otherwise.
2. A machine "drinks" a language $L$ if on input $x$ it halts in an `accept` state when $x \in L$ and in a `reject` state if $x \not\in L$.
3. A machine "sniffs" a language $L$ if on input $x$ it halts in an `accept` state when $x \in L$, and never terminates if $x \not\in L$.
4. A machine "gobbles" a language $L$ if on input $x$ it reaches a `OK` state when $x \in L$ and never enters the `OK` state otherwise.
5. A machine "chews" a language $L$ if on input $x$ it halts in state `0` when $x \in L$, and either never terminates or halts in state `1` when $x \not\in L$.

These all look the same but are all slightly diffent. You should expect some definitions to be slightly broken (because you got it from Wikipedia or your classmate's notes), or phrased in a weird way that suits the needs of a particular texbook, etc.

The most important thing to do is to figure out what the definitions are really trying to convey. If they are basic definitions that everyone refers to, they are likely to tell you something important. (In a research paper people sometimes make definitions to numb the readers' brains.) Once the *concepts* are clear, it does not matter what they are called. Also, in case of terminological confusion, you will always be able to quckly resolve possible misunderstanding because you already know what concepts to expect.

In the present case, there are really two possible notions. One in which a machine always halts and signals acceptance/non-acceptance in some way, for example by halting in certain states, or by outputting certain symbols. The other concept is when a machine does not always halt, and it uses halting to indicate acceptance and non-halting to indicate non-acceptance.

A nice exercise is to figure out which of the five definitions given above corresponds to which of the two concepts (and which definition is a bit unclear, if any). But even before the exercise you need to know why these are two different concepts! You need to be aware of a language which falls under one but not the other concept.

The trouble with learning math is that you have to simultaneously learn new phrases *and* their meaining, *and* figure out why people invented them.
> 10 votes

# Answer
There is major difference. A turing machine "accepts" a language, if it enters an accepting state for any input from the langue, while it "decides" the language if it "accepts" it **and** enters a rejecting state for any input not in the language.

These are different, because there is a third thing that a Turing machine can do: never stop. Such Turing machine accepts the language, but does not decide it.

See also this other question and definition of decidable language on WP.
> 9 votes

# Answer
They are usually used as synonyms. In your example, the Turing Machine should first go all the way to the end of the input, and then check that the two rightmost digits are 0, as you suggest.
> 3 votes

---
Tags: terminology, turing-machines
---


# Question
Title: Is there a name for this relation on CFGs?
I'm looking for the name (or *a* name if there isn't one already) of this relation between $G\_1=\left\<\Sigma\_1,\mathcal{N}\_1,\mathcal{R}\_1,S\_1\right\>$ and $G\_2=\left\<\Sigma\_2,\mathcal{N}\_2,\mathcal{R}\_2,S\_2\right\>$: $$\exists f\_\Sigma\in\Sigma\_1\times\Sigma\_2,f\_\mathcal{N}\in\mathcal{N\_1}\times\mathcal{N}\_2 \text{ surjective functions s.t. }\\ \mathcal{R}\_2=\left\\{f\_\mathcal{N}(N)\rightarrow f(\alpha)\mid N\rightarrow\alpha\in R\_1\right\\}\text{ and } S\_2=f\_\mathcal{N}(S\_1) $$ where $f$ is the extension of $f\_\Sigma$ and $f\_\mathcal{N}$ to words ($f\in(\Sigma\_1\cup\mathcal{N}\_1)^\*\times(\Sigma\_2\cup\mathcal{N}\_2)^\*$).

In other words, you can map $G\_1$ to $G\_2$ (but not necessarily $G\_2$ to $G\_1$).

If the mapping function were bijective, this would be an isomorphism, but they're not.

What about if only $f\_\mathcal{N}$ is surjective, i.e. $f\_\Sigma$ is bijective, or even the identity function?

# Answer
This is a kind of (surjective) homomorphism, but the traditional definition is defined only over terminal symbols, not nonterminals.

Your definition would merge unrelated nonterminals from the first grammar with each other in the second grammar, thereby allowing (the image of) unrelated parts of the grammar to get mixed up with each other. This probably does not have nice properties, at least compared to the traditional definition of homomorphism.

That said, I can imagine that it is useful for some kinds of modelling, of AOP, of dynamic binding, of extensible grammars. I'd be interested in knowing what your application is.
> 3 votes

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


title: How to show that L*=(L*)*?

text:
# Question
Title: How to show that L*=(L*)*?
I am studying formal language theory and have been asked to prove the following:

$\forall L, L^\*=(L^\*)^\*$

I've started with

$def. L^\* = \bigcup\_{i \in \mathbb{N}} L\_i, L\_0=\\{{\epsilon}\\}, L\_1=\\{L\\}, L\_{i+1}=\\{uv|u\in L\_i, v\in L\\}$

$then (L^\*)^\* = \bigcup\_{i \in \mathbb{N}} L\_i^\*, L\_0^\*=\\{{\epsilon}\\}, L\_1^\*=\\{L^\*\\}, L\_{i+1}^\*=\\{uv|u\in L\_i^\*, v\in L^\*\\}$

$L^\*L\_0^\*\in(L^\*)^\* = L^\*\epsilon^\* = L^\*$ $\therefore L^\* \subseteq (L^\*)^\*$

$L^\*L\_0^\* = L^\*, L^\*L^\*\_1 = L^\* (def), L^\*L\_{i+1}^\*=L^\*\_iL^\*=L^\*L^\*$ but the * operator is closed under concatenation, thus, $L^\*L^\* \in L^\* \therefore (L^\*)^\* \subseteq L^\*$

$\therefore L^\* = (L^\*)^\*$

I simply don't have an intuition on whether this attempt at a proof is correct and I would appreciate any insight about it since the subsequent problems are to show $L^+=(L^+)^+$ and then to argue whether $(L^\*)^+=(L^+)^\*$

# Answer
> 12 votes
It's a big problem if you can't tell whether your proof counts as a proof or not. Perhaps it's better to write the proof "in words". Here is an example.

Since $M \subseteq M^\*$ for every language $M$, clearly $L^\* \subseteq (L^\*)^\*$. Now suppose $w \in (L^\*)^\*$. Then $w = w\_1 \ldots w\_\ell$ for some $w\_1,\ldots,w\_\ell \in L^\*$. Then for each $i$, $w\_i = w\_{i,1} \ldots w\_{i,\ell\_i}$, where $w\_{i,j} \in L$. So $w = w\_{1,1} \ldots w\_{1,\ell\_1} \ldots w\_{\ell,1} \ldots w\_{\ell,\ell\_\ell} \in L^\*$. This shows that $(L^\*)^\* \subseteq L^\*$, and so $L^\* = (L^\*)^\*$.

This is probably very similar to the proof you give, but your proof is written "in symbols" and so it is somewhat hard to parse.

# Answer
> 10 votes
We should prove that $L^\* \subseteq (L^\*)^\*$ and then $(L^\*)^\* \subseteq L^\*$.

The first case follows from showing that for every set $A$, we have $A \subseteq A^\*$, then let $A = L^\*$. The second follows from noticing that every $(L^\*)^\*$ is made of factors of $L^\*$ and every word of $L^\*$ is made of factors of $L$, therefore every word in $(L^\*)^\*$ is a word in $L^\*$. This proves the theorem.

---
Tags: formal-languages
---


# Question
Title: Find the origin and the destination of a trip from a serie of tickets
I was asked to design an algorithm that solves the following problem :

> Consider a travel from city A to city B, made of several trips by train through other cities in between. With an access to the unordered list of train tickets from which you can read the cities of departure and arrival of each trip, find A and B.

Unfortunately, I was unable to give an efficient algorithm when I needed to (in pseudo code), but once I got home, I came up with this answer (in JavaScript).

```
var tickets = [
    {from:'Paris', to:'Berlin'},
    {from:'London', to:'Paris'},
    {from:'Zurich', to:'Milan'},
    {from:'Berlin', to:'Zurich'}
    ];

function getTrip(tickets)
{
    var ticket = tickets.shift();
    var trip = {from:ticket.from, to:ticket.to};

    while(tickets.length > 0)
    {
        ticket = tickets.shift();

        if(ticket.from == trip.to)
        {
            trip.to = ticket.to;
        }
        else if(ticket.to == trip.from)
        {
            trip.from = ticket.from;
        }
        else
        {
            tickets.push(ticket);
        }
    }

    return trip;
}

var trip = getTrip(tickets);

console.log('The trip was from %s to %s', trip.from, trip.to);

```

While this might look like a very simple problem, I am still curious to see if there is a more efficient solution (for both time and space) or simply considerations I completely forgot. This may not need to be in JavaScript (especially if the language gives greater control over some aspects of the problem).

# Answer
> 2 votes
Using a hash table, record for each city mentioned how many times it was mentioned as a source and how many as destination. The source of the trip is the city that has appeared as a source an odd number of times, and similarly for the destination of the trip. That's linear time and space (with high probability).

Also, as Jan comments, the statistic that should be odd is the total number of times that the city has appeared. If a city appeared an odd number of times, then it is the source if it appeared as a source more than as a destination, and vice versa for destination.

# Answer
> 2 votes
Several answers have already been given, but I still think this is somewhat cuter.

Construct a bidirectional map $m: \mathcal{C} \to \mathcal{C}$ from cities to cities. This map means that if $m(x) = y$, then there is a path of tickets such that you start in $x$, take an arbitrarily long path (using only your tickets), and end up in $y$. The map encodes connected component with entry and exit points.

Now, the algorithm is as follows: On ticket $(u,v)$,

* if $m(v)$ exists, let $m(u) = m(v)$ and delete $m(v)$,
* if $m^{-1}(u)$ exists, say $m^{-1}(u) = w$, let $m(w) = v$, and
* else add $m(u) = v$.

What you end up with, should be *one* entry in $m$, $m(s) = t$, where $s$ is starting city and $t$ is destination.

This is under the assumption that the tickets you have form a path.

# Answer
> 1 votes
Yuval's answer is on right track, but being oriented graph, you need to compare number of times a city appears as arrival with number of times it appears as departure.

Overall departure is the city that appears more times as departure than as arrival (usually once as departure and never as arrival) and overall arrival is the city that appears more times as arrival than as departure (again usually once as arrival and never as departure).

# Answer
> 0 votes
The train tickets form a directed walk. The departure place will have one more leaving arc than entering arcs, and the destination one more entering arc than leaving ones.

# Answer
> 0 votes
You don't have to reorder everything:

**A** is the ticket that has no matching departure
**B** is the ticket that has no matching destination

When you're looking for efficiency, abuse the specifics of the system.

---
Tags: algorithms
---


# Question
Title: How to prove this isomorphism-related graph problem is NP-complete?
Consider the following problem: Given two graphs $G\_1 = (V\_1, E\_1)$ and $G\_2 = (V\_2, E\_2)$ and some non-negative integer $k \in \mathbb{N}$, is it possible to delete at most $k$ vertices from $G\_1$ to obtain $G\_1'$ such that $G\_1' \cong G\_2$, i.e. the resulting graph is isomorphic to $G\_2$.

I have to show that this problem is NP-complete.

Can somebody help me with this problem? It is school homework and I don't know how to solve it.

# Answer
> 9 votes
Here's a hint: Consider Vertex Cover, which is NP-complete. If $G = (V,E)$ has a vertex cover of size $k$, then you can remove $k$ vertices from $G$ to obtain $G'$ such that $G'$ is an edgeless graph on $n-k$ vertices.

Edit: The correct reduction (by using Vertex Cover) shows the problem to be NP-hard. Given the correct witnesses, you can easily show that it is in NP.

# Answer
> 0 votes
Your problem is one version of famous **subgraph isomorphism problem** which is NP-complete. It is a computational task in which two graphs G and H are given as inputs, and one must determine whether G contains a subgraph that is isomorphic to H. There are many solutions on the web for this problem.

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


title: RTT (Round Trip Time) calculation

text:
# Question
Title: RTT (Round Trip Time) calculation
How do I calculate RTT, do I start to measure the time from the beginning of the segment transmition or from the moment all the segment had been transmitted?

The end time is the moment the sender gets the "ACK".

# Answer
> 2 votes
The round trip time is the time required to go and return, so it must be measured from the *start* of the transmission to the *start* of the reception of the response. If you measure from the end of the packet to the end of the ACK, you are subtracting the package length and adding in the length of the acknowledgement's package (the ACK could be piggibacked on any package doing the back trip). This can very well be measured during a stream of data (and it is done so by your neighborhood TCP stack to tune timeouts and so on).

# Answer
> 1 votes
The best way to measure RTT is to send a *single* message packet and wait for the acknowledgement.

Starting your measurememt differently would only add unnecessary details because you start measuring delays not caused by the network. This is why pings are usually used measure RTT.

But it s nothing but an implementation detail.

# Answer
> 1 votes
Something that you should consider is to do some statistics on different data size. Send different data packet size, measure RTT, Then you can measure **Avg**. RTT based on data size, its **variance** and **jitters**. there are some open source tools for measuring these numbers like **Wireshark**.

---
Tags: computer-networks
---


# Question
Title: What's the reason for the second condition of the pumping lemma(s)?
For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows:

**Regular version**: If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following conditions:

1. $|y|\geq 1$
2. $|xy|\leq p$
3. $ \forall i\geq 0: xy^iz\in L$

**Context-free version**: If $|s| \geq p$, then $s$ can be written as $uvxyz$, satisfying the following conditions:

1. $|vy|\geq 1$
2. $|vxy|\leq p$
3. $ \forall i\geq 0: uv^ixy^iz\in L$

My question is this: **Why do we have condition 2 in the lemma (for either case)?** I understand that condition 1 essentially says that the "pumpable" (meaning nullable or arbitrarily repeatable) substring has to have some nonzero length, and condition 3 says that the pumpable substring can be repeated arbitrarily many times without deriving an invalid string (with respect to $L$). I'm not sure what the second condition means or why it is important. Is there a simple but meaningful example to illustrate its importance?

# Answer
When proving that a language isn't regular/context free it is quite useful to be able to limit the area containing the pumped string. The classical example is proving $\\{a^n b^n \colon a \ge 0\\}$ non-regular: If you take $\sigma = a^p b^p$, where $p$ is the lemma's constant, then without condition (2) you have to consider the three pieces into which $\sigma$ can be cut to be formed of $a$, of $b$, or both. Can be done, but is a lot more complicated. In the language given in the question (same number of $a$ and $b$), you can select $\sigma = a^p b^p$, and unless you can force the piece pumped to be just $a$ or $b$ you won't go anywhere, and there condition (2) is vital.
> 5 votes

# Answer
Consider the language of words over $\\{a,b\\}$ consisting of words with an equal number of $a$s and $b$s. This language is context-free but not regular. To show that it is not regular using the pumping lemma, you start with the word $a^pb^p$ and pump $y$, which must consist solely of $a$s. Without condition (2), this wouldn't work: you can pump $ab$ (in the middle) and remain inside the language. Moreover, for *any* word that you start with, you will be able to find one of the substrings $ab,ba$ which you could then pump.

Similar considerations show that condition (2) is needed for proving that the language over $\\{a,b,c\\}$ consisting of those words having an equal number of $a$s, $b$s and $c$s is not context-free.
> 7 votes

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


title: BFS in K shortest paths

text:
# Question
Title: BFS in K shortest paths
Do we need to use BFS or DFS algorithm to find the k shortest loopless paths in a graph between any two nodes? If so where can it be useful?

# Answer
Whenever they ask for *shortest* paths in a graph, it is a safe bet that some form of BFS is called for (you need to first check the neighbors of the starting point, if none qualifies you need to check all their neighbors, and so on. I.e., BFS).
> 1 votes

# Answer
For k=1.

I would like to draw your attention to the Theorem 22.5: Cormen
"upon termination d.v = ð(s,v) for all v € V"

ð(s,v) ... the minimum number of edges from s to v
> 0 votes

# Answer
Consider the case $k=1$ first. Can you use BFS or DFS? Now try to generalize.
> -1 votes

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


# Question
Title: How to calculate the depth of sorting networks?
I have trouble understanding how to calculate the depth of a sorting network on $n$ inputs.

For example, in case of selection sort, we have:

$\qquad \displaystyle D(n)=D(n-1)+2\\\qquad D(2)=1$

which leads to

$\qquad \displaystyle D(n)=2n-3=\Theta(n)$

I have confirmed that the depth of selection sort is equal to $2n-3$ by hand, but I can't understand how the recurrence $D(n)=D(n-1)+2$ is derived.

# Answer
For selection/bubble sorting network algorithms, the main tricky point is that "**some operations are overlapped**" or in other words because of ***pipeling***! (it is shown in figure below) You can find more information in these lecture notes by Rolf Karlsson.

This is the reason why the time complexity is linear!
> 2 votes

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


# Question
Title: Algorithms to prioritize equipment renewals
I am looking for algorithms to prioritize equipment renewals.

Input: (years since last renewal, cost of renewal, importance of renewal).

Output: An ordering of the equipment according to which it will be renewed.

I do not know if there are any algorithms for this particular problem. If you have any idea how to fit this problem into a more general context, that would be useful too.

A way to rephrase the problem:

You have $n$ pieces of equipment $E\_1,\ldots,E\_n$. For each piece $E\_i$ you have a triple $(\text{age}\_i,\text{cost}\_i,\text{importance}\_i)$. At the beginning of the year you have $X$ amount of money. You want to spend these money in order to *minimize* the function $\sum\_i \text{age}\_i\cdot \text{importance}\_i$ at the end of the year. So, during the year you have to select a subset $S$ of $\\{1,\ldots,n\\}$ such that: $$\sum\_{i\in S} \text{cost}\_i\le X \text{ (cost constraint)}$$ and the sum $$\sum\_{i\in S} \text{age}\_i\cdot \text{importance}\_i$$ is *maximal* among all subsets of $\\{1,\ldots,n\\}$ that satisfy the cost constraint.

Any help?

# Answer
Given the clarification to the question, it is a 0-1 knapsack problem (your knapsack is the money available, the value is the objective function), and look for ways to solve that one, for example following the Wikipedia lead.

**Edit:** A simple approximate algorithm would be just sort equipment on increasing cost per unit (age * importance), and in that order include each if it fits (doesn't run over maximal cost). In the case of continuous knapsack (i.e., can include a fraction of a item) that strategy is optimal. *Should* work fine if there are many items, and the data isn't too spread out.
> 4 votes

# Answer
It all depends on how you define how you decide a an equipment is to be renewed. But at the end, you may sort the lists lexicographically. That is, define a *comparison function* that takes as input two sets $X = (x \_1, ..., x\_k)$ and $Y = (y \_1, ..., y \_k)$, it will return true if $X \succ Y$ and false otherwise, where $X \succ Y$ if:

* $x \_1 \succ y \_1$ or:
* if there is a $j$ s.t. $1 \< j \leq k$, $x \_j \succ y \_j$ and $x \_i = y \_i$ for each $1 \leq i \< j$.

Use this function with any sorting algorithm you know. (but instead of sorting numbers, you sort lists according to the set comparison function you define).
> 1 votes

---
Tags: algorithms, optimization
---


# Question
Title: Facebook Hackercup 2013: Balanced Smileys
On Facebook HackerCup 2013, they asked the following question:

> Your friend John uses a lot of emoticons when you talk to him on Messenger. In addition to being a person who likes to express himself through emoticons, he hates unbalanced parenthesis so much that it makes him go :(
>
> Sometimes he puts emoticons within parentheses, and you find it hard to tell if a parenthesis really is a parenthesis or part of an emoticon.
>
> A message has balanced parentheses if it consists of one of the following:
>
> * An empty string ""
> * One or more of the following characters: 'a' to 'z', ' ' (a space) or ':' (a colon)
> * An open parenthesis '(', followed by a message with balanced parentheses, followed by a close parenthesis ')'.
> * A message with balanced parentheses followed by another message with balanced parentheses.
> * A smiley face ":)" or a frowny face ":("
>
> Write a program that determines if there is a way to interpret his message while leaving the parentheses balanced.

Balancing parentheses is talked about in a lot of places. E.g. `(()) vs ()()`. You can count

* `'(' = +1`
* `')' = -1`

Then you have to make sure your sum never falls below **0**.

In this question they consider `:)` and `:(` as balanced and I wonder how much it changes things. One solution says that you can replace `r'[^a-z:() ], ''`, `':)' -> '}'` and `':(' -> '{'`.

While I agree with the first sub, why are the last two substitutions valid?

# Answer
> 2 votes
The solution is correct because the "}" and "{" symbols are considered "optional" parentheses.

```
(:):):(:::) → (}}{}

```

The left one is an example of an input string, the right is the preprocessed version of it. If you read the algorithm, you see that they keep *two* values,

```
min_level, max_level = (0, 0).

```

Reading the actual solution should convince you.

---
Tags: algorithms, context-free, binary-trees, parsing
---


# Question
Title: How come finding an $n/2$ size clique in a directed/ non directed graph is not in $\sf NL$?
obviously the "Finding an $n/2$ size clique in a directed/ non directed graph" is not $\sf NL$ but I'd really like to understand where does it fall in terms of the definition of the $\sf NL$ definition.

I have to have an input and witness tapes, both of them can be polynomial and a logarithmic size of work stripe. So why can't I just guess an $n/2$ clique, each time put 2 vertices on the work tape, check that they share an edge, and count them. The witness tape provides me each time two vertices from left to write, in total $O({\frac{n}{2}}^2)$. In order to count that I need $O(\log ({\frac{n}{2}}^2))$ which is logarithmic. so what's lacking or wrong with this attempt?

# Answer
> 2 votes
(Turning my comments into an answer.)

You have to deterministically verify that the $\mathcal{O}(n)$ vertices on your *witness tape* form a clique. Since you can only move to the right, you can only do linear amount of work for this set, however there are $\mathcal{O}(n^2)$ *pairs of vertices* in the clique, and you have to check every pair. Hence you cannot check every pair and thus not verify if it is a clique or not.

Note that this is not a proof that $\mathbf{Clique}$ is not in $\mathsf{NL}$, only that this algorithm (or idea) doesn't work.

# Answer
> 0 votes
Short answer: the wrong thing in your solution is that the definition you are using does not give an $\mathsf{NL}$ algorithm, it gives an $\mathsf{NP}$ algorithm.

Here is another way to explain the problem: in $\mathsf{NL}$ you can't really assume that you get a witness to verify which is of polynomial size (as we do in $\mathsf{NP}$). In fact if we take the polynomial size witness plus a log-space verifier we end up with $\mathsf{NP}$ not $\mathsf{NL}$ (and this is true even if we use weaker verifiers, as long as the witness is polynomial size and the class that verifier belongs to is capable of checking if a given string is an accepting computation of a given TM we end up with $\mathsf{NP}$).

So don't let the witness definition confuse you about $\mathsf{NL}$. An $\mathsf{NL}$ machine is *a nondeterministic machine which makes nondeterministic decisions and uses only logarithmic space* and we don't have a result that allows us to use a witness definition similar to the $\mathsf{NP}$ witness-verifier definition by just changing the verifier to be a log-space machine in place of a poly-time machine.

One can use a real-only read-once tape for a witness definition but that is not usually a good way of thinking about $\mathsf{NL}$. The witness verifier definition for $\mathsf{NP}$ is used because we end up with a very nice intuitive definition for $\mathsf{NP}$: verifying answers in polynomial time. We don't end up with a similarly nice definition for $\mathsf{NL}$.

ps: for completeness, it is consistent with the current state of knowledge that there is an $\mathsf{NL}$ algorithm for the problem. However, such an algorithm would imply $\mathsf{NL}=\mathsf{P}=\mathsf{NP}$ since the problem is complete for $\mathsf{NP}$. Therefore although it is not completely ruled out, it is considered a very unlikely possibility (and you would win a 1 million dollar prize if you had such an algorithm).

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


# Question
Title: On the generalization of two recreational problems: request for references, if there's any
I wonder if two famous (and, IMHO, very nice) recreational problems are been studied in some general form.

Here's the first. We have 13 balls, all looking absolutely the same, with 12 of them having the same weight; we don't know whether the ball that has a different weight is heavier or lighter. We have a balance with two arms and, using it at most 3 times, it is required to identify the ball with different weight. For the generalization below, I will consider a slightly different version of it: same scenario, but requesting the needed minimum number of times by which, in all cases, using the balance we can identify the different ball.

Here's the second. We have three card and we are in front of a door with three slot in which we can insert the cards. Each card is the correct one for exactly one slot and vice versa. Each slot is connected to a hidden circuit and, at the beginning, we don't know wheter a circuit is opened or closed (but at least one of them is opened). The door will open only if all three circuits are closed. We can change the state of a circuit solely by inserting all the three cards; when we insert all the cards, the circuits change state according to these rules: if a circuit is closed, it will open; if a circuit is opened, it will close only if the correct card is inserted in its slot. In general, without knowing the initial states of the circuits, what is the minimum number of insertions by which the door will certainly open?

We can generalize the above problems in obvious ways: the first problem by having $n$ balls (possibly, with $k$ of them having different weight), the second problem by having $n$ cards/slots/circuits (possibly, each card being correct for more than a slot/circuit).

Are these general problems new? Any similar and well-studied one?

# Answer
The first problem is well-known. Lots of different generalizations appear in this paper, which is listed in the Wikipedia entry on the 12 coins problem.

I've never heard of the second problem, but it is similar in spirit to the carrom board puzzle (which probably goes under other names as well), described in a note by Dijkstra. A further generalization appears in this writeup.
> 4 votes

---
Tags: reference-request, combinatorics
---


# Question
Title: Explanation of a specific recurrence with respect to Master Theorem
Concerning the Master Theorem. I have found the following equation as the base of analysis:

$\quad T(n) = aT(n/b) + \Theta(n^k)$

but I also found the following:

$\quad T(n) = aT(n/b) + \Theta(n^k\cdot\log\_p n)$

where the base $p$ is a real number.

Can anyone explain the second equation? I understand the proof with the first equation but can not understand the second formula.

# Answer
> 2 votes
Sometimes the master theorem is only given for recursions of the form $T(n) = aT(n/b) + \Theta(n^k)$, but the Wikipedia article includes a more general version which can handle functions of the form $T(n) = aT(n/b) + \Theta(n^k(\log n)^l)$, and even more general ones when $k \neq \log\_b a$. The similar Akra-Bazzi theorem handles more general situations.

---
Tags: algorithm-analysis, asymptotics, recurrence-relation, master-theorem
---


# Question
Title: What is meant by $\operatorname{poly}(|F|, n, e)$?
When I am reading a paper I found a notation $\operatorname{poly}( |F|,n,$$\frac{1}{\epsilon}) $. Its not clear to me that what this notation represents. Can you please help me out?

# Answer
> 6 votes
$F=\mathrm{poly}(n)$ means that $F$ is polynomial in $n$, i.e., that there exists a constants $c$ such that $F=\Theta(n^c)$. (sometimes it might mean upper-bounded by polynomial, that is $F=O(n^c)$)

For multiple variable, the same applies, $\mathrm{poly}(n,m)$ means polynomial both in $n$ and $m$, that is, there are constants $c\_1,c\_2$ and the quantity is $\Theta(n^{c\_1}m^{c\_2})$. (again, the more common use is for $O(n^{c\_1}m^{c\_2})$)

# Answer
> 4 votes
$\mathrm{poly}(\cdot)$ is simply notation for a function that is polynomial with respect to its parameters. In your case it would be polynomial in terms of $|F|$, $n$, and $\frac{1}{\epsilon}$.

---
Tags: terminology, algorithm-analysis
---


title: asymptotic notations with two exponents

text:
# Question
Title: asymptotic notations with two exponents
I am familiar with asymptotic notations like Big-O ,little-o. But while I am reading some papers people are using the notations like $O(\epsilon^{1/2^d})$, $O(d)^d$ etc. I couldn't understand these notations properly. Is there any way (Lecture notes or video lectures with examples) to understand these things clearly. Thank You.

# Answer
> 4 votes
That syntax is actually rather questionable formally, since it treats the big-O as a function, which it is not. But with a bit of slop the rule to interpret these is rather simple. The big-O stands for some function with the asymptotic behaviour given by the big-O.

I'll start with the full syntax of the big-O notation:

$$ f(n) = O(g(n)) $$

means that

$$ \exists C~\exists n\_0~\forall n \> n\_0: f(n) \leq Cg(n). $$

So when we write "complexity is $O(n)$", we are really saying complexity is $c(n)$ for which $c(n) = O(n)$.

Alternatively we can say $O(g(n))$ is a set of functions defined as

$$ O(g(n)) = \\{ f(n) | \exists C~\exists n\_0~\forall n\>n\_0: f(n) \leq Cg(n) \\}. $$

And write $f(n) \in O(g(n))$ instead. While this definition is more logical, it seems to be less used in textbooks.

Now if we say that complexity is $2^{O(n)}$, we can't expand it simply as $c(n) = 2^{O(n)}$, because we didn't define that. So instead we replace the big-O with a function that conforms to the big-O. Like this:

$$ c(n) = 2^{f(n)},\ f(n) = O(n) $$

And you can expand any other expression containing big-O. The approach applies to any expression having big-O as subexpression, so $O(n)^n$ is just

$$ c(n) = f(n)^n,\ f(n) = O(n) $$

In the set notation it makes even more sense, because

$$ g(F) = \\{ g \circ f | f \ in F \\} $$

where $g$ is a function and $f$ is a set of functions with one argument is the only logical definition of expression involving set of functions. So than:

$$ 2^{O(n)} = \\{ 2^{f(n)} | f(n) \in O(n) \\} $$

and

$$ O(n)^n = \\{ f(n)^n | f(n) \in O(n) \\}. $$

As for $O(\epsilon^{1/2^n})$, that's just standard big-O notation:

$$ f(n) = O(\epsilon^{1/2^n}) $$ $$ \exists C~\exists n\_o~\forall n\>n\_0: f(n) \< C\epsilon^{1/2^n} $$

(which tends to $1$ as $n$ tends to $\infty$). The $\epsilon$ would usually be some tunable parameter in the algorithm.

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


# Question
Title: Where did the terms memory pool and memory leak come from?
I wonder where those terms came from.

Is it computer science related?

Or are they related to civil engineering, or swimming sports?

Is it some analogy with filling water in a pool, or something like that?

# Answer
Yes, Computer Science.

Back in the days of the NASA/Apollo program (and possibly before), mainframe computers had wads of memory (like as much as 256 Mwords). To support multi-tasking, a program/task running on that mainframe had to specify how much memory was required to do its job, and the system would allocate that much - if possible - out of the "memory pool". This "pool" nomenclature comes at a time when we had motor pools, secretarial pools, labor pools... nonspecific resources of a certain class; indeed, this working memory on a mainframe was not dedicated to a specific use (there are regions of mainframe memory that are not available to "normal" programs/tasks).

As the tasks run, they are supposed to only use what they ask for, and they are required to signal the system when the memory is no longer needed. Depending on efficiency concerns, they may ask for the memory a little at a time (it's nice for other tasks that you don't grab either everything available, or more than you need). Poorly developed programs have a nasty side-effect of not returning what was allocated to them. From the system's perspective, the available memory pool is getting smaller and smaller, hence the memory "leaks out". It doesn't go anywhere, but the net effect is that a program that needs a certain amount of memory to either load or run will have to wait until a better behaved program/task returns a sufficient part of the allocation - or the memory system is restarted.
> 3 votes

---
Tags: terminology, history
---


title: Can GDB debug itself?

text:
# Question
Title: Can GDB debug itself?
Can GDB be run on itself? How or why not? I see something about it http://www.math.utah.edu/docs/info/gdbint\_3.html But GDB might not be written in a language that it can debug?

# Answer
> 3 votes
Yes, it's possible. Here's how to do it.

1. Obtain the source code for gdb.
2. Compile with the `-g` flag on.
3. Run `gdb gdb`.

---
Tags: correctness-proof, program-correctness
---


# Question
Title: About the behaviour of multi-layer perceptrons
I have a multilayer perceptron. It has an input layer with two neurons, a hidden layer with an arbitrary number of neurons, and an output layer with two neurons.

Given that `randomboolean` and `targetboolean` are random boolean values, and the network operates as such:

```
input(randomboolean); //Set the input neurons to reflect the random boolean
propagateforwards(); //Perform standard forward propagation
outputboolean = output(); //To get the networks output
ideal(targetboolean); //Performs connection updating via back-prop

```

Is it possible to get the network to map the `randomboolean` value to the `targetboolean` value in such a way as the the `outputboolean` value will correctly match the `targetboolean` while running in an 'on-line' (where prediction occurs along with continued learning) mode after some arbitrary number of training cycles.

I hear that the network needs to be recurrent to process this as it may be temporal behaviour, however the MLP is a universal computing platform and I assume it should be able to approximate the temporal behaviour needed for this task.

# Answer
The answer is no. What you want to do is to predict randomness. The perceptron network takes randomboolean(true/false) and it outputs outputboolean(not random!!). The random generation of targetboolean is independent from the generation of outputboolean.

Perceptrons generally learn functions. If you have $f(A)=B$ and $f(A)=C$ and $B\neq C$, then $f$ is not a function.

EDIT: To predict temporal behavior you should add some time dependent variable in the input of the network.
> 0 votes

# Answer
The question isn't very clear, but it seems that you are trying to use a neural network to analyze a pseudo random number generator (PRNG). The idea being that if the values are properly random, the network won't learn anything, and if it will, then the random number generator is flawed.

If this is the case, I don't expect that you'll have much luck. To be fair, many PRNGs have exploitable flaws, but these are very deep and highly specific. Basic statistical tests aren't enough, and I don't expect that a simple neural network will do any better.

Still, it never hurts to try. If you are going to perform this experiment, you should define very clearly where in the sequence of random bits your input and output value come from. No system is going to predict any bit from an PRNG from just a given other bit (unless the relative frequencies of 0s and 1s aren't uniform, but that would make it a very bad PRNG). The best strategy, I think, would be to use the most recent N bits in the bitstring as inputs and the next bit as the target. You can then slide a window over your PRNG's stream of random bits to generate a training set.

Finally, as mentioned, your neural network is trying to learn a probability distribution over outputs rather than a function. The best option here is to have two output nodes, one for 0 and one for 1 whose activations sum to one (and represent the probabilities per bit). If they predict the behavior of the PRNG better than chance, you've shown a weakness in the PRNG. To make sure that the activations sum to one, you can use the softmax activation function for the output layer.

I recommend trying some obviously flawed PRNGs to see where the method works, and at what level of sophistication it breaks down.
> 0 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks
---