# Question
Title: How to find specificity of a regex match?
I'm thinking about a routing system. Imagine I have the two following regexes

* pathpart1/pathpart2 =\> specific match that routes to controller1
* .\* =\> catch-all that routes to controller2

And I let them match on a URL, e.g. 'pathpart1/pathpart2'.

They both match, but I would want to give prevalence to the most specific regex, i.e. the regex where **the cardinality of all possible matches of that regex** is the lowest.

> Is there a good way to calculate that the first regex has a low cardinality on its match-set (so I want to to go with that match) and the second has a very high cardinality on its match-set (i.e. it is completely not specific, so a match is basically a catch all last resort)...?

I do not know upfront which routes are registered with the router, so I can't loop over them in order of cardinality by hand (i.e. low cardinality first, and the catch-all last if all others don't match).

# Answer
There are two angles I see to define "specifity" in this context.

1. Specifity of a regular expression $r$ that matches input $w$ is the (inverse of the) number of words of length $|w|$ that also match $r$.
2. Specifity of a regular expression $r$ that matches input $w$ is (the ratio of) the (maximum) number of symbols of $w$ that are matched by non-wildcard symbols in $r$ (and $|w|$).

The first option follows your idea: choose among all matches the regular expressions that matches the fewest others. Since there are in general infinitely many matching strings, we have to restrict ourselves to a certain length, or a finite set of lengths.

The second option follows another approach. If the input string is well described by a given expression, long parts of it should be (more or less) explicitly described in the regular expression. For example, $(aa|ab)+.^\*bba$ is a more specific match for $aaababaababababba$ than $.^\*$.

### Option 1

In this case, we have to count all words in $\mathcal{L}(r)$ that have length $n$. Luckily, this is easy once we have an unambiguous, regular grammar¹ $G$ for $\mathcal{L}(r)$. See here how this can be done.

### Option 2

Let's assume we have an unambiguous regular expression (for instance by specifying lazy wildcards). In that case, we can translate the regular expression into a DFA. Run the word through it and count how many non-wildcard transitions are taken.

If the expression is ambiguous, we can do the same with the corresponding NFA if we explore *all* possible paths.

---

1. Convert $r$ to an $NFA$, determinise, convert to right-regular grammar. All conversions are standard and algorithmically feasible (if not necessarily efficient).
> 3 votes

# Answer
I don't know if you would consider this a "good" way, but the naive approach would be to count the matches of each regex, and compare.

This is not too expensive: In order to find a match, you run a DFA for $r$ (where $r$ is the regex in question) starting at every index of the input. You then wait for an accepting run. Usually, we optimize this algorithm such that if the two runs of the DFA (from different indices) are in the same state at index $i$, then we "unify" them to a single run. The runtime is $O(n)$, where $n$ is the length of the word, assuming $r$ is fixed.

This can be modified to an algorithm that counts matches by simply counting the number of DFAs that are in the same state at each index. Then, whenever an accepting state is reached, you sum the number of runs to this state and add it to a running total. This still takes $O(n)$ time, and only adds counters for each state.

Note that this crucially uses a DFA and not an NFA. Indeed, if you start with an NFA for $r$, this is a problematic solution, since you will overestimate the number of matches.
> 2 votes

# Answer
The gist of the problem, I think, is to properly define a partial order on regexps. Since the language accepted by them is potentially infinite, using cardinality seems very difficult.

However, the problem can be broken down to comparing accepted input at each step of the processing of the input string. The comparison predicate for character sets can be built upon cardinality comparison.

Regexps may be (and usually are) encoded, as you know, as DFAs, which necessarily contain for every state the accepted input set. An efficient solution could then be, having access to the internal data of a regexp compiled down to a DFA, to compare these input sets at every step of the parsing of the input string. However, the suvcessive input set accepted by a regexp get scattered on different states, which render comparison difficult in general, as opposed to a discrete input string. The resulting partial order would be specific to the string (or to the class of strings following the same path in the DFA).

You can also establish a partial order on regular expressions by computing their derivatives against the input string, but this will be slower in practice than using the DFA data.

Here's a quick rundown of what it's all about. A regexp derivative $r'$ of a regexp $r$ is, given an input letter, the regular expression which will behave as $r$ after having received that input letter. This notion can easily be expanded to a full input set, by computing the union

Regular Expressions derivatives are defined in terms of the derivatives of their operators, which I will recall here:

* concatenation (elided in practice, but noted $.$ here)

for an expression $r = \alpha . e$ where $\alpha$ is a letter of the alphabet, the derivative with respect to $\alpha$ of $r$ is $e$, and the null match otherwise.
* kleene star, noted $\*$ (repetitions)

An expression $r\* = (\alpha . e)\*$ has for derivative $r' = e | r\*$ wrt. $\alpha$
* the alternative operator, noted $|$

The derivative of the expression $r = a l b$ is $r' = a' | b'$ with the input set being the union of the input set of $a'$ and $b'$.
* ranged repetitions, noted $\\{a,b\\}$, where $a$ and $b$ are the lower and upper bounds

For $r\\{a,b\\}$, the derivative will be (similarily to $\*$) $r' | r\\{a-1,b-1\\}$

Other operators ($?$,$+$) can be easily defined from these operators.

The idea to compare the specificity of two regexps is to recursively compute the derivatives of both regexps on the input string, and compare their input sets (which have to be infered from the regexps, but this can be done, as demonstrated in this article, to actually construct the corresponding DFA).
> 1 votes

---
Tags: algorithms, regular-expressions, strings
---


# Question
Title: Deciding whether a Language is Context-free/Regular/Non Context-Free
I need some help with deciding if a given language is regular, context-free or not context-free.

Lets' say I have the following languages over the alphabet $\mathcal{A} = \\{a,b,c,d\\}$: $$ \begin{align} L\_1 &= \\{ w \in \mathcal{A}^\* \mid \text{\\(\\#a(w)\\) is even and \\(\\#b(w) = 1 \mathrel{\mathrm{mod}} 3\\) and \\(w \not\in \mathcal{A}^\* abc \mathcal{A}^\* \\)} \\} \\ L\_2 &= \\{ w \in \mathcal{A}^\* \mid \text{\\(\\#a(w)\\) is even and \\(\\#b(w) \lt \\#c(w)\\)} \\} \\ L\_3 &= \\{ w \in \mathscr{A}^\* \mid \\#a(w) \lt \\#b(w) \lt \\#c(w) \\} \\ \end{align} $$

This is my solution:

$L\_1 = L\_4 \cap L\_5 \cap L\_6$ where $$ \begin{align} L\_4 &= \\{ w \mid \text{\\(w\\) does not have a substring \\(abc\\)} \\} \\ L\_5 &= \\{ w \mid \\#a(w) \text{ is even} \\} \\ L\_6 &= \\{ w \mid \\#b(w) = 1 \mathrel{\mathrm{mod}} 3 \\} \\ \end{align} $$

A DFA can be constructed for $L\_5$, because $L\_5$ does not need infinite memory, so $L\_5$ is regular. For $L\_6$ the same reasoning as above. And for $L\_4$ we can construct a DFA that simply does not accept $abc$, hence regular.

$L\_1$ is regular because regular languages are closed under intersection.

For $L\_2$ we can divide the language thus: $L\_2 = L\_5 \cap L\_7$ where

$$ \begin{align} L\_5 &= \\{ w \mid \\#a(w) \text{ is even} \\} \\ L\_7 &= \\{ w \mid \\#b(w) \lt \\#c(w) \\} \\ \end{align} $$

We now that a DFA can be constructed for $L\_5$, hence $L\_5$ is regular. $L\_7$ is context-free because we can construct a PDA where the stack counts the number of $a$s and $b$s.

$L\_2$ is hence context-free because the intersection of a regular language and a context-free language result in a context-free language.

For $L\_3$ we can see that it's not context-free because where are limited to 1 stack.

Is my reasoning right?

# Answer
> 1 votes
Your reasoning for the positive statements seems sound to me, although they lack some detail if formal proofs are required. In particular, you might at least want to give the automata for $L\_4,L\_5,L\_6$ and $L\_7$; especially the latter can be considered non-trivial, depending on your level of expertise.

You lack proofs for

* $L\_2 \notin \mathrm{REG}$ and
* $L\_3 \notin \mathrm{CFL}$.

Both are true and straight-forward to prove; you find all you need in our reference questions for the regular and context-free case, respectively.

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


title: Non-trivial runs of Prim's algorithm

text:
# Question
Title: Non-trivial runs of Prim's algorithm
What does it mean when we say that a run of Prim's algorithm is *trivial*? What are example graphs for either case, that is with and without trivial runs?

# Answer
Prim's algorithm greedily chooses the smallest edge leaving the set of already connected nodes (until all nodes are connected).

It is not clear what "non-trivial run" means here; I propose this: a run of Prim is trivial if in every step, it can choose the smallest available edge. This would happen on linear chains, for instance.

With this "definition", a non-trivial run is one during which the algorithm can not choose a cheap edge because it would create a cycle, but has to take a more expensive one. Here is an example graph:

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

If you start the algorithm with $A$, edge $\\{B,C\\}$ would be the cheapest after having chosen $\\{A,B\\}$ and $\\{A,C\\}$, but it can not be chosen.
> 1 votes

---
Tags: algorithms, terminology, graphs
---


title: Is this NIM game tree correct?

text:
# Question
Title: Is this NIM game tree correct?
I have an assignment to construct a game of Nim (a game in which two players must divide a pile of tokens into two unequal sizes; 6 can be divided into 2 & 4 but not 3 & 3). I was provided a game tree (the same one I find on Google), but I am confused. Shouldn't the first turn of the second player have access to S6, S5, *and* S4 and S3 since 7 can be divided into 4 & 3?

# Answer
No, the game tree is not correct for the description you gave.

If you look a few levels downward, there's the position F(2), which by your description should be a dead end: you can't make a move, since splitting a pile of 2 into non-equal parts is not possible. Yet, the tree gives two options. Your observation that you should be able to move from 7 to 5, 6, or 3+4 is also correct.

I think Hendrik Jan is right, and this tree describes the game where you either take one or two tokens from a pile, and the player who takes the last token wins.
> 2 votes

# Answer
There are many kinds of NIM. The one in the picture is a rather classic example. Take either one or two tokens, the one who takes the last token looses.

Does not sound like the version you suggest. Your game does not state what happens with the divided heaps?
> 3 votes

# Answer
The game that you outline, while it can be handled by the same *Sprague-Grundy Theory* that is used for Nim (and therefore can have a nim-value assigned to every position), is better known as *Grundy's Game*; note that there's no legal move on a heap of size 1 (since it can't be divided into two heaps) and no legal move on a heap of size 2 (since it can't be divided into two unequal heaps). As perhaps a bit more of a curiosity, while it was once conjectured that the game was periodic, its value has now been calculated for more than 30 billion starting heap sizes without any periodicity having been found.
> 3 votes

---
Tags: game-theory
---


# Question
Title: Decreasing runs of inner loop in outer loop
I am trying to determine the worst case runtime of this program:

```
while n > 1
  for i = 1,..,n
    m = log(n)
  n = n/2

```

Obviously the outer loop runs `log(n)` times, because n is halfed after each step.

But the inner for loop is dependent on the decreasing n and I am not quite sure how to deal with that.

A simple bound for it would be `n`, so the whole thing runs in at most `log(n)*n`, but I am sure the inner loop is faster than that.

If I look at each step of the outer loop, I see that the inner loop runs `n,n/2,n/4,..,2` times. So I would say all together the inner loop runs at most `2n` times which is in `O(n)`.

Can I just deduct from that fact that the overall runtime is `O(log(n)+n) = O(n)`?

I am unsure because I am not multiplying anything, which I feel like I should when dealing with multiple loops.

# Answer
When loops are nested, the running time is the amount of time the innermost loop is executed multiplied by the time it takes to execute the body of the loop. In your case, the innermost loop executes $n+n/2+n/4+\dots+1\lt2n$ and we'll assume that computing the $\log$ takes constant time. So the running time is linear in $n$.
> 2 votes

---
Tags: time-complexity, asymptotics, runtime-analysis
---


title: Poker with Bluffing (game theory)

text:
# Question
Title: Poker with Bluffing (game theory)
I'm doing a self-study of Game Theory Evolving by Gintis, and am stuck on problem 4.16 "Poker with Bluffing".

The first question asks "*Show that Ollie has 64 pure strategies and Stan has 8 pure strategies.*". But no matter how I try to approach this, I can't get more then 4 strategies for Stan!

Here is the game tree for the game in question:

The question marks (?) in the figure mean that the payoff depends on who has the higher card.

Here is the game description:

* Two players, each with a deck of three cards: H (high), M(medium) or L (low).
* Each puts \\$1 in the pot, chooses random card
* Ollie (P1) either stays or raises
* Stan (P2) simultaneously also stays or raises
* If both raise/stay - highest card wins the pot (tie - they take their money back)
* If Ollie raises, Stan stays Ollie gets the \\$3 pot.
* If Stan raises and Ollie stays - Ollie gets another chance:
-\> Drop - Stand wins the \\$3 pot
-\> Call - add \\$1 to the pot.

Why does Stand have 8 pure strategies?

# Answer
> 5 votes
Stan has two pure strategies for each type of card. Since there are three types of cards (H, M, L), in total he has $2\times 2\times 2 = 8$ strategies. Here is a list of them:

* Always stay.
* Always raise.
* Stay only if H.
* Stay only if M.
* Stay only if L.
* Raise only if H.
* Raise only if M.
* Raise only if L.

---
Tags: game-theory, board-games
---


# Question
Title: While proving optimality of the A* algorithm, why can we change graphs?
In the original paper of A\* algorithm, *A Formal Basis for the Heuristic Determination of Minimum Cost Paths*, the author proved the optimality of A\* in *Theorem 2*, page 105.

However, I cannot understand the proof. The assumption is that we have a node in $G\_s$ which is not expanded by algorithm A, but in the proof we change the graph to $G\_{n,\theta}$, isn't it a problem?

# Answer
No, it isn't a problem.

The whole idea is that the algorithm doesn't operate on a single graph, but rather on a family of graphs (with costs), determined by what the algorithm knows from the heuristic and the explored nodes. That family is denoted by $G\_{n,\theta}$ in the paper.

The admissibility of the heuristic basically means that the actual graph is amongst the family $\\{G\_{n,\theta}\\}\_\theta$ for some $\theta$.

The proof of Theorem 2 says, that if the other algorithm established that the shortest path form $s$ to $t$ has cost $f(t)$ and $A^\*$ expanded the node $n$ which the other hasn't, it means that the estimate of cost of $s \rightarrow t$ path via $n$ was lower than the actual $f(t)$, which means there is some graph in the $\\{G\_{n,\theta}\\}\_\theta$ family where the shortest path from $s$ to $t$ passes through $n$. Because the other algorithm didn't expand $n$, it is not admissible for the assumed graph family (because that particular graph would break it).

In other words, if the problem was eg. going from Madrid to Paris, the algorithm might have discovered that (for simplicity) you can get to Barcelona and Valencia in 300 km. Then you know the distance to Paris is $\>$1000 km from Valencia, and $\>$800 km from Barcelona. If the other algorithm hasn't expanded Valencia and tells you that the shortest path goes through Barcelona with distance 300 km$+$1100 km (for the stretch Madrid-Barca and Barca-Paris), it hasn't ruled out an (alternative universe) situation where the distance between Valencia and Paris was only 1050 km (and would be therefore shorter).

Apologies for distorting Europe a bit
> 4 votes

---
Tags: algorithms, algorithm-analysis, search-algorithms, correctness-proof
---


# Question
Title: How many minimal spanning trees are there when all edge costs are distinct?
Suppose all costs on edges are distinct. How many minimal spanning trees are possible?

I dont know if this question is supposed to be easy or hard, but all I can come up with is one, because Kruskal's, and any other greedy algorithm should choose all the smallest weighted edges first. Then, if all weights on all edges are distinct, then there are no two equivalently weighted minimum spanning trees if a greedy algorithm is used.

# Answer
Consider Kruskal's or Prim's algorithms to get minimal spanning trees. They consider arcs in increasing order of cost. If all costs are different, the order in which they are added is fixed, and so is the spanning tree constructed. It is unique in this case.
> 10 votes

# Answer
Assume there were at least two distinct minimal spanning trees. What can you deduce?

> Consider an edge $e\_1$ in one tree and the cut it induces. What can you say about the edges that are both in this cut and in the other tree?

The ultimate hint:

> With this knowledge, can you construct a smaller MST?

This is *the* standard argument when working spanning trees (and several other graph problems).
> 4 votes

# Answer
You can give an explicit condition for whether an edge should be in the MST. Consider edge between x and y with weight w. Remove all edges with weights greater than or equal to w. Are x and y still connected? If so, edge e should not be in the MST, otherwise it should.

This isn't qualitatively different to previous answers. It makes sense to prove it using Kruskal's algorithm, but perhaps is an easier statement to think about in the context of uniqueness. More details at: http://tinyurl.com/d9lnb82.
> 0 votes

---
Tags: graphs, spanning-trees
---


# Question
Title: How to write Context Free Grammar with numerical restrictions
I am supposed to write a Context free grammar that generates the language:

$\qquad L(G) = \\{0^{3n}1^{2n}0^{m}1^{m} : n \ge 1, m \ge 1\\}$

I have the rules:

$$S \rightarrow 000S$$ $$S \rightarrow S11T$$ $$T \rightarrow 0T$$ $$T \rightarrow T1$$

This looks correct in terms of the structure of the grammar but I am not sure how to denote how to tell the grammar to terminate at the correct time given the conditions $n \geq 1$ and $m \geq 1$.

# Answer
> 3 votes
First off, your grammar isn't quite right, since there's no way to eliminate $S$; every production with $S$ on the LHS produces a string including $S$, so your grammar generates no (finite) strings at all.

To capture the "greater than or equal to 1" requirement, you should have a rule that produces the smallest permissible string; to handle the $m$ case, this would mean you need a production yielding $00011$. To handle the $n$ case, on the other hand, you'd need a production yielding $01$. Together, this implies that $0001101$ is the smallest string in your language. With the base cases out of the way, you can add other productions to build on this base case.

For your case, you have have a context-free language which is the concatenation of two other context-free languages. If you can make a grammar for the two constituent languages, it's easy to make a grammar for your language:

$$S \rightarrow S\_1S\_2$$

Grammars for the other are easy, too, and you had the right idea:

$$S\_1 \rightarrow 00011 \mid 000S\_111$$

and

$$S\_2 \rightarrow 01 \mid 0S\_21$$

# Answer
> 1 votes
Notice that $L(G)=\\{(000)^n(11)^n0^m1^m\\}$.

Hint: find a grammar for $\\{0^n1^n\\}$

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


# Question
Title: Can a Turing Machine decide if an NFA accepts a string of prime length?
I want to know if the following problem is decidable:

Instance: An NFA A with n states

Question: Does there exist some prime number p such that A accepts some string of length p.

My belief is that this problem is undecidable, but I can't prove it. The decider can easily have an algorithm to figure out if a particular number is prime, but I don't see how it would be able to analyze the NFA in enough detail to know exactly what lengths it can produce. It could start testing strings with the NFA, but for an infinite language, it may never halt (and thus not be a decider).

The NFA can easily be changed to a DFA or regular expression if the solution needs it, of course.

This question is something I've been pondering as a self-made prep question for a final I have coming up in 2 weeks.

# Answer
> 17 votes
The lengths of the strings accepted by a DFA form a semilinear set (like in Parikh's theorem for context free languages), the description of those isn't too hard to come by (essentially splice up all possible cycles of the automaton), and by Dirichlet's theorem any arithmetic progression of the form $a + b k$ with $\gcd(a, b) = 1$ contains an infinitude of primes.

Pulling the above together gives an algorithm to check if your regular (or even context free language) contains strings of prime length. Definitely *not* a simple question, IMVHO...

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


# Question
Title: The space complexity of recognising Watson-Crick palindromes
I have the following algorithmic problem:

> Determine the space Turing complexity of recognizing DNA strings that are Watson-Crick palindromes.

Watson-Crick palindromes are strings whose reversed complement is the original string. The *complement* is defined letter-wise, inspired by DNA: A is the complement of T and C is the complement of G. A simple example for a WC-palindrome is ACGT.

I've come up with two ways of solving this.

**One requires $\mathcal{O}(n)$ space.**

* Once the machine is done reading the input. The input tape must be copied to the work tape in reverse order.
* The machine will then read the input and work tapes from the left and compare each entry to verify the cell in the work tape is the compliment of the cell in the input. This requires $\mathcal{O}(n)$ space.

**The other requires $\mathcal{O}(\log n)$ space.**

* While reading the input. Count the number of entries on the input tape.
* When the input tape is done reading
    + copy the complement of the letter onto the work tape
    + copy the letter L to the end of the work tape
* (Loop point)If the counter = 0, clear the worktape and write yes, then halt
* If the input tape reads L
    + Move the input head to the left by the number of times indicated by the counter (requires a second counter)
* If the input tape reads R
    + Move the input head to the right by the number of times indicated by the counter (requires a second counter)
* If the cell that holds the value on the worktape matches the current cell on the input tape
    + decrement the counter by two
    + Move one to the left or right depending if R or L is on the worktape respectively
    + copy the Complement of L or R to the worktape in place of the current L or R
    + continue the loop
* If values dont match, clear the worktape and write no, then halt

This comes out to about $2\log n+2$ space for storing both counters, the current complement, and the value L or R.

**My issue**

The first one requires both linear time and space. The second one requires $\frac{n^2}{2}$ time and $\log n$ space. I was given the problem from the quote and came up with these two approaches, but I don't know which one to go with. I just need to give the space complexity of the problem.

**The reason I'm confused**

I would tend to say the second one is the best option since it's better in terms of time, but that answer only comes from me getting lucky and coming up with an algorithm. It seems like if I want to give the space complexity of something, it wouldn't require luck in coming up with the right algorithm. Am I missing something? Should I even be coming up with a solution to the problem to answer the space complexity?

# Answer
> 8 votes
**Disclaimer**: *The following algorithm does not use the standard model for sublinear space complexity (see WP:DSPACE), because it writes to the input tape. Furthermore the set of (Watson-Crick) palindromes is not in $\mathsf{DSPACE}(\mathcal{O}(1)) = \mathsf{REG}$. Nevertheless, it's an in-place solution for many practical purposes (e.g. if each letter is a `char` in C).*

To show that a problem has a specific space complexity, one generally needs to come up with an algorithm that has that space complexity. This may require trial and error, but a better approach is to have a good understanding of the problem you are looking at and a good amount of experience in algorithms and complexity.

For this particular example, there is a third algorithm that does not need any additional space and requires $O(n^2)$ time complexity. This algorithm would be constant space.

Hint: why use additional space, when you can use the space occupied by the input?

Hint: zip back-and-forth across the string checking one character at a time – use the state of the Turing Machine to remember which character you are checking and erase characters you've already checked.

# Answer
> 3 votes
The way the question is asked you should come up with an **upper bound** and a **lower bound** on the space complexity.

The first part is usually done by presenting an algorithm for your problem but a reduction **to** some other well studied problem would also work (and indirectly yield an algorithm, too). Since you don't consider a combined complexity (time and space) only the space matters, even if the time increases. So you found an upper bound of $\mathcal{O}(\log n)$.

The second part is usually a lot trickier, but you can easily show that constant space is not enough, because this would make your language regular. Using the pumping lemma with, say $a^lb^{2l}a^l$, where $l$ is the assumed pumping number will do the trick. This still leaves a large gap between $\omega(1)$ and $\mathcal{O}(\log n)$.

I found an exercise (see Exercise 6) which gives some hints. If I interpret their hint correctly, try proving that there are to many different equivalence classes of the Myhill-Nerode relation for each input size. This is similar to the argument that you can't distinguish more than $c\cdot\Gamma^{s(n)}$ strings of length $n$ (where $\Gamma$ is your tape alphabet and $s(n)$ your space complexity). This will give you a lower bound of $\Omega(\log n)$.

---

Note that you don't need to care about the complement of letters since this operation is trivial, so everything that works for ordinary palindromes can be modified with a few more states to solve your problem.

# Answer
> 0 votes
It is extremely likely that the classical time-space tradeoff for palindromes holds also in your case. This result states that a Turing machine recognizing palindromes in space $S$ must take time $\Omega(n^2/S)$, i.e. $$ \textrm{Time} \times \textrm{Space} = \Omega(n^2). $$ In your case, the first algorithm has $TS = \Theta(n^2)$, and the second has $TS = \Theta(n^2\log n)$. One can also show that the lower bound for space is $\Omega(\log n)$. I haven't been able to found what is the best upper bound - that is, whether there is an algorithm using logarithmic space and time $O(n^2/\log n)$, or in general, for what values of $S$ can we achieve time $\Omega(n^2/S)$. As an exercise, you can try finding other, hybrid algorithms interpolating your two algorithms.

---
Tags: algorithms, algorithm-analysis, turing-machines, space-complexity
---


# Question
Title: For regular languages A and B, determine whether B might match early in (A B)
I have two regular languages *A* and *B*, and I want to determine whether there is any pair of strings, *a* in *A* and *b* in *B*, such that (*a* *b*) is a prefix of a string in (*A* *B*) and the left-most match of *B* in (*a* *b*) includes one or more characters from *a*.

Raphael's formulation is good:

> Given two regular language A, B, is there a (non-empty) prefix of a word b in B that is a suffix of a word in A so that the rest of b is a prefix of another word in B?

# Example

For example, let's say I have two regular languages, one which describes some properly escaped HTML text, and one which describes an end tag:

```
A := ([^&<>] | [&] [a-z] [a-z0-9]+ [;])*;
B := "</title";

```

By inspection, I can tell that there is no string (*a* *b*) in (*A* *B*) such that the first match of *B* includes characters from *a* because `"<"` is a prefix of *B* which cannot occur as a suffix of *A*.

But given a different grammar:

```
A' := (A | "<![CDATA[" ("]"? ">" | "]"* [^\]>])* "]]>")*;
B' := "</title" ([^>\"] | [\"] [^\"]* [\"])* ">";

```

then there are strings

```
a = '<![CDATA[</title "]]>"';
b = '</title>';

```

where (*A* *B*) matches `'<![CDATA[</title "]]>"</title>'` and the left-most match of *B* is `'</title "]]>"</title>'` which includes a non-empty suffix of *a* : `'</title "]]>"'`.

# Motivation

*A* in my situation describes the output of an encoder/sanitizer that is derived from a grammar, so an untrusted input is fed to the encoder/sanitizer and I know the output matches *A* by construction.

*B* is a limit condition in a larger grammar that describes how parsers determine where a chunk of an embedded language ends so they can hand it off to a parser for the embedded language.

My end goal is to be able to determine when I can optimize away runtime checks that ensure that it is safe to embed a particular encoded string. For these examples, it would be safe to optimize out the first check, but not the second.

---

Is this a solved problem? Does it have a name? Any pointers appreciated.

# Answer
> 4 votes
If I translate your description properly, here is what you want to ask:

> Given two regular language $A$, $B$, is there a prefix of a word $b$ in $B$ that is a suffix of a word in $A$ so that the rest of $b$ is a prefix of another word in $B$?

Formally:

> Given regular $A$ and $B$, are there $a = wx \in A$ and $b = yz \in B$ so that $xy \in B$?

Deciding this boils down to deciding whether

$\qquad B \cap (\operatorname{suff}(A) \cdot \operatorname{pref}(B) ) = \emptyset$.

Now we employ some closure properties: $\mathrm{REG}$ is closed against right and left quotient, concatenation and intersection, so with

$\qquad \operatorname{suff}(A) = A \backslash \Sigma^\*$ and $\operatorname{pref}(B) = B / \Sigma^\*$

the set we want to check for emptiness is regular, and therefore the check is indeed decidable.

In order to actually *do* this, I suggest you build automata for $\operatorname{suff}(A)$ and $\operatorname{pref}(B)$, concatenate them, intersect the result with the automaton for $B$ and use the standard check for emptiness (is a final state reachable from the initial state?).

Note that you never need DFA, all of this works nicely with NFA. Therefore, no exponential state explosion occurs; intersection multiplies the state numbers, though.

# Answer
> 2 votes
DFA intersection is a solved problem - given two DFAs (or NFAs, or regular grammars), we can come up with a DFA for the intersection of the two languages accepted by these DFAs. Also, it is known how to check whether the language accepted by a DFA is empty or not. Other closure properties are listed in the Wikipedia article.

Your problem is most probably solvable by using "constructive closure properties" (like intersection and concatenation), and the test for emptiness. In this sense, it is a solved problem. I don't know whether it appears anywhere.

# Answer
> 0 votes
Assume DFAs given, it is easier. And get rid of useless states, and kill off any dead states.

To get a DFA for the language of all prefixes of $A$ is easy: Make all states final.

Then you can compute the intersection between that and $B$, and you have the set of $B$s that are prefixes of $A$s.

No idea what it might be called. The algorithm cited is just a proof of concept idea.

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


# Question
Title: Does $c^*(b \cup (ac)^*)^*$ define all strings over $\{a,b,c\}$ that don't contain the substring $bc$
I'm reading my textbook and it claims that the regular expression $c^\*(b \cup (ac)^\*)^\*$ defines the language $L$ over $\\{a,b,c\\}$ which consists of **all** strings that do not contain the substring $bc$.

However, I'm failing to see how that language would contain strings such as $bbbaaa$ or $aaabbb$. Am I missing something or is that regular expression incorrect? The expression I come up with was $ \left( \left( \left( a \cup b \right) ^\*a \right) ^\* \left( c \cup a \right) ^\* \right) ^\*b^\* $

# Answer
> 7 votes
I checked an older edition of Sudkamp, and it had the same example. Actually the expression is $c^\*(b\cup ac^\*)^\*$, which has a different bracketing. Your $(ac)^\*$ specifies strings of the form $acac\dots ac$, whereas Sudkamp has $ac^\*$ which means strings like $acc\dots c$.

It follows the arguments of the answer by Raphael, but backwards. Any sequence of $c$'s is either at the beginning of the string, or else it cannot be preceeded by $b$ because there is an explicit $a$ in the expressing.

# Answer
> 4 votes
Here is how you can make sure there is a mistake in the book:

1. Use the algorithm from the book to transform the regular expression into an NFA.
2. Optional: determinise the automaton, using the algorithm from the book.
3. Run your example through the automaton and note whether it accepts.

Provided you followed the conversion algorithm correctly and the word is not accepted, there is a mistake in the book: either the claim you quote is wrong or one of the algorithms is wrong.

Spoilers: as mentioned in the comments, the regular expression does not describe the claimed language. The author's epxression enforces "every $a$ is followed by a $c$", which is stronger than the claim.

Your expression looks quite complicated. All you need to do is ensure that every $b$ is followed by $a$, $b$ or the end of the word!

> $(b^\*a \mid c )^\*b^\*$

You can also build a suitable automaton -- basically, start with one that accepts everything and modify it to move to a dead state upon reading $bc$ -- and convert it to a regular expression. Perform whatever construction you can more easily prove correct.

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


# Question
Title: How to enumerate all combinations of $n$ binary variables s.t. their sum is $k$?
Suppose we are given $n$ variables $X\_i, i=1,\dots,n$, each taking values from $\\{0,1\\}$, and a constant integer $k$ with $ 0\leq k \leq n$.

What are some efficient ways to enumerate all possible combinations of values of $X\_i$'s subject to the constraint $\sum\_{i=1}^n X\_i = k$?

A naive way is to first enumerate one by one all possible combinations of values of $X\_i$'s without the constraint $\sum\_{i=1}^n X\_i = k$, and for each combination, check if it satisfies $\sum\_{i=1}^n X\_i = k$ (if it does, keep it; if it doesn't, discard it).

That naive way may be inefficient. For example, when $k=1$, a more efficient way will be for each $i$, letting $X\_i=1$ and $X\_j =0, \forall j \neq i$.

So I wonder for general $k$, what are some efficient ways to do the above task?

# Answer
First, separate the set of variables $I = \\{1,\dots,n\\}$ according to their values:

$\qquad\begin{align} I\_+ &= \\{ i \mid X\_i = 1\\} \text{ and} \\ I\_- &= \\{ i \mid X\_i = 0\\} \\;. \end{align}$

Let $n\_+ = |I\_+|$ and $n\_- = |I\_-|$.

Given $X\_1, \dots, X\_n$ and $k$, it is clear that we have to choose $k$ indices from $I\_+$ and arbitrarily many from $I\_-$. That means we will have to output

$\qquad \binom{n\_+}{k} \cdot 2^{n\_-}$

solutions. Note that if we assume $\binom{a}{b} = 0$ for $b\<0$ and $b\>a$, this extends nicely to inputs that allow no solution.

Generating all valid solutions in a list can be done by two nested recursions: the outer creates all $k$-subsets of $I\_+$, the inner all subsets of $I\_-$. This way, no illegal solutions are investigated, which is as efficient as you can expect (up to list operations).

```
  outer(I+, 0, I-) = inner(I-)
| outer(I+, k, I-) =
    result = []
    foreach ( i in I+ ) {
      suffices = outer(I+ - i, k-1, I-)
      result ++= (suffices map { [i] ++ _ })
    }
    return result

  inner([])      = []
  inner(x::rest) =
    smaller = inner(rest);
    return smaller ++ (smaller map { [x] ++ _ })

```

If you want an iterator, note that you can replace recursion with stacks (which allows you to compute it step by step) and emit solutions in the innermost call of `inner`. Of course, you'll have to reverse the way solutions are constructed (while descending, as opposed to during ascension as I did above).
> 4 votes

---
Tags: algorithms, combinatorics, enumeration
---


# Question
Title: How to write stack programs for arithmetic terms?
I have been given a question about a stack program which I can not solve.

> Write a stack program to evaluate the term
>
> $\qquad (((A+B)-(A\*B))\*C)/(((A-B-C))⁄2)$

How do I approach this problem?

# Answer
> 1 votes
What you want to do is; either first translate the expression into something that is easier for a stack machine to handle (like reverse polish).

The other is to use a modified shunting yard algorithm which can handle parenthesis.

You have 2 stacks: a result stack that holds the numbers where you push the numbers as you encounter them;

and an operator stack that holds operators in decreasing priority order.

When you need to add a operator that is of lower precedence you pop from the operator stack. Then apply that operator to the top 2 values on the result stack and replace them with the result. A parenthesis is of lowest priority but is the only one that can go on top of a higher priority operator.

When you encounter a closing parenthesis you pop from the operator stack and apply to the result stack until you find a closing parenthesis which you pop.

---
Tags: programming-languages
---


# Question
Title: How to convert a context free grammar (could generate regular language) to a right-linear grammar
Consider the context free grammar:

$$S \rightarrow aSb \mid aSa \mid bSa \mid bSb \mid \varepsilon$$

It could generate regular language, which means it can be converted to a right linear grammar. Is there a general rule to convert CFG into a RLG? If there is no general rule, could you please show me how to convert this CFG to a RLG?

# Answer
> 8 votes
Assuming you want your general method to be computable, the answer is no. When you consider a CFG that generates a regular language and convert it into a right-linear grammar, the size-increase is not bounded by any computable (or "recursive") function (first shown by Meyer and Fischer in this paper; also, if you can access it, this paper by Kutrib is a nice survey on the general area of non-recursive tradeoffs).

If a (computable) general conversion method existed, you could use it to construct a computable bound on the blowup between CFGs and right-linear grammars, which would contradict the non-existence of such a bound. Thus, knowing that your grammar generates a regular language does not help you at all.

# Answer
> 3 votes
An undecidable property of context-free grammars is whether they generate all words over the alphabet. That implies that converting a context-free grammar into a linear grammar (if possible) should be difficult, since it is easy to decide whether a linear grammar (which is the same as an NFA) generates all words over the alphabet.

More accurately, we show that the following (type of) function is uncomputable: given a context-free grammar, either output an equivalent linear grammar, or output NO if the grammar represents a non-regular language.

# Answer
> 2 votes
There's has been some work in Computational Linguistics on 'regular approximations' of context-free grammars -- converting CFGs into roughly equivalent regular grammars. A lot of this revolves the notion of a 'strongly-regular-grammar', this is a CFG that doesn't have self-embedding rules, such as A --\> alpha A beta (like your rules), where alpha and beta are non-empty. Grammars with self-embedding are not regular languages, the problem being that further expansions of A by the same rule creates unbounded communication between the left and right, i.e. alpha^n A beta^N. In the other direction, Chomsky proved (the original paper is hard to find, see Harrison's book for the proof) that CFGs without self-embedding rules are regular (see this paper for a constructive proof).

The basic idea for dealing with self-embedding CFG grammars, like the ones you mention, is to convert them to strongly regular (i.e. non self-embedding) grammars -- there are efficient algorithms for doing this e.g. here, see this for review, and citations to original work) . The resulting 'strongly regular' grammar can then be converted into a finite-state automata, or perhaps some other type of regular grammar you're interested in.

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


title: Shannon Entropy to Min-Entropy

text:
# Question
Title: Shannon Entropy to Min-Entropy
In many papers I've read that it is well known that the Shannon entropy of a random variable can be converted to min-entropy (up to small statistical distance) by taking independent copies of the variable. Can anyone explain to me what exactly this means?

# Answer
> 6 votes
This is a consequence of the asymptotic equipartition property (AEP), which is a form of the law of large numbers. The AEP states that if a random variable has (binary) entropy $H$ and you take $n$ copies of it, then most of the data points have probability roughly $2^{-nH}$. This is only true for most data points, which is the source of the small statistical distance that you mention.

As an example, consider a $p$-biased coin. If you throw $n$ coins with bias $p$, then most likely you will get roughly $pn$ heads, each of which events has probability roughly $$ p^{pn} (1-p)^{(1-p)n} = 2^{-nh(p)} .$$

---
Tags: terminology, probability-theory, entropy
---


title: The complexity class FP

text:
# Question
Title: The complexity class FP
I have a hard time understanding the following lines from our lecture notes:

---

$f \in \text{FP}$ iff there is a transducer T that computes $f$ and there exists a polynomial $p$ such that $TIME(T(x)) \leq p(|x|).$

Note: If $f \in \text{FP},$ then $|f(x)| \leq p(|x|)$ holds for a fixed polynomial $p.$

Examples:

$f(x) = x^2$ ($x$ is a binary number)

$f(x) = $ Table of the shortest paths from a start node s in a directed graph $G,$ where $G$ and $s$ are coded as $x.$

$f(x) = 2^x$ is not in $\text{FP}.$

---

Can somebody please explain the examples in a dummy-friendly way?

# Answer
Recall that Turing Machines are often defined to output only a yes/no answer. Transducers are used to extend this to a general output, which is sometimes more appropriate for a certain task (e.g. defining mapping-reductions).

When we use transducers, we can also analyze their runtime, and in this case they compute functions, so we are interested in which functions can be computed using a transducer that runs in polynomial time.

In this context, running in polynomial time means that, as you state, the transducer is allowed to run for $p(|x|)$, where $p$ is a fixed polynomial, and $x$ is the input to the transducer. Finally, the transducer outputs the binary representation of the function that it computes.

Let's consider the first example: $f(x)=x^2$. A transducer that computes it takes as input a binary number, for example $11$ (3 in binary). It then needs to output $1001$. To actually compute this value, we can use the long-multiplication algorithm from preschool. What we need to notice is that this algorithm is indeed polynomial in $|x|$ - the length of the binary *representation* of $x$. It is not hard to verify that the algorithm runs in quadratic time of this length.

So we have a polynomial-time transducer for $f(x)=x^2$, so it is in FP.

Now let's consider example 3: $f(x)=2^x$. Consider an input $x$. What is the size of the binary representation of $f(x)$? Well, it's $\log f(x)$. But $$\log f(x)=\log 2^x=x$$ and $x$ is exponential in $|x|$ - indeed, the size of the representation of $x$ is $\log x$.

So we have that $\log(f(x))$ is exponential in $|x|$, or in other words, $|f(x)|$ is exponential in $|x|$, and in particular, $|f(x)|\>|p(x)|$ for every polynomial $p$ and for large enough $x$ (because $2^n\in \omega(p(n))$ for every polynomial $p$).

So it is no possible to even **write down** $f(x)$ in polynomial time, let alone compute it. This is why $2^x\notin FP$.

Finally, the second example is just an emphasis on the relation between FP and P: Given $G,s$ in some representation (e.g. a "text file" encoded in binary) it is easy to compute the shortest path from $s$ to all the vertices using BFS, which runs in polynomial time. So essentially, once you run BFS on the graph and mark all the shortest paths, you get some binary string which represents it. You then output this binary string.

The important thing to take from the second example is the concept that if you are looking for a solution which is not a yes/no answer (e.g. shortest path, result of an arithmetic expression, etc.) and you can solve a related decision problem using TMs in polynomial time (e.g. "is there a path shorter than $k$?", "is the result of this expression smaller than $v$?"), then in many cases you can use the TM that solves the decision problems to actually obtain a transducer that runs in polynomial time, so the problem will be in FP.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: Lower bound for sorting n arrays of size k each
Given $n$ arrays of size $k$ each, we want to show that at least $\Omega(nk \log k)$ comparisons are needed to sort all arrays (indepentent of each other).

My proof is a simple modification of the decision tree argument used to obtain the lower bound for comparison-based sorting of one array. More specifically, I argue that there are in total $k!^n$ possible permutations for the entries in all given arrays, and that a binary tree with that number of leaves is of height $h \in \Omega(nk \log k)$. Is that argument correct?

Furthermore, I was told that merely observing that one needs $\Omega(k \log k)$ comparisons for each of the arrays and we need to sort $n$ times in total (for $n$ arrays) is *not* a sufficient argument. Why is that? My answer would be that this is just *one* possible approach to this problem, and not a general argument excluding each and every other potential comparison-based algorithm for solving the given task with less than $\Omega(nk \log k)$ comparisons. However, this is not particularly concise and I would consider a rather technical argument (which I don't see) as more appropriate. What would that be?

# Answer
> 6 votes
For the first part, as the comments suggest - observe that there are $k!^n$ possible permutations for the inputs - indeed, every array has $k!$ permutations, and there are $n$ arrays, so you have $k!$ options for the first array, $k!$ for the second, and so on.

So the height of a decision tree is $$\log (k!^n)=n\log (k!)\in \theta(nk\log k)$$ So you need at least that many comparisons in order to determine a single leaf.

For the second part - the argument you suggest is quite close to a formal explanation. The lower bound of $\Omega(k\log k)$ is for comparison-based algorithms that compare elements in the array. When you have several arrays, then it is not justified to assume that sorting them is equivalent to sorting each one independently.

A-priori, it may be easier to sort them by comparing elements between the arrays. But the lower bound on sorting does not utilize such a setting, so it is not directly relevant for this problem.

In my opinion, this is as formal as you can get without formally defining what a comparison-based algorithm actually is. To define the latter, you need to formally model the computational model you use (which would be a sort of pointer-machine), and this is unlikely to result in any insights other than what you already mentioned.

---
Tags: algorithms, sorting, arrays, lower-bounds, check-my-proof
---


title: Existence of bipartite perfect matching

text:
# Question
Title: Existence of bipartite perfect matching
Let $B = G(L, R, E)$ be a bipartite graph. I want to find out whether this graph has a perfect matching. One way to test whether this graph has a perfect matching is Hall's Marriage Theorem, but it is inefficient (i.e $|\mathcal P(L)| = 2^{|L|}$ tests -- not polynomial). I can always find out whether a perfect matching exists by computing a maximum cardinality matching and testing its perfectness, but this involves computing that perfect matching.

Is there an *efficient* way of deciding whether a perfect bipartite matching exists without computing the matching it self? Ideally I would want an algorithm which is faster than algorithms like Hopcroft Karp or matrix based matching algorithms, which explicitly find out the matching (i.e so not computing the matching makes sense).

Edit: The italic part.

# Answer
> 5 votes
A quick literature review suggests that the fastest algorithm for deciding whether a dense bipartite graph has a perfect matching is still the matrix algorithm, which runs in time $O(|V|^\omega)$. You can reduce the space of the algorithm, see Isolation, Matching and Counting by Allender, Reinhardt and Zhou. A recent paper from 2010, which focuses on planar graphs, suggests that the result of Allender et al. is the best that is known.

---
Tags: graphs, bipartite-matching
---


# Question
Title: Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free?
Can a two-stack PDA accept language $L=\\{a^nb^mc^nd^m \mid n \geq m\\}$, which has no context-free grammar?

I don't believe this has a context-free grammar, but please correct me if I'm wrong.

# Answer
A two-stack PDA is equivalent in computing power to a Turing machine. Since a Turing machine can accept that language (stated without proof), a two-stack PDA can as well. The actual definition of such a machine is left as an exercise :)
> 6 votes

# Answer
You don't even need to know about the equivalence to a Turing Machine to decide this language and if it was the intention of this exercise to come up with the equivalence, the language is (IMHO) to easy to motivate this.

A simple two-stack PDA for this language works like this:

1. Put $n$ on both counters, while counting $a$s.
2. Use counter one to check the $b$s.
3. Count up on counter one and down on counter two to check the $c$s.
4. Check the $d$s.

I left out some details, but filling them should be easy.

By the way: You should not **believe** that this language is not context free, but **prove** it (it should be obvious which word to choose as a counter example using the pumping lemma).
> 2 votes

---
Tags: formal-languages, automata, machine-models
---


# Question
Title: How to enumerate combinations in parallel
I have $n\times k$ matrix with $k\<n$ and I would like to find all its $n\choose k$ submatrices which are $k\times k$ matrices that are the concatenations of all possible $k$ rows. Actually I tried to do it with Matlab but it takes too long time specially when $n\>20$ and I couldn't find a way how to generate in parallel the $n\choose k$ indices.

I found online a paper titled A Parallel Algorithm for Enumerating Combinations but they didn't provide their code in that paper.

# Answer
Since you just need to select $k$ rows, this becomes the same as choosing $k$ elements of a given set of $n$ elements, say $\\{1,2,\dots,n\\}$.

You can generate $n \choose k$ combinations in lexicographic order (i.e. starting with $\\{1,2,3, \dots, k\\}$ and ending with $\\{n-k+1, ..., n-1,n\\}$), with the next one depending only on the previous one.

The fact that the order is predictable, and that you only need the previous state, allows you to split the output space, and apply independent parallel computations to each.

There are plenty of algorithms available on the web for lexicographic generation, for instance Frank Ruskey's book: Combinatorial Generation has a chapter (4) on lexicographic algorithms, and for your purposes, you can use Algorithm 4.4 which appears on page 58.
> 5 votes

---
Tags: algorithms, combinatorics, parallel-computing, matrices
---


# Question
Title: What's the regex corresponding to this DFA?
Here is a DFA from a research project. We created the DFA manually. We are interested in which regex is this DFA corresponding to. Certainly, there could be multiple regex corresponding to it; we prefer a simpler one.

Inspired by the first answer from Karolis Juodelė, one correct **Answer** should be:

`(00*10*1|1(0*|(10)*)*110*1)*1(0*|(10)*)*110*`

# Answer
$$(00^\*10^\*1 ~~~ | ~~~ 10^\*(10)^\*110^\*1)^\*~~~10^\*(10)^\*110^\*$$ This should be one representation. Not sure if it could be made simpler. The part from $($ to $|$ represents one lap in the upper cycle. The part from $|$ to $)$ represents a lap in the lower cycle. The last part represents the path from $A$ to $D$.
> 3 votes

# Answer
Assuming I haven't made a mistake, I get $(0^{+}10^{\ast}1)^{\ast}10^{\ast}(0^{+}1)^{\ast}10^{\ast}$ via one application of the DFA to regular expression conversion algorithm, however there are up to $5!$ possible answers as there are $5$ states to eliminate. I would assume some of these give the same answer of course. The order I happened to choose was $F, D, E, B, C$.
> 0 votes

---
Tags: regular-expressions
---


title: Recognizing loops in computation on LBA

text:
# Question
Title: Recognizing loops in computation on LBA
In the case of LBAs (Linear Bounded Automaton), in writing a decider for the language

$\qquad A = \\{ \langle M,w\rangle \mid M\ \mathrm{LBA}, w \in \mathcal{L}(M) \\}$

we reject the input after a specific number (number of possible different configurations) of computation steps. We say that the machine must be looping after this many steps. Why don't we just check in every step to see if there is a loop (repetition of the same configuration) and if it is the case then just reject the input?

# Answer
If I understand the question correctly, you are asking why are we bounding the number of configurations, rather than checking for a repeating configuration?

Well, clearly these are equivalent in the sense that in both ways you will detect a repeating configuration.

In the first method, we use the pigeonhole principle, and we say that if we passed a certain number of configurations, then there must be a repetition, since in an LBA the number of configurations is bounded (after fixing the input). In order to detect this, we must keep a **counter** of the number of configurations we passed. The advantage of this method is that keeping the counter is simple (it takes linear space). The disadvantage is that the loop may have occurred early in the run, and we will only detect it late (after an exponential number of steps).

In the second method, we need to track the configurations we have seen so far, and compare every new configuration to all the configurations we have already seen. The advantage is clear- we will detect the loop immediately when it is caused. But the disadvantage is huge - we need to track all the configurations - this may take exponential space, and in every step we need to compare all the configurations to the current one.

Essentially, the first method solves $A$ in PSPACE, whereas the second solves it in EXPSPACE, so we usually take the first.
> 5 votes

# Answer
Because the TM, as it has an infinite tape, can get into a loop that runs off into infinity and the configuration doesn't repeat. For a minimal example, just make it move right on blank, and rewrite with 0. Start it on a blank tape, and watch it ride into the sunset.
> 3 votes

---
Tags: linear-bounded-automata
---


# Question
Title: Can you complete a basis in polynomial time?
Here is the problem: we are given vectors $v\_1, \ldots, v\_k$ lying in $\mathbb{R}^n$ which are orthogonal. We assume that the entries of $v\_i$ are rational, with numerator and denominator taking $K$ bits to describe. We would like to find vectors $v\_{k+1}, \ldots, v\_n$ such that $v\_1, \ldots, v\_n$ is an orthogonal basis for $\mathbb{R}^n$.

I would like to say this can be done in polynomial time in $n$ and $K$. However, I'm not sure this is the case. **My question** is to provide a proof that this can indeed be done in polynomial time.

Here is where I am stuck. Gram-Schmidt suggests to use the following iterative process. Suppose we currently have the collection $v\_1, \ldots, v\_l$. Take the basis vectors $e\_1, \ldots, e\_n$, go through them through them one by one, and if some $e\_i$ is not in the span of the $v\_1, \ldots, v\_l$, then set $v\_{l+1} = P\_{{\rm span}(v\_1, \ldots, v\_l)^\perp} e\_i$ (here $P$ is the projection operator). Repeat.

This works in the sense that the number of additions and multiplications is polynomial in $n$. But what happens to the bit-sizes of the entries? The issue is that the projection of $e\_i$ onto, say, $v\_1$ may have denominators which need $2K$ bits or more to describe - because $P\_{v\_1}(e\_i)$ is $v\_1$ times its $i$'th entry, divided by $||v\_1||$. Just $v\_1$ times its $i$'th entry may already need $2K$ bits to describe.

By a similar argument, it seems that each time I do this, the number of bits doubles. By the end, I may need $2^{\Omega(n)}$ bits to describe the entries of the vector. How do I prove this does not happen? Or perhaps should I be doing things differently to avoid this?

# Answer
The result of the Gram-Schmidt can be expressed in determinantal form, see Wikipedia. This shows that the output of the Gram-Schmidt process is polynomial size. This suggests that if you run the classical Gram-Schmidt process, then all intermediate entries are also polynomial size (even in LLL, all intermediate entries are polynomial size). However, even if it is not the case, then using efficient algorithms for computing the determinant (see my other answer), you can compute the Gram-Schmidt orthogonalization in polynomial time.
> 3 votes

# Answer
Edit: This answer doesn't address the requirement of orthogonality. Perhaps the Bareiss algorithm still helps.

Let $V$ be a matrix whose rows are $v\_1,\ldots,v\_\ell$. Convert $V$ to row echelon form, say $PVP^{-1} = \[I|A\]$, using the Bareiss algorithm. Continue from there. (There are other alternatives using the same general idea.)

If you used Gaussian elimination instead, then intermediate entries could have exponential size, but the Bareiss algorithm avoids this somehow.

Edit: Here is a practical suggestion. Add random vectors - if you do it in a reasonable way, then it is very probably that the result will be a basis. You could even check whether you get a basis by computing the determinant. The latter can be done in many ways, see for example a survey by Rote, or you can compute the determinant modulo $p$ for "random" $p$ - if the result is non-zero (which it probably will), you know you got a basis.
> 0 votes

---
Tags: algorithms, linear-algebra
---


title: Pumping lemma for CFG doubt

text:
# Question
Title: Pumping lemma for CFG doubt
I was looking at the pumping lemma for CFG. I came across the first problem $a^nb^nc^n$ and understood the answer. Then I thought of the problem $a^nb^n$. I know that this is context free and thought of applying it. I came across a weired situation. Someone please tell me where I went wrong.

So our language is $a^nb^n$. Let $m$ be the pumping length. Pumping lemma says that any sufficiently long string can be divided in $uvxyz$, where $v$ and $y$ can be pumped.

we take our string to be $a^mb^m$ and we can split it into $uxvyz$. Also we know that $|vxy|\le m$. Also $u$ can be $\epsilon$. In that case $vxy$ consists only of $a$, since $|vxy|\le m$ and there are $m$, $a$'s. So when we pump $v$ and $y$, the resulting string wont be in the language!

So where I got wrong? Is it wrong to take $u$ is $\epsilon$ and proceed from there?

# Answer
> 8 votes
I'm not sure why the answer of Karolis doesn't satisfy you. Let me chew it a bit more for you. First, let's recall what the pumping lemma says (taken form the credible source of Wikipedia):

> If a language L is context-free, then there exists some integer p ≥ 1 such that any string s in L with |s| ≥ p (where p is a "pumping length") can be written as
>
> s = uvxyz
>
> with substrings u, v, x, y and z, such that
>
> 1. |vxy| ≤ p,
> 2. |vy| ≥ 1, and
> 3. uv$^n$xy$^n$z is in L for all n ≥ 0.

Ok, so you say $L=\\{a^nb^n \mid n \ge 0\\}$ is CF, and thus we can run the Lemma on it. Great. Here I'll show you that the lemma works for it. Say the pumping length is $p\ge2$.$^3$

The lemma says, that for any long enough $s$ string in $L$ (let's take $s=a^mb^m$ with $m\ge p$ as you suggest) we **can** write it as $uvxyz$ that satisfies some conditions.$^1$

Ok, let's give a try. Let's set $u=a^{m-1}$, $vxy=ab$, $z=b^{m-1}$.

Sanity check: indeed, $uvxyz$ gives $s$. I don't know yet how to split the middle part into $vxy$, but see that condition (1) is satisfied, $|vxy|= 2 \le p$. Now for condition (2), i'll have to get the $vxy$ thing. Let's take $x=\epsilon$, thus $v=a$ and $y=b$. Do we satisfy condition (2)? Yes! $|vy|=2\ge1$. Yey.

Now, it says that no matter what $n$ I take, $uv^nxy^nz$ needs to be a word in the language $L$. Let's see. By the way we picked the substrings, $$ uv^nxy^nz = a^{m-1}a^n\epsilon b^{n}b^{m-1}$$ indeed! for any $n\ge 0$ we pick the word we get is $a^{m+n-1}b^{m+n-1}\in L$.

To conclude, we were able to take any word in $L$, and write it as $uvxyz$ so that the conditions of the lemma hold. This can be done for any language which is context-free (and for some that are not, as well) and we just saw how to do it for $L$.

more questions?

## <br>

$^{1)}$ This should be emphasized: any word **can** be written in some way uvxyz etc. It doesn't mean that **ALL** the possible $uvxyz$ will work. Only one of them needs to work in order to satisfy the lemma.
$^{2)}$ when you want to prove that a language is **not** CF, then **all** the ways $uvxyz$ must be checked. This is because when you negate the lemma, the word "There exists ... that satisfies (1), (2), (3)" negates to "does not exist ... that satisfy" == "for all ... the condition is not satisfied". So to prove $L$ is not-CFG you need to check all possible ways. To show the lemma is satisfies for a CF $L$, you only need to find one.
$^{3)}$ What if $p=1$? Well, it is not. The lemma says that there exists some $p$. It doesn't say what this $p$ is. For our $L$, any $p \ge 2$ works, but $p=1$ doesn't. We need just one such $p$ (i.e., there *exists*), so taking $p=2$ is enough.

# Answer
> 3 votes
It's wrong to take $u$ to be $\epsilon$. Pumping lemma for regular languages says that the substring to pump will be somewhere near the beginning of the string. Pumping lemma for context free languages says no such thing. In general, neither pumping lemma lets you make many assumptions about what to pump. In the case of $a^nb^n$, the substring to pump will always be in the middle.

---
Tags: context-free, automata, pumping-lemma
---


# Question
Title: Proving undecidability of the language composed of LBAs where their language is empty
As it is explained in Sipser's book, the following language is undecidable and he proves this using the computation history method.

$\qquad E = \\{\langle M \rangle \mid M\ \mathrm{LBA}, L(M)=\emptyset\\}$

I wanted to see if we could use the same method used for proving undecidability of the following language in the case of LBAs too (instead of using computation history method).

$\qquad E' = \\{\langle M \rangle \mid M\ \mathrm{TM}, L(M)=\emptyset\\}$

Is it possible?

# Answer
> 3 votes
Consider the reduction that shows that LBA-emptiness is undecidable: you reduce from $\overline{A\_{TM}}=\\{\<M,w\>: M $ does not accept $w\\}$.

So the reduction takes as input $\<M,w\>$, and outputs an LBA $T$ such that $L(T)\neq \emptyset$ iff $M$ accepts $w$.

Now, recall that an LBA is in particular a TM. So this same reduction actually outputs a TM, and actually shows that $E\_{TM}$ is undecidable as well.

The reason this works is that the relationship between $E\_{LBA}$ and $E\_{TM}$ is such that if $M$ is an LBA, then $M\in E\_{LBA}$ iff $M\in E\_{TM}$. Since the reduction above always outputs an LBA, then you can just plug it in.

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


title: Understanding DPLL algorithm

text:
# Question
Title: Understanding DPLL algorithm
I'm trying to understand DPLL algorithm for solving SAT problem. And here it is:

```
Algorithm DPLL
  Input: A set of clauses Φ.
  Output: A Truth Value.
function DPLL(Φ)
   if Φ is a consistent set of literals
       then return true;
   if Φ contains an empty clause
       then return false;
   for every unit clause l in Φ
      Φ ← unit-propagate(l, Φ);
   for every literal l that occurs pure in Φ
      Φ ← pure-literal-assign(l, Φ);
   l ← choose-literal(Φ);
   return DPLL(Φ ∧ l) or DPLL(Φ ∧ not(l));

```

At first, I don't clearly understand how `unit-propagate(l, Φ)`, `pure-literal-assign(l, Φ)` and `choose-literal(Φ)` work. I'll try to guess on particular examples. Correct me please if I do something wrong.

* For the first one

`unit-propagate(a, (0 v -a) ∧ (a v b) ∧ (b v d) ∧ (f v g) v ...)`

we will have

`((0 v -0) ∧ (0 or 1) ∧ (1 v d) ∧ (f v g) ∧ ... = (f v g) v ...`,

having `a = 0`, `b = 1`.
* For second procedure

`pure-literal-assign(a, (a v b v c) ∧ (d v -b v a) ∧ (-d v b))`

result is

`(b v c) ∧ (d v -b) ∧ (-d v b)`,

assigning `a = 1`.
* And finally `choose-literal(Φ)` just returns some random (in common case) unassigned literal for further computations.

Now, I don't understand why algorithm has such strange conditions for finishing? Why does it work?

Thanks!

# Answer
> 5 votes
It works because the three cases you mention will remove every non-pure variable after some number of steps, but it is crucial that you also consider the recursive step, namely $\mbox{dpll}(\phi \land l) \lor \mbox{dpll}(\phi \land \neg l)$.

After a recursive step, you are guaranteed to have at least one unit clause, so the unit clause will be set to its value and hence all the variable will in the end be assigned a value.

I think your misunderstanding must arise from the recursive calls. Observe that if you have any formula $\phi = ((a \lor b \lor c) \land \cdots)$, then $\mbox{choose-literal}(\phi)$ will return some unassigned variable, say $a$. The recursive call will then be with $\phi \land a$ which will be $(a \lor b \lor c) \land \cdots) \land (a)$. And then $\mbox{unit-literal}(\phi)$ will return $a$ and set it to true. The other recursive call is equivalent, but with $\phi \land (\neg a)$ so $\mbox{unit-literal}(\phi)$ will still return $a$ and set $a$ to false.

# Answer
> 6 votes
I think your problem is not the algorithm itself but a few surrounding notions.

1. A *literal* is a variable or its negation: $a$ or $\neg a$ for example.
2. A *clause* is a disjunction of literals: $a \lor b$
3. A *unit clause* contains only one literal: $\neg a$ is an example
4. The *empty clause* contains no literals and is written $\\{\\}$ or $()$ or $\Box$. The empty clause is not satisfiable and you can think of it as equivalent to $False$.
5. A *conjunctive normal form (CNF)* formula is a conjunction of clauses: $(a \lor b)\land(\neg a)$
6. The *empty formula* contains no clauses and is written $\emptyset$. The empty formula is satisfied by every assignment and you can think of it as $True$.

Please notice the difference between an empty clause and an empty formula. These are the basic objects that the algorithms manipulates. Now we come to the operations.

1. The *unit rule* says that if we have a unit clause $\neg a$ and a clause $a \lor \theta$, then to satisfy the formula, we must satisfy the clause $\theta$. This is because to satisfy the unit clause $\neg a$, the variable $a$ must be set to $False$ meaning, we cannot satisfy $a$, so we must satisfy $\theta$. Unit propagation repeatedly applies the unit rule.
2. Observe that in implementing the unit rule as above, we are deleting unsatisfiable literals from a clause and leaving only literals that may help satisfy the clause. If we delete all literals, we have the empty clause, which means that no constraint of that clause is satisfiable, in turn meaning that the entire formula is not satisfiable.
3. The *pure literal rule* is based on the observation that if a variable occurs only with one polarity in the entire formula, meaning we either only have $a$ or only have $\neg a$ in the formula, then there is never going to be a constraint of the form $a \land (\neg a \lor b)$ in the formula. So we can make that literal true. This will satisfy every clause in which that literal occurs, so we can delete those entire clauses.

There is a difference between unit propagation and the pure literal rule. Unit propagation deletes literals from inside a clause and brings us closer to discovering if there is an empty clause, in which case the formula is not satisfiable. The pure literal rule deletes entire clauses and brings us closer to the empty formula, in which case the formula is trivially satisfiable.

If you consider the two cases above, you see that it does not cover all possible behaviour. Specifically there may not be any unit clauses and there may not be any pure literals. In this case, to make progress, we pick a literal that does not occur in a unit clause and assign it a value. The choose-literal step can be viewed as adding a unit clause to the formula, which has the effect of triggering more unit propagations.

---
Tags: algorithms, logic, satisfiability, sat-solvers
---


title: Context free grammar construction

text:
# Question
Title: Context free grammar construction
My problem with CFG is, I am to generally create ones that don't have requirements such as:

$\qquad \\{a^m b^n \mid m \le n \le 2m \\}$

I have no clue where to begin, and how to approach it. I was wondering if you can provide some hints for such daunting problems, along with how to solve that problem.

This is not homework, this is merely me trying to learn it. I solved many problems that did not have such requirements, but those problem are the ones where I am forced to look at the solution.

# Answer
> 2 votes
Just read the constraint carefully. $m\le n$ tells you that you must have at least as many b's as a's. The other part: $n\le 2m$ tells you that you cannot have more than twice as much a's.

Here is an EBNF description that yon can convert to BNF.

$S\to aSb\[b\] \mid \epsilon$

# Answer
> -2 votes
Hint: Each $a$ corresponds to either one $b$ or two $b$s. Form a hybrid between grammars for $a^n b^n$ and $a^n b^{2n}$.

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


title: Reconstructing files from binary

text:
# Question
Title: Reconstructing files from binary
Popular view tells us that any kind of information is just a collection of bits, that is zeroes and ones placed in a particular order. I was thus having this thought.

Suppose that I have some kind of file such as a text document, a PDF or anything else and that I also have a memory so perfect that I can remember the file exactly in its binary format, i.e. the number and place of zeroes and ones. But nothing else.

My question would then be if, in practice, it would be possible to reconstruct my initial file (without imposing any assumptions on what format it takes) from just this binary format.

Please be advised that I am not an expert in computer science and I do have only some very basic understanding. I do hope though this question fits here.

# Answer
First notice that a "file" is a sequence of 0s and 1s in binary format that are stored in some kind of persistent storage (an hard disk, a CD, an USB key, ...).

According to the the *type of information* stored in the file (a plain text, a PDF document, an image, a video, a song, ...) its bits (bytes) are usually arranged using standard rules and they have precise meaning: they follow a file format which specifies how *information* is encoded in the file.

Usually the name of the file (filename) has an *extension* (.mp3, .txt, .jpg, .pdf, .tex, ...) that indicates the file format i.e. how information is encoded.

Computer programs like text editors, image editors, video players, music players, ... can read a file in one (or more) format and decode the information stored in it (show the text on the screen, play it, process it, ... ).

Now suppose that you have a bunch of bytes in your head. First you can write them directly in a file using a program like a binary editor. When they are stored in a file, you need to discover its file format ...

1. first you can try to display it as a text file (like suggested by saadtaame in his answer): many file formats (text data, html files, xml files, ...) store the information in plain text (ASCII);
2. or you can change its extension (.pdf, .jpg, .mp3, .gif, .avi, ...), and try to open it with some standard programs ... if you are lucky you'll find one that opens it correctly;
3. or you can do something smarter. You can examine the first bytes of the file (header): they usually have a particular structure or contains specific fixed characters that allow you to quickly find the file format of the whole file.

For example the bytes 6,7,8,9 of a JPEG file are always 0x4a 0x46 0x49 0x46, which correspond to the string "JFIF" in ASCII. Windows PE executables contain the string "This program cannot ..." in the header. The first two bytes of a file in ZIP format are "PK", and so on ...

But there are thousands of file formats out there, so you can also consider using a computer program that given an unknown file can help you to find its file format automatically.

Finally don't forget that the information in a file can also be encrypted or the file format can be proprietary (and closed, i.e. undocumented); in these cases there are very little probability (zero?) to decode the information stored in the files.
> 6 votes

# Answer
Files are always stored in the disk in binary format. Therefore if you know the binary version of the file, you simply know the file itself.

A more interesting question is whether you can reconstruct the semantics of the file from its binary contents. Suppose you memorized the binary contents of a file, but forgot what type the file was. Could you reconstruct how to "read" the file?

If the file format is standard, the answer is yes. You could tell what type the file is in various ways - by looking at statistics, by considering the header, and more. Once we know what format the file is, we can "understand" it using the format specification.
> 5 votes

# Answer
I assume you understand binary. If every character is a byte (8 bits), you can recover the initial file (text) by translating every byte to a character. A simple algorithm for doing that is:

```
let initial_file be an empty text file
for every byte in binary file:
  write character corresponding to byte in initial_file

```
> 1 votes

---
Tags: encoding-scheme
---


# Question
Title: All paths of less than a given length in a directed graph between couple of nodes
Counting all possible paths, or all possible paths with a given length, between a couple of nodes in a directed or undirected graph is a classical problem. Attention should be given to what *all* means, due to the possibles cycles.

This question is slightly different, or at least I think.

**INPUT:** Be **G** a directed graph. **G** can have cycles and also selfconnected nodes. Let **A(G)** be the adjacency matrix of **G** (with a 1 in **G**i,j if there's a link going from i to j and a 0 otherwise). Define **T** and **B** two subset of nodes of **G**, possibly with void intersection.

**OUTCOME:** A list of all paths of length *at most* k going from one node in **T** to one node in **B**. Paths can contain multiple time the same edges, as long as they go from the source node to the target node in strictly less than k+1 steps.

**QUESTION:** I would like to know which algorithm perform best in this task. I'm trying to develop a possible answer based on the fact that the n-th power of the adjacency matrix, if computed symbolically (with a different variable for each entry instead of a 1), keep traks of all this paths (and it reduces to the counting of paths if computed numerically with 1 in the entries). But I really don't know if this is the fastest way of doing the task (probably not).

**CAVEAT:** I'm not asking for the counting problem, nor for the shortest paths, the length of a path is defined as the number of edges used (counting the repetition). I'm using R, but if you prefer think about it in any other language! I'm really sorry if the question was already posed and solved. Thank you for the kind help!

**additional info:** I tried a matrix power series approach (A^3 gives all the 3 long path, ...) and dfs / bfs. I think the latter two are far from optimality as they don' take into account that I'm working on sets of sources and targets, and hence do a lot of redundant work...

# Answer
> 7 votes
If I am not missing something about your question, you can apply the standard trick for reducing the question about multiple sources and destinations to the case of single source and single destination:

> 1. Add two new nodes $s$ and $t$,
> 2. Connect $s$ to all sources,
> 3. Connect all destinations to $t$.

After this reduction we are in the standard question setting with two extra vertices $s$ and $t$ and we want to find walks from $s$ to $t$ of length at most $k+2$.

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


title: Time complexity based on two variables

text:
# Question
Title: Time complexity based on two variables
Suppose we have a function based on two inputs of length $m,n$. Therefore the time complexity of the function is calculated by $T(m,n)$. Suppose that we have:

* $T(m,c)\in O(m^2)$ for any constant $c$.
* $T(c',n)\in O(n^2)$ for any constant $c'$.

What can we say about $T(m,n)$?

# Answer
With this exact phrasing, and without additional assumptions on the structure of $T$, you can't really say anything about it's asymptotic behavior in general.

First, observe that the function $m^2n^2$ satisfies the constraints, so you can at least $\Omega(m^2n^2)$. However, you can get much more than that.

Let $f(k)$ be some function. Think of $f$ as a very quickly-growing function (e.g. $f(k)=2^k$).

Now, think of $\mathbb{N}^2$ as a two dimensional plane, with the $m$ and $n$ axes. We require that along every vertical and every horizontal line, the function is **asymptotically** quadratic. This means that we can do whatever we want with finitely many elements of every row/column.

Thus, for example, you can set $T(k,k)=f(k)$ for every $k$, and set $T(m,n)=m^2n^2$ for all entries where $m\neq n$.

The diagonal of this function is huge. That is, $T(k,k)=\Omega(f(k))$. However, the function still satisfies the constraints. Also, note that you can make this function monotonic by adding $f(k)$ to all elements in the relevant row/column. That is, take $$T(m,n)=f(\min\\{m,n\\})+m^2n^2$$ This still has the same property, only here we change finitely many elements, instead of a single element.
> 4 votes

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


title: What are two's complement integers?

text:
# Question
Title: What are two's complement integers?
Can someone explain in plain English what "two's complement integer" means? I read this:

> in Java long is a 64-bit signed two's complement integer

# Answer
> 7 votes
Two's complement is the most commonly used way to represent signed integers in bits. First, consider unsigned numbers in 8 bits. Notice that $2^8 = 256 = 100000000\_2$ does not fit into 8 bits and will thus be represented as `0000 0000`. Therefore $255 + 1 =$ `1111 1111` \+ `0000 0001` = `0000 0000` and in that sense `1111 1111` acts as if it was $-1$. Two's complement is based on this observation.

For a deeper understanding of it, I suggest reading the wikipedia page on it. Note that as long as you you don't need to directly manipulate bits of your integers and your numbers don't go out of range, it makes no difference what signed integer representation is used.

# Answer
> 0 votes
Karolis Juodele's answer is good. Here's another take.

To represent a negative number over $k$ bits in two's complement:

1. Take the complement of the absolute value of the number over $k$ bits, by changing $0$ to $1$ and vice-versa.
2. Add 1 to the number obtained previously, using regular unsigned integer arithmetic.

Example: find the two's complement representation of $-55$ assuming an 8-bit representation. The binary representation of $|-55| = 55$ is $00110111$. The complement of this is $11001000$. Adding $1$ using unsigned integer arithmetic yields $1101001$. This is the two's complement representation of $-55$ over 8-bit integers. Note that, as Karolis points out, performing binary addition using unsigned integer arithmetic of these two representations (the representations for $55$ and $-55$) yields $00000000$, or $0$.

# Answer
> 0 votes
The two's complement of a number $N$ is the amount that you need to add to $N$ to get $2^k$ where $k$ is the number of binary digits needed to represent $N$; analogously three's complement would be the amount to add to get $3^k$ ($k$ is the number of ternary digits now) and you get the pattern. So this complement idea can be generalized to any base not only $2$. In other words, the complement is the amount that you need to add to get the WHOLE where the WHOLE is some predetermined quantity (thinking of complements of sets might help).

Let's say numbers are stored in $8$ bits so the maximum number in this representation is $2^8 - 1$ and $2^8$ is equivalent to $0$ because it can't fit in the $8$ bits representation (it overflows). The complement of the maximum is $1$ since $1 + (2^8 - 1) = 2^8$. This suggests that a legitimate representation of a negative number $-M$ is $(2^8-M)$ because adding $M$ results in $2^8$ which is the same as $0$ and this is what we expect it to be.

The way computers do it is a bit different. Let's take the number $X=1$; in our representation this is written as: $X=00000001$. Now the amount that we need to add to $X$ to get the WHOLE is $11111110$ which turns all bits on and then add $1$ to cause an overflow so that the result is $100000000$ which is the same as $2^8$, so computers first flip all the bits ($0$ becomes $1$ and vice-versa) and then add $1$.

---
Tags: terminology, integers, encoding-scheme
---


# Question
Title: 2OPT Approximation Algorithm for Multiway Cut Problem
In the multiway cut problem, the input is an undirected graph $G= (V, E)$ and set of terminal nodes $s\_1, s\_2,\ldots s\_k$ are in $V$. The goal is to find a minimum set of edges in $E$ whose removal leaves all terminals in different components.

1. How do we show that this problem can be solved exactly in polynomial time when $k= 2$?
2. How do we get an approximation algorithm with ratio at most 2 for the case when $k \geq 3$?

# Answer
**Minimum $k$-Multiway Cut**

Given a graph $G =(V,E)$ and a set of terminals $S=\\{s\_1, s\_2, \dotsc, s\_k\\} \subseteq V$ find a minimum set of edges $E' \subseteq E$ whose removal separates each pair of terminals in $S$.

**Case when $k=2$**

For the case when $k=2$ Minimum $k$-Multiway cut is exactly the Minimum $s$-$t$ Cut problem. To see this simply let $(s\_1, s\_2) = (s,t)$ and compute a min $s$-$t$ cut. This can be solved in polynomial time by various Maximum-Flow algorithms.

**Case when $k \geq 3$**

We can design a very simple 2OPT approximation algorithm for the $k$-Multiway Cut problem. For each $s\_i$, where $1 \leq i \leq k$, collapse $S \setminus \\{s\_i\\}$ into a single node $t\_i$. Compute a min $s\_i$-$t\_i$ cut and call it $C\_i$. Repeat this for each possible $s\_i$. Output $C = \bigcup\_{i=1}^k C\_i$.

**Claim: $|C| \leq 2 \textrm{OPT}$**

Let $A$ be the optimal multiway cut and let $A\_i$ be a cut that separates $s\_i$ from the rest of the graph. Since each edge in $A$ is adjacent to 2 components, each edge must be in two of the cuts $A\_i$. Hence, $$\begin{align\*}&\sum\_i |A\_i| = 2|A| &(\*)\end{align\*}.$$ Further, since $C\_i$ is a minimal cut, $|C\_i| \leq |A\_i|$. This fact together with $(\*)$ implies that our algorithm achieves a $2\mathrm{OPT}$ approximation ratio.

**Claim: $\text{Proposed algorithm runs in polynomial time}$**

The algorithm requires $k$ calls to a Minimum $s$-$t$ cut procedure. Since we only make a constant number of calls to a polynomial-time algorithm, our resulting algorithm is still polynomial.

You can further improve this to $(2 - \frac{2}{k})\mathrm{OPT}$ by dropping the heaviest cut. Beating that bound requires a slightly more advanced LP rounding schema.
> 3 votes

---
Tags: algorithms, graphs, approximation, network-flow
---


# Question
Title: Can a Turing Machine decide if a regular expression matches all strings of exactly some length $l \geq 1$?
Earlier I asked the question: Can a Turing Machine decide if an NFA accepts a string of prime length?. The answer introduced me to Parikh's theorem, which I've been reading about. The concept of Parikh's theorem, if we apply it to regular expressions, allows us to break down a regular expression into expressions that only have one level of Kleene-star nesting.

So: $aa(b(cc)^\*)^\*$ can have a list of expressions created using the same methodology as Parikh's theorem where none of the new expressions in the final list has nested Kleene-stars. The linear subsets will use starred expressions

To make it more clear, I'm referencing this paper: http://people.inf.ethz.ch/torabidm/par-ext.pdf.

I'm not too concerned with it actually being a regular expression, DFAs or NFAs would work fine. It seems easier to work with as an RE.

---

I want to know if the problem is decidable:

**Instance**: A regular expression $R$

**Question**: Does there exist some length $l \ge 1$ such that $R$ accepts every string of that length (ie. if its alphabet is $\Sigma$, it accepts $\Sigma^l$, for some $l \ge 1$.

---

I'm pretty sure the problem actually is decidable but it's a tough one. I've enjoyed pondering it so far and would love to see what someone more experienced than myself can come up with.

# Answer
I think this procedure should work...

First, construct a DFA for the language. Now, start tracing all possible paths of length $k$ (start with $k = 1$). Call $S\_k$ the set of states reached by strings of length $k$.

If at any point you find $S\_k \subseteq A$, the set of accepting states, the answer is yes, and return.

If, on the other hand, you find that $S\_{k} = S\_{k'}$, where $k' \< k$, before you find an $S\_k$ that works, you know that you'll never find an $S\_k$ that works, and you can stop looking. The reason is that the next length you try, $k + 1$, will yield $S\_{k+1} = S\_{k'+1}$, another set that didn't work... and so on.

Note that this procedure is guaranteed to terminate since there are a finite number of possible $S\_k$; since they're subsets of the set of all states, $S$, there are no more than $2^{|S|}$ of them. By the pigeonhole principle, if you've tried enough candidates, you'll either have already found one that worked, or you'll have tried some set more than once.

Apologies in advance if this is completely missing the point of the question, blatantly wrong or intellectually hilarious.
> 4 votes

# Answer
While the algorithm above is fine, it may use exponential space, while this problem for DFAs should be polynomial time equivalent to (the complement of) the universality problem for NFAs. This makes it PSPACE-complete (according to this answer: https://mathoverflow.net/questions/24343/emptiness-and-determinization-of-nfas/24422#24422). The problem here for regular expressions or NFAs might be even harder, since a minimal DFA might have exponentially many states.

---

This problem for DFAs $\leq^p \overline{\mathrm{NFA-UNIV}}$:

Given a DFA $M$ with alphabet $\Sigma$, first compute $\overline{M}$ (DFA for $\overline{L(M)}$) by switching final and non final states, let $\delta$ be its transition function. Now construct an NFA $N$ with the same states, alphabet $\\{a\\}$ and transition function $\delta'$ s.t.

$$ \delta'(z,a) = \\{z' \mid \exists b: \delta(z,b) = z'\\}$$

If $N$ accepts a word $a^l$ then $\overline{M}$ accepts a word of length $l$ and $M$ does not accept all words of length $l$. So there is an $l$ s.t. $M$ accepts all words of length $l$ if and only if $L(N)\neq\\{a\\}^\*$.

---

$\overline{\mathrm{NFA-UNIV}} \leq^p $ this problem for DFAs:

For the other direction we use the same names but the construction is carried out in the opposite way. W.l.o.g. we assume $N$ has only one initial state. Let $\Sigma$ be the alphabet of $N$ and $k$ maximal s.t. $\exists z,a: k = |\delta'(z,a)|$. The alphabet of $\overline{M}$ is now $\Sigma \times \\{1,\dots,k\\}$ and if $\delta'(z,a) = \\{z\_{i\_1},\dots,z\_{i\_m}\\}$ we define $$\delta(z,(a,j))=\begin{cases}z\_{i\_j}&j\leq m \\ E & \text{else}\end{cases}$$ where $E$ is some special new error state (i.e. non final and $\forall a: \delta(E,a)=E$). Now a path form the initial state to a final state in $N$ maps to such a path in $\overline{M}$ (and vice versa). Finally we define $M$ by switching final and non final states of $\overline{M}$.
> 1 votes

# Answer
This can be solved using closure properties of regular languages and uniqueness of the minimal DFA.

Proceed as follows:

* Construct an NFA for the given regular expression.
* Construct the canonical DFA for $\Sigma^l$ (a linear chain with $l+1$ states, maybe an additional error state).
* Intersect the two (standard algorithm).
* Determinise and minimise.

If and only if $\mathcal{L}(R) \supseteq \Sigma^l$ the resulting automaton equals the one for $\Sigma^l$ (up to state names).
> 0 votes

---
Tags: computability, finite-automata, regular-expressions
---


# Question
Title: Sort array of 5 integers with a max of 7 compares
How can I sort a list of 5 integers such that in the worst case it takes 7 compares? I don't care about how many other operations are performed. I don't know anything particular about the integers.

I've tried a few different divide and conquer approaches which get me down to 8 compares, such as following a mergesort approach, or combining mergesort with using binary search to find the insertion position, but every time I end up with 8 compares worst case.

Right now I'm just looking for a hint, not a solution.

# Answer
> 27 votes
There is only one way to start this process (and for nearly all of your decisions of what to compare in later steps, there is only one correct one). Here's how to figure it out. First, note that there are $2^7 =128$ possible answers you can get for your comparisons, and $5! = 120$ different permutations you need to distinguish between.

The first comparison is easy: you have to compare two keys, and since you don't know anything about them, all choices are equally good. So let's say you compare $a$ and $b$, and find that $a \leq b$. You now have $2^6 = 64$ possible answers left, and $60$ possible permutations remaining (since we have eliminated half of them).

Next, we can either compare $c$ and $d$, or we can compare $c$ to one of the keys we used in the first comparison. If we compare $c$ and $d$, and learn that $c \leq d$, then we have $32$ remaining answers and $30$ possible permutations. On the other hand, if we compare $c$ with $a$, and we discover that $a \leq c$, we have $40$ possible permutations remaining, because we have eliminated $1/3$ of the possible permutations (those with $c \leq a \leq b$). We only have $32$ possible remaining answers, so we're out of luck.

So now we know that we have to compare the first and second keys, and the third and fourth keys. We can assume that we have $a\leq b$ and $c \leq d$. If we compare $e$ to any of these four keys, by the same argument we used in the previous step, we might only eliminate $1/3$ of the permutations remaining, and we're out of luck. So we have to compare two of the keys $a,b,c,d$. Taking into account symmetry, we have two choices, compare $a$ and $c$ or compare $a$ and $d$. A similar counting argument shows we must compare $a$ and $c$. We can assume without loss of generality that $a \leq c$, and now we have $a \leq b$ and $a \leq c \leq d$.

Since you asked for a hint, I won't go through the rest of the argument. You have four comparisons left. Use them wisely.

# Answer
> 8 votes
You can find this in The Art of Computer Programming vol III, by D.Knuth, but the strategy is as this (I'll assume you have array $\\{a,b,c,d,e\\}$): If you want hint read just first two lines of my answer

* First group pairs of numbers: $(a,b), (c,d)$.
* Compare pairs to sort them e.g: $a\<b, c\<d$.
* Compare smallest elements of pairs, we get result e.g $a\<c$.
* Compare the last element $e$, with bigger element in last comparison ($c$)
    + If $e\<c$, is easy to end up with 3 remaining comparison. Finished.
    + If $e\>c$ then you should sort $\\{b,c,d,e\\}$ with knowledge $c\<e, c\<d$.
        - $Compare(d,e)$, if $d \< e$ then
            * $Compare(b,d)$, if $b\>d$
                + $Compare(b,e)$. Finished.
            * if $b\<d$
                + $Compare(b,c)$. Finished.
        - if $d \> e$
            * $Compare(b,e)$ if $b\>e$
                + $Compare(b,d)$. Finished.
            * if $b\<e$
                + $Compare(b,c)$. Finished.

All above mentioned ways are cause to at most three comparison after first comparison of $e$ with $c$. (means 7 at most).

---
Tags: algorithms, sorting
---


# Question
Title: Is every regular language Turing-decidable, and how can we prove this?
I know every regular language is Turing-acceptable, but does that imply it is Turing-decidable?

# Answer
> 7 votes
Every regular language is Turing-decidable and therefore Turing acceptable / recognisable (but note that Turing acceptable does not imply Turing decidable).

Suppose you are given a DFA D such that L = L(D). One can construct a Turing Machine T that simulates D. T's states will be similar to D's. On reaching the end of the input, if T is in a state that corresponds to a final state of D, T halts and accepts; otherwise it halts and rejects.

---
Tags: terminology, computability, regular-languages, decision-problem
---


# Question
Title: Are genetic algorithms special instances of random search done in an unexpectedly short run-time?
I was wondering since randomness is embedded in genetic algorithms at almost every level, is there a really fine line between genetic algorithms and pure random search?

Ever since I finished my implementation of a GA , since randomness is present in the mutation function,the initialization part (as well as the reinitialization part) and crossbreeding part as well... other than a encoder which tries to sense of the chromsomes (encoder tailored to make sense of the chromosome in context of the problem) and a fitness function , it feels like genetic algorithms are just random search functions in disguise .

So my question is : are GA implementations just plain old random searches with a shot of memory to make it look like there is some sort of meaningful feedback?

# Answer
> 1 votes
I guess the easiest way to reason it (this is after thinking about what user:vzn said

> a genetic algorithm exploits the gradient in the fitness function due to crossbreeding. if there is no gradient to exploit, it is indeed roughly the same as a random search over the search space.

, um that the chromsomes which embedd some sort of a possible solution has a higher chance of being a solution than a randomly generated chromosome.On mutation and crossbreeding it up its chance of being closer to the answer.I do not know random variable theory or stochastic calculus(if it is ver used in such a thing) to prove it but it's feels pretty intuitive now.

ANd if you think carefully about what the fitness function does probabilistically, because it takes the best fits, the best fits have a higher chance of being crossbred and mutated into a better solution than an unfit solution.

As for a random search based searching , it really doesn't this narrowing down part to give an answer in most cases as compared to a GA.

---
Tags: search-algorithms, efficiency, randomness, evolutionary-computing, genetic-algorithms
---


# Question
Title: Finding recurrence when Master Theorem fails
Following method is explained by my senior. I want to know whether I can use it in all cases or not. When I solve it manually, I come to same answer.

$T(n)= 4T(n/2) + \frac{n^2}{\lg n}$

In above recurrence master theorem fails. But he gave me this solution, when

for $T(n) = aT(n/b) + \Theta(n^d \lg^kn)$

if $d = \log\_b a$

if $k\geq0$ then $T(n)=\Theta(n^d \lg^{k+1})$

if $k=-1$ then $T(n)=\Theta(n^d\lg\lg n)$

if $k\<-1$ then $T(n)=\Theta(n^{\log\_ba})$

using above formulae, the recurrence is solved to $\Theta(n^2\lg\lg n)$. When I solved manually, I come up with same answer. If it is some standard method, what it is called ?

# Answer
OK, try Akra-Bazzi (even if Raphael thinks it doesn't apply...) $$ T(n) = 4 T(n / 2) + n^2 / \lg n $$ We have $g(n) = n^2 / \ln n = O(n^2)$, check. We have that there is a single $a\_1 = 4$, $b\_1 = 1 / 2$, which checks out. Assuming that the $n / 2$ is really $\lfloor n / 2 \rfloor$ and/or $\lceil n / 2 \rceil$, the implied $h\_i(n)$ also check out. So we need: $$ a\_1 b\_1^p = 4 \cdot (1 / 2)^p = 1 $$ Thus $p = 2$, and: $$ T(n) = \Theta\left(n^2 \left( 1 + \int\_2^n \frac{u^2 du}{u^3 \ln u} \right) \right) = \Theta\left(n^2 \left( 1 + \int\_2^n \frac{du}{u \ln u} \right) \right) = \Theta(n^2 \ln \ln n) $$ (The integral as given with lower limit 1 diverges, but the lower limit should be the $n\_0$ for which the recurrence starts being valid, the difference will usually just be a constant, so using 1 or $n\_0$ won't make a difference; check the original paper.)

\[I've taken the liberty to add this to the Akra-Bazzi examples in the reference question, thanks!\]
> 5 votes

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