# Question
Title: When is epsilon a part of the result of computing the right quotient?
The right quotient of two languages is defined as

$$L\_1/L\_2=\\{ x \mid xy \in L\_1 \text{ and } y \in L\_2 \\}.$$

**Example**:
$L\_1=\\{ab,aab,baa\\}$ and $L\_2=\\{b\\}.$

I read somewhere that $L\_1/L\_2=\\{a,aa,\varepsilon\\}$ but I cannot understand why $\varepsilon$ is contained in the quotient.

# Answer
> 2 votes
In words, your definition says "The right quotient, written $L\_1 / L\_2$, is defined to be the set of all strings $x$ such that $xy$ is a string in $L\_1$ for some string $y$ in $L\_2$." According to this definition, the empty string is a member of the right quotient if and only if there is a common string in the two languages. In symbols, $\epsilon \in L\_1 / L\_2 \iff L\_1 \cap L\_2 \neq \emptyset$. In particular, this is not the case in your example, hence, the empty string is not in your right quotient.

---
Tags: formal-languages
---


# Question
Title: Are these two relations on integers partial orders?
Are the following relations $R\_1$ and $R\_2$ defined on the set $\mathbb{Z}$ of integers partial orders? (A partial order is reflexive, antisymmetric and transitive.)

1. $a$ $R\_1$ $b$ if and only if $a = 2b$.
2. $a$ $R\_2$ $b$ if and only if $a^2|b$.

Would someone help me understand?

# Answer
> 3 votes
Let's look at all the different criteria (reflexivity, symmetry or antisymmetry, and transitivity) for the first relations, $aR\_1b\Leftrightarrow a=2b$ :

a) Is it reflexive, or antireflexive, or neither? For this we want to test $aR\_1a$ — or in other words, whether $a=2a$. This *can* hold if $a=0$, but otherwise it never holds. So on $\Bbb{Z}$ the relation is neither reflexive nor antireflexive; but on $\Bbb{N}$ (the set of 'whole numbers', not counting 0) it would be antireflexive, since $a=2a$ can never hold there.

b) Is it symmetric, or antisymmetric, or neither? Here we want to compare $aR\_1b$ and $bR\_1a$ where $a$ and $b$ are distinct values; in other words, can we have both $a=2b$ and $b=2a$? Dividing by 2, the latter is equivalent to $a=\frac{1}{2}b$, and the only way we can have both $a=2b$ and $a=\frac{1}{2}b$ is to have $b=0$, in which case $a=0$ — but since we said that $a$ and $b$ had to be distinct, this can't hold. In other words, if we have $aR\_1b$ for $a\neq b$ we can never have $bR\_1a$; the relation is antisymmetric.

c) Is it transitive? (Note that we never ask about 'antitransitivity', even though the concept hypothetically makes sense). For this, we want to figure out if $(aR\_1b)\wedge(bR\_1c)\implies(aR\_1c)$ — in other words, if $a=2b$ and $b=2c$, is $a=2c$? Well, if $a=2b$ and $b=2c$, then we have $a=2b=2(2c)=4c$, so it's definitely not the case that $a=2c$; this relation is *not* transitive.

Since this has the feel of homework, I'll let you do the second one yourself, but it should be relatively straightforward (as long as you know a little bit about divisibility). For looking at reflexivity, you'll have special cases again where $a=0$ and also where $a=\pm1$ to keep an eye out for; for symmetry you should be able to use the divisibility to say something about the relative order of $a$ and $b$; and for transitivity you should try to figure out how to 'staple' the two conditions $a^2|b$ and $b^2|c$ together to see if you can figure out whether $a^2|c$.

# Answer
> 2 votes
Assuming that the answer to my comment is yes,

1. The first is not a partial order, since it is not reflexive; in general, it is not true that $a = 2a$ (consider the case $a \neq 0$).
2. The second is not a partial order, since it is not reflexive; in general, it is not true that $a^2 | a$ (consider the case $a \> 1$).

---
Tags: partial-order
---


title: Pumping lemma for a finite language

text:
# Question
Title: Pumping lemma for a finite language
> **Possible Duplicate:**
> Pumping lemma for simple finite regular languages

The pumping lemma says that for any regular language $L$, there exists a constant $p$ such that any word $w$ in $L$ with length at least $p$ can be split into three substrings, $w = xyz$, where the middle portion $y$ must not be empty, such that the words $xz, xyz, xyyz, xyyyz, \ldots$ constructed by repeating $y$ an arbitrary number of times (including zero times) are still in $L$.

Consider a regular Language which contains only one string - the alphabet $a$. ie, $L = \\{a\\}$.

Now, in this $L$, what would be the value of $p$, and possible values of $x$, $y$ , $z$?

I am confused to the boundary cases of the pumping lemma.

# Answer
The short answer is that for any finite language $p$ is greater than the length of every string in the language - i.e. finite languages are a trivial case as it's true that every string longer than $p$ can be pumped.

Beyond the question you asked, understanding what the pumping length is can help with stuff that you might do later. A very brief sketch of the proof of the lemma is that given a regular language, there's some DFA that accepts it. We can can take $p$ to be the number of states in that DFA.

Then if there are no loops in the DFA, we have a finite language an every string has length strictly less than $p$ (it can't have passed through the same state twice), this is the case in the question.

If there are loops (i.e. the language is infinite) then there can be strings of length greater than $p$, but this means that they have to have repeated some states (by going around the loop), and that it has to have done this loop in the first $p$ characters (otherwise we have too many characters for the number of states). This loop is the $y$ section of the string, obviously we can go around the loop as much as we want (even zero times), and this is the pumping part.

Obviously this is quite informal, but you should be able to glean the essential parts that give the conditions of the pumping lemma.
> 5 votes

# Answer
Short answer: Let $p = 10^{100}$. There are no strings of length $p$ in your language, so the conditions of the pumping lemma are vacuously satisfied.
> 0 votes

---
Tags: formal-languages
---


title: Solvability of Turing Machines

text:
# Question
Title: Solvability of Turing Machines
I'm preparing for an exam, and on a sample one provided (without solutions), we have this question: Is the following solvable or non-solvable: Given a turing machine $T$, does it accept a word of even length? - Given a deterministic 1-tape turing machine $T$, does $T$ ever read the contents of the 10th cell?

Thanks! -

# Answer
> 2 votes
"Non-trivial properties" for Rice's theorem are properties of the *language*, not of the *machine* itself - for instance, it's decidable how many states a TM has, which is certainly a non-trivial property! See Perplexed by Rice's theorem for a bit of a clarification on this. Now, one of your two properties is a property of the language, while one is a property of the machine; this should allow you to apply Rice's theorem in one case but not the other. Note that this isn't *conclusive* evidence that the other case is solvable, but it's guidance that you might try looking for a positive answer there.

(Note that this is meant to be a very loose hint just to guide you; I can certainly go into more specific details if you'd like...)

---
Tags: turing-machines, undecidability
---


title: Finding "fingerprint" sets

text:
# Question
Title: Finding "fingerprint" sets
Let's say we have 10 people, each with a list of favorite books. For a given person X, I would like to find a special subset of X's books liked only by X, i.e. there is no other person that likes all of the books in X's special subset. I think of this special subset as a unique "fingerprint" for X.

I would appreciate suggestions on an approach for finding such sets. (While this reads like a homework problem, it is related to a problem in my biology research that I am trying to solve.)

# Answer
> 6 votes
I assume you want the fingerprint to be as small as possible. Then this is the Hitting Set problem: For each person, make a list of all books liked by X but not by this person. Then, the goal is to select at least one book from each list. The problem is NP-hard, so you can't expect to find an algorithm that always solves it optimally in polynomial time. The greedy algorithm has a bad theoretical worst-case bound, but often works quite decent in practice. If you want to solve it optimally, an Integer Linear Programming solver should be able to solve instances of up to 1000 or maybe 10000 books. If you give more details on the size and structure of your instances, we could suggest other approaches.

# Answer
> 4 votes
This isn't a particularly clever algorithm, but it's polynomial, and I think it should work. Take any set. For each element in this set, count the number of remaining sets which do not contain it and remember which sets contain it. Pick the element with the highest count, and redo the counts for the remaining elements, ignoring the sets which lack the element you just chose. Continue until all remaining sets have been eliminated from consideration.

Example: let $A = \\{1, 2, 3\\}$, $B = \\{2, 3, 4\\}$, $C = \\{2, 4, 6\\}$, and $D = \\{1, 3, 5\\}$. Then we have counts $c\_1 = 2$, $c\_2 = 1$, and $c\_3 = 1$. We choose 1, eliminating sets $B$ and $C$ which did not contain it; redoing the counts, we have $c\_2 = 1$ and $c\_3 = 0$. We choose 2 as the next element, and remove $D$ from consideration. We are now done, and our "fingerprint" set is $\\{1, 2\\}$. EDIT: to complete the example, you should get the other fingerprint sets to come out as $\\{3, 4\\}$, $\\{6\\}$, and $\\{5\\}$.

I haven't given this a lot of thought, but intuitively, it seems like it should work. The idea is to greedily take as the next element of the fingerprint set the item which covers the most uncovered sets.

# Answer
> 0 votes
Maybe I did not understand the question correcty (based on somewhat complicated answers), but here goes. You just go through all persons, and through all their books, that they like. You create a data structure (prefferably a Hash Map $M$), where key is the book and value is a list of persons who like this book. You fill this data structure in an intuitive way (for each person/book pair, you append person to list $M\[book\]$). Then you go through the map keys and where the length of the list is equal to one, then this book is one of the `fingerprint books` of this particular person.

Let me demonstrate on python code:

```
%persons with books they like (it could also be a list or a set)
joe='ABCD'
andy='CDG'
frank='AHX'
anna='HAYZ'
matt='ACH'
%just transformation form variables, to names
names={joe:"Joe",andy:"Andy",frank:"Frank",anna:"Anna", matt:"Matt"}
%the map, from books to persons who like this book
books={}

%for each person
for p in names:
    %go through his liked books
    for book in p:
        %if book is already in the map, then append the person
        if book in books:
            books[book].append(names[p])
        else:
            %if not, then create a new book, and append the current person
            books[book]=[names[p]]

%create the fingerprint map (from person to books he likes)
fingerprint={}

%for each person create an empty list
for p in names:
    fingerprint[names[p]]=[]

%for each book in the map
for book in books:
    %if only one person likes this book, then it must be a part of his fingerprint
    if len(books[book])==1:
        fingerprint[books[book][0]].append(book)

print fingerprint

```

The code prints:

```
{'Frank': ['X'], 'Matt': [], 'Andy': ['G'], 'Joe': ['B'], 'Anna': ['Y', 'Z']}

```

# Answer
> 0 votes
This is the OP (didn't register on initial submission, so now I can't comment properly). Thank you so much for the feedback -- the original greedy algorithm solution got me going in the right direction. The total space I'm working on concerns 100s of individuals and 1000s of "books" -- if this is feasible with the integer programming approach, I'd love to hear more about it.

---
Tags: algorithms, sets
---


# Question
Title: Proving the language which consists of all strings in some language is the same length as some string in another language is regular
So I've been scratching my head over this problem for a couple of days now. Given some language $A$ and $B$ that is regular, show that the language $L$ which consists of all strings in $A$ whose length is equal to some string in $B$ is a regular language.

In equation form:

$$L = \\{x \in A \mid \exists y \in B \text{ s.t. } |x| = |y| \\}$$

My initial thought was to try and come up with some DFA for both languages $A$ and $B$ and map the two states to each other and hopefully get a 1:1 ratio that way I can generate a new DFA which proves that $L$ is regular. But then I realized that $A$ and $B$ don't have to be over the same set of symbols.

I think the correct way to solve this is to use the closure properties of regular language, but I'm not sure of how to begin/use the properties for "lengths" of strings instead of strings themselves.

Could someone point me in the right direction?

# Answer
Remember (or come up with) the proof for

$\qquad \displaystyle L\_1, L\_2 \in \mathsf{REG} \implies L\_1 \cap L\_2 \in \mathsf{REG}$.

Do you see how to modify the proof for your setting?

> Abstracting the equality of lengths thing, come up with a construction for an automaton for
> $\qquad \displaystyle L\_l = \\{ w \in \Sigma^\* \mid \exists x \in L.\\, |x|=|w|\\}$
> for given, arbitrary $L \in \mathsf{REG}$ over $\Sigma$.

Do you see the connection?

> Now note that $L = A \cap B\_l$.
> 4 votes

# Answer
**Hints:** Let's assume you know all the different lengths of words in $B$, $len(B) = \\{ \ell\_1, \ell\_2, \ell\_3, ... \\}$. For the time being, let's assume it is finite.

Can you use this knowledge to construct a DFA for $A$?
<sup>(hint: intersection, or "cross-product" construction)</sup>

Does the alphabet of $B$ even matters?

Next, it might be the the set of lengths $len(B)$ is infinite. Then look at this question which should resolve that matter as well.
> 3 votes

# Answer
The closure property way, so no (explicit) automata. Regular languages are closed under morphisms, inverse morphisms and intersection (with regular languages).

Let $\Sigma\_A$ and $\Sigma\_B$ be the alphabets of $A$ and $B$. Let $h\_X:\Sigma\_X^\* \to \\{1\\}^\*$ be the morphism that maps every letter $a\in\Sigma\_X$ to $1$. Then $h\_B(B) \subseteq \\{1\\}^\*$ codes the length set of $B$, and $h\_A^{-1}(h\_B(B))$ consists of (all) strings that are of the same length as strings in $B$, but over the alphabet of $A$. Finally, we observe that $L= A\cap h\_A^{-1}(h\_B(B))$.

Now for the *bonus*. It also works for *context-free* $A$ and $B$. We need however an additional property: if $B$ is context-free then $h\_B(B)$ is regular (!) as all 'unary' (=single letter alphabet) context-free languages are regular, a consequence of Parikh's theorem. Thus also $h\_A^{-1}(h\_B(B))$ is regular, and $L$ is context-free.
> 2 votes

---
Tags: formal-languages, regular-languages, finite-automata, proof-techniques, closure-properties
---


title: Speed-up of two-tape Turing machine

text:
# Question
Title: Speed-up of two-tape Turing machine
I try to figure out linear speed-up of Turing machine.

*Prove that any problem that can be solved by a two-tape Turing machine that has time complexity t can be solved by another two-tape Turing machine having time complexity $t′$, where $t′(n) = O(n) + (t(n)/2)$.*

The idea seems to show that what the first machine does within two steps the second machine is capable to do within one step. Time complexity $O(n)$ seems to be complexity of encoding input of first machine to input of second machine.

I have a problem with proving this statement and will appreciate any help.

In addition, why only two-tape Turing machine was mentioned, what about one-tape Turing machine.

# Answer
The single tape case is known as the Linear speedup theorem. It has a nice little trick by compressing the tape *and* using overlapping chunks of the tape. Try whether it also works in the two-tape case.
> 3 votes

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


# Question
Title: An interesting metric space related to Turing machines
In this question we only consider Turing machines that halt on all inputs. If $k \in \mathbb{N}$ then by $T\_k$ we denote the Turing machine whose code is $k$.

Consider the following function

$$s(x,y) = \min\\{k \mid |L(T\_k) \cap \\{x,y\\}| = 1\\}$$

In other words, $s(x,y)$ is the code of the smallest Turing machine that recognizes precisely one of the strings $x,y.$ We can now define the following map

$$d(x,y) = \left\\{ \begin{array}{ll} 2^{-s(x,y)} & \mbox{if } x \ne y, \\ 0 & \mbox{otherwise.} \end{array} \right. $$

It can be quickly verified that $d(x,y)$ induces a metric space (in fact an ultrametrics) on $\Sigma^{\*}.$

Now I would like to prove that if $f:\Sigma^{\*} \mapsto \Sigma^{\*}$ is a uniformly continuous function then for every recursive language L, $f^{-1}(L)$ is recursive as well.

In other words let $f$ be a map such that for every $\epsilon \> 0$ there is a $\delta \> 0$ such that if for strings $x,y \in \Sigma^{\*}$ $$\quad d(x,y) \leq \delta$$ then $$ d(f(x),f(y)) \< \epsilon.$$ Then we need to show that $f^{-1}(L)$ is a recursive language given that $L$ is recursive.

Now as already noted in this post one way to approach the problem is to show that there is a Turing machine that given a string $x \in \Sigma^{\*}$ computes $f(x).$

I am stuck proving this claim and slowly wondering if there is some other approach to solve this?

Hints, suggestions and solutions are welcome!

# Answer
*Edit: removed hints, posted my solution.*

Here is my solution. We're going to pick a reference point $x$ where $f(x) \in L$ and consider the universe from $x$ and $f(x)$'s points of view. It turns out that every "neighborhood" of a point corresponds to a recursive language. So $L$ is a neighborhood around $f(x)$, and there will be some neighborhood around $x$ that maps to it; this neighborhood is a recursive language.

*Lemma. In this space, a language is recursive if and only if it is a neighborhood of each of its strings.*

*Proof*. First, fix a recursive language $L$ and let $x \in L$. Let $K$ be the minimal index of a decider for $L$. Then we have that if $y \not \in L$, $s(x,y) \leq K$, so $d(x,y) \geq 1/2^K$. Thus $d(x,y) \< 1/2^K$ implies that $y \in L$.

Second, let $x$ be an arbitrary string and fix $\varepsilon \> 0$; let $K = \lfloor \log(1/\varepsilon) \rfloor$. Let $L\_K = \\{y : d(x,y) \< \varepsilon\\}$; then $L\_K = \\{y : s(x,y) \> K\\}$. Then we can write

$$L\_K = \\{ y : (\forall j=1,\dots,K) |L(T\_j) \cap \\{x,y\\}| \neq 1\\}.$$

But $L\_K$ is decidable: On input $y$, one may simulate the first $K$ deciders on $x$ and $y$ and accept if and only if each either accepted both or rejected both. $~\square$

Now we're almost done:

*Prop. Let $f$ be continuous. If $L$ is recursive, then $f^{-1}(L)$ is recursive.*

*Proof.* Under a continuous function, the preimage of a neighborhood is a neighborhood.

---

Interestingly, I think that in this space a continuous function is uniformly continuous: Let $f$ be continuous, so for each point $x$, for each $\varepsilon$ there exists a corresponding $\delta$. Fix an $\varepsilon$ and let $K = \lfloor \log(1/\varepsilon) \rfloor$. There are a finite number of balls of size $\varepsilon$: there is $L(T\_1) \cup L(T\_2) \dots \cup L(T\_K)$; then there is $\overline{L(T\_1)} \cup L(T\_2) \dots \cup L(T\_K)$; then $L(T\_1) \cup \overline{L(T\_2)} \dots \cup L(T\_K)$, and so on. $f$ associates to each of these languages $L\_i$ a preimage language $L\_i^{\prime}$ with associated diameter $\delta\_i$. For each $x \in L\_i^{\prime}$, $d(x,y) \leq \delta\_i \implies d(f(x),f(y)) \leq \varepsilon$. So we can take the minimum over these finitely many $\delta$s to get the uniform continuity constant $\delta$ associated with this $\varepsilon$.
> 9 votes

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


title: Triple nested for-loops

text:
# Question
Title: Triple nested for-loops
> **Possible Duplicate:**
> A puzzle related to nested loops

I am trying to count the exact/total number of iterations the following nested for-loops are executed:

```
s=0
for (i: 1 to n)
 for (j: 1 to i)
  for (k: j to i)
   s = s + 1

```

I know that the first two for-loops will have `n(n+1)/2` iterations. My problem is with the third for-loop. Due to this third loop what factor am I supposed to multiply with `n(n+1)/2` to get the total number of iterations?

Any help would be appreciated? Thanks

# Answer
> 11 votes
Instead of a general "formula", you should try to work out from principles first, at least in the beginning. You can see that the number of executions are:

$$\sum\limits\_{i=1}^{n} \sum\limits\_{j=1}^{i} \sum\limits\_{k=j}^{i} 1$$

We try solving them one step at a time. The innermost (right-most) summation can be solved as:

$$\sum\limits\_{k=j}^{i} 1 = i - j + 1$$ (how many times will the loop execute from $j$ to $i$, inclusive).

Going on to the next level, by substituting the above result, we get: $$\sum\limits\_{j=1}^{i} \sum\limits\_{k=j}^{i} 1 = \sum\limits\_{j=1}^{i} (i - j + 1) = i\sum\limits\_{j=1}^{i} 1 -\sum\limits\_{j=1}^{i}j + \sum\limits\_{j=1}^{i}1$$ $$ = i^2 - \frac{i(i+1)}{2} + i = \frac{i(i+1)}{2}$$

Notice that when summation is over the variable $j$, $i$ behaves like a constant, and so could be taken out of the summation.

The above expression gives the number of times the inner two loops are executed for every value $i$ that the outer loop takes. Solving the outermost summation with this expression ($i$ runs from $1$ to $n$), we have:

$$\sum\limits\_{i=1}^{n}\frac{i(i+1)}{2} = \frac{1}{2}\sum\limits\_{i=1}^{n}i^2 + \frac{1}{2}\sum\limits\_{i=1}^{n}i$$ $$ = \frac{1}{2}\cdot\frac{n(n+1)(2n+1)}{6} + \frac{1}{2}\cdot\frac{n(n+1)}{2}$$ $$ = \frac{n(n+1)(n+2)}{6}$$

This will also be the value of the variable `s` in your pseudocode. I suggest that you should approach these kind of questions from the basics, and revise the summation rules. There are no general formulas or multiplication factors for some arbitrary nesting of loops. You might even want to go along these lines to again derive your result for the first two loops only.

---
Tags: runtime-analysis, loops
---


title: Proofs using the regular pumping lemma

text:
# Question
Title: Proofs using the regular pumping lemma
I have two questions:

1. I consider the following language $$L\_1= \\{ w\in \\{0,1\\}^\* \mid \not \exists u\in \\{0,1\\}^\* \colon w= uu^R\\}.$$ In other words $w$ is not palindrome with even length. I proved that this language is NOT regular by proving that its complement is not regular. My question is how to prove it using the pumping lemma without using going over the complement.
2. Let $$L\_2=\\{w\in\\{0,1\\}^\* \mid \text{$w$ has same number of 101 substrings and 010 substrings}\\}. $$ I proved that this language is not regular by using equivalence classes. How I can prove it using the pumping lemma?

Thanks alot for edit:)

# Answer
Not all non-regular languages fail the test of the pumping lemma. Wikipedia has an annoyingly complex example of a non-regular language which can be pumped. So even if a language is non-regular, we may not be able to prove this fact using the pumping lemma.

But it turns out we can use the pumping lemma to prove your first language is not regular. I'm not sure about the second.

Claim: $L\_1$ is non-regular.

Proof: By the pumping lemma. Let $p$ be the pumping length. (I'm going to use the alphabet $\\{a,b\\}$ rather than $\\{0,1\\}$.) If $p = 1$, then take the string $abbaa$, which is in $L\_1$ and pump it to $aabbaa$ which is not in $L\_1$, so $L\_1$ would not be regular.

If $p \> 1$, then take the string $a^pbba^{N}$. (We'll figure out what we want $N$ to be later.) Then consider any division of the string into $xyz$ where $x=a^{p-k}$, $y=a^k$, and $z=bba^{N}$.

Now let's pump this string $i$ times. (We'll figure out what we want $i$ to be later.) We get the string $xy^iz$, which gives $a^{p-k}a^{ik}bba^{N} = a^{p-k+ik}bba^{N}$.

Now let's back up. First, we picked $N$. Then, some choice of $k$ was made. Then, we picked $i$. We want to figure out what $N$ to pick so that, for any choice of $k \in \[1,p\]$, we can choose an $i$ that makes this string a palindrome by making the number of $a$s on the left equal the number on the right. (It will always have even length.)

So we want to always get that $p-k+ik=N$. If we play around with the math, we find that we should pick $N=p+p!$ and pick $i=p!/k+1$.

So to recap, we picked $N=p+p!$ and chose the string $a^pbba^N$. Then some choice of $k$ was made so that the string was made up of $a^{p-k}ybba^N$ where $y=a^k$. Then we picked $i=p!/k + 1$. We pumped the string to get $a^{p-k}y^{i}bba^N = a^{p-k}a^{ik}bba^N = a^{p-k+ik}bba^N$.

But we know that $p-k+ik = p-k+(\frac{p!}{k}+1)k = p-k+p!+k=p+p!$. And $N=p+p!$. So the number of $a$s on both ends is the same, so the string is an even-length palindrome, so it's not in $L\_1$, so $L\_1$ is not regular. $\square$
> 7 votes

# Answer
For question one the string $0^{p}1^{2p}0^{p+p!}$ is a suitable counter-example. What ever the length of $y$ is, it must be a factor of $p!$, so we pump it enough and we get $p+p!$ zeroes at the start.
> 3 votes

# Answer
After long thinking i think i answered 2.

we choose string (010)^N(101)^N , where N is pumping length. No matter what y we will choose, xy^0z will have more 101 then 010. the idea is that we can only add more 101 sub strings in first part of string or remove some 010 sub strings.
> 1 votes

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


title: Is this language regular?

text:
# Question
Title: Is this language regular?
Consider the following language: $$ L\_1=\\{uu^rv \mid u,v\in\\{0,1\\}^+\\}.$$ that means that neither $u$ nor $v$ can be $\varepsilon$. As usual $u^r$ refers to $u$ reflected.

I think that this language is not regular, but i am not sure. Any ideas?

# Answer
> 5 votes
Nice question. It is not regular.

Notice that this language consists of words where some nonempty prefix is an even palindrome.

Intersect $L$ with $(01)^{+} (10)^{+}$. If a word of this form has a palindromic prefix: $(01)^n (10)^m = u u^R v$ and $u \neq \varepsilon$, then the center of palindrome must be between the group of $01$ and the group of $10$. For example, take the word $0101011010101010$. The only possibility of breaking a prefix into a palindrome is $(010101\cdot 101010)\cdot1010$. (I leave the proof of this statement to you.)

Therefore, $L \cap (01)^{+} (10)^{+}=\\{(01)^n (10)^m : m \> n \geq 1\\}$. However, this language is not regular - for example, each prefix $(01)^n$ is in a different Myhill-Nerode class.

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


# Question
Title: If I have a large random array of 0s and 1s that I want to sort what kind of an algorithm and data structures should I consider?
What are the types of things that need to be considered if I need to sort a large random array of 0s and 1s?

You can assume large array is in the order of million or billions.

I understand there are tons of sorting algorithms out there (quick, merge, radix,.etc.) and there are so many different data structures out there (trees, skip lists, linked lists, etc.)

If somebody asks me to sort this large array, do I simply jump to Quick Sort and say that's the best solution? If not, what am I supposed to be thinking about?

I'm not even sure if I know the right answer to this question, but I would really appreciate it if somebody in the community can give some advise.

Thanks.

# Answer
> 9 votes
Use counting sort: run through the array once and count the number of 0's. Then run through the array once more and write in it the counted number of 0's, followed by 1's. In any case, this is a purely academic exercise because nobody would ever need to do such a thing in real life.

# Answer
> 1 votes
While Andrej Bauer points out that your problem can be solved very efficiently, 0-1 sorting has some interesting and nontrivial aspects. For example, a sorting network is valid if and only if it can sort all sequences of 0s and 1s.

Intuitively, a sorting network is an sorting algorithm that does not change what it does based on previous results. This is not true of, say, quicksort, which recurses differently based on the rank of the chosen pivot (quicksort is clearly not a sorting network for several reasons in its standard form). This is why for sorting networks 0-1 sorting is exactly as difficult as unrestricted sorting--the algorithm can't examine the input to see how to handle it most efficiently. In this case, the most efficient way to handle the 1s and 0s is to not really sort at all but count instead. This option is not available to a sorting network, so instead it performs all operations as usual, costing as much as any other kind of sort.

# Answer
> 0 votes
My approach would be this:

```
ptr1 := start_of_array
ptr2 := end_of_array
while ptr2 > ptr1 :

    while arr[ptr1] == 0 : //pass1
        ptr1++

    while arr[ptr2] == 1 : //pass2
        ptr2--

    if ptr2 > ptr1 :
        swap ptr1, ptr2    //swap

```

This will work like this :

Input Array : ***0*** 0 0 0 1 1 1 0 1 0 1 **1**

Pass1 : 0 0 0 0 ***1*** 1 1 0 1 0 1 **1**

Pass2 : 0 0 0 0 ***1*** 1 1 0 1 **0** 1 1

Swap : 0 0 0 0 ***0*** 1 1 0 1 **1** 1 1

---

Pass1 : 0 0 0 0 0 ***1*** 1 0 1 **1** 1 1

Pass2 : 0 0 0 0 0 ***1*** 1 **0** 1 1 1 1

Swap : 0 0 0 0 0 ***0*** 1 **1** 1 1 1 1

---

Pass1 : 0 0 0 0 0 0 ***1*** **1** 1 1 1 1

Pass2 : 0 0 0 0 0 **0** ***1*** 1 1 1 1 1

Exit from loop

# Answer
> -3 votes
This really depends on the number of zeroes and ones your dealing with on a per element basis.

If your dealing with 64 or less, just convert it to a number, pop it into an array, and sort the array.

32 or less, make a blank array, convert the entry to a number, and keep track of the number of times the number passed.

ok If this is a pathological case-- lets say a billion entries each a 16kilobits long.. now your into diskland... you split your file into ~100 mb pieces then use the unix split, sort, and \>\> operators to implement a merge sort. There is a temptation to just let sort do it all in one go, ignore that temptation it leads to the land of frustration (It might have been a memory limitation). (I did an 800GB sort this way via script a few years back)

Best of luck --Storm

---
Tags: sorting, big-data
---


# Question
Title: Retrieving the shortest path of a dynamic graph
I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is dynamic? By saying dynamic I mean that we can insert or remove vertices during the execution of the program. I'm trying to find an efficient algorithm for updating the shortest paths from a vertex $v$ to every other vertex $u$, after inserting an edge $e$, without needing to run the shortest path algorithm in the new graph again. How can I do this? Thanks in advance.

* *Note:* the changes can be done after the first iteration of the algorithm
* *Note\[2\]:* two nodes are given, $s$ the source and $t$ the target. I need to find the shortest path between these nodes. When the graph is updated I only have to update $\pi(s,t)$, which is the shortest path between $s$ and $t$.
* *Note\[3\]:* I'm only interested in the edge insertion case.

> **A formal definition**: Given a graph $G = (V,E)$. Define an *update operation* as 1) an insertion of an edge $e$ to $E$ or 2) a a deletion of an edge $e$ from $E$. The objective is to find efficiently the cost of all pairs shortest paths after an update operation. By efficiently, we mean at least better than executing an All-Pairs-Shortest-Path algorithm, such as Bellman-Ford algorithm, after each update operation.

---

**Edit:** Below there is a simplified version of the problem:

> A weighted graph $G(V,E)$ is given, consisting of unidirectional edges, and two critical vertices $s$ and $t$. A set $C$ of candidate *bidirectional* edges is also given. I have to build an edge $(u,v) \in C$ to minimize the distance from $s$ to $t$.

# Answer
> 15 votes
The problem as you probably have noticed is a quite difficult problem. Checking the web will lead to some complex instances that probably you will not need. Here is a solution - as required (i.e. you don't need to recalculate everything from scratch).

For the case of adding an edge $(u,v)$ \- then using your already built-distance matrix - do the following:

For every pair of nodes $x$ and $y$ check if $d((x,u)) + c((u,v)) + d((v,y)) \< d((x,y))$ \- this can be done in $O(n^2)$ since you are comparing every pair of nodes.

For the case of edge deletion: Given the distance matrix already built, then you can have for every node $u$ a shortest-path tree rooted at $u$. If the deleted edge $e$ is not in that tree, then the shortest paths from $u$ to every other is not affected - (they remain the same).

If $e$ is in the shortest path tree of $u$, then for every node $v$ such that the shortest path $\pi(u,v)$ includes $e$, the paths will change. Therefore, compute the shortest path from $u$ to $v$. Now, repeat the previous for every node -- this is not the best solution. In fact, in its worst case it is asymptotically equivalent to doing every thing from scratch, but can be better on average.

If you want to have better results than this, then have a look at:

1. Demetrescu, Camil, and Giuseppe F. Italiano. "A new approach to dynamic all pairs shortest paths." Journal of the ACM (JACM) 51.6 (2004): 968-992. (can be found freely from Google)
2. or have a look at this nicely written survey

# Answer
> 18 votes
The problem you are asking for is a well-known algorithmic problems. It is actually still open, how hard this problem exactly is. Also you should know that there are different incarnations of this problem. In contrast what you are asking for, usually only the distances are returned, whereas you are asking for the the actual shortest paths. Notice that these paths can be already very long. Dynamic graph algorithms distinguish between edge deletions only (decremental dg algorithms), edge insertions only (incremental dg algorithms) and edge insertions and deletions (fully-dynamic dg algorithms). Thus you are interested in **incremental** algorithms.

The algorithms mentioned in the post of AJed, are slightly outdated. There are newer results by Thorup, see here, on page 8 for a short survey. The currently best **fully-dynamic** exact APSP algorithm by Thorup (for distance queries, not the path), needs $O(n^2(\log n +\log^2 (1+m/n))$ amortized update time, while supporting $O(1)$ worst case query time. Notice, that if you have $O(n\log n)$ edges, then you could just recompute from scratch with Dijkstra and Fibonacci-heaps and get the same running time as in Thorup's algorithm. So if your graphs are not to dense, I would recommend using Dijkstra.

I am not aware of any better **incremental** algorithm. But you should do a web search if there exist newer results for this specialized problem.

# Answer
> 5 votes
I believe the AD\* algorithm might help you.

http://www.cs.cmu.edu/~ggordon/likhachev-etal.anytime-dstar.pdf

> When updated information regarding the underlying graph is received, the algorithm incrementally repairs its previous solution. The result is an approach that combines the beneﬁts of anytime and incremental planners to provide efﬁcient solutions to complex, dynamic search problems

AD\* highlights: It's "anytime", which means it can give you a "sub-optimal solution" very quickly, though it might not be the best. Given enough time though, it will return the optimal solution. Also, you can restrict the sub-optimal solution to be no worse than the optimal solution by some user-defined constant. This gives you the ability to use this in a real-time planning scenario where having an okay solution (where 'okay' is theoretically bounded) is better than having no solution at all.

http://www.cs.cmu.edu/~maxim/software.html

---
Tags: graphs, data-structures, shortest-path, efficiency, dynamic-algorithms
---


# Question
Title: Smallest string length to contain all types of beads
I read this question somewhere, and could not come up with an efficient answer.

A string of some length has beads fixed on it at some given arbitrary distances from each other. There are $k$ different types of beads and $n$ beads in total on the string, and each bead is present atleast once. We need to find one consecutive section of the string, such that:

* that section contains all of the $k$ different types of beads atleast once.
* the length of this section is as small as possible, provided the first condition is met.

We are given the positions of each bead on the string, or alternatively, the distances between each pair of consecutive beads.

Of course, a simple brute force method would be to start from every bead (assume that the section starts from this bead), and go on till atleast on instance of all beads are found while keeping track of the length. Repeat for every starting position, and find the minimum among them. This will give a $O(n^2)$ solution, where $n$ is the number of beads on the string. I think a dynamic programming approach would also probably be $O(n^2)$, but I may be wrong. Is there a faster algorithm? Space complexity has to be sub-quadratic. Thanks!

Edit: $k$ can be $O(n)$.

# Answer
> 4 votes
With a little care your own suggestion can be implemented to $O(kn)$, if my idea is correct.

Keep $k$ pointers, one for each colour, and a general pointer, the possible start of the segment. At each moment each of these colour pointers keeps the next position of its colour, that follows the segment pointer. One colour pointer points to the segment pointer. That colour pointer is updated when the segment pointer moves to the next position. Each colour pointer in total moves only $n$ positions. For each position the segment pointer computes the maximal distance to the colour pounters, and one takes the overal minimum of that.

Or, intuitively perhaps simpler, let the pointers look into the past, not the future. Let the colour pointers denote the distance to the respective colours last seen. In each step add the distance to the last bead to each pointer, except the one of the current colour, which is set to zero.

(edit: answer to question) If $k$ is large, in the order of $n$ as suggested, then one may keep the $k$ pointers in a max heap. An update of a pointer costs $\log k$ each of $n$ steps. We may find max (the farthest colour, hence the interval length) in constant time, each of $n$ steps. So $n \log k$ total plus initialization.

Now we also have to *find* the element/colour in the heap that we have to update. This is done by keeping an index of elements. Each time we swap to elements in the heap (a usual heap operation) we also swap the positions stored in the index. This is usually doen when computing Dijkstra's algorithm with a heap: when a new edge is found some distances to vertices have to be decreased, and one needs to find them.

---
Tags: algorithms, dynamic-programming, search-algorithms
---


# Question
Title: Why does the Count-Min Sketch require pairwise independent hash functions?
The Count-Min Sketch is an awesome data structure for estimating the frequencies of different elements in a data stream. Intuitively, it works by picking a variety of hash functions, hashing each element with those hash functions, and incrementing the frequencies of various slots in various tables. To estimate the frequency of an element, the Count-Min sketch applies the hash functions to those elements and takes the minimum value out of all the slots that are hashed to.

The original paper on the Count-Min Sketch mentions that the data structure requires pairwise independent hash functions in order to get the necessary guarantees on its expected performance. However, looking over the structure, I don't see why pairwise independence is necessary. Intuitively, I would think that all that would be required would be that the hash function be a universal hash function, since universal hash functions are hash functions with low probabilities of collisions. The analysis of the collision probabilities in the Count-Min Sketch looks remarkably similar to the analysis of collision probabilities in a chained hash table (which only requires a family of universal hash functions, not pairwise independent hash functions), and I can't spot the difference in the analyses.

Why is it necessary for the hash functions in the Count-Min Sketch to be pairwise independent?

Thanks!

# Answer
You are right: universal hashing suffices. Pairwise independence, while stronger, is the usual method to construct a universal hash family. Also pairwise independence is contrasted in the paper with the 4-wise independence required by previous methods, such as the AMS sketch.
> 6 votes

---
Tags: algorithms, data-structures, randomized-algorithms, hash
---


# Question
Title: If $f(n) = \Theta(g(n))$, do both functions bound each other for all $n$ or only sufficiently large $n$?
The following is an excerpt from CLRS:

> $\Theta(g(n))= \\{ f(n) \mid \text{ $\exists c\_1,c\_2,n\_0\>0$ such that $0 \le c\_1 g(n) \le f(n) \le c\_2g(n)$ for all $n \ge n\_0$}\\}$.

Assuming $n \in \mathbb{N}$, I was unable to find $f(n)$ and $g(n)$ such that the bound does not apply for all $n$.

**Note:** This question was asked with the flawed assumption that $f(n)$ and $g(n)$ necessarily have natural domains.

# Answer
You need to have a non-negative sufficiently large input size $n$ from which point on the bound holds. Have a look the Figure 3.1 in CLRS, which shows graphically examples of the $O, \Theta$ and $\Omega$ notation. You can also see why this makes sense. For example, we are interested in knowing how an algorithm's runtime behaves as the input gets larger and larger. Thus, we don't really care too much about small values of $n$.

It is not always the case that for every nonnegative $n$ a bound would hold. For example, consider two functions $f(n)=n$ and $g(n)=n \log n$. We can plot them for a few small values of $n$. $g(n)$ does not dominate $f(n)$ for all values of $n$. For sufficiently large values of $n$, it will. In other words, $f(n) = O(g(n))$. Note that this is only an upper bound, but the idea will be the same for $\Theta$.
> 0 votes

# Answer
If we restrict consideration to $\mathbb{N}$ and both functions are strictly positive on every $n \in \mathbb{N}$, then it is true that, if $f(n) \in \Theta(g(n))$, then there exists a $c$ such that $f(n) \leq cg(n)$ for all $n$, and vice versa.

(As pointed out in the comments, if the functions can be negative, then the answer is clearly "no", since we could take $f(1) = -1$ and $g(1) = 1$.)

The proof is straightforward. If $f(n) \in O(g(n))$, then there is an $N$ and a $C$ so that, whenever $n \geq N$, $f(n) \leq C g(n)$.

Now consider $n = 0,1,2,\dots,N-1$. For each $n$, if $g(n) \> f(n)$, pick some $c\_n$ so that $f(n) \leq c\_n g(n)$. We can easily do this because there's only $N$ of these numbers to check.

Now pick $K = \max\\{C,c\_0,c\_1,\dots,c\_{N-1}\\}$. By construction, $f(n) \leq K g(n)$ for all $n$. So we're done.

The intuition here is not tricky: We know that, if we go far enough out, $C g(x)$ bounds $f(x)$. So we just check all the cases up to that point and pick the biggest bound.

If we consider strictly positive functions defined on the reals, it is not much different to prove that, if $f$ and $g$ are both continuous and bounded below by some $\delta \> 0$, we get the same result.
> 3 votes

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


# Question
Title: is determinism = non determinism for one counter automata?
This language I think is not accepted by a deterministic one counter but accepted by a non-deterministic one counter :

$L = \\{a^{i}b^{j}c^{k} \mid (i=j) \vee (j=k) \text{ such that } i\geq0, j\geq0, k\geq0\\}$

But how to prove this claim?

Or is it the case that they are equivalent?

# Answer
> 4 votes
You are right: the language $L$ from your question is accepted by a (nondeterministic) one-counter automaton.

Now for the deterministic case. Counter automata are a special case of push-down automata, where one only uses a single stack symbol (apart from a bottom-of-stack). Every (deterministic) one-counter language is also a (deterministic) push-down language. So in order to demonstrate it is not a deterministic one-counter language, I show a stronger result: it is even not accepted by a deterministic PDA.

According to Ogden, in his paper introducing Ogden's Lemma, that same language $L$ is inherently ambiguous context-free, meaning that *every* possible context-free grammar for the language is ambiguous, i.e., it has a string with two different succesful derivation trees. On the other hand, it is known that every deterministic PDA can be transformed into a non-ambiguous CFG. In fact I believe the standard construction PDA to CFG does the trick (but that is not obvious). Hence as there is no non-ambiguous CF grammar for $L$ (Ogden), there can be no deterministic PDA for $L$, and in particular no deterministic one-counter automaton.

Conclusion: for one-counter automata determinism is less powerful than the general model, using your example.

(In an edit I moved info from comments into this text.) Reference, see also Wikipedia: Ogden, W. (1968). A helpful result for proving inherent ambiguity. Math. Syst. Theory 2, 191–194.

# Answer
> -4 votes
All non-deterministic finite-state automata (NFA) can be represented with an equivalent deterministic finite-state automata (DFA). If you can make a NFSA that recognizes the language, you can convert it to a DFA. Have a look here for more information on how to do that.

In this particular case, I believe that that language cannot be represented even by a NFA, as it would require an infinite number of states to represent the different values of *i*, *j* and *k* (as FSA do not have "memory" so a machine cannot remember that it's counted *i* a's to count that many b's).

---
Tags: automata
---


# Question
Title: Present syntax rules in a more succinct way
I am resuming syntax rules for a small language:

\begin{eqnarray\*} e\_C &::=& \epsilon \mid constant \\ \textit{prefix-op} &::=& - \\ \textit{infix-op} &::=& + \mid - \mid * \\ e\_E &::=& e\_C \mid \textit{prefix-op} \\; e\_E \mid e\_E \\; \textit{infix-op} \\; e\_E \mid \textit{function}\_E (e\_{E,0}, e\_{E,1},\ldots) \mid \textit{specialE} \\ e\_V &::=& e\_C \mid \textit{prefix-op} \\; e\_V \mid e\_V \\; \textit{infix-op} \\; e\_V \mid \textit{function}\_V (e\_{V,0}, e\_{V,1}, \ldots) \mid \textit{specialV} \end{eqnarray\*}

The expressions $e\_E$ and $e\_V$ have something common: $e\_C$. Some of their operators look same: $\textit{prefix-op}$ and $\textit{infix-op}$. Their functions $\textit{function}\_E$ and $\textit{function}\_V$ are 2 different sets, and $\textit{specialE}$ and $\textit{specialV}$ are totally different.

I am wondering if it is still possible to present this syntax more succinct, more compact in a conventional way... Could anyone help?

# Answer
> 0 votes
Van Wijngaarden grammars are a way to handle this problem. It would be something like:

```
KIND : e ; v .

e KIND : e c ; prefix-op, e KIND ; e KIND, infix-op, e e; function KIND (e KIND, ",", e KIND, "," ... ) ; special KIND .

```

(There is no "..." in the formalism, so you'd have either to extend the grammar syntax or express it in another way).

# Answer
> 4 votes
One direct way of solving this problem is to make the syntax rules parameterised, as follows:

\begin{eqnarray\*} e\_{X,Y} &::=& e\_C \mid \textit{prefix-op} \\; e\_{X,Y} \mid e\_{X,Y} \\; \textit{infix-op} \\; e\_{X,Y} \mid Y (e\_{X,Y}, e\_{X,Y},\ldots) \mid X \\ \end{eqnarray\*}

And then to set \begin{eqnarray\*} e\_E &::=& E\_{\mathit{specialE},~\mathit{function}\_E} \\ e\_V &::=& E\_{\mathit{specialV},~\mathit{function}\_V} \\ \end{eqnarray\*}

This is using notation I just invented, and it could probably be reworked, but you get the idea, I hope.

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


title: Origin of quantum complexity theory

text:
# Question
Title: Origin of quantum complexity theory
Who was/were the first person/people to introduce the topic of quantum complexity theory and problem classes like BQP and QMA?

# Answer
> 8 votes
The class **BQP** (see also Complexity Zoo: BQP) was defined by

* E. Bernstein and U. Vazirani. *Quantum complexity theory*. SIAM Journal on Computing **26**, pp. 1411-1473 (1997).

The class **QMA** (see also Complexity Zoo: QMA) was defined by

* A. Kitaev. *Quantum NP*. Talk at AQIP’99: Second Workshop on Algorithms in Quantum Information Processing, DePaul University (January 1999).

which apparently built on the idea of a "quantum proof" suggested by

* E. Knill. *Quantum randomness and nondeterminism.* Technical Report LAUR-96-2186, Los Alamos National Laboratory (1996). \[arXiv:quant-ph/9610012\].

An important relative to **QMA**, which is perhaps more delicate but which in a certain respect is a more exact analogue of **NP** for quantum computation, is the class **QMA1** (Complexity Zoo), in which the completeness constraint is perfect (*i.e.* for *YES* instances, there is a "quantum proof" with acceptance probability 1, albeit for a noiseless quantum computer). This was defined in

There are other interesting quantum classes, of course. If you want an introduction to the subject, a good start would be

* John Watrous. *Quantum Computational Complexity*. Encyclopedia of Complexity and System Science, Springer (2009). \[arXiv:0804.3401\].

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


title: Advice speeds up computations

text:
# Question
Title: Advice speeds up computations
I want to show that reasonable advice can really speed up computation.

Show, that every time-constructible function $t$, there exists a set $S$ in time $\text{DTIME}(t^2) \setminus \text{DTIME}(t)$ that can be decided in linear time using an advice of linear length, $S \in \text{DTIME}(l) / l$ (definition in analogy to $P / \text{poly}$), where $l(n)=O(n)$.

The problem is that I cannot come up with the structure of set.

# Answer
> 2 votes
Hint: Start with a problem in $\mathrm{DTIME}(e^{2t}) \setminus \mathrm{DTIME}(e^t)$.

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


title: execises in computational complexity

text:
# Question
Title: execises in computational complexity
I am trying to get better in proofs and deep understanding of concept of **computational complexity**. Unfortunately, so far, with no success.

In order to get more intuition, I decided to do more exercises, but most of them are still difficult for me.

I am looking for exercises with solutions in field of computational complexity. Sometimes on course pages there are homeworks with solutions.

I am asking if you aware about any decent course on computational complexity with exercises and solutions on course page, please let me know.

# Answer
I had a course held by Jiri Srba a few years ago on basic complexity and computability theory is good, I would say. The second part (Lecture 9 to 15) goes through time and space complexity, shows some important results on the field and has pdf's of both exercises and solutions for each lecture. It is based on the book "Introduction to the Theory of Computation" by Michael Sipser, which also has a good walkthrough of both topics in general.

Link: https://intranet.cs.aau.dk/education/courses/2010/cc/course-plan/ (owned by Aalborg University)

Good luck!
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Handling untrusted string input in printf in C
I stumbled upon the MSDN Best Practices for Code Review.

Under the section “Untrusted Inputs”, I found following which I didn't understand properly. Why is the following considered safe?

```
printf("%s", buffer);

```

What kinds of guarantees does the C language give regarding the behavior of this snippet? Given that both `printf(buffer)` and `printf("%s", buffer)` are accepted by the compiler, why is one considered safer than the other — shouldn't the unsafe version be rejected?

---

Copied following text from the source:

> Untrusted Inputs
>
> If the input buffer comes from an untrusted source, this can result in a security attack, as the input can contain formatting specifiers that will pull data off the stack. Additionally, it can cause buffer overflows by expanding the resulting string beyond expected limits:
>
> `printf(buffer);`
>
> These should always be converted to the following:
>
> `printf("%s", buffer);`

# Answer
*Since you asked on a computer science site, I'll give you a computer science answer. This might not be the most directly helpful from a programmer's point of view, though understanding this will definitely make you a better programmer.*

The first argument to the `printf` function is a `char *`, i.e. a pointer to a byte¹. However, not all pointers to bytes are valid arguments to `printf`. The **type system** of C is not precise enough to express the type of the argument.

It's well-known that the first argument to `printf` must be a **string**. A string, in C, is a zone of memory (i.e. a region of bytes with contiguous addresses) which is not empty and where the last byte has the value 0. The string is designated through a pointer to its first byte. A string is isomorphic to an array of nonzero bytes.

A null pointer, or a pointer value that does not point to a valid object, are not valid first arguments to `printf`. C does not offer any guarantees when a program is invalid. If you pass an invalid argument to `printf` (or any other function), \**the behavior is undefined--. That means the behavior of the program is at the whim of the implementation. It may cause your program to crash. Or to print nonsense. Or to make demons fly out of your nose². Or to execute some code which was specially chosen by the attacker who specified the first argument — in a security context, undefined behavior is typically whatever the attacker has decided it to be (that's what exploit writing is all about).

Not all strings are valid first arguments to `printf`. The most obvious restriction is that the string must be a **format string**. In a format string, the character³ `%` has a special meaning. For example, `"%B"` and `"%0s"` are not valid format strings in standard C. A string which isn't a well-formed format string isn't a valid first argument to `printf`.

It gets worse. Not all valid format strings are valid first arguments to `printf`. For example, the call `printf("%s")` is not well-formed: the format specifier `%s` consumes an argument, but there is none; the behavior of this call is undefined. In practice, in many implementations, `printf` will grab the value at the top of the stack and assume that it's a valid string; this may crash, print out confidential information, print out data that whatever is reading the output of the program won't understand, or any combination thereof.

The type of `printf` is really a **dependent type**: the number and type of subsequent arguments depends on the value of the first argument. This is very far beyond the capabilities of C's type system⁴. Like just about everywhere in C, the onus is on the programmer to write a correct program.

Conceptually, a call like `printf(buffer)` is wrong, because a *buffer* is an arbitrary string, whereas the argument to `printf` must be a printf format. All printf formats are strings (the type of formats is a subtype of the type of strings), but not all strings are printf formats. The call `printf(buffer)` is only valid if the string `buffer` happens to be a printf format with zero arguments. This means no format specified other than `%%`, in standard C; in other words, the valid values of `buffer` in `printf(buffer)` are the strings where every `%` is followed by another `%`.

If you have a string lying around, how do you know whether it's a valid printf format? If the string is a literal written syntactically within the `printf` argument list, then it is very easy for the programmer or a code reviewer to check whether the format is correct. Any good compiler can check the format string and report a compilation error if it is incorrect, too. If the string comes from a variable, verifying that it is correct is a lot more difficult.

The correctness of the `printf` call becomes more and more difficult to ascertain as the value of the format string is specified further and further from the point of use. This is where **trust** comes into play. In order for the program to behave as desired, the format string must be valid for the call. When you claim that your program behaves as desired, you rely on the format string being valid — in other words, you trust the format string. This is only valid if you trust the entity where the format string originates to provide a valid format string. If the format string comes from a source that is external to your program, that source is often untrusted. Even when it is trusted, tracing that source is a heavy burden, which makes relying on such an external source bad engineering practice.

As a parting piece, why is `printf("%s", buffer)` valid? The `%s` format specifier expects a string, so this call is valid if and only if `buffer` is a valid string. This is as safe as it gets in C.

¹ <sub> It's in fact a little more complicated, because `char` isn't exactly a byte, but for our purposes here it's close enough. </sub>
² <sub> Sadly, many computers lack the hardware device that would make this very educational behavior possible. </sub>
³ <sub> By “character”, I mean the byte whose interpretation in the execution character set is the `%` (percent) character. </sub>
<sub> There are languages where `printf` is provided and has a type that describes its behavior. The obvious way to do it is in dynamically typed languages like Lisp, Perl, etc., where the behavior of `printf` if the arguments are not well-formed is to signal an error. OCaml typechecks `printf` statically; it requires that the format string be known at the compile time, as the compiler parses it and deduces the type of the remaining arguments. </sub>
> 7 votes

# Answer
buffer might contain a %n character, which could cause malicious memory writes.

See http://www.kernel.org/doc/man-pages/online/pages/man3/sprintf.3.html or man 3 printf for more details.
> 0 votes

---
Tags: programming-languages, memory-management, security, typing, c
---


# Question
Title: Undecidability of the following language
So we can prove that the language say $A = \\{ \langle M,w \rangle \mid \text{M is TM that accepts } w^R \text{ whenever it accepts } w \\}$ is undecidable by assuming it is decidable and use that to construct a $TM$ deciding $A\_{TM}$. So by contradiction $A$ is undecidable. But what if the language was $\\{ \langle M,w \rangle \mid \text{M accepts } w \text{ but on input } w^R \text{halts and rejects} \\}$?

I was thinking to prove that it's r.e, we can construct a Turing recognizer, say $K$, which recognizes this language by simulating $M$ on $w$ and do whatever $M$ does. But how does the machine know what's $w$ and $w^R$? Non determinism maybe? Or am I looking at it the wrong way?

And to prove that it's undecidable would we use the same approach as that for $A$?

# Answer
> 1 votes
Let $ A = \\{\langle M, w \rangle \mid M \text { is a TM, } M \text { accepts } w \text { and on input } w^R \text { halts and rejects} \\} $.

We prove that $A$ is not decidable by showing $\text{HALT}\le\_m A$. The reduction works as follows. Let $\langle M, w \rangle $ be an instance of $\text{HALT}$, then we construct a Turing machine $M'$ based on $M$ and $w$. Let $M\_{01}$ be some TM that accepts $01$ and rejects all other inputs. The TM $M'$ on input $v$ works now as follows

1. $M'$ simulates $M(w)$
2. When the simulation is finished simulate $M\_{01}(v)$ and return the result of the simulation

The reduction maps $\langle M, w \rangle$ to $\langle M', 01 \rangle$.

We have now $$ \begin{align} \langle M, w \rangle \not \in \text{HALT} & \Rightarrow M' \text{cycles on every input} \\ & \Rightarrow \langle M', 01 \rangle \not \in A \end{align} $$ and \begin{align} \langle M, w \rangle \in \text{HALT} & \Rightarrow M' \text{acts as } M\_{01} \\ & \Rightarrow M' \text{ accepts } 01 \text{ and rejects } 10\\ & \Rightarrow \langle M', 01 \rangle \in A \end{align}

# Answer
> 2 votes
You can construct a recognizer that simply simulates M on w and then simulates M on $w^R$. This will halt in finite time for all that are in A (by definition), and then you can accept if the first simulation accepted and the second rejected. That suffices for the language being recognisable (recursively enumerable).

I'm not sure what you mean by "how does the machine know what's $w$ and $w^R$ ?" w is part of the input pair, and w^R is easily generated from it. The way you've defined the language A, you don't have to worry about guessing which is the one that M should accept and which is the one it should reject. But if the language was such that *either* M accepts w and rejects in finite time w^R *or* M rejects w in finite time and accepts w^R, then it's still easy. You do the same thing and accept if exactly one of the two simulations accepts, without caring which one.

I don't actually know a "standard" proof that $A$ is undecidable. But to prove your new language undecidable, I'd make a decider for A\_TM that on input produces M' that rejects all other input than w and behaves as M on w. M' definitely rejects $w^R$ in finite time, so will be accepted by the decider for your language iff M accepts w. I imagine to prove $A$ undecidable you do the same thing but make M' accept all other strings, so it definitely accepts $w^R$ and accepts w iff the hypothetical $A$ decider accepts.

# Answer
> 0 votes
This is what I had mind to prove it's undecidable.

Let $ A = \\{\langle M, w \rangle \mid M \text { is a TM, } M \text { accepts } w \text { and on input } w^R \text { halts and rejects} \\} $

Assume $A$ is decidable. Let $H$ be a $TM$ deciding it.

Construct $TM$ $K$ deciding $A\_{TM}$ as follows

$K$: ''On input $ \langle M, w \rangle :$

$ \hspace {20 mm}$ -Run $H$ on input $ \langle M, w \rangle $

$ \hspace {20 mm}$ -If $H$ accepts, then accept

$ \hspace {20 mm}$ -If $H$ rejects, then reject.''

Now $K$ decides $A\_{TM}$ as it always accepts or rejects based on $H$ which will always accept or reject as it is also a decider.

$\Longrightarrow A\_{TM}$ is decidable which is a contradiction.

$\Longrightarrow A$ is undecidable.

Is this right?

---
Tags: turing-machines, undecidability
---


# Question
Title: Finding the element that occurs the most in a very large file
I've heard this interview question asked a lot and I was hoping to get some opinions on what good answers might be: You have a large file 10+ GB and you want to find out which element occurs the most, what is a good way to do this?

Iterating and keeping track in a map is probably not a good idea since you use a lot of memory, and keeping track as entries come in isn't the greatest option since when this question is posed the file usually already exists.

Other thoughts I had included splitting the file to be iterated through and processed by multiple threads and then have those results combined, but the memory issue for the maps is still there.

# Answer
When you have a *really* large file and *many* elements in it, but the most common element is very common -- occurs $\> 1/k$ fraction of the time -- you can find it in linear time with space $O(k)$ words ( the constant in the $O()$ notation is very small, basically 2 if you don't count the storage for auxiliary things like hashing). Moreover, this works great with external storage, as the file is processed in sequence one element at a time, and the algorithm never "looks back". One way to do this is via a classical algorithm by Misra and Gries, see these lecture notes. The problem is now known as the heavy hitters problem (the frequent elements being the heavy hitters).

The assumption that the most frequent element appears $\> 1/k$ fraction of the time for $k$ a small number may seem strong but it is in a way necessary! I.e. if you will have sequential access to your file (and in case the file is huge random access will be too expensive), any algorithm which always finds the most frequent element in a constant number of passes will use space linear in the number of elements. So if you don't assume something about the input you cannot beat a hash table. The assumption that the most frequent element is very frequent is maybe the most natural way to get around the negative results.

Here is a sketch for $k = 2$, i.e. when there is a single element that occurs more than half the time. This special case is known as the majority vote algorithm and is due to Boyer and Moore. We will keep a single element and a single count. Initialize the count to 1 and store the first element of the file. Then process the file in sequence:

* if the current element of the file is the same as the stored element, increase the count by one
* if the current element of the file is different from the stored element, decrease the count by one
* if the updated count is 0, "kick out" the stored element and store the current element of the file; increase the count to 1
* proceed to the next element of the file

A little bit of thinking about this procedure will convince you that if there exists a "majority" element, i.e. one that occurs more than half the time, then that element will be the stored element after the whole file is processed.

For general $k$, you keep $k-1$ elements and $k-1$ counts, and you initialize the elements to the first $k$ distinct elements of the file and the counts to the number of times each of these elements appears before you see the $k$-th distinct element. Then you run essentially the same procedure: an element's count is increased each time it is encountered, all element counts are decreased if an element that is not stored is encountered, and when some count is zero, that element is kicked out in favor of the current element of the file. This is the Misra-Gries algorithm.

You can of course use a hash table to index the $k-1$ stored elements. At termination, this algorithm is guaranteed to return any element that occurs more than $1/k$ fraction of the time. This is essentially the best you can do with an algorithm that makes constant number of passes over the file and stores only $O(k)$ words.

One final thing: after you found $k$ candidate "heavy hitters" (i.e. frequent elements), you can make one more pass over the file to count the frequency of each element. This way you can rank the elements between each other and verify whether all of them occur more than $1/k$ fraction of the time (if there are less than $k-1$ such elements, some of the elements returned by the algorithm might be false positives).
> 6 votes

# Answer
The obvious answer is of course to keep a hash map and store a counter of the occurrence of elements as you move through the file as Nejc already suggested. This is (in terms of time complexity) the optimal solution.

If however, your space requirements are tight you can perform an external sort on the file and then find the longest consecutive run of equal elements. The following should have a constant memory footprint and can be done in $\Theta(n\log{n}).$
> 3 votes

# Answer
If the most common element is more common than the next common element by a substantial margin, and the number of different elements is small compared to the file size, you can randomly sample a couple of elements and return the most common element in your sample.
> 1 votes

---
Tags: algorithms, arrays
---


# Question
Title: Show that approximation ratio for a convex hull algorithm is $\pi/2$
**Facts:** n points in the plane, each has one of k colors, all k colors are represented.

**Problem:** You wish to select k points, one of each color, such that the perimeter of the convex hull is as small as possible.

**Greedy algorithm:** For each point p, for each color c not equal to p, select the point of color c closest to p. In the end, choose the point set that has a convex hull with the smallest diameter (diameter is the distance between the two points furthest apart.)

Why is the approximation ratio $\pi/2$?

This was an exercise on my graduate level algorithms exam. We were only given a few lines to answer so it should be simple enough, but I do not know where to start.

# Answer
Here is a suggestion as to where to start. Suppose that the optimal solution has diameter $D$. Its optimal value is at least $2D$. If you could somehow show that the set selected by the greedy algorithm has diameter $d \leq D$, then it would follow that its value is at most $\pi d \leq \pi D$.
> 3 votes

---
Tags: algorithms, approximation, greedy-algorithms
---


# Question
Title: Why does every member $f(n) \in \Theta(g(n))$, and $g(n)$ have to be asymptotically non-negative?
The following is an excerpt from CLRS:

> The definition of $\Theta (g(n))$ requires that every member $f(n) \in \Theta(g(n))$ be asymptotically nonnegative, that is, that $f(n)$ be nonnegative whenever n is sufficiently large. (An asymptotically positive function is one that is positive for all sufficiently large $n$). Consequently, the function $g(n)$ itself must be asymptotically nonnegative, or else the set $g(n)$ is empty.

Intuition suggests that having one function with a positive domain while the other with a negative one perverts the purpose of asymptotic analysis (a measure of the order of growth) as the positive function can be an upper asymptotic bound of the negative function simply on merit of it being positive, even in cases where the negative function grows faster.

In cases where *both* functions have negative domains, asymptotic analysis would still be a valid measure of the order of growth, making the restriction of both functions having to be positive appear useless.

# Answer
Mostly for convenience's sake. Since big-theta notation specifically tends to be used mostly for algorithmics (as opposed to $O()$ and especially $o()$, which make occasional appearances in more 'traditional' mathematics for talking about goodness of estimates) and is generally used to measure 'usage' quantities of some sort (e.g. CPU cycles, memory, comparisons, etc) there's generally little lost by requiring the quantities involved to be non-negative, and it simplifies some of the definitions and results.

Note that unlike with $\Theta()$, the definitions of $O()$ and $o()$ are often phrased in terms of absolute value, making this point moot - can you see why that idea doesn't make sense for $\Theta()$?
> 4 votes

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


# Question
Title: Theoretical CS and Math - self-study recommendations
I am a non-CS grad and my field of study is unrelated to CS. However, as part of a larger plan to become a computer scientist, I want to obtain a solid background in theoretical computer science and math as it relates to CS. I did a plenty of research and selected the following best/really good books on the topic of CS and math and would like to ask for your opinions on:

* Completeness of topics covered (please recommend anything I've missed)
* Overlap of material covered / overkill area (please recommend books that should be removed from the list)
* Order to study the books (I listed in the order that I think they should be studied)

The list feels excessively long, so I would appreciate recommendations to remove some books, without the loss of the core knowledge require for CS.

So, the books are:

1. Mathematician's Delight by W. W. Sawyer
2. How to Prove It: A Structured Approach by Daniel J. Velleman
3. How to Solve It: A New Aspect of Mathematical Method by G. Polya
4. An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson
5. Foundations of Computer Science by Al Aho and Jeff Ullman (http://i.stanford.edu/~ullman/focs.html)
6. Concrete Mathematics: A Foundation for Computer Science by Graham, Knuth, and Patashnik
7. Introduction to the Theory of Computation by Michael Sipser
8. Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
9. Computational Complexity: A Conceptual Perspective by Oded Goldreich
10. Computational Complexity: A Modern Approach by Sanjeev Arora, Boaz Barak
11. A Course in Combinatorics by J. H. van Lint, R. M. Wilson
12. Computability: An Introduction to Recursive Function Theory by Nigel Cutland
13. Computers and Intractability: A Guide to the Theory of NP-Completeness by M.R. Garey, D.S. Johnson
14. Theory of Recursive Functions and Effective Computability by Hartley Rogers
15. Inequalities by G.H. Hardy, J. E. Littlewood, G. Polya
16. Mathematical Logic: A Course With Exercises (Part I): Propositional Calculus, Bookean Algebras, Predicate Calculus by René Cori, Daniel Lascar
17. Mathematical Logic: A Course With Exercises (Part II): Recursion Theory, Godel's Theorems, Set Theory, Model Theory by René Cori, Daniel Lascar

# Answer
Your list is extremely problematic.

To start with, I would flatly skip books 6,11,12,14,15,16,17: Books 6, 11 and 15 are general mathematics which is not really needed unless you become a *theoretical* researcher. Books 12 and 14 cover recursion theory which is not computer science (even though it deals with computability!). Books 16 and 17 cover advanced topics in logic, whereas you only need to know very basic logic.

Out of books 1,2,3, I would choose just one to serve as a general introduction to mathematics and proofs.

Books 5,7,8,9,10,13 cover several subjects: automata theory, algorithms, and complexity theory. Let me suggest that you follow Sipser (Book 7) for automata theory and complexity theory, and Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein ("CLRS") for algorithms.

Book 4 deals with functional programming. While my computer science education has never included any courses on this subject, it is fair to say that many researchers in theoretical computer science count functional programming as part of the essential foundations.

Summarizing: what you remain with is

* One of books 1-3 (or any comparable "introduction to proof" text)
* CLRS
* Book 4 (functional programming)
* Book 7 (automata theory and complexity theory)
> 11 votes

# Answer
You might also consider taking advantage of some of the many online courses available. For example, both Stanford and MIT offer (free) online courses in computer science, and I think there are many others available as well.

As far as books go, I second most of Yuval's recommendations, except that CLRS is a great reference, but a little overwhelming as an introductory book to just sit down and read through. For a first pass at the algorithms portion, I might recommend Algorithms by Dasgupta et al.. The previous link is to the free online pre-print, but it's also pretty cheap to buy in paperback.
> 5 votes

# Answer
The references you are suggesting would make a "very" theoretical computer scientist. but I honestly dont find any benefit reading all these books if you are from a non-CS degree. This of course all depends on what you need.

I find some books such as Book 14, 15, 16, 17 are not intended to computer scientists. Book 3 is verbose. It is just general for any student. Therefore I assume book 1 and 2 are the same.

For me - being in your same situation as not originally a computer scientist (but instead an electrical/computer engineer) - I propose two initial directions:

* algorithms design and analysis, (many people suggest the *CLRS Introduction to Algorithms*. It is a great reference, but I am really not a fan of it and initially it was a bet harder to understand it and sometimes very verbose. I suggest though that you follow its table of contents, and from there you check online courses for clearer references).

--- make sure to master a programming language to IMPLEMENT the algorithms and data structures you learn - therefore, I suggest the series of *Algorithms, of Sedgewick* (amazing !)

--- ADDED: I also suggest this book: Combinatorial Algorithms: Generation, Enumeration, and Search by D. Kreher. This is a very nice book. Will give you a different prespective to many issues in algorithms.

* combinatorics (especially graph theory), *A Course in Combinatorics by J. H. van Lint, R. M. Wilson*, is good. There exist many other references. Usually any well-known combinatorics book is enough - everything else you'd get from additional references from the internet. I personally liked: peter j cameron combinatorics, and Bondy and Murty Graph Theory.
* a bet of probability (always necessary). It is striking that many fields in science do not use probability. But believe me, all you have to know are the basics.

Then: Many researchers calling themselves theoretical computer scientists focuses so much on theory of computation (automota and others). There are some good books for this (See Yuvul Filmus post),

Aho and Ullman is good (actually all books of Ullman are good). Make yourself comfortable with compiler design (see http://infolab.stanford.edu/~ullman/ullman-books.html).

After that: it all depends on what you want to do. Different directions you can take: 1) databases, 2) pattern recognition and data mining, 3) distributed algorithms, 4) foundation of programming languages, 4) randomize algorithms, and many others. \[each of which requires another post\] **but try to have an idea about all !**

**The general idea: if you are new to CS, then make yourself comfortable with as many CS sub-domains as possible. Restricting yourself to "theory" will make you lose much of CS creativity ! ** (my opinion)
> 2 votes

---
Tags: books
---


# Question
Title: Calculating traversal position of a node in a full binary tree, given its path
Given a path down a *full* binary tree to a node (for example, a sequence of $1$s and $0$s, $0$ representing "go left" and $1$ representing "go right"), how would one find the position of the node in the preorder traversal. In other words the $i$th node in the preorder traversal will end up with at this node.

Obviously something better than brute force would be nice.

# Answer
Essentially the algorithm is:

1. Each time you go left, you add one.
2. Each time you go right, you add the size of the left sub-tree, *and* you add one.

The size of a full binary tree can be calculated as $2^{h+1}-1$. Thus, the height of the left sub-tree can be calculated by $2^{h\_{\text {subtree}}+1}-1=2^{h-l+1}-1$ where $l$ is the level of the left sub-tree.

```
#WARNING: non tested, python-ish

def calc_tree_size(tree_height):
  return (1<<(tree_height+1)) - 1

def inorder_traversal_position(tree_height,path):

  result = 0

  for level in range(len(path)):
    if path[level] == 0:
      #If we go left,

      #Preorder goes left after visiting a node.
      #Add one for the node we just visited.
      result += 1
    elif path[level] == 1:
      #If we go right,

      #Preorder normally goes left, visiting all the nodes
      # in the left sub-tree before going right.
      #Add the number of nodes in the left sub-tree.

      left_subtree_level = level + 1
      left_subtree_height = tree_height - left_subtree_level
      left_subtree_size = calc_tree_size(left_subtree_height)

      result += left_subtree_size

      #Add one for the node we just visited.
      result += 1

    return result

```
> 2 votes

---
Tags: binary-trees, trees, graph-traversal
---


# Question
Title: Validating a sequence of points as a convex hull
I'm familiar with the classical convex hull calculation algorithms. The lower bound for computing the CH of a set of points $P$ is $n\log(n)$.

However, what if I'm given a sequence of points and told they form a CH? One check is to "walk the points" in order and check for "left turns" (CCW). However, this doesn't handle the case of self-intersections (you could imagine a counter-example that "winds around starting from the center" making only CCW turns.

I've been told this "validation" can be done in $O(n)$ time, but to check for self-intersection naively, I see $O(n^2)$ time.

My next thought is to run Graham's Scan. Since the points are presumably on a CH, it takes $O(n)$ to find the lower left point, say $p\_0$, and from there, **I THINK you can guarantee** that all points $p\_1, p\_2,\dots,p\_n$ are already sorted by angle between $p\_0$ and $x$-axis. As you move the three-point-window forward along the hull, the points ahead are still properly sorted. The reasoning for $O(n)$ then follows per normal reasoning for Graham's scan, minus the need for $O(n\log n)$ sorting.

1) Is my assumption, in bold, correct?
2) Is there an easier method that wouldn't involve running Graham's scan?

# Answer
The answer is easier than you think. As you remarked you should check if you take always CCW or CW turns. But of course, this might result in a curve that is self-intersecting. But you can detect this easily, just sum up then angles of the "turns". Since your curve is closed this angle sum is a multiple of $2\pi$. If it *winds up* exactly once it does not self-intersect. In this case the angle sum is $2\pi$. Thus you are left with checking, if the angles sum up to $2\pi$.

See this paper for analogues in higher dimension.

Interestingly, in the smooth version (CCW turn is here positive sectional curvature), for a 1d curve you still have to check the winding number, but by an old theorem of Hadamard, if higher dimensional (immersed) manifolds have positive sectional curvature everywhere, then they enclose a *convex* body.
> 3 votes

---
Tags: computational-geometry
---


# Question
Title: Proofs based on narrowing down sets of possibilities
Consider the argument made in this question based on the comparison sorting lower-bounds proof, which runs as follows.

First, the comparison sorting lower-bounds proof was recited:

1. For $n$ distinct numbers, there are $n!$ possible orderings.
2. There is only one correct sorted sequence of the $n$ numbers.
3. We are given that comparison ($\<$) is the only operation we have that can narrow down the $n!$ possible orderings, and each comparison has only two possible outcomes.
4. So $\log\_2(n!)$ comparisons are required.

Then, the argument was generalized:

1. Define a space of input possibilities
2. Define the goal space, a subset of the input space
3. Define the amount of information that is gained at each step of the computation
4. Calculate the information difference between the space of possibilities and the goal space and divide by the information gain per step to yield the lower bound on the number of steps.

Both arguments above rely on information arguments to prove a lower bound on the number of steps.

Question: are there proofs and/or proof strategies like the above which:

1. prove lower bounds,
2. define an input space,
3. define a goal space which is a subset of the input space, and
4. do not rely on information arguments?

# Answer
> 3 votes
The more general argument is an example of an *adversary argument*. A nice example is a lower bound for the number of comparisons needed to find the minimum and the maximum *at the same time*. Said number is $\lceil 1.5 n \rceil - 2$. You can try to construct the algorithm and prove its optimality, or just have a look at the paper.

---
Tags: proof-techniques, lower-bounds
---


# Question
Title: Does the DFS algorithm differentiate between an ancestor and a parent while computing back edges?
Below is the general code for DFS with logic for marking back edges and tree edges. My doubt is that back edges from a vertex go back and point to an ancestor and those which point to the parent are not back edges (lets assume undirected graph). In an undirected graph we have an edge back and forth between 2 vertices $x$ and $y$. So after visiting $x$ when I process $y$, $y$ has $x$ as an adjacent vertex, but as its already visited, the code will mark it as a back edge. Am I right in saying that? Should we add any extra logic to avoid this, in case my assumption is valid?

```
DFS(G)
    for v in vertices[G] do
         color[v] = white
         parent[v]= nil
         time = 0

    for v in vertices[G] do
        if color[v] = white then
            DFS-Visit(v)

```

Induce a depth-first tree on a graph starting at $v$.

```
DFS-Visit(v)
    color[v]=gray
    time=time + 1
    discovery[v]=time
    for a in Adj[v] do
        if color[a] = white then
            parent[a] = v
            DFS-Visit(a)<br>
            v->a is a tree edge
        elseif color[a] = grey then
            v->a is a back edge
    color[v] = black
    time = time + 1

```

white means `unexplored`, gray means `frontier`, black means \`processed'

# Answer
> 3 votes
The algorithm you describe works on *directed graphs*. In such a graph, an edge $(u, v)$ does not imply an edge $(v, u)$. Your confusion arises because you are probably trying it for undirected graphs.

For undirected graphs, the algorithm has to be modified slightly. Again, the modification will depend on whether this graph is a simple undirected graph or a multigraph. I will use the same variable names used that you use in your algorithm:

* Simple Graph: When checking the colour of the adjacent vertex $a$ of a vertex $v$, if the colour is grey *and* the vertex $a$ is not a parent of $v$, then it is a back-edge. Ignore if $a$ is the parent.
* Multigraph: If the colour of $a$ is grey *and* it is a parent of $v$, you need to check if $a$ occurs more than once in the adjacency list of $v$. This indicates multiple edges between $a$ and $v$, and one of them can be considered as a tree edge while the rest will be back edges. If there is only one edge between the two, it is a tree edge and has already been considered, so do nothing. Loops (edge from $v$ to $v$, that is, $a$ = $v$) are always back edges.

You are basically finding a spanning tree of the graph, and so try to go by the definitions and see how the algorithm should be modified for various cases. And how a tree-edge or a back edge are informally defined for various types of graphs.

# Answer
> 1 votes
Usual definitions of *back edge* and *tree edge* is that they return to a node previously visited or that they go straight to a new node, respectively. Formally speaking, these definitions result from understanding graphs as spanning trees, so that my definitions are rather informal but I hope they suffice and are understandable.

Now, wrt the previous definitions, even if you are exploring an undirected graph, returning to the parent happens through a *back edge* since that node was already part of the current path ---and, of course, of the current spanning tree. Note that spanning trees are required to contain all nodes of the original graph, but usually a number of edges are removed.

Hope this helps,

---
Tags: algorithms, graphs
---