# Question
Title: Asymptotic expected runtime of Randomized Algorithm
I am analyzing the asymptotic runtime of a randomized algorithm in expectation. The algorithm has the following properties:

* Given input size $n$, with probability $3/4$ it moves on to solve an instance of size $n-1$
* With probability $1/8$ it moves on to solve an instance of size $n-2$
* With probability $1/16$ it moves on to solve an instance of size $n-3$
* With probability $1/2^i$ it moves on to solve an instance of size $n-i$
* Each instance pays a cost of $O(n)$, where $n$ is the input size of that instance

Over expectation, the runtime can be defined recursively as follows:

$T(n) = O(n) + \sum\limits\_{i=0}^{n-1} (\dfrac{1}{2^{n-i+1}} T(i)) + \frac{1}{2}T(i-1)$

$T(0) = O(1)$

I have calculated that the expected number of "jumps" at each stage is $\leq 1$. I did this by showing $\sum\limits\_{i=0}^\infty \dfrac{i}{2^{i+1}}= 1$ by using telescoping and geometric series. However, since the complexity at each stage diminishes as $n$ gets smaller, although this hints the runtime is $O(n^2)$, it does not prove it. Anyone have any ideas to prove a runtime for the less relaxed version?

EDIT: Slight gap in my formulation. The "$3/4$" probability for moving onto an instance of size $n-1$ should actually be larger than $3/4$ since the probabilities $1/2, 1/4, 1/8, ...$ only go on till $1/2^{n+1}$. If no jumps were made, the algorithm deterministically moves on to an instance of size $n-1$.

# Answer
> 1 votes
As you mention, it is easy to prove by induction that the overall runtime is $O(n^2)$. If we don't have any more information, that's (almost) all we can deduce. For example, suppose that at each instance we pay a cost of $O(1)$. The running time will then be $O(n)$. In order to make progress, we have to assume that at each instance we pay a cost of $\Theta(n)$. In that case, we can argue as follows:

1. Since each "jump" is $O(1)$, it takes $\Omega(n)$ steps (on average) to reach $n/2$.
2. At each of these $\Omega(n)$ steps, we pay a cost of $\Omega(n)$.
3. Hence the total expected cost is $\Omega(n^2)$.

This is not a rigorous argument, but it can be turned into one if you're careful enough.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, randomized-algorithms, average-case
---


# Question
Title: Is there a proof of the recursive algorithm for generating all permutations of a sequence?
For clarity, I attach below a concise implementation of the algorithm in Python. I understand that it checks all possible element swaps, but I don't see how that necessarily means that all possible orderings of the elements will be reached, and/or that no ordering will be duplicated.

For example, what if the elements at index 0 and 1 are swapped, then 1 and 2 are swapped? How does the algorithm guarantee this won't result in a duplicate ordering?

```
P = []
def permute(l, n=0):
    if n == len(l):
        return P.append(list(l))
    for i in xrange(n, len(l)):
        l[i], l[n] = l[n], l[i]
        permute(l, n+1)
        l[i], l[n] = l[n], l[i]

```

# Answer
Hint: Prove by induction that $\mathrm{permute}(l,n)$:

* Adds to $P$ all permutations obtained from $l$ by permuting coordinates $n,\ldots,|l|$.
* Leaves $l$ unchanged. That is, the value of $l$ after running the function is the same as its value before running it.
> 2 votes

# Answer
Another option, just to show that you can think out of the box. You can prove that:

1. The algorithm appends exactly `factorial(len(l))` permutations to `P`;
2. No permutation is appended twice.
> 1 votes

---
Tags: algorithms, correctness-proof, permutations, enumeration
---


title: prove decidability and recognizability

text:
# Question
Title: prove decidability and recognizability
I want to prove that for any language $L\_1$ described by a Turing machine and any regular language $L\_2$, $L\_1 \cap L\_2$ is described by a Turing machine that its recognizability and decidability is same as $L\_1$.

I thought so far that I can describe $L\_2$ with a Turing machine. So I can next find the intersection Turing machine of both.

I do not know what to do about the last part of the problem. Maybe I can say that $L\_2$ is decidable (because it is regular) and $L\_1 \cap L\_2$ is a subset of that. So it is also decidable.

I am not sure whether my approach is correct or not. Please help me.

# Answer
The method you propose in your answer is mostly correct. $L\_2$ is, indeed, decidable because it's regular. But you can't argue that $L\_1\cap L\_2$ is decidale because it is a subset of the decidable language $L\_2$: *every* language is a subset of the decidable language $\Sigma^\*$ but that doesn't mean that every langauge is decidable.

**Hint.** You chose the tag , which shows you're on the right lines. $L\_1$ is either decidable or recognizable; $L\_2$ is both. What do you know about the intersection of two decidable/recognizable languages?
> 0 votes

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


# Question
Title: Prove existence of different programs printing each other code
How to prove that there exist two different programs A and B such that A printing code of B and B printing code of A without giving actual examples of such programs?

# Answer
You maybe know the recursion theorem. It implies, that you can assume that you have a procedure called `get_your_own_code`if your programming language is at least as powerful as a Turing machine.

Now do the following

```
Progr. A
w=get_your_own_code
print "print "+w

```

Note that some code is hidden in the subroutine of get\_you\_own\_code. So we assume the complete source code is a string called `source_code_of_A`.

```
Progr. B
print source_code_of_A

```

Program A prints:

```
  print source_code_of_A

```

Program B prints

```
  source_code_of_A

```
> 2 votes

# Answer
We will show that any Turing-complete "programming language" has such a pair of programs by using classic recursion theory, that is the notions of Gödel numberings with s-m-n property/theorem (smn) and Kleene's fixed-point/recursion theorem (FPT).
Denote with $\mathcal{P}$ the set of all (partially) recursive functions and with $\mathcal{R}$ the set of all total recursive functions.

We interpret "program $A$ outputs the code of program $B$" to mean

$\qquad\displaystyle \forall x.\ \varphi\_A(x) = B$, i.e. $\varphi\_A = \bigl\[x \mapsto B\bigr\]$;

in our setting $A, B \in \mathbb{N}$.

So let $\varphi$ an arbitrary Gödel numbering (with smn) of $\mathcal{P}$. From

$\qquad\displaystyle f = \bigl\[(i,x) \mapsto i\bigr\] \in \mathcal{P} $

we get with the s-m-n theorem that there is $g \in \mathcal{R}$ so that

$\qquad\displaystyle \varphi\_{g(i)} = \bigl\[x \mapsto i\bigr\] \\;. $

Now we are essentially looking for a fixed point of $g \circ g$, i.e. $a$ so that $\varphi\_{g(g(a))} = \varphi\_{a} = \bigl\[x \mapsto g(a)\bigr\]$; recall that $\varphi\_{g(a)} = \bigl\[x \mapsto a\bigr\]$.
This is easy to obtain by FPT, but we *also* need that $g(a) \neq a$ -- otherwise we just have a regular quine, not a pair of programs as required.

Therefore, we define¹ a "modified $g \circ g$" by

$\qquad\displaystyle h(j) = \begin{cases} g(g(j)) &, g(j) \neq j \\ g(j+1) &, g(j) = j \end{cases} \\;,$

and $h \in \mathcal{R}$ since $g \in \mathcal{R}$. Now FPT yields

$\qquad\displaystyle \exists\\, a.\ \varphi\_{h(a)} = \varphi\_a \\;.$

Now we know by construction of $h$ that $g(a) \neq a$. For a proof, note that assuming $g(a) = a$ leads immediately to

$\qquad\displaystyle \bigl\[x \mapsto a\bigr\] = \varphi\_{g(a)} = \varphi\_a = \varphi\_{h(a)} = \varphi\_{g(a+1)} = \bigl\[x \mapsto a+1\bigr\] \\;, $

a contradiction. So we can now let $b = g(a) \neq a$ and obtain as final result

\begin{align\*} \varphi\_b &= \varphi\_{g(a)} = \bigl\[x \mapsto a\bigr\] \quad\text{and} \\ \varphi\_a &= \varphi\_{h(a)} = \varphi\_{g(g(a))} = \bigl\[x \mapsto g(a) = b\bigr\] \\;. \end{align\*}

Credits go to a friend of mine who, after some fruitless tinkering on both of our parts, came up with the final idea.

---

1. Note that the second case is not unique; all we need is an index other than $j$. Using $g$ is convenient since we know what it does on every parameter.
> 2 votes

---
Tags: computability
---


# Question
Title: Why do relational databases use 2PC for distributed transactions over the likes of Paxos?
Paxos is more powerful and in the famous writing "Consensus on Transaction Commit" : http://research.microsoft.com/pubs/64636/tr-2003-96.pdf, Jim Gray and Leslie Lamport describe 2PC as a special case of Paxos.

Why do relational database use 2PC in real world? Also 2PC is not fault tolerant because it uses a single coordinator whose failure can cause the protocol to block.

# Answer
One of the reasons is the message complexity. For N nodes, 2PC will require 3N to be exchanged whereas Paxos requires 4N. Also, Paxos adds sequence numbers to each message which adds a significant overhead to the overall execution.
> 3 votes

---
Tags: distributed-systems, database-theory
---


# Question
Title: Hierarchy of complexity classes $\bigcup_{c > 0} \mathrm{Time}(2^{c \log^k n})$, w.r.t. $k$
This is a true/false question:

> For each integer $k \> 1$, define the complexity class $\sf QP\_k := \bigcup\_{c \> 0} Time(2^{c \log^k n})$. Then for all integers $k \> 1$, $\sf QP\_k \subsetneq QP\_{k+1}$.

I have to prove it is true, or I have to give a counter example as to why it is not true.

I am having a lot of difficulty understanding the notation and also how to approach this problem. My understanding is that $c$ is some constant and effectively doesn't matter.

Edit: I guess I am unclear about how c and k work, the c seems like it doesn't matter so its asking us if there is every a point where from k = 2 to k = infinity if there will ever be a situation in which $2^{c \log^k n}$ = $2^{c \log^{k+1} n}$ for all c and n.

Is this the right interpretation?

I cannot find a single counter example that would make this true for any k, so it must be true. I am not sure how I would go about proving this is true.

# Answer
Hint: Use the time hierarchy theorem.

The first step, naturally, is understanding the question, that is, the definitions involved. The class $\mathsf{QP}\_k$ consists of all problems solvable in time $2^{O(\log^k n)}$. We could similarly define $\mathsf{P}\_k$ to consist of all problems solvable in time $O(n^k)$, and $\mathsf{P}$ to be a union over all $\mathsf{P}\_k$: $$ \mathsf{P}\_k = \bigcup\_{c\>0} \mathsf{Time}(cn^k), \quad \mathsf{P} = \bigcup\_{k\>0} \mathsf{P}\_k = \bigcup\_{c,k\>0} \mathsf{Time}(cn^k). $$ The class $\mathsf{QP} = \bigcup\_{k\>0} \mathsf{QP}\_k$ is known as *quasi-polynomial time*. The question asks you to show that the corresponding hierarchy $\mathsf{QP}\_2 \subseteq \mathsf{QP}\_3 \subseteq \cdots$ is strict, that is $\mathsf{QP}\_2 \subsetneq \mathsf{QP}\_3 \subsetneq \cdots$. The same happens with the hierarchy corresponding to $\mathsf{P}$, again using the time hierarchy theorem: $\mathsf{P}\_1 \subsetneq \mathsf{P}\_2 \subsetneq \cdots$.

Why can't the same approach be used to prove $\mathsf{P} \subsetneq \mathsf{NP}$? Because here we're comparing deterministic computation to non-deterministic computation with the same time bounds, and there is no counterpart of the time hierarchy theorem which helps us here. Moreover, the time hierarchy theorems, in both the deterministic and non-deterministic case, are proved using diagonalization, a technique which is known to be unable to separate $\mathsf{P}$ from $\mathsf{NP}$ (in its vanilla form).
> 3 votes

---
Tags: complexity-theory, time-complexity, complexity-classes, notation
---


# Question
Title: What's the definition of a (deterministic) formal language?
**Definitions**

According to my UML teacher formal means strictly according to rules, officially and how it's supposed to be. He says a formal language = syntax + symbols + spelling. Another term he uses is deterministic. According to him it means "strictly predictable", which means its only interpretable in a single way. So one input can't map to two outputs.

**Confusion**

If I'm given any example of a language that humans invented, I can't tell nor elaborate whether it's a formal language or not. Some of these examples are natural languages (English, French, Dutch, etc.), UML, Math, notesheets, programming languages, markup languages, braille.

In my teachers powerpoint presentation, he explained a natural language is not formal because it's dependent on context (Unless I understand the definition of "deterministic" wrong, deterministic is the opposite of context dependency. By context dependency I mean, a sentence or a word can have two different meanings, e.g. *You were right*. But also *Make a right turn at the light* Thus a natural language is not deterministic).

But then a few slides later he said a formal language doesn't have to be deterministic, which makes me wonder why he would use context dependency as an argument to explain formal languages in the first place.

**Question**

What makes a language formal? Perhaps you can elaborate by using the examples given above. And what makes a language deterministic? Is it correct that deterministic is the opposite of context dependency?

**N.B.** Wikipedia isn't making much sense to me, and I've read that the article about formal languages is quite a mess because people have different opinions on it.

# Answer
The word formal has many meanings, among which you have:

* being precisely defined mathematically, or at least with very precise rules.
* being devoid of meaning.

In the case of formal languages in Computer Science, it is both: pure representation (syntax) with no meaning.

A formal salute is according to rule, and often devoid of feeling.

Lack of meaning does not mean that no meaning can be attached, but at least that none is being considered at first.

But the use of words and qualifiers must always be considered in context. A formal language, defined mathematically by a context-free grammar, may have no meaning. Then, it is possible to attach meaning to it in formally (mathematically) precise ways. This meaning can be a precise mathematical meaning, and we can then talk of formal semantics. That is how, for example, programming languages are now often defined, very precisely. It also apply to other mathematical languages.

If you consider natural language (say English), it was not created that way, but evolved by users, independently of a formal mathematical model, Furthermore, it does have semantics and exists for only that purpose. So it can on no account be considered formal.

Not only it is not syntactically formal, but its semantics is not formal either, because it is also evolved, and because it does depend on a context that is not precisely definable.

Regarding the word deterministic, it also has several meanings depending on context.

In computer science, a formal language is detrministic if there is a formal (mathematically defined) deterministic device (automaton) that can identify the sentences of the language. Here, the term deterministic means only that for a given sentence to be recognized, this automaton will always work/compute/behave in exactly the same way. A non-deterministic automaton is one that may have one of several well defined behaviors on the same input sentence (independently of any contextual issue). Automata are one way to define formal languages in computer science. Such a language is said to be deterministic if it can be defined by a deterministic automaton, and non-dterministic if it can only be defined by a non-deterministic automaton (I am skipping a lot of important details).

This is clearly not the meaning intended by your teacher, according to what you are saying. For him, something is deterministic when it is context independent, from a semantic point of view. In this sense, natural language is non deterministic (though I would never say it that way). I would rather called that "contextual".

In that sense, "non-deterministic formal automata" are deterministic since their "erratic" behavior (which needs to be explained) is independent of any context.

You can use words for any purpose, if you are careful to define what you mean. However I would never use "deterministic" as the opposite of "context dependent". A better word might be "univocal", or "non-contextual", or "context indpendent".

What really matters is to agree with your teacher on the meaning of words for the purpose of your course. Once you have passed the exam, you will be free to use a different terminology if convenient or required by a new environment, as long as you keep the concepts and possibly use other words to express them.
> 3 votes

# Answer
Formal languages could (potentially) mean different things in different contexts. The Wikipedia page explains one sense, while your teacher might be referring to a different (and more informal) sense. You should probably not worry too much about the formal definition of formal language.

The point your teacher is probably trying to get across is that a human language has an undesirable feature: it doesn't always have an accurate denotation. For example, what do we mean by a "sad song"? This doesn't have an accurate denotation. Compare this to "a string of a's and b's", which does have an accurate denotation. This highlights the vagueness of human language. Another problem is polysemy: the same term can have several different meanings. For example, "formal language" can mean "a set of strings over an alphabet" (the Wikipedia meaning) or the more vague "a language in which each expression has a well-defined and unique meaning", which is closer to your teacher's.

In contrast, formal language defines everything in an unequivocal way. You'll see many examples of formal definitions in class, and hopefully the difference will become clear. But more importantly, you are not a philosopher, and so you shouldn't necessarily be able to explain the difference or to consciously identify which is which. Rather, you should understand that in some contexts we try to banish vagueness as far as we can, and present things in a "formal" and unequivocal way. In other contexts, say writing a newspaper article or a novel, we have different aims, but that kind of writing doesn't fit in a UML class.
> 3 votes

---
Tags: formal-languages, terminology
---


title: All but Five Three Colorable

text:
# Question
Title: All but Five Three Colorable
An NP Problem Named All But Five Three Colorable(AB53C) is defined as follows :- Input : Connected Graph G(V,E) The Connected Graph is AB53C, iff the Given Graph is 3-Colorable by leaving UPTO 5 Vertices Uncolored.

Question:- The Problem is in NP. Show the reduction from 3-Colorable Problem.

The Proposed Solution is :-

Find Permutation of All Subsets where |V'| = |V| - 5. Basically these subsets will have 5 vertices less than the original set. Remove all edges from V' to V. All such subsets are found out and then passed through the 3-Color. If we get YES on any one of these Subgraphs, then we have a AB53C.

I want someone disprove my method OR show that the reduction is non-polynomial. Otherwise, my proposal is correct.

# Answer
Hint: Add a clique on 8 vertices to the graph.
> 1 votes

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


title: Function with minimum sensitivity

text:
# Question
Title: Function with minimum sensitivity
Let sensitivity be defined as in Sensitivity and Block sensitivity

Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose sensitivity is $O(\log n)$?

Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose average sensitivity is $O(\log n)$?

Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose sensitivity and average sensitivity is $O(\log n)$?

# Answer
The tribes function is the classical example of a transitive balanced function whose average sensitivity is $\Theta(\log n)$. Its maximal sensitivity is however $\Theta(n/\log n)$.

The addressing function is an example of a balanced function depending on all inputs which has sensitivity $\Theta(\log n)$ and average sensitivity $\Theta(\log n)$. It is simpler to describe this function as having an input of size $n + \log n$: the first $n$ bits describe a binary string $x$, and the last $\log n$ bits describe a number $i \in \[1,n\]$. The output of the function is $x\_i$. At any point the function depends only on the $\log n$ bits of $i$ as well as the single bit $x\_i$.
> 1 votes

---
Tags: complexity-theory, boolean-algebra
---


title: Questions on Topological Sorting

text:
# Question
Title: Questions on Topological Sorting
Currently learning about topological sorting. My teacher gave us this problem.

The answer given to us is : B,A,C,E,D,G,F,H in lexicographical order.

Why does the order go from B,A,C THEN go to E and then D IF it is in lexicographical order? Also, can another topological sort of this graph be: B,A,C,D,E,G,F,H?

# Answer
> 2 votes
The comments are right. In a topological sort, we start with nodes that have no incoming arrows and remove them from the graph, so to speak. In this case, if there are multiple possible nodes to remove, then we want to remove them in lexicographical order. Hence, the order should be $B, A, C, D, E , F, G, H$.

Your suggest topological sort does not work. This is because you propose to put $G$ before $F$.

---
Tags: graphs, sorting, graph-traversal
---


title: Counting nodes in a trie

text:
# Question
Title: Counting nodes in a trie
I'm studying random tries in one of my classes, and was wondering if anyone could offer any guidance regarding a problem.

**Question:** Given a random $m$-ary trie with $n$ total leaves, letting $I$ be the number of internal nodes in the tree (that is, nodes which aren't a leaf), show that $E(I)$ is $O(n)$.

**About the distribution:** We have an alphabet of $m$ letters (hence an $m$-ary trie), each with a corresponding probability $p\_i$. We randomly create $n$ words of infinite length by drawing the first letter from our distribution, the second letter, etc. Finally, we insert these $n$ infinite words into a $k$-ary trie. This trie will be infinite in length, but we prune it by removing any paths which are traversed by only one of our $n$ words, to eliminate 'redundancy'.

**Attempt:** I tried relating things back to the size of the random trie, which I call $S$. Every non-root node in the trie is the child of some internal node, so $mI = S-1$
That is $E(I) = E\left(\frac S m\right) - \frac 1 m$
So if I can show that the expected size of a random trie is O(n) I'm golden. But unfortunately everything we've covered in class relates to expected depths and heights of a given trie, and I don't have any ideas moving forward. Could anyone offer advice on what might be useful here?

# Answer
If you don't have any degree-1 nodes in your trie (which is a tree) than you have more leaves than interior nodes. So in this case you have $I\le n $.

It depends a bit how you define the trie whether you can have many interior degree-1 nodes. If you study a *compressed trie* the all the path of degree-1 nodes are merges to an edge, so you are done. For an uncompressed trie, I am afraid, you can have many degree-1 nodes. Say you have one letter $a\_i$ that is very common and has a high probability of $1-\varepsilon$ and $\varepsilon\in \Omega(1/n^2)$. Then your trie contains many long degree-1 paths with high probability. In this case the you can have more than $O(n)$ interior nodes. Please do the computations by yourself (you might choose a smaller $\varepsilon$ if you like).
> 3 votes

---
Tags: data-structures, trees, probability-theory, average-case
---


# Question
Title: Using induction to prove transition states are the same
Suppose that you have a DFA $M=\left(S,\Sigma,s\_0,\delta,{s\_f}\right)$ with $s\_f\neq s\_0$.

Suppose further that, for all $a\in\Sigma$, $\delta\left(s\_0,a\right)=\delta\left(s\_f,a\right)$.

Show that for any *non-empty* word $w$ over $\Sigma$, we have $\delta^{\*}\left(s\_0,w\right)=\delta^{\*}\left(s\_f,w\right)$.

I know there is something I am overlooking, specifically with regards to the non-empty word. Here is my attempt at an answer via a proof by induction:

Let's use a word $w=ax$

$$\delta^{\*}\left(s\_f,ax\right)=\delta\left(\delta^{\*}\left(s\_f,a\right),x\right)$$

Since $\delta^{\*}\left(s\_0,w\right)=\delta^{\*}\left(s\_f,w\right)$.

We can also write this equation as $$\delta^{\*}\left(s\_f,ax\right)=\delta\left(\delta^{\*}\left(s\_f,a\right),x\right) = \delta\left(\delta^{\*}\left(s\_0,a\right),x\right)=\delta^{\*}\left(s\_0,ax\right)\\,.$$

This seems almost too obvious... I am new to this style of maths and would appreciate some guidance with regards to my proof style and if I'm ommitting something significant.

***New attempt thanks to @Patrick87's guidance:***

$$\delta^{\*}\left(s\_f,ax\right)=\delta^{\*}\left(\delta\left(s\_f,a\right),x\right) = \delta^{\*}\left(\delta\left(s\_0,a\right),x\right)=\delta^{\*}\left(s\_0,ax\right)\\,.$$

I think this makes sense but I can't help but feel something is missing.

# Answer
We use induction on the length of $w$. Let this length be denoted by $|w|$

**Base case: $|w|$ = 1**

Immediate by the assumption that $\forall a∈Σ. δ(s\_0,a)=δ(s\_f,a)$

**Induction hypothesis: $δ^\*(s\_0,w)=δ^\*(s\_f,w)$ for $|w| = k$ where $k \geq 1$**

**Inductive step:** Assuming the induction hypothesis, prove that it works for $k+1$:

Let $w$ be a word s.t $|w| = k+1$. Clearly $w$ can be seen as two strings $w = w^{-1} \circ v$ where $\circ$ is concatenation of strings.

As $|w^{-1}| = k$ we, by induction, get that $δ^\*(s\_0,w^{-1})=δ^\*(s\_f,w^{-1})$. As $x$ is a string of length $1$ we get by $\forall a∈Σ. δ(s\_0,a)=δ(s\_f,a)$ that $δ^\*(s\_0,w)=δ^\*(s\_f,w)$

The proof could be a bit more formal, but atleast the intuition should be clear.
> 1 votes

---
Tags: automata, finite-automata, proof-techniques, induction
---


# Question
Title: Is there a method for automatic runtime analysis of algorithms?
I am wondering, is there a method for automatic runtime analysis that works at least on a relevant subset of algorithms (algorithms that can be analyzed)?

I googled "Automatic algorithm analysis" which gave me this but it is too mathy. I just want a simple example in psuedocode that I can understand. Might be too specific, but I thought it was worth a shot.

# Answer
The COSTA tool does just this, although it fails in many cases, as you can imagine, due to computability problems. There are many papers about this; Cost Analysis of Java Bytecode by E. Albert, P. Arenas, S. Genaim, G. Puebla, D. Zanardini is a good starting point.

The approach taken is to infer a run-time recurrence from the Javabyte code, the convert this to a closed form. The tool also compute space usage bounds.
> 13 votes

# Answer
No algorithm can decide whether a given algorithm ever halts or not, so in particular no algorithm can tightly analyze the complexity of a given algorithm.
> 13 votes

# Answer
I know one approach to (semi-)automated average case analysis, namely MaLiJAn¹. It closely resembles the kind of analysis Knuth uses in TAoCP. The core idea is to

* model the program (flow) as Markov Chain,
* train its transition probabilities for some fixed input sizes $n$ by counting a set of program runs (which yields maximum likelihood estimators),
* extrapolate to probility functions *in $n$* and
* use computer algebra to derive the average cost (w.r.t. these functions).

Note that only additive cost measures (e.g. comparisons, "time") work and only the expected value is accurate (assuming perfect probability functions), higher moments can not be derived.

All steps but the extrapolation are rigorous \[2\] and the method has been demonstrated to reproduce well-known results with high precision -- given suitable random sample inputs, of course. While there is no proof or even approximation guarantee on the results (the extrapolation step is, so far, purely heuristic) the results obtained with the tool serve well to experiment with hard to analyse algorithms and formulate hypotheses \[3,4\].

---

1. Full disclosure: I'm was a member of this research group and had been involved in the development of the tool.
2. Maximum Likelihood Analysis of Algorithms and Data Structures by U. Laube and M. Nebel (2010) \[preprint\]
3. Engineering Java 7's Dual Pivot Quicksort Using MaLiJAn by S. Wild et al (2012) \[preprint\]
4. Maximum Likelihood Analysis of the Ford–Fulkerson Method on Special Graphs by U. Laube und M. Nebel (2015) \[preprint\]
> 10 votes

# Answer
Of course, as noted by Yuval Filmus, one should not expect a general solution to such problems. But as is usually the case, solutions can be found for interesting subsets of the general case.

I am in no way expert, or even significantly knowledgeable in this area, by I happen to know of some work of the kind. It concerns automatic average complexity analysis, and the work was done by Philippe Flajolet and his colleagues.

From what I understood when it was explained to me, the authors designed a small language (nothing Turing complete as you might expect, but significant enough) so that any algorithm written within the constraint of that language could have its average complexity analyzed automatically.The system was called at the time Lambda-Upsilon-Omega, i.e. $\lambda\acute\upsilon\omega$ (I unbind).

One paper I found on the web is a 1990 paper: *Automatic average-case analysis of algorithms* by Philippe Flajolet, Paul Zimmermann, and Bruno Salvy.

I would expect that later papers have extended this work, but I do not really know. The work was quite heavily cited, and searching the web for it should yield more recent work on the same topic.

Now, I am afraid that the work of Flajolet and his colleagues was very mathematical, and I would not expect much easy reading.
> 8 votes

---
Tags: algorithms, algorithm-analysis, reference-request, runtime-analysis
---


# Question
Title: What is a conventional format for presenting algorithms?
I'm writing a technical paper and the review committee wants my methodology to be represented in a conventional algorithm format.

I've been searching all over the web for the conventional structure of an algorithm with little luck. Can someone tell me the conventional format of an algorithm or any specification from IEEE for writing algorithms?

# Answer
There is no such thing as *the* "format" for algorithms. A general agreement¹ is to use *pseudocode*, i.e. code that abstracts from the particulars of specific programming languages, machines and/or libraries.

The most important thing is to be consistent. If you want to follow a specific style, I recommend you pick up some textbooks on algorithms and/or data structures and follow the style you like best.

Some kinds of pseudocode have specific package support in LaTeX, e.g. `clrscode`, `algorithms` or `pseudocode`. For help with these go to tex.SE.

---

1. As long as you publish about algorithms as *scientist*. Articles featuring concrete technology frequently use real code, for better or worse.
> 7 votes

# Answer
A quick google search will tell you what an algorithm is.

Now for "convential algorithm format" I think it would be helpful to look at how to write **pseudocode**.

From wikipedia: "Pseudocode is an informal high-level description of the operating principle of a computer program or other algorithm."

It is useful to express ideas and main concepts behind an algorithm without relying on implementation details and is used in almost any paper discussing implementation.

Even though people aim to write pseucode anyone with any programming background can read, there are some general guidelines. One example could be this
> 3 votes

---
Tags: algorithms, reference-request, notation, research
---


# Question
Title: 3 dimensionnal matching to partition transformation
We want to transform $3DM$ to $PARTITION$, I am reading Garey and Johnson book and I really don't understand how they do the transformation, I know how they create elements $a\_i$ from triples of set $M = W \times X \times Y$, but I don't know why they add two other elements $b\_1$ and $b\_2$ with definition $$ s(b\_1) = 2 (\sum\_{i=1}^{k} s(a\_i)) - B \\ s(b\_2) = (\sum\_{i=1}^{k} s(a\_i)) + B $$

with $B$ being: $$ B = \sum\_{j = 0}^{3q - 1} 2 ^ { pj} $$ and $p = \[log\_2(k)\] + 1$ and $q$ is the number of elements in $X$ (Y, W also have the same number of elements) and also $k$ is the number of triples in $M$.

It would be very nice if anyone could clarify this transformation.

# Answer
What they actually do is a composition of two reductions (and some optimization). The first is from 3DM to SUBSET-SUM, and the second is from SUBSET-SUM to PARTITION. For the first part, I have it written down here, and the second reduction is quite well known, e.g. here.

Note that there is a small caveat in the first reduction, where we assume that the numbers are encoded in base $|X|+1$, while SUBSET-SUM requires the numbers to be in binary. The reduction you mention does the conversion explicitly, which accounts for the strange $p$ you encountered (which is just the base-conversion constant).
> 3 votes

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


# Question
Title: Equivalence of Recursively Enumerability (RE) definitions
Let A be a subset of N n

Definition1 of RE

DEF1\_RE = A is RE iff there is a TM M st M(x) = 1 iff x belongs to A, 0/undefined otherwise

Definition2 of RE

DEF2\_RE = A is RE iff there is a recursive/Turing-decidable relation R subset of Nn+1 st

```
x belongs to A <=> there exists a y R(x,y)

```

So I have proved that if A belongs to DEF2\_RE, then A belongs to DEF1\_RE

but I can't prove the other direction. Can someone please help me prove the other direction?

# Answer
> 1 votes
"For the other direction, let R(x,y) hold iff y codes a halting computation with output 1 of M on input x." (A friend's answer)

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


# Question
Title: Complexity Classes (P, NP) vs Language Hierarchies (REC, RE)
## NOTE: The statement of this question has a LOT of misconceptions.

---

Is there any relation between the Complexity Classes *(like P or NP)* and Language hierarchies *(like REC or RE)* ?

> **Form what I understand**: (*easy* things are the things that can be done in polynomial time span, as opposed to *tough* things. *Tough* things require exponential time span or even infinite time to finish).

## P

These are the set of problems which can be *easily solved*. If multiple answers exist, then all those answers can be easily found.

## NP

These are the set of problems, for which a tentative answer can be *easily verified*. Some of these problems can even be easily solved. Others are tough to solve but either way, given a tentative solution, that can be easily verified.

For those which can be easily solved, fall under the `P` class. Hence `P <= NP`. The equal sign is something scientists are still working on.

These problems *can* be solved easily on a non-deterministic Turing Machine. Unfortunately, such a machine does not exist. The real deterministic Turin Machines (our laptops) cant guarantee how much time it would take to solve such a problem. it might even hang.

## REC

These are the set of strings (a language) which belong to one family of strings. The family is called The Grammar. Given a Grammar and a string, if we can easily tell whether the string is member of the family, then the family is `REC` family.

## RE

These are an even broader set of strings, which belong to an even broader family. Some of the members of this family are `REC`, but some are not. That is, given a Grammar and a string, we may or may not easily tell whether the string is a member or not. If we are able, then the family is `REC`, if we are not, then it is `RE` family.

Membership in `RE` family cannot be easily verified **but**, given such a Grammar, all the members can be easily listed-out. Hence the name- *recursively enumerable*.

> **Now, Question:** both (P/NP) and (REC/RE) seem similar. I know they are not the same. One is problem, another is language. But is there any connection between the two?

Also, From what I understand, is there anything **wrong** in my understanding? I mean certainly there must be things missing. But for the part which is not-missing, is there anything wrong?

# Answer
All the classes you mention *are* classes of languages, formally, even if P and NP are often discussed in different (more sloppy?) terms. Note that terminology revolving around *decision problems* is equivalent to formal languages; the decision is always whether a word is in the given language, i.e. the problem is to solve the word problem.

What you need to do is go back to the *formal* definitions. Summarising:

* $\mathrm{RE}$ contains languages which are *accepted* by *any* TM.
* $\mathrm{REC}$ contains all languages which are *decided* by *any* TM.
* $\mathrm{NP}$ contains all languages which are *accepted* by any *polynomial-time* TM.
* $\mathrm{P}$ contains all languages which are *decided* by any *polynomial-time* and *deterministic* TM.

It's already quite clear from the definitions that we have

$\qquad\displaystyle \mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{REC} \subseteq \mathrm{RE}$.

So, essentially, computability and complexity theory deal with the same kind of questions: which kinds of problems can I solve with which type of machine?

In fact, the famous Complexity Zoo diagram (via the companion the wiki) displays "computability", "complexity" and "Chomsky" classes in a single inclusion hierarchy -- because they all use the same formalism.

I recommend that you check out some of our reference questions on computability and complexity theory; you'll see the similarities.
> 18 votes

---
Tags: complexity-theory, formal-languages, complexity-classes
---


title: find the optimal combination

text:
# Question
Title: find the optimal combination
Suppose I have these values with weights -- $$ x\_1 = 2\\ x\_2 = 4\\ x\_3 = 5\\ $$ There is no negative or $0$ value. I need to find $2$ element subset with maximum value computed from a function $f(\cdot,\cdot)$, lets say the function values are like this -- $$ f(x\_1,x\_2) = 10\\ f(x\_2,x\_3) = 12\\ f(x\_3,x\_1) = 14\\ $$ What I am doing is running $O(n^2)$ loop (trying all combinations) and keeping the best pair, i.e. $\\{x\_3, x\_1\\}$

Is there any faster way to do this ? because my dataset can get arbitrarily large (10,000) and instead of 2 elements, I may need to compute the same with k elements ($k \< \text{number of data points}$)

**Sorting:** Unfortunately, sorting is not possible, actually the weights that I am getting is from a function, the function takes $k$ data point (any combination) at a time and returns a value, i.e. $w = f(x\_i, x\_j, \ldots, x\_k)$ so I need to pick the $k$ subset with the best (or you can say highest) $w$ value.

please help.

# Answer
If I understand you correctly, the order of the inputs to function F does not influence the output W, so order is not important. I'm deducing this from the three possible subsets in your example at the top where K = 2 and N = 3.

For a set of N elements, and a function F taking K inputs where order of inputs does not matter, the complexity to find all possible W outputs I don't think is O(N \** K). I'm using \** as to the power of.

I would think it is the same problem as finding the number of ways to choose K elements from a set of N elements disregarding order. I think one could also say the number of partitions of K elements over a set of N elements.

The number of ways to choose K elements from a set of N elements is: `N // since you are choosing from a set of N elements
* (N - 1) // since next you are choosing from a set of N - 1 elements
* (N - 2) // same reasoning as above
...
* (N - (K - 1)) // just before you have chosen K elements
* (N - K) // you have chosen the K-th element` Sort of like factorial, but from N - K + 1 up to N, which is the same as N! / (N - K)!.

Lastly, we have to disregard order of the elements, and there is K! ways to order K elemetns, which brings us to: `N! / (N - K)! / K!` As each W is calculated you can simply keep the highest yealding inputs, and when you have tried all inputs you will be guaranteed to have found the right set of inputs.

So, supposing the above is correct (it worked for small mental verification of K = 2, N = 4 and K = 3, N = 4 and K = 3, N = 5) then I suppose the complexity analysis is O(N! / (N - K)! / K!) and not O(N \** K).

If you know F then you could optimise it, to get a linear improvement, or maybe find inputs that could be omitted to get an even bigger speedup.

Without knowing F you are stuck with trying everything.

One other thing you could do is employ memoization to avoid having to evaluate F for similar inputs.
> 1 votes

# Answer
If I understand correctly you can just sort the elements in time $O(n \log n)$ using say, mergesort, and pick the $k$ largest elements.
> 0 votes

---
Tags: algorithms, optimization, sets
---


# Question
Title: $T(n) = \sqrt{n}\,T(\sqrt{n}) + n\log n$
I tried to solve the recurrence $T(n) = \sqrt{n}\\,T(\sqrt{n}) + n\log n$ with the master theorem but I can't get it to work.

How many arrays exist in each step in the recursion tree?

Or can I solve this problem some other way?

Thanks.

# Answer
> 2 votes
At level 0, the top level, you'll have $1$ array, of size $n$.

At level 1, you'll have $n^{1/2}$ arrays for each array at level $0$, for a total of $n^{1/2}$ arrays, each of size $n^{1/2}$.

At level 2 you'll have $n^{1/4}$ arrays for each array at level 1 for a total of $n^{1/2}n^{1/4}$ arrays, each of size $n^{1/4}$.

At level 3 you'll have $n^{1/8}$ arrays for each array at level 2 for a total of $n^{1/2}n^{1/4}n^{1/8}$ arrays, each of size $n^{1/8}$.

In tabular form we have for the first few levels, $$\begin{array}{ccccc} \mathbf{level} & \mathbf{arrays} & \mathbf{size} & \mathbf{contribution/array} & \mathbf{total\ contribution}\\ 0 & 1 & n & n\lg n & (1)(n\lg n)=n\lg n\\ 1 & n^{1/2} & n^{1/2} & n^{1/2}\lg n^{1/2} & (n^{1/2})(n^{1/2}\lg n^{1/2})=n\lg n^{1/2}\\ 2 & n^{1/2}n^{1/4} & n^{1/4} & n^{1/4}\lg n^{1/4} & (n^{1/2}n^{1/4})(n^{1/4}\lg n^{1/4})=n\lg n^{1/4}\\ 3 & n^{1/2}n^{1/4}n^{1/8} & n^{1/8} & n^{1/8}\lg n^{1/8} & (n^{1/2}n^{1/4}n^{1/8})(n^{1/8}\lg n^{1/8})=n\lg n^{1/8} \end{array}$$ So the total runtime, $T(n)$, will be the sum of the contributions at each level, namely $$ n\lg n + n\lg n^{1/2} + n\lg n^{1/4} + n\lg n^{1/8} +\dotsb $$ Use a property of the log function and you'll see that this simplifies to a simple expression.

---
Tags: data-structures, time-complexity, recursion
---


# Question
Title: Reducing context-free languages with polynomial-time reductions
So, let's say we have two languages $L$ (which is any context-free language) and $M$ which is the basic CFL $\\{0^n1^n: n\geq 0\\}$.

Can $L \le\_p M$ ? Why or why not? How do polynomial time reductions even work with CFLs in general?

# Answer
Since context-free languages are in P and $M$ is non-trivial, there is an easy polynomial time reduction from every context-free language $L$ to $M$. The reduction decides whether the input is in $L$ or not, and according to that outputs either $\epsilon$ or $0$, say.
> 2 votes

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


# Question
Title: Amortized analysis of virtual, dynamic array using potential function
You often want to implement an array $A$ where the length fluctuates over time. If at some point $A$ has length $n$, then you would like to use space $O(n)$. Consider the following: At all moments, a virtual array $A\[0...n-1\]$ is simulated by an actual array $B\[0...m-1\]$ where $m\ge n\ge 1$. Initially, $m=n=1$.

Extend: If $n\<m$: increment $n$ and set $B\[n-1\] = NULL$. Else: set $m=2m$, allocated a new array $B'$ with length $m$, copy $B\[0...n-1\]$ to $B'\[0...n-1\]$, deallocate $B$, rename $B' $to $B$, increment $n$, and set $B\[n-1\] = NULL$.

Show, using a potential function, that the amortized cost of $N$ extend operations is $O(N)$.

The potential function I was thinking of using was $r(s)$ defined as the number of elements in the virtual array $A$ at time $s$. So $r(0) = 0 \le r(s)$ for $s \> 0$.

However, when I calculate the potential of the extend operation, I get $r(s+1)-r(s) = n+1-n = 1$ (i.e. the number of elements in the array after the operation minus the number of elements in the array before the operation). Yet, the actual amount of work seems to be much higher in the "else" case $\Rightarrow 2m$ (to allocate new array $B'$) $+n$ (to copy from $B$ to $B'$) $+m$ (to deallocate $B$) $+3$ (to rename, increment, and set to $NULL$).

So the amortized cost (equal to actual cost + potential cost) is clearly not $O(1)$, and so the cost of $N$ extend operations will not be $O(N)$. What am I doing wrong here?

# Answer
> 2 votes
*What am I doing wrong here?* You're using the wrong potential function. Keep looking. If you want to know the solution, the Wikipedia page on the potential method contains the answer.

---
Tags: data-structures, runtime-analysis, arrays, amortized-analysis
---


# Question
Title: Finding the values of x and y using base 8
In finding the values of x and y, if `(x567) + (2yx5) = (71yx)` ( all in base 8) I proceeded as under.

I assumed `x=abc` and `y=def` and followed.

```
  (abc+010 def+101 110+abc 111+101)=(111 001 def abc) //adding ()+()=() and equating LHS=RHS.
  abc=111-010=101 which is 5 in base 8 and then def=001-101 which is -4
  so x=5 and y=-4

```

Now the Question is that the answer mentioned in my book is `x=4` and `y=3`.

# Answer
> 0 votes
Aaron's answer points out the problem you had. There's a general method, too. This is a simple example of a cryptarithm, where some or all the digits in an arithmetic expression are replaced by unknown variables. For addition problems, you can write each digit sum as one or more equations (since you won't necessarily know the carry values) and solve the set of equations.

For your problem, a clever solver might first check whether there's a possible pattern: could it be that the terms being added had a particularly nice forms, like perhaps

```
 4567
+2345
-----

```

Well, well, well. In octal, $4567+2345=7134$ and with $x=4, y=3$ we see that we've found a solution.

Of course, it won't always be that easy, but it's still not terrible to find the solution in this case. Given

```
 x567
+2yx5
-----
 71yx

```

we could look at the 1s-place sum: $7 + 5 = x$. Aha! in octal $7+5=4$ with a 1 carry, so $x=4$. We're halfway there, with a sum that's now

```
 4567
+2y45
-----
 71y4

```

Now look at the 8's column in the sum. Recalling that the 1's column gave us a carry of 1 we have $1+6+4=y$ so in octal $y=3$. We're done, modulo checking that the 64s column sum is correct, which it is.

In a true cryptarithm, often all of the numbers are unspecified, like this:

```
 TWO
+TW0
----
FOUR

```

(which does have solution(s) in octal).

# Answer
> 0 votes
I think the issue with your method is that your subtracts are neglecting to account for the carry values that happen during the addition. If we instead go right to left and account for carries, we get:

```
(abc+010 def+101 110+abc 111+101)=(111 001 def abc)
                         100
                 (110 + 100 + 1) // carrying the 1 here from the addition in the previous place
                 011
         (011 + 101 + 1) // carrying a 1 from the previous place again
         001
(100 + 010 + 1) // again, carrying a 1
111

```

Thus, we have that:

```
111 001 011 100 = (111 001 def abc)

```

Meaning that `100_2 = abc_2` and `011_2 = def_2`, implying `x=4` and `y=3`.

---
Tags: number-theory, base-conversion
---


# Question
Title: If the Halting Problem was solvable, and we solved it, what would be its implications?
Perhaps a way to better understand the Halting Problem's importance is to know what would happen or what could be possible if this was solved.

What would be the Halting Problem's implications in today's technology, mathematics and its practical applications, if it was somehow solved?

# Answer
Maybe I should make a more serious answer. First off: the unsolvability of the halting problem by "conventional" computing methods is a logical theorem. It is very simple to prove, and can be proven in almost any reasonable logical framework (that can express the problem).

There are however two questions we can reasonably ask:

1. What are the mathematical consequences of having a halting oracle? A halting oracle can be imagined as a genie (instantly) giving us the answer to any halting problem we ask of it. This is a rather well studied subject in computability theory and the "world" in which you have access to such a genie is called the first turing degree.

An interesting observation is that even given such an oracle, we can ask computational problems for which we cannot compute the answer, such as "does the turing machine $M$ with access to the halting oracle halt on all inputs"? The proof is **almost identical** to the original proof of undecidability of the halting problem!
2. What would happen if we could solve all halting problems that come up "in practice"? This isn't really a mathematical question, since you would need to define *in practice* but it's a really interesting *scientific question*. The whole field of termination analysis tries to find such algorithms. It works surprisingly well: if you write a reasonable program to compute some quantity, odds are that there is a tool in this list that can handle it.

It's not too hard to find examples that break these tools though: even a program as simple as the $3n+1$ algorithm would choke them, since there it is not known whether it halts on all inputs. A lot of similar open problems in number theory (the twin primes conjecture, the existence of odd perfect numbers) can be expressed as a halting problem, which suggests that there are many such problems that can't be handled by any "reasonable" automated termination tool.
> 8 votes

---
Tags: computability, halting-problem, philosophy
---


title: Can oracle arguments separate P and NP?

text:
# Question
Title: Can oracle arguments separate P and NP?
I know that the general consensus among CS researchers is that non-relativizing techniques will be needed to separate **P** and **NP**. However, if there is an oracle language $A \in \textbf{P}$ such that ${\textbf{P}}^A \neq {\textbf{NP}}^A$ would that necessarily imply ${\textbf{P}} \neq {\textbf{NP}}$? I read somewhere that it would be enough, but I'm not sure.

On the one hand, since any NDTM can be supplemented with a polynomial-time deterministic subroutine for $A$, having oracle access to it should not give an NDTM any more "power".

On the other hand though, aren't oracle TM's able to make queries about strings of any length in the oracle language? In that case, we could not jump to the conclusion that **P** does not equal **NP**, because according to my understanding, polynomial-time Turing machines (whether deterministic or non-deterministic) cannot be "influenced" by strings of length exponential in the length of the input string.

# Answer
For an oracle $A\in {\sf P}$ you have ${\sf P}^A={\sf P}$ (since you can encode all requests to the oracle as a submodule of the TM). By the same argument you als have that ${\sf NP}^A={\sf NP}$.

Thus in this case ${\sf NP}^A\neq{\sf P}^A$ would imply ${\sf NP}\neq{\sf P}$.

You basically said this already in your question. Note that we cannot query "exponentially long" strings to the oracle, since we need to write the string on the oracle tape first, and this would clearly take too long. Maybe this caused your confusion?
> 7 votes

---
Tags: complexity-theory, p-vs-np, oracle-machines
---


# Question
Title: Is Dijkstras algorithm used in modern route-finding systems?
Is Dijkstra's algorithm used in modern route-finding systems such as Google maps or the satnav in your car? If not, then what is?

# Answer
> 5 votes
Yes, Dijkstra's algorithm is used in modern maps systems. A lengthy and informative discussion can be found in the following question from StackOverflow: What algorithms compute directions from point A to point B on a map?

# Answer
> 8 votes
Google Maps in 2009 used Contraction Hierarchies \- see this tech talk.

Since then, some mind-blowing methods have been discovered, capable of doing cross-country routing in fractional milliseconds - the so-called "two-hop labeling distance oracles". See here, or search for "Hub labeling" or "Shortest paths for the masses". I think I heard Bing uses this one. It also has applications like the ability to find the nearest point of interest (e.g. nearest gas station) with a complexity independent on the number of gas stations.

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


# Question
Title: algorithm time analysis "input size" vs "input elements"
I'm still a bit confused with the terms "input length" and "input size" when used to analyze and describe the asymptomatic upper bound for an algorithm

Seems that input length for the algorithm depends a lot of the kind of data and the algorithm you are talking about.

Some authors refer to input length to the size of characters that are required to represent the input, so "abcde" if use as input set in an algorithm will have an "input length" of 6 characters.

If instead of characters we have number (integers for instance) then sometimes the binary representation is use instead of characters so the "input length" is calculated as $N\*log(L)$ (Being L the Max number in the input set).

There are other problems that even if the input set are numbers, they describe the "input length" as "decision variables", so for a input set of length N with numbers in the range $0-2^{32}$ the input length is just N (subset sum for instance), or even more complicate the number of binary place values that it takes to state the problem (what I believe is just the same as $N\*log(L)$)

So:

* it depends on the algorithm?
* What means and when to use each input length "version"
* Is there are some rule I can use to decide which one to use?

# Answer
> 10 votes
In the most formal sense, the size of the input is measured in reference to a Turing Machine implementation of the algorithm, and it is the number of alphabet symbols needed to encode the input.

This is of course rather abstract, and is very difficult to work with in practice, or at least very annoying - we would need to consider how we're going specify delimeters etc. etc. What happens normally in practice then is that we look for a *proxy* measurement of the size of the input - something more convenient and accessible, but that does not cause any mathematical problems in our analysis.

Using your "abcde" example, it would normally be the case that the alphabet we use for the input is small, so even using the proxy measurement of $5$ characters, we known that even on a Turing Machine, we can, if we bothered, specify an input encoding that would convert "abcde" to some encoded form that had length at most $5\times c$ for some *constant* $c$. This expansion by a constant would typically make no difference in our asymptotic analysis, as we routinely discard constant factors.

In a different case, we often measure the size of an input graph by the number of vertices $n$. Clearly if we want to specify arbitrarily large graphs, the size of the encoded input is not simply $n$ - what happened to the edges, for example? What we do know is that we can use a reasonable encoding scheme that represents the graph in $N = c\cdot n^{2}\log n$ bits. This is a bit more of an expansion than constant, but in a lot of interesting cases, we're only dealing with things at a granularity of polynomials, and polynomials compose nicely in a lot of ways - in particular, as an example, if we determine that our running time is $O(p(n))$ where $p$ is a polynomial, then we know that there is some polynomial $p'$ such that $O(p(n)) = O(p'(N))$, so when we move back to the formal measure of the input, we're still in polynomial time.

A place where this might fall down is when you are working with numbers. As a number with magnitude $m$ can be encoded in $n = O(\log m)$ bits, if our running time were $O(m)$, this would be $O(2^{n})$ - exponential in the actual input size - which would make the magnitude $m$ a bad choice for a proxy for the input size if we wanted to talk about membership in $\mathcal{P}$ for example (when you come to Strongly-$\mathcal{NP}$-complete and Weakly-$\mathcal{NP}$-complete, remember this). On the other hand, if all we were interested in was decidability, then it would be a good enough proxy measure.

So while there's no stated rule for picking a proxy measure for the input size, the requirement is that the expansion or contraction of the proxy size compared to the input size should be compatible with what you're trying to prove. As a rule of thumb, constant factor changes almost never matter, small polynomial factors are normally fine and work for most of the basic theory that you see, large polynomial factors might still work in for theory, but can be a nasty surprise in practice, and exponential amounts of change are normally way too extreme.

# Answer
> 8 votes
It depends on your model of computation and also on the unfortunately sometimes on the algorithm itself.

* If your model of computation is a **Turing machine**, then the size of the input is the number of cells occupied by the input. So if your input is $ababcd$ then the input has length 6.
* If your model is the **RAM** then the size of the input is the number of registers/memory cells where the input initially stays. This might be misused since you could technically write the whole input in one register. However then computations are more costly if you use the logarithmic costs model.
* If your model of computation is a **word-RAM**, then you also count the memory cells, but they can only store $w$-bit integers, for $w$ being a parameter of your model.

However many algorithms are not measured with respect to the "actual" input size. Then you have to carefully look, what the statement of the analysis refers to.

* Often you have a implicit assumption with the problem. When saying that it takes $O(n\log n)$ time to sort $n$ items then you assume that two items can be compared in $O(1)$ time. Of course if you sort, say $n$ very long strings, then this might not be true.
* For conventional reasons you measure sometimes with respect to a different parameter of the input. For example matrix multiplication is typically analyzed for multiplying two $n\times n$ matrices.

**Some rule:** Use whatever you want, but make it clear in the statement of the result. So just say what $n$ exactly is, if there is a chance of misunderstanding.

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


title: Vertex degree in De Bruijn graphs

text:
# Question
Title: Vertex degree in De Bruijn graphs
How can I find the degree of a vertex in a De Bruijn graph? Also, given a vertex, is there an easy way to find which other vertices it is connected to?

# Answer
Both questions can be answered by looking at the rules for constructing a De Bruijn graph:

1. We have a set of symbols $S$, and a number $n$.
2. There is a vertex for each element of $S^{n}$, labelled as such - i.e. one for each sequence of symbols from $S$ of length $n$, the same symbol can appear multiple times in the sequence.
3. If the label of vertex $v$ can be obtained from the label of vertex $u$ by removing the first symbol and appending a new symbol to the end, there is a directed edge from $u$ to $v$ (i.e. $(u,v)$ is an arc).

It should be clear that both the out-degree and the in-degree are $|S|$ - one incoming and one outgoing edge for each symbol in $S$. Remeber that every sequence of symbols appears somewhere, so no matter how we apply rule 3, the resulting sequence is somewhere in the graph. Similarly the reverse of rule 3 works for every possible symbol.

Rule three also tells us the neighbours, just perform rule 3 for with every symbol to get the out-neighbourhood, and reverse rule 3 with every symbol to get the in-neighbourhood.

Some examples, plus these and additional properties can also be found on the wikipedia page.
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: Can a CS grad student work on quantum field theory and string theory problems?
The mathematical aspect of particle physics theory are interesting and there seems to be a lot more connections being made to computation and information (like with complexity theory having some impact of physics and the whole quantum computation thing). Does it make sense (or is even possible) to work on some of these connections as a grad student in a theoretical computer science department or should I be looking at mathematical physics programs instead?

My main concern is with finding advisors and departments that are game for something like this (given that this makes any sense in the first place).

# Answer
There are plenty of computer scientists working on quantum computation and quantum information so, yes, there should be plenty of opportunities to work on that sort of thing as a CS grad student.

I'm not aware of any computer scientists working on string theory but it's far from my area of expertise so it's possible it happens without my knowing about it. However, I've been to plenty of theoretical CS conferences where there were a couple of talks about quantum things but I don't remember any talks at all about string theory. And, of course, if you try to Google for something like "string theory computer science", Google thinks you mean strings of text.
> 0 votes

---
Tags: complexity-theory, quantum-computing
---


# Question
Title: Example of graph with exponential many s-t minpaths and min cuts
I am trying to find a graph in which both s-t minpaths and min cuts are exponential.

Individually I found examples in which s-t minpaths and s-t min cuts are exponential. Can some one provide me an example of graph which has both min paths and min cuts in exponential size.

# Answer
I can offer an example for super-exponentially many shortest paths and super-polynomially many minimum cuts.

An example for many shortest s-t-paths you probably came up with is the layer graph, similar to the one here. Turns out we can use the same idea here -- all we have to do is use many layers so that there are many minimum cuts, and fiddle with the weights so that there have to be enough "inner" nodes in either partition.

**Idea:** Use a complete layer graph with $\sqrt{n}$ layers and $\sqrt{n}$ nodes in each layer. Add $s$ and $t$ and wire with the first resp. last layer; make the weights on these edges so large that the first layer has to be in the partition of $s$ (and the last in that of $t$) for every minimum cut.

The graphs look like this (unit weights on all unlabelled edges):

<sup>\[source\]</sup>

Now we can count.

* The graph has $n + 2$ nodes and $(n+2)\sqrt{n} - n \in \Theta(n^{\frac{3}{2}})$ edges.
* Every shortest s-t-path picks one node in every layer; hence, we get $\sqrt{n}^{\sqrt{n}}$ such paths.
* No edge $(s,\\\_)$ or $(\\\_,t)$ is ever part of a minimum cut (each such edge has more weight than all others together). Convince yourself that all cuts constructed by fixing a column (but the first and the last), putting every node either left or right and using this as the "cut line", are minimal with weight $n$. We obtain $(\sqrt{n}-2) \cdot 2^{\sqrt{n}}$ many such cuts.

At least with layer graphs, I think the two quantities can not be exponential at the same time; one needs non-constant depth, the other linear width. I'm not sure if a similar argument carries over to general graphs.
> 13 votes

# Answer
Take any graph $G$ on $n$ vertices which has $2^{\Omega(n)}$ minimal $s$-$t$ paths. Add to $G$ an independent set of size $n$. Now it has at least $2^n$ minimum cuts.
> 7 votes

---
Tags: graphs, combinatorics, shortest-path
---


title: Context-free grammars and priority

text:
# Question
Title: Context-free grammars and priority
This grammar is supposed to give priority to multiplication:

* E -\> E + T | T.
* T -\> T * F | F.
* F -\> x.

A derivation for "x + x * x" would be (unless I'm wrong):

E =\> E + T =\> T + T =\> F + T =\> x + T =\> x + T * F =\> x + F * F =\> x + x * F =\> x + x * x.

So how is multiplication given priority over addition? It appears that the addition is produced first.

# Answer
> 6 votes
You are correct that additions operator is produced first when you derive. But when you parse, you do the opposite (reduction), and the multiplications are recognized first, wich is precisely what you want.

THis need a bit of discussion, when you compare top-down and bottom up parsing, but basically the bottom of the tree must be know correct before the top can be.

More to the point, this is a consequence of the fact that the parse tree produced with such a grammar will be structured to conform the operator operand structure defined by priorities, up to idosyncrasies of a CF grammar definition, which are ironed out in an abstract syntax tree (AST). In other words, this gives the parse tree a shape that is close to the shape desired for the AST (Thanks to Raphael for suggesting comparison with the AST).

This is why such a grammatical definition is simpler to use to generate the AST. More importantly, it was much more convenient in older compilers and interpreters that did not use AST, as the parse tree reflected the priority structure.

For example, the parse tree for `x + x * x` is

```
   E
 / | \
E  +   T
|     /|\
T    T * F
|    |   |
F    F   x
|    |
x    x

```

And the AST for `x + x * x` is

```
   +
 /   \
x     *
     / \
    x   x

```

It is derivable from the parse tree by moving all operators up one edge on the preceding node, and then ignoring all non-terminals, making each linear downward path a single edge. Essentially the same shape.

This AST is the expression tree defined by the priorities, from which the meaning of the expression can be derived (by homomorphism), from which it can be evaluated or compiled.

# Answer
> -3 votes
I think this is the case of ambiguous grammar.In the rules' list addition is definitely above multiplication and that needs to be rectified,multiplication should go above addition.

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


# Question
Title: Can every context free language written as a intersection of another context free language and a regular language?
I'm preparing an Formal language exam, One question from previous year's final is:

Prove or disprove:If L is a context free language, then there exists a language P that is generated by a pure context-free grammar and a regular language R so that $L = P \cap R$.

My solution to this question is quite simple. Assume context-free language P is equal to context free language L, and let regular language R to be $\Sigma^\*$, where $\Sigma$ is the alphabet set. $\Sigma^\*$ is definitely a regular language. So the answer to this question is yes.

However, I do came up with a more difficult problem. What if I add a limitation $P \neq L?$ Will this statement still hold? I current have no idea about this.

# Answer
The question in the title of your contribution "Can every context free language written as a intersection of another context free language and a regular language?" is the one you answer above, by taking $P=L$ and $R=\Sigma^\*$.

However that is *not* the question you quote from your test: "If $L$ is a context free language, then there exists a language $P$ that is generated by a pure context-free grammar and a regular language $R$ so that $L=P\cap R$." This additionally requires $P$ to be *pure* context-free, that is, generated by a grammar that has no dictinction between terminals and nonterminals.

Let $G$ be a context-free grammar with alphabet $\Sigma$ (terminals and nonterminals) and terminal alphabet $\Delta$. As an ordinary context-free grammar the language of $G$ equals $L(G) = \\{ w\in \Delta^\* \mid S\Rightarrow^\* w\\}$. Interpreted as pure grammar it cannot "see" terminals and the language is $P(G) = \\{ w\in \Sigma^\* \mid S\Rightarrow^\* w\\}$. Or, $L(G) = P(G) \cap \Delta^\*$, which gives the answer to your final exam. The elements in $P(G)$ are usually called sentential forms.
> 5 votes

# Answer
If you are allowed to change the alphabet, then the answer is trivially yes. For example, let $\Sigma$ be the original alphabet, and let $\alpha$ be a new symbol. Then $P = L \cup \\{\alpha\\}$ is context-free, and $L = P \cap \Sigma^\*$.

If you are not allowed to change the alphabet, then the answer is trivially no. For if you take $L = \Sigma^\*$, you must take $P = \Sigma^\*$.

What if you are not allowed to change the alphabet and $L \neq \Sigma^\*$? Again the answer is trivially yes. Choose some word $w \notin L$. Then $P = L \cup \\{w\\}$ is context-free and $R = \overline{\\{w\\}}$ is regular, and $L = P \cap R$.
> 3 votes

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


# Question
Title: Is Myhill-Nerode equivalence class of a language which contains all palindrome pairwise distinct?
In my formal language class, we define a language called PAL, which is on a alphabet set $\Sigma = \\{0,1\\}$. $PAL = \\{w \in \\{0,1\\}^\* : w = w^R\\}$. We have proved that every string in this language will be pairwise inequivalent, i.e. every string is in its own Myhill-Nerode equivalence class.

However, what if we extend this definition to an alphabet $\Sigma$ that contains more than two characters? Can I still claim any 2 distinct strings in $\Sigma^\*$ are still pairwise inequivalent?

# Answer
Your proof goes also through with a larger alphabet. Let $x,y\in \Sigma^\*$, with $x\neq y$. We use as $z$ the word $10^{|x|+|y|+2}1x^{rev}$. Clearly, $xz$ is a palindrome and therefore the word is in the language. The word $yz$ however is not a palindrome. Note that the middle of $yz$ there has to be a $0$ coming from $z$, hence for being a palindrome the middle of $yz$ has to be centered between the two $1$s of $z$. As a consequence, $yz$ is a palindrome only if $x=y$. Thus $yz$ is not in the language.

For the proof you only need that $|\Sigma|\ge 2$. I would say having more letters makes it even easier, since you have more possibilities to choose the *split word* $z$.
> 2 votes

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


title: FM-index - print all patterns

text:
# Question
Title: FM-index - print all patterns
How is it possible to print all patterns of length $k$ contained in a string, using the FM-index and Burrows-Wheeler transform?

PROBLEM DETAIL:
The input I have is:

* the text encoded with the Burrows-Wheeler Transform
* the data structure of the FM-Index.

In particularly for the second element listed, I have:

* $C(c)$ is a table that, for each character $c$ in the alphabet, contains the number of occurrences of lexically smaller characters in the text
* $Occ(c, k)$ is the number of occurrences of character $c$ in the prefix of the Burrows-Wheeler transform $1..k$

The only strategy that I've found at the moment is to reconstruct the text from the Burrows-Wheeler transform and, during that operation, for every char print the pattern that starts from it. In pseudocode,

```
---------------------------------------------
DATA
---------------------------------------------

bwt[n]  => burrow wheeler transform of the text
C, Occ => FM-index data structure
K => lenght of the patterns to be extracted (so extract all patterns of length k from text T)

---------------------------------------------
Algorithm
---------------------------------------------

n = |bwt|; //text length
T[0,n]; //array used to save the original text
T[--n] = bwt[0]; //first char of the original text

currentIndex = 0;

for i = 0 to |btw(T)| - 1 do
    //get original
    lastFirst = c(bwt[currentIndex]) + Occ(bwt[currentIndex], currentIndex);
    T[--n] = bwt[lastFirst];
    currentIndex = lastFirst;

    //print pattern only if we have reconstructed at least k char
    if((|btw(T)| - n) >= k) from original text
        print T[n, n+k]; //print last k char reconstructed
    endif;
endfor;

```

Is there a better technique or strategy to solve the problem? Is there a strategy that doesn't need to reconstruct the original text?

# Answer
If I understand correctly, you want to print every substring of length $k$ from the original text. To do this you will need to invert the Burrows-Wheeler transform completely at some point, which is indeed what you do in your pseudocode. One improvement for your method would be to just store the $k$ latest characters instead of storing the whole string.

Your method is already as good as it gets, as it is equivalent to doing one pass over the string and directly printing the substrings, which is the minimum you have to do in any case.

--

Edit: so we want to print each substring only once. Now the problem becomes more interesting. An easy solution is to store the substrings in a hash map, for example, and thus avoid printing duplicates. If you can afford storing the original string and the inverse suffix array, then there is a sophisticated solution available which is good if $k$ is small.

A basic operation on the FM index is a left extension of a string. If we know the range of suffixes in the suffix array that start with the string $\alpha$, we can compute in constant time the range of $w\alpha$ for any character $w$. Here's how. Let $(i,j)$ be the range of the string $\alpha$. The range of $w \alpha$ is:

$$(C\[w\] + occ(w, i - 1) + 1,\\;\\; C\[w\] + occ(w,j)) \\;.$$

We can start with the range of an empty string, which is $(1, n)$, and do a depth-first search of left-extensions down to a depth of $k$. At depth $k$ we will print the substring corresponding to the current range. For this we need to have the original string and the inverse suffix array $ISA$, which is defined by $ISA\[SA\[i\]\] = i$, where $SA$ is the suffix array. The substring corresponding to the range $(i,j)$ is the first $k$ characters of the suffix $ISA\[i\]$.

This method is very efficient in practice if $k$ is small, as it often is in bioinformatics applications. For a more thorough explanation on the backwards search I recommend e.g. this blog post: http://alexbowe.com/fm-index/
> 2 votes

---
Tags: algorithms, strings, pattern-recognition
---


# Question
Title: How to construct a Turing machine for a language
I have proved that language $L$ is not regular and think that it is recognizable by a Turing machine. I want to prove it by constructing a Turing machine for it.

$L=\\{0^n|n \in A\\}$ where $A$ is set of all numbers that do not contain 1 in their base 3 representation. However, n is in base 10.

What I have done so far:
When I was proving that the language is not regular, I used the fact that there cannot be any arithmetic sequences in $A$. I think if I work on the number of 1 in base three, I may get somewhere.

# Answer
> 4 votes
Try to come up with an algorithm, and then write the simplest possible program in some usual programming language for recognizing L. Then translate that program to a Turing machine.

N is not "in base 10" - it's just a number in your computer's memory, which is probably internally represented in base 2, but your program shouldn't care.

To check if a number contains 1 in base 3 representation, try to build the base-3 representation using the usual base conversion algorithm (digit = x mod 3, proceed with x div 3), and stop when you see a 1.

# Answer
> 1 votes
As remarked already by jkff, a number is a number in whatever representation. Actually you get your number $n$ in unary representation as a sequence of $n$ $0$'s.

Checking whether the base 3 representation includes a $1$ is extremely easy. You scan the input, and for every three $0$'s, you replace each of the last two by a $+$ (just some symbol). This is like dividing by 3. When you reach the end, if there has been only a single $0$ read since the last replacement, you reject the input, else you replace each of the remainig $0$'s, if any, by $+$. Then you repeat a new scan, until you have less than three $0$'s left. If there is only one $0$ left then the input string is rejected, else it is accepted.

This is easily implemented with a Linear Bounded Automaton (LBA). Hence the language is Context Sensitive (but that does not usually say much more than recognizing it with a terminating Turing Machine). It is probably not too hard to write a CS grammar for it.

---
Tags: turing-machines
---


# Question
Title: Assign undirected edges in a mixed graph to make graph cyclic/acyclic
What is the complexity of the following problem?

Given a mixed (some edges directed, some undirected) graph, assign a direction to all the undirected edges to make the graph contain a cycle.

It doesn't "feel" like an NP-hard problem, but I can't think of an easy poly-time algorithm.

---

What about to make the graph acyclic?

As R B points out in the comments, to make the graph acyclic, you can just use a topological sort on the directed edges (ignoring the undirected edges temporarily) to get an ordering of the vertices, then use that ordering to direct the undirected edges. Therefore, that problem is easy and can be solved in $O(|V|+|E|)$ time.

However, orienting the edges to create a cycle is more tricky. Consider the graph:

```
    A
  /   \
 B --> C

```

In this case, simply sorting the graph to get A B C and then pointing the AC and AB edges backwards does not reveal the cycle.

# Answer
As noted by R B, the acyclic variant of the problem is solvable iff the directed part of the graph is acyclic, in which case one can take a topological sort of the directed edges, and orient undirected edges consistently with the linear order obtained.

For the cyclic variant of the problem, we can use the following polynomial-time algorithm, where $G=(V,E)$ is the input graph:

* for every directed edge $e=(a,b)\in E$, and for every orientation $(a,b)$ of an undirected edge $e=\\{a,b\\}\in E$:
    + if there is a path (directed where applicable) from $b$ to $a$ in $(V,E\smallsetminus\\{e\\})$:
        - find such a path $p$
        - make sure the path is simple by deleting subcycles
        - output any orientation of the undirected edges that agrees with the cycle $e,p$ and stop
* if no edge worked, reject

Note that the simplicity of $p$ in particular ensures that no undirected edge appears twice in $e,p$, hence it gives a consistent orientation. Thus, if the algorithm accepts, it is correct. On the other hand, if there exists an orientation of $G$ that includes a (wlog simple) cycle $c$, and $e=(a,b)$ is any edge in $c$ (properly oriented), then $a$ is reachable from $b$ in $(V,E\smallsetminus\\{e\\})$ by means of the rest of the cycle. Thus the algorithm will accept sooner or later.

In terms of complexity, both problems are NL-complete as decision problems, and the search problem versions are in FNL.
> 9 votes

---
Tags: complexity-theory, graphs, graph-algorithms
---


# Question
Title: How to prove that the Myhill-Nerode equivalence classes for L are the same as for its complement?
Given language $L$, I want to show that its Myhill-Nerode equivalence classes are the same as for its complement $\overline{L}$.

I am thinking of constructing a DFA $M$ for the Language $L$ so the DFA for the language of its complement will be just changing the final states to non final states but the states will be same. So the classes do remain same? How do I put this in a more formal way?

# Answer
Note that the Myhill-Nerode equivalences are also defined for non-regular languages, so constructing a finite state automaton will not help.

What is the definition of such a class? $x \sim\_L y$ iff $xz\in L$ whenever $yz\in L$ (for any string $z$). How does that change when we consider the complement of $L$? We use basic logic: $P\Leftrightarrow Q $ iff $\lnot P\Leftrightarrow \lnot Q $.

$x \sim\_L y$ *iff*
$xz\in L$ whenever $yz\in L$ (for any string $z$) *iff*
(not $xz\in L$) whenever (not $yz\in L$) (for any string $z$) *iff*
$xz\in \bar L$ whenever $yz\in \bar L$ (for any string $z$) *iff*
$x \sim\_{\bar L} y$.
> 3 votes

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


# Question
Title: Proving correctness of a CFG by induction on length of strings generated
Consider the following grammar with starting symbol of $S$.

$$S \rightarrow 0S11\\;|\\;S1\\;|\\;0$$

Let $L = \\{0^i1^j:\\; \ge 1\\; and\\; j \ge2i-2\\}$ . Give a formal proof of the following claim : For all $n\\;\ge0$, every string of length $n$ in $L$ can be generated by the grammar.

I don't know how to start doing it. Any hints ? What I can think of is the base case which will be : Let $w$ be the string generated by the given grammar. If $n=1$, then $w=0$, which can be generated by applying the third rule.

# Answer
> 0 votes
Let's try induction. The base case is easy (although not as trivial as you write in your question).

Now, assume any word in $L\cap \\{0,1\\}^n$ is generated by $G$. Let's take a word $w$ in $L\cap \\{0,1\\}^{n+1}$ and show it is generated by $G$.

Assume $w=0^a1^b$. We know that $b\ge 2(a-1)$. Note that $0^{a-1}1^{b-1}\in L\cap \\{0,1\\}^n$ (i.e., $b-1\ge 2(a-2)$) so it must be generated by $G$ . Since there is only one terminal derivation $S\to 0$, this must be the last derivation. It follows that there must be a sequence of derivations in $G$ which looks like:

$$S \to^\* 0^{a-2}S1^{b-1} \to 0^{a-1}1^{b-1}$$ with the last transition $S\to 0$. Here you need to explain why $0^{a-2}S1^{b-1}$ is the only possible sentinel phrase that yields $0^{a-1}1^{b-1}$ (and it can't be, e.g., of the form $0^{a\_1}S0^{a\_2}1^b$); This is a simple argument that I'll leave you to complete.

So if $S \to\_{G}^\* 0^{a-2}S1^{b-1}$ we can now take the second transition and then the third, and get $$ S \to^\* 0^{a-2}S1^{b-1} \to 0^{a-2}S11^{b-1} \to 0^{a-2}011^{b-1} = 0^a1^b$$

and we are done.

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


title: Find the coins required which sum to S

text:
# Question
Title: Find the coins required which sum to S
Given a list of $N$ coins, their values $V\_1, V\_2, \cdots , V\_N$, and a parameter of a total sum $S$. Find the coins the sum of which is S (we can use each coin at most once).

I was recently studying the very same problem from topcoder.com but there "we can use each coin any number of times". I am just stuck here if we can use each coin only once and not multiple times.

It will be very helpful if you can help or just give a hint. (this is not my homework quiz :P)

# Answer
This is a classic problem in dynamic programming, so you could review in literature a nicely description, search for the *subset sum problem*. With that problem the *set* is the values of coins, and you're looking for a subset that sum exactly $S$. (a subset is the answer).

The first, it's know it's exists such subset and it could find with the first version of subset-sum algorithm using dynamic programing as I show after with the recursive relation $f$. Then, we have to modify a little the algorithm to construct the solution (the subset of coins) using recursion maybe or other method.

The recursive relation to this problem with bases cases defined is:

$$ f(k, S) = Or \begin{cases} f(k -1, S) & \text{Case #}1\\ f(k-1, S - V\_{k}) & \text{Case #}2\ \ S\geq V\_{k} \end{cases} $$

* Case #1: it's possible to get $S$ with first $k-1$ coins ?
* Case #2: coin $V\_{k}$ it's taken. So it's possible to get the rest, i.e. $S - V\_{k}$ with the first $k-1$ coins?

Note: Sure about the base cases. I mean $f(k, 0) = False$, $f(0, 0)=True$, and others.

To construct the coins to sum $S$. You got to remember which of cases for $f$ were *True*, because the first says, don't to need $V\_k$, and the second case do.

The algorithm looks like more or less:

If $f(N, S)$ is True. You ask it's $f(N-1, S)$ is True. If it's True, you don't need to put $V\_N$ in the solution. If it's False, $f(N-1, S- V\_N)$ should be True, so, you need to put get in to it. And so on until you'd finished to consider the N coins or you've finished before looking for a sum zero.
> 2 votes

# Answer
Hint: Dynamic programming on this subproblem: "Can I get a sum of $x$ if I can use only the $k$ smallest coins?"
> 2 votes

---
Tags: algorithms, dynamic-programming, greedy-algorithms
---


# Question
Title: Help me find the ambiguity in this grammar
I've been sitting on this for 20+ minutes and can't seem to generate a string that is ambiguous. Can anyone help me? The grammar is:

$$S \xrightarrow{} SS \mid T$$ $$T \xrightarrow{} aTb \mid ab $$

Strings I have attempted to generate and failed are:

1. abab
2. abababab
3. aabbab
4. abaabb

And none of these seem to be generated by more than one left-most derivation. Can anyone come up with one that works?

# Answer
$$S \xrightarrow{} SS \xrightarrow{} SSS \xrightarrow{} TSS \xrightarrow{} abSS \xrightarrow{} abTS \xrightarrow{} ababS \xrightarrow{} ababT \xrightarrow{} ababab$$ $$S \xrightarrow{} SS \xrightarrow{} TS \xrightarrow{} abS \xrightarrow{} abSS \xrightarrow{} abTS \xrightarrow{} ababS \xrightarrow{} ababT \xrightarrow{} ababab$$

As @babou mentions in a comment, a production of the form

$$N \xrightarrow{} NN \mid X$$

is always ambiguous, since it can generate any binary tree with the right number of leaves as a parse tree. Compare it with:

$$N \xrightarrow{} XN \mid X$$ or $$N \xrightarrow{} NX \mid X$$

which only generate right- and left-biased binary trees, respectively.

As a point of interest, the number of binary trees with $k$ leaves is $C\_{k-1}$, the Catalan number of index $k-1$. So $TTT$ can be produced in two ways (as above) and $TTTT$ in five ways.
> 4 votes

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


# Question
Title: Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal directed cycle mean cost
Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c\_{i,j}$ that has at least one directed cycle.

Define **the directed cycle mean cost** to be $\frac {\\{\text {sum of cost of arcs}\\}} { \text {# arcs}}$.

Consider the LP:

> $\max \lambda$
>
> s.t: $p\_i + \lambda \le p\_j + c\_{i,j}$ where $(i,j)\in \mathcal A$.

I've shown:

* The LP is feasible.
* If $(\lambda,p)$ is a feasible solution then the directed cycle mean cost of every directed cycle is at least $\lambda$.
* The LP has an optimal solution (doesn't contain a line and $\lambda$ can't be greater than the maximum cost).

Now, I want to show given an optimal solution to the LP, it can be used to construct a directed cycle with minimal directed cycle mean cost.

I really don't have a clue on how to proceed. I don't see how an optimal solution give me the required information ?

# Answer
> 3 votes
I traced the LP back to this article. Here you can find the answer to your question presented in Theorem 2.

It might be helpful to look at the dual problem of your LP. This is analyzed in the above paper in Theorem 1. In this dual program your variables are defined as variables $z\_e\ge 0$ for the edges. Then they show that the optimal cycle is given by the edges for which $z\_e\>0$ in the optimal solution. Then you can use the complementary slackness condition. It follows that the **tight inequalities in your program define the optimal cycle.**

Note also that the author provide an interpretation for the variables in your LP. The value of $p\_i$ of a vertex not in the optimal cycle denotes the "least length of the path from the vertex $v\_i$ to the optimal cycle".

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


# Question
Title: If A is in P and B is non-trivial, then A ≤p B
On wikipedia's article on Polynomial-time reduction it states:

> Every nontrivial decision problem in P (the class of polynomial-time decision problems, where nontrivial means that not every input has the same output) may be reduced to every other nontrivial decision problem, by a polynomial-time many-one reduction. To transform an instance of problem A to B, solve A in polynomial time, and then use the solution to choose one of two instances of problem B with different answers

Some looking into the history of this entry reveals a link to math.SE that was referenced as a proof at one time.

However I am still confused as to exactly how this works. I understand polynomial-time reductions but there are some specific questions I have in regards to this statement.

1. Is it required that A is non-trivial as stated on wikipedia? Some places seem to suggest that the requirement is only B has to be non-trivial, and A doesn't matter if trivial or non-trivial. Based on this question.
2. Can someone provide me a concrete example of this working. I don't quite understand how there are two instances of problem B with different answers and how it relies on problem A to choose

# Answer
> 3 votes
First, it's important to realize here that the output of a decision problem will always be "Yes" or "No." So what this is saying is basically that $B$ has at least two inputs $x,y$ where $x \in L\_B$ and $y \not \in L\_B$, if $L\_B$ is the set (language) of all accepted inputs to $B$.

Let's let $B$ be SAT. We'll take two instances, $x = v\_1 \vee \neg v\_1$, which has a solution and thus is in SAT, and $y = v\_1 \wedge \neg v\_1$.

Let's let $A$ be the undirected graph-connectivity problem. We know that we can solve this in polynomial time using Breadth First Search.

So, given a graph $G$ as input to $A$, we'll define a function $f$:

$f(G) = x$ if $BFS(G)$ returns connected

$f(G) = y$ if $BFS(G)$ returns not connected

Clearly, we can compute $f(G)$ in linear time for any graph, since it's just a breadth-first search. Moreover, we see that $G$ is connected if and only if $f(G) \in SAT$.

The whole process is kind of trivial (in the mathematical sense), because we're basically saying "If we could solve $B$ in polynomial time, we could also solve $A$ in polynomial time". But we can always solve $A$ in polynomial time, so the whole thing is trivially true.

It holds for the same reason $P \implies \top$ is always true.

# Answer
> 1 votes
A reduction maps the yes-instances of problem $A$ to yes-instances of problem $B$ and the no-instances of problem $A$ to no-instances of problem $B$. In other words the mapping $f$ is a reduction if and only if $x \in A \Leftrightarrow f(x) \in B$ for all strings $x$.

Let $A$ be any language in $\mathbf{P}$ and $B$ be the finite language that contains only the string "1". We can simply map every string $s \in A$ to "1", and every string $s \not\in A$ to "0". Since $A$ is in $\mathbf{P}$, we can do this in polynomial time by using a polynomial time algorithm to decide whether a string is in $A$, and then output "1" or "0" accordingly.

In general, if $A$ has yes-instances, then $B$ must also have yes-instances. If $A$ has no-instances, then $B$ must also have no-instances. Therefore a reduction is always possible if $B$ is non-trivial, which just means that $B$ has both no- and yes-instances. If $B$ is trivial, then $A$ must also be trivial. Say $B$ is the trivial language that contains all strings. Then $A$ must not have no-instances, because they cannot be mapped anywhere, because $B$ has only yes-instances.

# Answer
> 1 votes
Now that I think I understand it more, I will provide my own understanding of the question for archive purposes in case someone in the future finds this post and is equally as confused as I was and may benefit from the mathematical laymen perspective.

Given A is in P, and the reduction itself is just a way of saying that you can solve A by using B in polynomial time. The reduction is a bit of a cheat, the way it lets B solve A is by first solving A and then uses B as a middle man to relay the solution.

As long as B has some input that says its false, and some input that says its true (B is non-trivial) then B can act as a middle man.

The process involves first solving A, which can be done in polynomial time since it is in P. Then you will input into B whatever corresponds to the output A had. If A's decision was TRUE, you will send whatever input makes B true, so that it relays TRUE. If A's decision is FALSE you will send whatever input makes B false so it relays FALSE. This way you are using B as a way to find a solution that works for A (Although in reality you are using A to solve A)

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


# Question
Title: Is the difference of a non-recursive and recursive set recursive?
I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$?

$B-A$ is obviously recursively enumerable (to generate its elements, I can generate B's elements and check if they are in A).

If A is the empty set or $A \cap B$ is the empty set, it's easy. Otherwise, I believe $B-A$ is not recursive (I can't tell if a number is in B, since B is not recursive) and $A-B$ is not recursively enumerable (I can generate A's elements, but I can't check if they are in B), so it's not recursive either.

Am I wrong? How can I actually (and formally) prove any of those?

# Answer
The empty set is recursive, hence B cannot be the empty set.

You are right the B-A is recursively enumerable.

You cannot prove B-A is not recursive for a good reason: it may be recursive. Maybe you can imagine an example of A recursive, B not recursive, and B-A recursive. Hint: it is not even necessary that B be recursively enumerable, or A recursive.

**Proof that $B-A$ can have properties more specific than recursively enumerability** (i.e. compatible with being recursively enumerable), **indpendently of the properties of B.**

> Consider 2 disjoint alphabets $\Sigma$ and $\Sigma'$, such that $\Sigma\cap\Sigma'=\emptyset$. Take $C=\Sigma'\\,^\*$ and $A=\Sigma^\*$. Let $E$ be a non-recursive language in $\Sigma^\*$. Let $B=C\cup E$. Then $B$ is a non-recursive language on the alphabet $\Sigma\cup\Sigma'$, because $C$ is recursive (trivially). Now you can see that $B-A=C$ since substracting $A$ removes precisely $E$, i.e. all words in *B* that are in $\Sigma^\*$. So you have $B$ non-recursive, and both $A$ and B-A are recursive. Here I chose $A$ recursive. But I could have chosen any non-recursive language on $\Sigma^\*$ that contains $E$.

Similarly, you cannot prove anything about A-B. Think why.
> 1 votes

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


# Question
Title: Regular expression for words over $\{0,1\}$ containing at least one 1
I had an exam on *Theory of Computation*, and one of the questions was to write down a regular expression for the language over $\\{0,1\\}$ consisting of all words containing at least one 1. My answer was:

$$ 0^\* 1 0^\* (0^\* 1 0^\*)^\* \\, . $$

My teacher gave me one mark out of 5, yet I can't find a possible string that will give false output here! His answer, which was $(0+1)^\*1(0+1)^\*$, was better, but mine works as well, I believe.

> Is my answer correct?

# Answer
> 4 votes
Your answer is correct. $0^\*1$ matches the portion up to the first $1$. After that, any subsequent $1$s may have any number of $0$s between them.

There are slightly simpler regular expressions for the same language. For example,

$$0^\*10^\*(0^\*10^\*)^\* \ \equiv\ 0^\*10^\*0^\*(10^\*)^\*\ \equiv\ 0^\*10^\*(10^\*)^\*\\,.$$

You could also observe that a string with at least one $1$ is formed of some number of initial $0$s, followed by the first $1$, followed by anything else, leading to $0^\*1(0+1)^\*\\!$, which is arguably slightly simpler than the teacher's solution.

However, you should consider that you probably lost marks for reasons other than the teacher mistakenly thinking that you were wrong. I wouldn't allocate five marks just for writing down a simple regular expression. To me, that would be either a one-mark question (one mark for right, none for wrong) or a two-mark question (two marks for right, one for being close and maybe missing a corner case, none for wrong). For five marks, I'd expect an explanation of why the regular expression does what it's supposed to do.

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