# Question
Title: Is Smoothed Analysis used outside academia?
Did the smoothed analysis find its way into main stream analysis of algorithms? Is it common for algorithm designers to apply smoothed analysis to their algorithms?

# Answer
I could be wrong, but I view smoothed analysis as a way to *explain* the in-practice behaviour of algorithms that have bad theoretical guarantees (simplex, k-means, and so on). I'm not sure what it would mean to *use* smoothed analysis in practice, except to justify the use of a particular heuristic with bad worst-case performance ("My heuristic has blah blah worst-case behaviour but a smoothed analysis indicates that it will do well in practice etc etc")
> 12 votes

# Answer
The way people analyze algorithms in the real world is vastly different from academia. While in academia the goal is to find a provably-correct upper bound on the running time, in real life the goal is to understand how the algorithm works, and what tweaks can improve the running time. There are two main methods that are banned in academia but used in practice:

* The method of approximation. Here you use a lot of simplifying assumptions to try to forecast the running time of an algorithm. Similar to what theoretical physicists (used to) do.
* Experimentation. You run your algorithm and measure several statistics - how much time went to each part, how many times each function was called, how often was each branch run, and so on. This information can be used to optimize the algorithm. Experimentation is also used to find out whether some approximations done while analyzing the algorithm work in practice or not.

That said, I don't think that it's very common to analyze an algorithm in practice, other than to add some filler text in a related academic publication. The focus is either on software engineering or on low-level optimization, depending on the subject matter.

Finally, smoothed analysis is a heuristic that can be used to explain why algorithms work better in practice than their worst case would suggest - namely since some of the inputs are "random" in some sense. This heuristic can be used to approximate the behavior of the algorithm if one is using the method of approximation.
> 3 votes

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


# Question
Title: Connection between KMP prefix function and string matching automaton
Let $A\_P = (Q,\Sigma,\delta,0,\\{m\\})$ the *string matching automaton* for pattern $P \in \Sigma^m$, that is

* $Q = \\{0,1,\dots,m\\}$
* $\delta(q,a) = \sigma\_P(P\_{0,q}\cdot a)$ for all $q\in Q$ and $a\in \Sigma$

with $\sigma\_P(w)$ the length of the longest prefix of $P$ that is a Suffix of $w$, that is

$\qquad \displaystyle \sigma\_P(w) = \max \left\\{k \in \mathbb{N}\_0 \mid P\_{0,k} \sqsupset w \right\\}$.

Now, let $\pi$ the *prefix function* from the Knuth-Morris-Pratt algorithm, that is

$\qquad \displaystyle \pi\_P(q)= \max \\{k \mid k \< q \wedge P\_{0,k} \sqsupset P\_{0,q}\\}$.

As it turns out, one can use $\pi\_P$ to compute $\delta$ quickly; the central observation is:

> Assume above notions and $a \in \Sigma$. For $q \in \\{0,\dots,m\\}$ with $q = m$ or $P\_{q+1} \neq a$, it holds that
>
> $\qquad \displaystyle \delta(q,a) = \delta(\pi\_P(q),a)$

But how can I prove this?

---

For reference, this is how you compute $\pi\_P$:

```
m ← length[P ]
π[0] ← 0
k ← 0
for q ← 1 to m − 1 do
  while k > 0 and P [k + 1] =6 P [q] do
    k ← π[k]
    if P [k + 1] = P [q] then
       k ← k + 1
    end if
    π[q] ← k
 end while
end for

return π

```

# Answer
> 4 votes
First of all, note that by definition

* $\delta(q,a) = \sigma\_P(P\_{0,q}\cdot a) =: s\_1$ and
* $\delta(\pi\_P(q),a) = \sigma\_P(P\_{0,\pi\_P(q)}\cdot a) =: s\_2$.

Let us investigate $s\_1$ and $s\_2$ in a sketch:

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

Now assume $s\_2 \> s\_1$; this contradicts the maximal choice of $s\_1$ directly. If we assume $s\_1 \> s\_2$ we contradict the fact that *both* $s\_2$ and $\pi\_P(q)$ are chosen maximally, in particular because $\pi\_P(q) \geq s\_1 - 1$. As both cases cases lead to contradictions $s\_1=s\_2$ holds, q.e.d.

---

*As requested, a more elaborate version of the proof:*

Now we have to show $s\_1=s\_2$; we do this by showing that the opposite leads to contradictions.

* Assume $s\_2 \> s\_1$. Note that $P\_{0,s\_2} \sqsupset P\_{0,q}\cdot a$ because $P\_{0,s\_2} \sqsupset P\_{0,\pi\_P(q)}\cdot a$ and $P\_{0,\pi\_P(q)} \sqsupset P\_{0,q}$ by definition of $s\_2$. Therefore, $P\_{0,s\_2}$ -- a prefix of $P$ *and* a suffix of $P\_{0,q}\cdot a$ -- is *longer* than $P\_{0,s\_1}$, which is by definition of $s\_1$ the longest prefix of $P$ that is a suffix of $P\_{0,q}\cdot a$. This is a contradiction.

Before we continue with the other case, let us see that $\pi\_P(q) \geq s\_1 - 1$. Observe that because $P\_{0,s\_1} \sqsupset P\_{0,q}\cdot a$, we have $P\_{0,s-1} \sqsupset P\_{0,q}$. Assuming that $\pi\_P(q) \< s\_1 - 1$ immediately contradicts the maximal choice of $\pi\_P(q)$ ($s\_1 - 1$ is in the set $\pi\_P(q)$ is chosen from).

* Assume $s\_1 \> s\_2$. We have just shown $|P\_{0,\pi\_P(q)}\cdot a| \geq s\_1$, and remember that $P\_{0,\pi\_P(q)}\cdot a \sqsupset P\_{0,q} \cdot a$. Therefore, $s\_1 \> s\_2$ contradicts the maximal choice of $s\_2$ ($s\_1$ is in the set $s\_2$ is chosen from).

As neither $s\_1 \> s\_2$ nor $s\_2 \> s\_1$ can hold, we have proven that $s\_1 = s\_2$, q.e.d.

---
Tags: algorithms, finite-automata, strings, searching
---


# Question
Title: Grammar in formal languages versus programming language theory
Grammars seem to be used for different purposes. In formal languages, they are used to describe sequences of symbols. In programming language theory, they are used to describe objects in a term algebra (possibly enriched with some implicit, extra structure such as variable scoping rules). My question is, are these two kinds of grammars the *same notation reused for unrelated purposes*, or are they *describing the same things*? If they are unrelated, then do we have nomenclature to distinguish them?

For instance, the grammar

```
e ::= 1 | e e

```

could be describing a set of strings that includes "1", "1 1", and "1 1 1", or it could be describing a set of terms that includes "1", "1 1", "(1 1) 1", and "1 (1 1)".

# Answer
> 5 votes
Programming language theory usually does not care about parsing: it does not address this problem. So when you have this grammar in programming language theory:

```
e ::= 1 | e e

```

it does mean the same thing as in formal language theory but programming language theory really only talks about the generated syntax trees. However it is much better to have a non-ambiguous grammar. For example in the lambda-calculus, the grammar is written like this:

$$M ::= x ∣ λx.M ∣ M M$$

and things like $L M N$ have several meanings as you pointed out. Usually the author/context makes it non-ambiguous like this: he says the application case is left-associative, authorizes parentheses, or sometimes changes $MM$ into $(MM)$ and says "we omit parentheses when unnecessary" or several other ways.

In conclusion it may generates the same string for different trees but programming language theory only applies on the latter.

# Answer
> 5 votes
On top of jmad's answer I'll add that when talking about programming languages one usually distinguishes between *concrete syntax* and *abstract syntax*.

Concrete syntax is the one the programmer uses and when dealing with it one generally wants an unambiguous grammar, so often spurious elements such as semi-colons and `begin`-`end` keywords and the like are added to help the parser out.

Abstract syntax is the one a language theoretician is more concerned with. (It is also interesting inside the compiler internals.) The grammar rules are used more or less directly to express the abstract syntax trees, which means that parentheses are added implicitly to disambiguate whenever terms are written linearly.

---
Tags: formal-languages, programming-languages
---


# Question
Title: Nilsson's sequence score for 8-puzzle problem in A* algorithm
I am learning the A\* search algorithm on an 8-puzzle problem.

I don't have questions about A\*, but I have some for the heuristic score - Nilsson's sequence score.

Justin Heyes-Jones web pages - A\* Algorithm explains A\* very clearly. It has a picture for Nilsson's sequence scores.

It explains:

**Nilsson's sequence score**

> A tile in the center scores 1 (since it should be empty)
>
> For each tile not in the center, if the tile clockwise to it is not the one that should be clockwise to it then score 2.
>
> Multiply this sequence by three and finally add the total distance you need to move each tile back to its correct position.

I can't understand the steps above for calculating the scores.

For example, for the start state, what h = 17?

> 0 A C
>
> H B D
>
> G F E

So, by following the description,

`B` is in the center, so we have 1

Then `for each title not in the center, if the **tile** clockwise to **it** is not the one that should be clockwise to it then score 2.` I am not sure what this statement means.

What does the double starred `title` refer to?

What does the double starred `it` refer to?

Does the double starred `it` refer to the center title (B in this example)? Or does it refer to each title not in the center?

Is the next step that we start from `A`? So `C` should not be clockwise to `A`, then we have 2. And then `B` should be clockwise to `A`, then we ignore, and so on and so forth?

# Answer
See if this explanation can help you:

```
Current pos:   Goal:
*AC            ABC
HBD            H*D
GFE            GFE

```

How to calculate the score:

*Center*

```
B in the center -> 1

```

*Distances (manhattan distance)*

```
A must move LEFT -> 1
B must move UP   -> 1
sum of distances = 2

```

*Successors (clockwise)*

```
current: ACDEFGH*  (skip B because it is in the center)
goal:    ABCDEFGH

the [tile,tile clockwise to it] pairs  are:
[A,C], [C,D], [D,E], [E,F], [F,G], [G,H], [H,*]
([*,A] is not considered)

the "goal" pairs are:
[A,B], [B,C], [C,D], [D,E], [E,F], [F,G], [G,H], [H,A]

```

There are 2 pairs that do not match the goal pairs:

```
[A,C], [H,*]

```

So the final score is: $distances + 3\*(center + 2\*successors) = 2 + 3 * (1 + 2\*2) = 17$
> 3 votes

---
Tags: algorithms, machine-learning, search-algorithms, heuristics
---


# Question
Title: NP-completeness of a spanning tree problem
I was reviewing some NP-complete problems on this site, and I meet one interesting problem from

NP completeness proof of a spanning tree problem

In this problem, I am interested in the original problem, which the leaf set is precisely $S$. The author said that he can prove this by reducing it to the Hamiltonian path. However, I still cannot figure it out. Could anybody help me with this in details?

# Answer
Seems this question has been bumped by the system because it has no answer yet:

The idea JeffE proposed is to reduce the Hamiltonian Path problem (a known NP-complete problem) to this version of the spanning tree problem.

This is not hard to do: given a graph and two nodes we want to find an HPath between, we can set S to the set containing those two nodes and ask for a spanning tree with those nodes as leafs. Since a tree with just two leaves is a path, and a spanning path (that goes through all the nodes) is a Hamilton path, we can see how its possible to use an algorithm for the spanning tree eproblem to solve any Hamilton Path problem.

This proves that the spanning problem is NP-Hard. Since the problem is also clearly in NP, we thus can conclude that its NP complete.
> 3 votes

---
Tags: complexity-theory, np-complete, graphs, spanning-trees
---


# Question
Title: What is postorder traversal on this simple tree?
Given the following tree:

Which traversal method would give as result the following output: CDBEA?

The answer in my study guide is *Postorder*, but I think postorder would output: DEBCA. Am I wrong?

# Answer
> 4 votes
You are not wrong.

A *postorder* traversal visits the left subtree, then the right subtree, then the root of the current tree (recursively).

---
Tags: algorithms, trees
---


# Question
Title: Vapnik-Chervonenkis Dimension: why cannot four points on a line be shattered by rectangles?
So I'm reading *"Introduction to Machine Learning"* 2nd edition, by Bishop, et. all. On page 27 they discuss the Vapnik-Chervonenkis Dimension which is,

> *"The maximum number of points that can be shattered by H \[the hypothesis class\] is called the Vapnik-Chervonenkis (VC) Dimension of H, is denoted VC(H) and measures the capacity of H."*

Whereas "shatters" indicates a hypothesis $h \in H$ for a set of N data points such that it separates the positive examples from the negative. In such an example it is said that "H shatters N points".

So far I think I understand this. However, the authors lose me with the following:

> *"For example, four points on a line cannot be shattered by rectangles."*

There must be some concept here I'm not fully understanding, because I cannot understand why this is the case. Can anyone explain this to me?

# Answer
> 11 votes
The definition of "a set $P$ can be shattered by rectangles" is that for **every** subset of $P$, there is a rectangle that contains precisely that subset and excludes the rest of $P$. Equivalently, every labeling of the points as positive and negative is consistent with at least one hypothesis in $H$.

Now consider four points $p,q,r,s$ along a line in the plane. Since there is no rectangle that contains $p$ and $r$ but excludes $q$ and $s$, these four points cannot be shattered by rectangles.

---
Tags: machine-learning, vc-dimension
---


# Question
Title: Making random sources uniformly distributed
How do I build a random source that outputs the bits 0 and 1 with $prob(0) = prob(1) = 0.5$. We have access to another random source $S$ that outputs $a$ or $b$ with independent probabilities $prob(a)$ and $prob(b) = 1 - prob(a)$ that are unknown to us.

How do I state an algorithm that does the job and that does not consume more than an expected number of $(prob(a) \cdot prob(b))^{-1}$ symbols of $S$ between two output bits and prove its correcteness?

# Answer
Consider this: get two elements $x\_0$ and $x\_1$ from $S$. If $x\_0x\_1$ is $aa$ or $bb$ then discard them and repeat. Otherwise return $0$ for $ab$ and $1$ for $ba$, events that occur with the same probability $p\_ap\_b$.

This will use $2n$ elements from $S$, $n$ the number of performed steps. The probability of stopping at each step is $p=1-2p\_ap\_b$. The expected value of $2n$ is therefore $$2p\sum\_{n=1}^∞{n(1-p)^{n-1}}=\frac{2p}{(1-(1-p))^2}=\frac{1}{p\_ap\_b}\enspace.$$
> 7 votes

---
Tags: algorithms, probability-theory, randomized-algorithms, randomness
---


# Question
Title: Preprocess an array for counting an element in a slice (reduction to RMQ?)
Given an array $a\_1,\ldots,a\_n$ of natural numbers $\leq k$, where $k$ is a constant, I want to answer in $O(1)$ queries of the form: "how many times does $m$ appear in the array between indices $i$ and $j$"?

The array should be preprocessed in linear time. In particular I'd like to know if there's a reduction to Range Minimum Query.

---

This is equivalent to RMQ in the case where $k=1$ and you want to query the number of ones within an interval. So we can use it.
I couldn't answer my own question because of limits of SE.

# Answer
> 4 votes
Since $k$ is constant, we can store the count of each element in the range $0..m$ for $0\leq m \lt n$ in $0..n$ in $O(nk) = O(n)$ time and space. The primary observation is that you can make a two-dimensional array `count[pos][elem] = occurences of 'elem' in the indices 0..pos` in $O(nk)$ time, then query ranges by finding the difference in $i,j$ indices in constant time.

**Preprocessing**

```
initialise count[pos][elem] to 0 for all elem, pos
for pos=0 to n
  for num=0 to k
      count[pos][num] = (0 if pos==0 else count[pos-1][num])
  count[pos][arr[pos]] ++

```

**Query**

(assumes i,j are both inclusive bounds)

```
if i == 0
  return count[j][m]
else
  return count[j][m] - count[i-1][m]

```

If the array is also getting updated throughout the query process, you can use $k$ Fenwick (binary index) trees in place of the `count` array. This lets you update in $O(\log n)$ and query in $O(\log n)$.

Apologies for any issues with this answer, it's my first.

---
Tags: algorithms, arrays, algorithm-design
---


title: Branch and Bound explanation

text:
# Question
Title: Branch and Bound explanation
I have a test about the branch and bound algorithm. I understand theoretically how this algorithm works but I couldn't find examples that illustrates how this algorithm can be implemented practically.

I found some examples such as this one but I'm still confused about it. I also looked for travelling salesman problem and I couldn't understand it.

What I need is some problems and how can these problems solved by using branch and bound.

# Answer
Let's apply Branch and Bound to Knapsack, hopefully this will make the concept clear to you.

We have $n$ items, labelled $1$ through to $n$. $v\_i$ is the value of the $i$th item, and $w\_i$ its weight. We try to fit them in a knapsack that can contain up to $T$ weight in total, and we try to maximize the sum of the values of the item we put in the knapsack.

The ordinary backtrack approach is our basis. We first put $v\_1$ in the pack, and then solve the problem for the remaining $n-1$ items with recursion. We then remove $v\_1$ from the pack and solve the problem for the remaining $n-1$ items again, and we return the best configuration that we've found.

This backtracking is the 'Branch' part of Branch and Bound. You branch on (in the case of Knapsack) two cases: 'item $i$ is part of the solution' and 'item $i$ is not part of the solution'. You can visualize this as a binary tree, where the left child is one case and the right child is the other case. This tree is the *search tree* (or *search space*): its depth is $n$, and it therefore has $O(2^n)$ nodes. The algorithm therefore has a running time exponential in the number of items.

Now we get to the 'Bound' part: we try to find criteria such that we can say 'this configuration never work out, so we might as well not bother computing this'. An example of such a criterion is 'the weight of the items we've already put in the knapsack exceeds $T$': if we've added, say, the first $n/2$ items to the knapsack and it is therefore already full, there's no point trying to put items $n/2+1$ through to $n$ in the knapsack as well, but there's also no point in trying to fit any subset of $n/2+1$ through to $n$ in the knapsack, as it's already full, so we save about $2^{n/2}$ cases. Another example is '*even if I put in all the remaining items, the value of the items I've put in will not exceed the best configuration I've found so far*'.

These criteria essentially cut away parts of the search tree: at some node, you say for instance 'the left subtree will not give me a better configuration, because X', so you forget about that subtree and you don't explore it. A subtree of depth $d$ that you cut out this way saves you $O(2^d)$ nodes, which can be quite a bit of a speed increase if you're lucky.

Note that this is called '*Bounding*' because it usually involves some kind of lower or upper bound: for the criterion '*even if I put in all the remaining items, the value of the items I've put in will not exceed the best configuration I've found so far*', the value of your best configuration so far is a lower bound on the best configuration, so anything that will never make it past this lower bound is doomed to fail.

You can make the 'Bounding' part as complex as you like. For instance, integer programming problems are often solved using relaxations: you relax your program to a linear program, which you can solve in polynomial time, and then you can throw away a lot of cases for your binary variables that will never work out anyway. You then branch on the remaining options.

Note that Branch and Bound usually only gives you a speed increase in practice, but not in theory: it's hard to say exactly how much of the search tree is cut out using your heuristics. This is testified by the number of different heuristics used in practice on such problems. If you're unlucky, the remaining search tree remains huge even with a lot of bounding.
> 11 votes

# Answer
Consider scheduling, the task of assigning jobs with certain durations and deadlines to machines. We assume discrete time. Many such problems are NP(O)-hard.

In particular, this answer will talk about $1 \mid r\_i \mid L\_\max$, that is we schedule

* on one machine
* problems with release dates and we
* minimise maximum lateness $L\_\max$, that is the maximum difference between deadline and completion time over all jobs.

The decision version of this problem is NP-hard; this can be seen by reduction from 3PARTITION.

Interestingly enough, if we allow *preemption*, that is swapping out active jobs, the problem can be solved in quadratic time by the Earliest Due Date First heuristic (on modified due dates). It is easy to see that the optimal solution of this variant can be no worse than the optimal solution of the original problem.

Now, in order to apply Branch & Bound to this problem we need to fix some parameters:

* We compute lower bounds by allowing preemption and using EDD.
* We branch by fixing every of the unscheduled jobs as next one.
* We go to the child with smalles lower bound first.

You have to do this for every application of B&B.

---

For a concrete example, consider this instance of $1 \mid r\_i \mid L\_\max$:

$\qquad \displaystyle \begin{array}{c|cccc} i & 1 & 2 & 3 & 4 \\ \hline p\_i & 4 & 2 & 6 & 5 \\ r\_i & 0 & 1 & 3 & 5 \\ d\_i & 8 & 12 & 11 & 10 \end{array}$

with $p\_i$ the jobs' processing times, $r\_i$ the release dates and $d\_i$ the due dates.

Executing B&B as specified above, this happens:

This GIF does not loop. Reload it in a new tab to see from the beginning.
\[source\] \[static version\]

Note that out of 41 nodes, only four are visited properly and only for ten are lower bounds computed.
> 5 votes

---
Tags: algorithms, optimization, branch-and-bound
---


# Question
Title: Does the language of Regular Expressions need a push down automata to parse it?
I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular expresssions?

I assume it must be a push down automaton because the presense of brackets means the need to count and a DFA/NFA cannot perform arbitrary counting. Is this assumption correct? For example, the expression a(bc\*)d would require a PDA so that the sub-expression in brackets is handled correctly.

# Answer
You are correct. It is easy to show that the syntax of regular expressions is not regular using standard techniques.

One possibility is to use a homomorphism (which $\mathrm{REG}$ is closed against) to get rid of all symbols but the parentheses, which leaves you with the Dyck language which is well-known to be non-regular. If in doubt, use the Pumping lemma on $(^p)^p$.

That said, you probably do not want to code a PDA by hand. Consider using a parser generator like ANTLR or byacc. If, on the other hand, you want to investigate the parsing of languages by programming parsers yourself, you should continue with other basic parsing algorithms such as CYK, Earley, recursive descent and LR.
> 10 votes

# Answer
I suggest you to read the Jukka's nice answer to the question "Matching regular expressions using regular expressions" on cstheory, too. An excerpt:

> For example, we can modify the standard notation as follows to obtain *"compressed" regular expressions*:
>
> * You are allowed to remove any prefix that consists of a sequence of ('s
> * You are allowed to remove any suffix that consists of a sequence of )'s
>
> That is, `((a|b)*c)de(f|g)` can be expressed in the "compressed" notation using, for example, any of the following forms: `a|b)*c)de(f|g` or `((a|b)*c)de(f|g` or `(a|b)*c)de(f|g)`.
>
> \[...\]
>
> The "compressed" notation (of a regular expression) is a regular language.

This is only a link to an interesting (according to me) "different view" on the regular expression language; as underlined in the comments below, it is not useful for building a syntax tree. If you want to hand code your parser I'll suggest you this simple article on codeproject "Writing-own-regular-expression-parser".
> 3 votes

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


# Question
Title: How to go from a recurrence relation to a final complexity
I have an algorithm, shown below, that I need to analyze. Because it's recursive in nature I set up a recurrence relation.

```
//Input: Adjacency matrix A[1..n, 1..n]) of an undirected graph G
//Output: 1 (true) if G is complete and 0 (false) otherwise
GraphComplete(A[1..n, 1..n]) {
  if ( n = 1 )
    return 1 //one-vertex graph is complete by definition
  else
    if not GraphComplete(A[0..n − 1, 0..n − 1])
      return 0
    else
      for ( j ← 1 to n − 1 ) do
        if ( A[n, j] = 0 )
          return 0
      end
      return 1
}

```

Here is what I believe is a valid and correct recurrence relation:

$\qquad \begin{align} T(1) &= 0 \\ T(n) &= T(n-1) + n - 1 \quad \text{for } n \geq 2 \end{align}$

The "$n - 1$" is how many times the body of the for loop, specifically the "if A\[n,j\]=0" check, is executed.

The problem is, where do I go from here? How do I convert the above into something that actually shows what the resulting complexity is?

# Answer
> 10 votes
From what you wrote it seems that for all $k$ you have $T(k)=k-1+T(k-1)$ and $T(1)=0$. Therefore you can get it directly:

$$T(n)=(n-1)+(n-2)+\dots+1+0 = \sum\_{k=1}^{n}{(k-1)}=\frac{n(n-1)}{2}$$

So $T(n)$ is in $Θ(n^2)$.

# Answer
> 6 votes
The recursion you have there is this, if we count only matrix accesses:

$\qquad \begin{align} T(1) &= 0 \\ T(n) &= T(n-1) + n - 1 \quad \text{for } n \geq 2 \end{align}$

Note that it is only an upper bound on the runtime function because the loop is not always executed. It is a *linear* recurrence relation, and there are many ways of solving those. You can probably unroll $T(n)$, spot a pattern and prove it by induction. This does not always work, though, which is why I want to present a general technique.

This is my favorite way, using generating functions. It uses only mechanical calculation (once you get used to the approach). This is the ansatz:

$\qquad \begin{align} \mathcal{T}(z) &= \sum\_{n=1}^\infty T(n)z^n \\ &= 0 + \sum\_{n=2}^\infty T(n)z^n \\ &= \sum\_{n=2}^\infty (T(n-1) + n - 1)z^n \\ &= \sum\_{n=2}^\infty T(n-1)z^n + \sum\_{n=2}^\infty (n-1)z^n \\ &= z\sum\_{n=2}^\infty T(n-1)z^{n-1} + z\sum\_{n=2}^\infty (n-1)z^{n-1} \\ &= z\sum\_{n=1}^\infty T(n)z^{n} + z\sum\_{n=1}^\infty nz^{n} \\ &= z\mathcal{T}(z) + z\cdot\frac{z}{(1-z)^2} \end{align}$

For the identity needed for the last step, see the TCS Cheat Sheet. If we now solve this equation for $\mathcal{T}$, we get:

$\qquad \displaystyle \begin{align} \mathcal{T}(z) &= \frac{z^2}{(1-z)^3} \\ &= z^2\sum\_{n=0}^\infty \binom{n+2}{n}z^n \\ &= \sum\_{n=0}^\infty \frac{(n+2)(n+1)}{2}z^{n+2} \\ &= \sum\_{n=2}^\infty \frac{n(n-1)}{2}z^{n} \\ &= \sum\_{n=1}^\infty \frac{n(n-1)}{2}z^{n} \\ \end{align}$

For the first step, see again the Cheat Sheet. Remember that we started with $\mathcal{T}(z) = \sum\_{n=1}^\infty T(n)z^n$ so we can read the solution off the last line:

$\qquad \displaystyle T(n) = \frac{n(n-1)}{2} \in \Theta(n^2)$

---
Tags: algorithms, algorithm-analysis, runtime-analysis, recursion
---


# Question
Title: Relation between simple and regular grammars
I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with simple and regular (especially right linear) grammars which are very similar to each other.

What relation exists between these? What is the difference? Can you create (non-deterministic) finite automata for simple grammars (obviously without using a stack)?

# Answer
A Simple Grammar (s-grammar) is one in which every production is of the form $A \rightarrow aB\_1B\_2...B\_n$ where $a$ is a terminal, $n\ge0$ and all $B\_i, i\geq1 $ are non-terminals, and there is only one production with any pair $\langle A,a\rangle$.

Clearly, every s-language (produced by an s-grammar) is unambiguous and easily parsed, since each terminal symbol from left-to-right and non-terminal uniquely determine the production to apply. For example, if the string is $abc$, then the pair $\langle S,a\rangle$ uniquely determines the first production of the parsing, and so on for each terminal and the non-terminal to its immediate right. Thus, a language defined by an s-grammar can be parsed one symbol at a time, without lookahead, yielding linear parsing time, in fact, time $|x|$.

S-grammars are not terribly important in their own right, since most real languages exceed their power. But they are a stepping stone to other grammars parsed in linear time, such as $LL(k)$ grammars in which there is a bound $k$ on the lookahead needed to determine a production during parsing. In effect, an s-grammar is an $LL(0)$ grammar.

The connection to automata is that an s-langauge can be parsed with a pushdown automaton with a single state which just looks at the input symbol and top stack symbol to determine a string of stack symbols to push. But since the s-grammar

$\quad S \rightarrow aSB\mid \\#$
$\quad B \rightarrow a$

generates non-regular $\\{a^i\\#a^i:i \geq 0\\}$, s-languages cannot in general be recognized by finite-state automata, deterministic or non-deterministic.
> 17 votes

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


# Question
Title: Decide whether a context-free languages can be accepted by a deterministic pushdown automaton
Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa)

There **may** also exist a Deterministic Pushdown Automaton D that accepts exactly the language G accepts too. It depends on the grammar.

By what algorithm on the productions of G can we determine if D exists?

# Answer
> 21 votes
There is no algorithm that given a context-free grammar, decide if a DPDA recognizes the same language and computes it if it exists.

Because if such an algorithm existed, we would be able to decide the undecidable problem of the universality of a context-free grammar i.e. whether a given context-free grammar $G$ on $Σ$ recognizes the whole language $Σ^\*$.

Suppose there is such an algorithm $A\_{DPDA}$. Let $G$ be some context-free grammar. Let $L$ be $\mathcal L(G)$. Then the algorithm $A\_{DPDA}$ will decide if there is a DPDA $A$ recognizing $L$.

* If there is no such DPDA, then $L$ is not recognizable by a DPDA, in particular it is not regular, so it can't be $Σ^\*$.
* If a DPDA $A$ exists then we can decide if $L$ is equal to $Σ^\*$ because universality is decidable for DPDAs. Why? Because:

+ DPDA languages are closed under complementation (because DPDAs are deterministic)
    + emptiness is decidable for DPDAs (because it is for PDAs)

Using $A\_{DPDA}$ we have built an algorithm deciding whether $L(G)=Σ^\*$ for any context-free grammar $G$, which has been proven impossible. Therefore $A\_{DPDA}$ does not exist.

---
Tags: automata, context-free, pushdown-automata
---


title: Algorithm to chase a moving target

text:
# Question
Title: Algorithm to chase a moving target
Suppose that we have a black-box $f$ which we can query and reset. When we reset $f$, the state $f\_S$ of $f$ is set to an element chosen uniformly at random from the set $$\\{0, 1, ..., n - 1\\}$$ where $n$ is fixed and known for given $f$. To query $f$, an element $x$ (the guess) from $$\\{0, 1, ..., n - 1\\}$$ is provided, and the value returned is $(f\_S - x) \mod n$. Additionally, the state $f\_S$ of$f$ is set to a value $f\_S' = f\_S \pm k$, where $k$ is selected uniformly at random from $$\\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f\_S - x) \mod n)\\} $$

By making uniformly random guesses with each query, one would expect to have to make $n$ guesses before getting $f\_S = x$, with variance $n^2 - n$ (stated without proof).

Can an algorithm be designed to do better (i.e., make fewer guesses, possibly with less variance in the number of guesses)? How much better could it do (i.e., what's an optimal algorithm, and what is its performance)?

An efficient solution to this problem could have important cost-saving implications for shooting at a rabbit (confined to hopping on a circular track) in a dark room.

# Answer
> 13 votes
First of all, I will assume that by

> Additionally, the state $f\_S$ of $f$ is set to a value $f\_S' = f\_S \pm k$, where $k$ is selected uniformly at random from $$\\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f\_S - x) \mod n)\\} $$

you actually mean

> Additionally, the state $f\_S$ of $f$ is set to a value $f\_S' = f\_S + k \mod n$, where $k$ is selected uniformly at random from $$\left\\{- \left| \left\lfloor \frac{n}{2} \right\rfloor - ((f\_S - x) \mod n) \right|, \ldots, -1, 0, 1, 2, \ldots, \left| \left\lfloor \frac{n}{2} \right\rfloor - ((f\_S - x) \mod n) \right|\right\\} $$

Otherwise, it is not entirely clear that $f\_S \in \\{ 0, ..., n-1\\}$ always holds and how exactly $f\_S \pm k$ behaves.

Using this, the problem basically comes down to "missing as much as possible". Observe that the closer we shoot the rabbit, the larger hops he makes; in the extreme case we have $f\_S - x = \pm 1 \mod n$. This results in a uniform hop between $ -(\lfloor n/2 \rfloor \pm 1)$ and $ (\lfloor n/2 \rfloor \pm 1)$, which basically completely randomizes the position of the rabbit again. On the other hand, if we miss as badly as possible - by an offset of $f\_S - x \mod n = \lfloor n/2 \rfloor$, the rabbit actually does not move at all (!) *and* the black box actually updates us on this fact. Therefore, we can just turn around and shoot the rabbit.

We are left with finding a procedure for missing increasingly in each shot. I propose a simple "binary search". (I will conveniently omit the rounding.) It proceeds roughly as follows:

1. Reset and shoot at an arbitrary position until you get from the blackbox the answer $(f\_S - x \mod n) \in \\{ \frac{1}{4}n, ..., \frac{3}{4}n\\}.$ This takes a constant amount of steps in expectation.
2. Now, we know that the rabbit's past position $f\_S$, and that it did not move more than $\frac{1}{4}n$ steps in either direction. This basically halves our search space in the next iteration, since the rabbit has to be at a position $f\_S' \in \\{ (f\_S - \frac{1}{4}n) \mod n, ..., f\_S, ..., (f\_S + \frac{1}{4}n) \mod n \\}$
3. Recurse: Shoot at position $f\_S - n/2 \mod n$. With probability $1/2$, the position $f\_S'$ the rabbit jumped onto in step 1&2 lies the range $\\{ f\_S - \frac{1}{8}n, ..., f\_S, ..., f\_S + \frac{1}{8}n \\}$. In that case we halved the search space once more. With probability $1/2$, the rabbit did not jump in that range, but since we know that $f\_S' - x \mod n = f\_S' - f\_S + n/2 \mod n \in \\{ \frac{1}{2}n - \frac{1}{4}n, ..., \frac{1}{2}n + \frac{1}{4}n \\}$, we have the same assumptions as in step (2) and therefore lose nothing.

Each step needs $2 = \mathcal{O}(1)$ expected time to succeed and halves the search space, yielding an overall of $\mathcal{O}(\log n)$ expected number of steps.

---
Tags: algorithms, probability-theory, randomized-algorithms
---


# Question
Title: Deterministic and randomized communication complexity of set equality
Two processors $A, B$ with inputs $a \in \\{0, 1\\}^n$ (for $A$) and $b \in \\{0, 1\\}^n$ (for $B$) want to decide whether $a = b$. $A$ does not know $B$’s input and vice versa.

A can send a message $m(a) \in \\{0, 1\\}^n$ which $B$ can use to decide $a = b$. The communication and computation rules are called a *protocol*.

* Show that every deterministic protocol must satisfy $|m(a)| \ge n$.
* State a randomized protocol that uses only $O(\log\_2n)$ Bits. The protocol should always accept if $a = b$ and accept with probability at most $1/n$ otherwise. Prove its correctness.

# Answer
For the first point, try a counting argument. How many different messages $m(a)$ can $B$ receive, if $|m(a)|\<n$? How many different strings can $A$ have?

For the second point, try first analyzing the trivial randomized protocol (randomly fixing $\log(n)$ positions of the string and sending these bits of $a$). Clearly, this protocol always accepts if $a=b$. Assume $a\neq b$, what is the probability that $\log(n)$ randomly picked bits are the same? Does that suffice?
> 6 votes

---
Tags: algorithms, probability-theory, randomized-algorithms
---


# Question
Title: Proof that $\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$ is not (co-)recursively enumerable
I would like to use your help with the following problem:

$L=\\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \\}$. Show that $L \notin RE \cup CoRE$.

I know that to prove $L\notin RE$, it is enough to find a language $L'$ such that $L'\notin RE$ and show that there is a reduction from $L'$ to $L$ $(L'\leq \_M L)$.

I started to think of languages which I already know that they are not in $RE$, and I know that $Halt^\* =\\{⟨M⟩ ∣ M\mbox{ halts for every input} \\} \notin RE$. I thought of this reduction from $Halt^\*$ to $L$: $f(⟨M⟩)=(M')$. for every $⟨M⟩$: if $M$ halts for every input $L(M')=0^n1^n$ otherwise it would be $o^n1^n0^n$, but this is not correct, Isn't it? How can I check that $M$ halts for every input to begin with? and- is this the way to do that?

# Answer
> 8 votes
I think the question is how to show that $L$ is not r.e. One way to do that is to reduce the complement of the halting problem to $L$, because the complement of the halting problem is not r.e.

Here's a hint about one way to do that reduction: given $M$ and $x$, we want to make a language that is context free if and only if $M(x)$ does not halt. So start simulating $M$ on input $x$. As long as $M(x)$ does not halt, we make a language that looks like $\\{ 0^n : n \in \mathbb{N}\\}$. But if $M(x)$ does halt, we change the language we're generating after that point to be some r.e. but not context free language.

---
Tags: formal-languages, computability, context-free, turing-machines
---


# Question
Title: Transforming an NFA into an NFA of similar size but without $\epsilon$-transitions
I'm learning for the exam and have problems with this task:

> Describe an algorithm that transforms a given NFA $A = (Q, \Sigma, \delta, q\_0, F)$ (which may have $\epsilon$-transitions) into an equivalent NFA without $\epsilon$-transitions with the same condition number. And then determine the maturity of the algorithm. The algorithm should have a running time $O(|Q| · |\delta|)$ where $$|\delta| := \sum\_{\substack{q\in Q\\ a\in\Sigma\cup\\{\epsilon\\}}} |\delta(q,a)|$$

# Answer
The obvious answer is: the powerset construction gets rid of $\varepsilon$-transitions, so you can use it. It blows up the automaton exponentially in the worst case, though, so it is not directly applicable. However, you can use the part that deals with $\varepsilon$-transitions and keep nondeterminism.

> That is, if a state $q$ has an $\varepsilon$-transition to $q'$, add all outgoing transitions of $q'$ to $q$ and remove the $\varepsilon$-transition. You have to iterate this process for every state because there may be chains of $\varepsilon$-transitions. In the worst case, you reach all transitions (for every state), causing the required runtime bound (to be sharp).

Note that formally, this does not change the number of states. It might lead to isolated states, though, that can safely be dropped.
> 2 votes

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


# Question
Title: Prove that regular languages are closed under the cycle operator
I've got in a few days an exam and have problems to solve this task.

Let $L$ be a regular language over the alphabet $\Sigma$. We have the operation $\operatorname{cycle}(L) = \\{ xy \mid x,y\in \Sigma^\* \text{ and } yx\in L\\}$ And now we should show that $\operatorname{cycle}(L)$ is also regular.

The reference is that we could construct out of a DFA $D=(Q,\Sigma,\delta, q\_0, F)$ with $L(D) = L$ a $\epsilon$-NFA $N$ with $L(N) = \operatorname{cycle}(L)$ and $2 · |Q|^2 + 1$ states.

# Answer
> 17 votes
The idea is to decide nondeterministically at the beginning how much the word is cycled, and have a copy of the automaton for every case. In terms of the automaton, that means that we guess in which state $D$ would have been after consuming a word's prefix (which is a suffix of our input), and start in that state.

Now the construction. For every state $q \in Q$, separate $D$ into two parts $A\_1$ and $A\_2$. $A\_1$ contains the states from which $q$ is reachable and $A\_2$ the states that are reachable from $q$:

\[source\]

Note that any given node may be contained in both $A\_1$ and $A\_2$. Therefore, the number of states can double if we make this step explicit.

Now we rewire this automaton so it accepts all words for which $q$ marks the "cycle point":

\[source\]

We get $|Q|$ automata of this form; create a new initial state which has $\varepsilon$-transitions to all their starting states. The resulting automaton accepts $\operatorname{cycle}(L)$. Altogether, we get at most $|Q|\cdot(2|Q|+1) + 1$ states, only $|Q|$ more states than the reference claims are possible.

You can achieve $2|Q|^2 + 1$ states by modifying the component automata a little bit; eliminate all $q\_0$ by replacing the incoming $\varepsilon$-transitions with copies of its outgoing transitions. That is, for every pair of transitions $(q\_1,\varepsilon,q\_0), (q\_0,a,q\_2)$, introduce a transition $(q\_1,a,q\_2)$.

Rigorous construction and correctness proof remain as exercise.

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


# Question
Title: Compare-and-Swap in an RDBMS for custom locks and lock escalation
I'm applying the Compare-and-Swap technique to a SQL database to create custom row-level locking in my dataset, allowing for safe READ UNCOMMITTED isolation at the database level.

The Resource table includes a LockOwner `GUID` and a IsLocked `BIT` field. To acquire a lock, a dirty-read query gets the ID, LockOwner, and LockStatus. If `Unlocked`, attempt to `UPDATE` the Resource by (ID, LockOwner) with a newly generated LockOwner and LockStatus of `Locked`. Abort and start again if no rows are updated - meaning someone else got there first. Otherwise, the Lock is held in the READ UNCOMMITTED transaction. The transaction is needed to allow rollback on client failure/abandon, but the dirty reads avoid locks.

**This seems to me to work great for resources that are independent of each other. But what must I add to account for a new kind of lock, ResourceGroup?**

ResourceGroup to Resource is a one-to-many relationship. Resources can be locked individually, but if the ResourceGroup needs to be locked, then all of the Resources must also be locked.

Locking a ResourceGroup is a far less frequent need than locking a Resource, so the scheme should be optimized for Resource queries, avoiding requiring joins to ResourceGroup if possible.

I am imagining a scenario where locking a ResourceGroup involves marking the member rows with some flag, but I'm not sure what scheme doesn't interfere with the original Resource-only scheme. Part of the problem comes from the UPDATE of a Resource while it is locked (and therefore already UPDATED in another transaction). I believe that even if the fields are different within the record, the UPDATE will place an UPDATE LOCK on the row, so any lock on ResourceGroup would introduce blocking that we are trying to avoid. Even if we could do this, how would the ResourceGroup lock acquisition mechanism know when all of the Resources (which may have had locks in process as we began locking their peers) have been released?

There may be differences in this locking granularity by RDBMS, I'm on MS SQL 2005+.

# Answer
> 3 votes
The Prevent race conditions across multiple rows on Stackoverflow seems to be relevant.

Also, I would urge you to use SQL server locks instead of your own lock column (which it sounds like you're doing).

And it looks like doing hierarchical locks is kind of clumsy in SQL, so if you're finding this to be a huge bottleneck you could try a locking service like zookeeper.

---
Tags: concurrency, database-theory
---


# Question
Title: Why absence of surjection with the power set is not enough to prove the existence of an undecidable language?
From this statement

> As there is no surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, thus there must exist an undecidable language.

I would like to understand why similar reasoning does not work with a *finite* set $B$ which also has no surjection onto $\mathcal{P}(B)$! (with $|B|=K$ and $K \in \mathbb{N}$)

Why is there a minimum need for the infinite set?

**EDIT Note:**

Although I chose an answer, many answers **and all comments** are important.

# Answer
> 6 votes
If you take any finite set $A$ of TMs, there is a language not decided by any TM in $A$ and the finite powerset would suffice for that. But this is not what we want. We want to show that there is an undecidable language, i.e. a language that *no* TM can decide it. The cardinality difference between a finite set and its power set would not show that. You need the cardinality difference with the set of all TMs which is countable to say there is a language which is not decided by any machine in the set.

# Answer
> 6 votes
Let us first recapitulate in which context the cited statement makes sense.

1. Let us restrict ourselves to the domain of (decision) functions in $\mathbb{N} \to \\{0,1\\}$ (a subset of all functions).
2. Every such function corresponds to one element of $\mathcal{P}(\mathbb{N})$ (see characteristic function).
3. There are countably many Turing machines (simple encoding).

By 1. and 2., there are uncountably many functions. Therefore, there are functions that have no corresponding Turing machine, that is they are not computable. There are simply *too many* functions; this is what is meant by "there is no surjection".

Now, there are only countably many finite sets in $\mathcal{P}(\mathbb{N})$(extension of Cantor's pairing function). Therefore, the same contradiction can not be derived when only considering finite sets.

If you add some infinite sets to your base set so it becomes uncountable, there is no reason to believe some of the finite sets were undecidable; you only know that there *are* some undecidable sets. In fact, all finite sets are decidable, so the culprits are always infinite sets.

---
Tags: formal-languages, computability, undecidability
---


# Question
Title: Is the set of LL(*) grammars the same as the set of CFG grammars?
Is the set of LL(\*) grammars the same as the set of context-free grammars?

# Answer
> 7 votes
No, since no `LL(*)` grammar can be left-recursive and obviously there are context-free grammars which are left-recursive.

As requested: A sample of a left-recursive, context-free grammar (which is therefore not `LL(*)`) :

```
S -> S x
   | ɛ

```

The language this grammar describes is *one or more times the character 'x'*.

# Answer
> 7 votes
Static LL(\*) grammar analysis is undecidable. In other words, there are some grammars that are LL(\*) but we can't figure this out statically. ANTLR v3 fails over to backtracking in this case and therefore can exhibit the PEG A-\>a/ab problem where ab is dead code in the cases where grammar analysis failed.

In ANTLR v4, I'm introducing adaptive LL(\*), which does all grammar analysis at runtime. Because I have an actual input stream in my paw, I can discover every LL(\*) decision. I'm also including full LL context (vs Strong LL == SLL context which is weaker). Because I also rewrite all immediate left recursion on-the-fly, ANTLR v4 handles all CFG except for indirect left recursive ones. These are much less common than the immediate left recursive ones like expressions.

```
e : e '*' e
  | e '+' e
  | INT
  ;

```

This works fine in v4. operator precedence is assumed to go from highest to lowest for ambiguous alternatives.

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


# Question
Title: Machine Learning algorithms based on "structural risk minimization"?
Which machine learning algorithms (besides SVM's) use the principle of structural risk minimization?

# Answer
The structural risk minimization principle is a principle that is at least partly 'used' in all machine learning methods, since overfitting is often to be taken into account: reducing the complexity of the model is (supposedly and in practice) a good way to limit overfitting.

* SVMs explicitly have a parameter for the complexity (the dimension of the feature space, or even the kernel function) and it's necessary because increasing the complexity is a part of the learning algorithm.
* Neuronal networks also have a easy indicator of their complexity (number of 'cells') and is part of the associated learning algorithm.
* Without this principle grammar inference would be both stupid and perfect grammar is the list of all possible words, so every non-trivial algorithm at least acknowledges this principle.
* Decision trees have their own notion of entropy.
* Clusters can be simply counted or kind of 'use' the principle intrinsically or have a fixed number of clusters and in that case you apply the principle at a higher level.

To be perfectly honest I don't really know about what happens in genetic programming but they don't have an intrinsic notion of complexity.

I don't know well Inductive logic programming but it doesn't seem to scale very well to this principle.
> 9 votes

---
Tags: reference-request, machine-learning
---


title: Optimal path - best career

text:
# Question
Title: Optimal path - best career
I am new and I have to develop an algorithm with a 2d integer array as input to compute the best career path. Lets consider a network with n nodes, which are numbered from $1$ to $n$. All are connected one to the other.

To move from node $i$ to node $j$ can have different costs (classical example job changing):

* positive value indicates a benefit
* negative value indicates a loss
* some steps have a cost of $0$

Each entry of $B\[i, j\]$ indicates the beneﬁt (or the cost, if negative), of a step from node $i$ to node $j$.

I need to find out the maximal gain of a path from i to j is

$$ G(i, j) = \max { \\{ g(p) \mid \text{ p is a path from i to j} \\} } $$

It is not possible to gain from walking in a cycle. This means, the values in B must be such that for any path p from a node i to itself, we have $g(p) \leq 0$.

Ex of matrix B:

$$ \begin{array}{cc} 0 & 1 & 0 & 1 \\\\ −2 & 0 & 0 & −2 \\\\ 0 & 2 & 0 & 1 \\\\ −3 & −1 & −3 & 0 \end{array} $$

Hints:

1) Cycles bring no gain. Therefore, the greatest possible beneﬁt of moving from $i$ to $j$ can be achieved by visiting any intermediate node at most once.

2) Consider the following variant of the problem. Let $G\_{aux}(i, j, k)$ be the maximal gain that can be achieved by walking from $i$ to $j$ along a path that uses only the nodes $1, \ldots, k$ as intermediate points.

The tasks asked:

1. Explain how $G\_{aux}(i, j, k)$ can be used to compute $G(i, j)$. Develop a recurrence for $G\_{aux}(i, j, k)$.
2. Write pseudo-code for algorithms that compute arrays with all values of $G\_{aux}$ and $G$ and explain why your algorithms are correct.

Who can help me with this tasks? Is the basis of all this task the Floyd-Warshall's algorithm ? right?

# Answer
> 4 votes
Be sure to complete the first task before reading below.

Hint 1:

> What are the conditions necessary to use the Floyd-Warshall's algorithm? Does it match those of your exercise?

Hint 2:

> Well, I think you are ready to write the corresponding pseudo-code :-)

---
Tags: algorithms
---


# Question
Title: Use closure properties to transform languages to $L := \{ a^nb^n : n\in \mathbb N \}$
For the purpose of proving that they are not regular, what closure properties can I use to transform the languages

1. $L\_a = \\{ a^\*cw \mid w \in \\{a,b \\}^\* \land |w|\_a = |w|\_b \\}$ and
2. $L\_b = \\{ab^{i\_1}ab^{i\_2}\ldots ab^{i\_n} \mid i\_j∈\mathbb N \land \exists j∈\[1,n\] \ i\_j \not= j \\}$

to $L := \\{ a^nb^n \mid n\in \mathbb N \\}$, respectively?

I tried:

1. $L\_a = \\{ a^\*cw \mid w \in \\{a,b \\}^\* \land |w|\_a = |w|\_b \\}$

$L\_a' = \\{ \\{a,d\\}^\*cw \mid w \in \\{a,b,d \\}^\* \land |w|\_a + |w|\_d = |w|\_b \\}$ (union?)

$L\_a'' = \\{ d^\*cw \mid w \in \\{a,b \\}^\* \land |w|\_a = |w|\_b \\}$ (concatenation?)

$L\_a''' = \\{ w \mid w \in \\{a,b \\}^\* \land |w|\_a = |w|\_b \\}$ (homomorphism?)
2. $L\_b = \\{ab^{i\_1}ab^{i\_2}\ldots ab^{i\_n} \mid i\_j∈\mathbb N \land\exists j∈\[1,n\] \ i\_j \not= j \\}$

$L\_b' = \\{ab^{i\_1}ab^{i\_2}\ldots ab^{i\_n} \mid i\_j∈\mathbb N \land\forall j∈\[1,n\] \ i\_j = j \\}$ (complement?)

$L\_b'' = \\{ac^{i\_1}ac^{i\_2}\ldots ac^{i\_n} \mid i\_j∈\mathbb N \land\forall j∈\[1,n\] \ i\_j = j \\}$ (homomorphism?)

# Answer
> 3 votes
Regular languages are closed under intersection. This often allows to cut away all parts of a language that are not needed to show non-regularity. Complementation serves a similar purpose: if the original language is "complicated", the complement may be simpler so work with (in terms of other closure properties).

Hints:

> For $L\_a$, the part right of $c$ is sufficient; try to intersect with a regular expression that gets rid of the clutter. Note that the part right of $c$ is close to $L$. Maybe another regular expression can help?
> For $L\_b$, note that we get $n$ times $a$ and $b$ (in the last block), respectively, if we replace $\exists \dots i\_j \neq j$ with $\forall \dots i\_j=j$.

Complete solution for $L\_a$:

> Let $L\_a' := L\_a \cap \mathcal{L}(ca^\*b^\*) = \\{ ca^nb^n \mid n \in \mathbb{N} \\}$. Then, with homomorphism $\phi : \\{a,b,c\\} \to \\{a,b\\}^\*$ defined by
> $\qquad \displaystyle \phi(w) = \begin{cases} \varepsilon &, w = c \\ w &, \text{ else} \end{cases}$
> we have $\phi(L\_a') = L$.

Complete solution for $L\_b$:

> In order to get rid of the pesky $\exists$, we can complement. That introduces lots of words we do not want, i.e. such that don't have the $(ab^\*)^\*$ structure, so we can intersect with exactly that regular expression to get structure back:
> $\qquad \displaystyle L\_b' := \overline{L\_b} \cap \mathcal{L}((ab^\*)^\*) = \\{ abab^2ab^3\dots ab^n \mid n \in \mathbb{N} \\}$.
> Note that words in $L\_b'$ contain exactly $n$ times the symbol $a$; if we can get rid of all blocks of $b$ but the last, we have $L$. This is possible by (nondeterministic) finite state transduction which $\mathsf{REG}$ is closed under. The transducer removes all $b$ until it decides on an $a$ that is was the last one. After that it emits the input and accepts if no further $a$ is encountered.
> Note that if we reverse $L\_b'$, we can cut away the excess $b$ with a deterministic transducer and reverse again to obtain $L$.

# Answer
> 2 votes
Hint: for $L\_a$ you can use stability with intersection from $L\_a'''$.

# Answer
> 1 votes
1. $L\_a = \\{ a^\*cw \mid w \in \\{a,b \\}^\* \land |w|\_a = |w|\_b \\}$

> $L\_a \cup d^\* = L\_a'$

$L\_a' = \\{ \\{a,d\\}^\*cw \mid w \in \\{a,b,d \\}^\* \land |w|\_a + |w|\_d = |w|\_b \\}$ (union?)

> $L\_a' \cap a^\*cw = L\_a''$

$L\_a'' = \\{ d^\*cw \mid w \in \\{a,b \\}^\* \land |w|\_a = |w|\_b \\}$

> homomorphism $ h(d) = \epsilon, h(c) = \epsilon, h(a) = a, h(b) = b $

$L\_a''' = \\{ w \mid w \in \\{a,b \\}^\* \land |w|\_a = |w|\_b \\}$

> $L\_a''' = L := \\{ a^nb^n \mid n\in \mathbb N \\}$ is the same but other syntax?
2. $L\_b = \\{ab^{i\_1}ab^{i\_2}\ldots ab^{i\_n} \mid i\_j∈\mathbb N \land\exists j∈\[1,n\] \ i\_j \not= j \\}$

> $\overline L\_b = L\_b'$ so follows $\forall j∈\[1,n\] \ i\_j = j $

$L\_b' = \\{ab^{i\_1}ab^{i\_2}\ldots ab^{i\_n} \mid i\_j∈\mathbb N \land\forall j∈\[1,n\] \ i\_j = j \\}$ (complement?)

> homomorphism $ h(b) = c, h(a) = a $ i say b is know my new c - is my idea of thislanguage correct? - $ab abb abbb ... ab^n$ ? O.o

$L\_b'' = \\{ac^{i\_1}ac^{i\_2}\ldots ac^{i\_n} \mid i\_j∈\mathbb N \land\forall j∈\[1,n\] \ i\_j = j \\}$

> $L\_b'' \cap a^\*b^\*$ and than homorphism $h(a) = a, h(b)=b, h(c) = \epsilon \\\ $ first we have $a \epsilon ^{i\_1}a \epsilon ^{i\_2}\ldots a \epsilon ^{i\_n}$ and than $a^\*b^\*$. Can anyone give me a hint for the transformation to $a^nb^n$?

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


# Question
Title: DLOGTIME complexity class and testing the length of the input string
I read that testing the length of the input string is in DLOGTIME.

The question is how can testing the length of the input string be in DLOGTIME?

$\text{DLOGTIME} = O(\log n)$, so what number would be in $n$? (as it seems that $n$ is definitely not the length of the input string..... or is it?)

So, to summarize, can anyone show me how the algorithm performs and how it is in DLOGTIME? At this point, it seems to me that $n$ is just an arbitary number..

Note: I know what binary search is :) so you do not need to explain me about what that is.

# Answer
It is hard to answer the question without further context.

Complexity is typically defined in terms of the size of the input (the number of bits needed to represent the input) and therefor depends on the representation you choose for the inputs. (More formally, a language or a formal computational problem is defined over strings of the alphabet, and the complexity is defined based on that, how you interpret these strings as objects (e.g. graphs, natural numbers, etc.) doesn't have an effect on the complexity, a "problem" corresponds to several (formal) computational problems based on the representations used.)

The complexity class $\mathsf{DLogTime}$ is defined as deterministic logarithmic time in the input size, $n$ is the size of the input. I guess you are confused because we typically use Turing machines for defining complexity classes but that may not make sense for sublinear time since one cannot even read the input. For sublinear time the model of computation is typically considered to be *Random Access Machines* where one can access any bit of the input directly without going over all previous bits using indexes (kind of similar to how memory works in real computers).

One can find the length of the input in two steps using an index variable (a binary number):

1. Start from 1 and repeatedly double the value till the memory square corresponding to it is blank (an upper bound on the length of the input),
2. Do a binary search to find the last nonblank symbol. (Blank symbol is not used in the input.)

If the input is a string of length $n$ then this algorithm will find the size of the input in binary in time $O(\lg n)$.
> 6 votes

# Answer
The model for $\text{DLOGTIME}$ is such that the input is given on a tape which has random access so you can "read" parts of it without "counting" the time needed to move the end. If so, then binary search solves it quite straightforwardly, and maybe this is what you meant to ask.

Changing the model is necessary when discussing complexity classes which are sub-linear, so that the machine will be able to read the input without "consuming" resources. As a similar example, the class $\text{DL}$ (deterministic logarithmic *space*) defines the model as follows: the input is given on a read-only input tape; in addition there is a read/write working tape. The space you use is counted only for the working tape, which means you are able to read the entire input without consuming any memory.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Is there an undecidable finite language of finite words?
Is there *a need* for $L\subseteq \Sigma^\*$ to be *infinite* to be undecidable?

I mean what if we choose a language $L'$ be a *bounded finite version of* $L\subseteq \Sigma^\*$, that is $|L'|\leq N$, ($N \in \mathbb{N}$), with $L' \subset L$. Is it possible for $L'$ to be an undecidable language?

I see that there is a problem of "How to choose the $N$ words that $\in$ $L' "$ for which we have to establish a rule for choosing which would be the first $N$ elements of $L'$, a kind of "finite" Kleene star operation. The aim is to find undecidability language without needing an infinite set, but I can't see it.

**EDIT Note:**

Although I chose an answer, many answers **and all comments** are important.

# Answer
> 15 votes
Yes, there is a need for $L$ to be infinite in order to be undecidable.

To add up on the answers of Raphael and Sam, you should think about "decidable" as things that a computer-program can solve. The program required is very simple, it just needs to output "Yes" for elements in $L$, or otherwise, say no.

So the more "complex" $L$ is, the longer the program you are required to write. In other words, the longer the program you run, you can check more things... So if someone gives a language $L$ which is finite, say $L=\\{ a\_1, a\_2, \ldots, a\_n\\}$, you can write the following program:

```
if INPUT = $a_1$ output Yes;
if INPUT = $a_2$ output Yes;
...
if INPUT = $a_n$ output Yes;
output No;

```

Now, if some one gives you a larger $L$ (yet finite), you will just write a longer program. This is always true, and any finite $L$ will have it's own program. The only "interesting" case is what happens when $L$ is infinite - your program **cannot** be infinite.

The issue of "undecidability" is even more interesting: its those (infinite) $L$'s that have no program that works correctly for them. We know that such languages must exists since there are way more (infinite) languages $L$ than the number of programs of finite (but unbounded) length.

# Answer
> 10 votes
I'm not sure I understand the question properly but every finite language is regular. There are no regular languages which are undecidable and therefore there are no finite languages which are undecidable. All of these statements are well-known and proofs can be found in Hopcroft and Ullman.

# Answer
> 8 votes
If your language $L'$ is finite, you can perform table lookup on a hardcoded table containing all words in $L'$. This is awkward to write down as Turing machine, but in other, equivalent models that is quite clear.

In fact, finite automata are sufficient. Construct an automaton for $L'$ as follows:

1. For every $w \in L'$, create a linear chain of states that accepts $w$.
2. Create a new initial state $q\_0$.
3. Connect $q\_0$ to the initial states of all automata constructed in 1. with $\varepsilon$-transitions.

The thus constructed automaton obviously accepts $L'$. Therefore, $L'$ is regular and therewith computable (by $\mathrm{REG} \subsetneq \mathrm{RE}$).

Note that the some reasoning applies for *co-finite* $L'$, that is $\big|\overline{L'}\big| \< \infty$; you just hardcode the elements *not* in $L'$.

# Answer
> 2 votes
To be at all interesting (for the purpose of thinking about computability) a decision problem has to have infinitely many "yes" answers and infinitely many "no" answers. Such decision problems correspond exactly to languages contain infinitely many strings over their alphabet and also exclude infinitely many strings over their alphabet.

Anything else is trivially able to be encoded in only a finite amount of information (at worst simply a big list of strings either in or not in the language), and therefore computable by simple DFAs / regular expressions. I would hope it should be obvious that for any finite list of strings you can immediately write down a regular expression that simply ORs all of the strings.

A witticism of my Theory of Computation lecturer was that the problem of "does God exist?" is computable - it is either computed by a machine that immediately accepts, or a machine that immediately rejects; we just don't know which one!

---
Tags: formal-languages, computability, undecidability
---


# Question
Title: Is open adressing with prime steps bijective?
Who can help me with this topic: Probing with a step width that is a prime number.

I am struggling with this question about defining a hashing function $h(k, i)$ for open addressing on a table of length m, that is, with slots numbers $0, 1, 2, \dots ,m − 1$.

We know that a function $h(k, i) = h\_1(k) + i \cdot h\_2(k) \mod m$ produces a permutation for every $k$ if $h\_2(k)$ and $m$ are relatively prime, that is, if $\operatorname{gcd}(h\_2(k),m) = 1$.

We can assume that $m, w$ be integers such that the greatest common divisor $\operatorname{gcd}(m,w) = 1$.

How can I prove that the function above

$\qquad f : \\{ 0, \dots,m − 1 \\} \to \\{ 0, \dots,m − 1 \\}\\ \qquad f(i) = i \cdot w \mod m$

is a permutation, in other words, a bijective function?

# Answer
> 4 votes
The following proof only uses basic modular arithmetic, and the fact that the least common multiple $\mathrm{lcm}(a,b)$ is equal to $a\cdot b$, if $\gcd(a,b)=1$.

## Injectivity:

Assume there are two different $a,b\in \\{0,...,m-1\\}$, $a\>b$, such that $f(a)=f(b)$. This means that

$$ a\cdot w \mod m = b\cdot w \mod m $$ and $$ a\cdot w=b\cdot w+k\cdot m $$ for some integer $k\>0$. We reorder to $$ (a-b)\cdot w=k\cdot m $$ Both sides of the equation are a multiple of $w$ and $m$. However, since $w$ and $m$ don't share any divisor, any common multiple is larger than $w\cdot m$. The left hand side of the equation clearly contradicts this fact. Hence, there are no such choices for $a$ and $b$, and $f$ is injective.

## Surjectivity

This can be argued by counting. The function $f$ is total on the set $\\{0,...,m-1\\}$, and since $f$ is injective as shown above, $f$ is also surjective.

---
Tags: algorithms, hash-tables, hash
---


# Question
Title: Finding small node sets that can not be avoided on paths from source to sink
In a directed graph with a starting node and an ending node, how to find a small (doesn't have to be smallest. \<10 for example) set S of nodes such that every possible path from the starting node to the ending node contains at least one member of set S. The graph may have loops. This may be NP hard. Is there an approximate method to find one or several such S from the graph? Enumerating and testing every candidate seems not work. thanks.

# Answer
Finding the smallest number of *edges* instead of vertices is the famous Minimum Cut problem which can be solved using any of the Max-Flow-Min-Cut algorithms. Picking vertices is a specific case of the generalised max-flow-min-cut theorem and similar algorithms can be used to solve it. In any case, it can be formulated as a linear program with polynomial complexity, which can be solved in polynomial time using any of the LP-solvers.
> 4 votes

---
Tags: algorithms, graphs
---


# Question
Title: Probabilistic poly-time machine always halts on all inputs?
In the usual definition of probabilistic poly-time machine it is said that the machine halts in polynomial time for all inputs.

Is the intention really to say that the machine halts for all inputs, or that if it halts it must be in polynomial time?

# Answer
We say that a probabilistic Turing machine M runs in time T(n) if *for any input x* M halts in less than T(|x|) steps independently of the random choices it makes during the computation (worst case over all possible computation paths).

For example, the most general definition of *Probabilistic Polynomial-time*, namely PP, is:

> A language L is in PP if and only if there exists a probabilistic Turing machine M, such that
>
> * M runs for polynomial time on all inputs
> * For all x in L, M outputs 1 with probability strictly greater than 1/2
> * For all x not in L, M outputs 1 with probability less than or equal to 1/2.

It always halts in polynomial time on all inputs.

Because the two probabilities can be made very close ($\frac{1}{2}+\frac{1}{2^n},\frac{1}{2}-\frac{1}{2^n}$), it would take potentially an exponential number of runs to distinguish accepting from rejecting with good confidence; so a more representative and efficient probabilistic class is BPP (Bounded-error Probabilistic Polynomial-time):

> A language L is in BPP if and only if there exists a probabilistic Turing machine M, such that
>
> * M runs for polynomial time on all inputs
> * For all x in L, M outputs 1 with probability greater than or equal to 2/3
> * For all x not in L, M outputs 1 with probability less than or equal to 1/3.

Again, M always halts in polynomial time on all inputs.

See also the complexity class RP (Randomized Polynomial time).

We have: $RP \subseteq BPP \subseteq PP$
> 6 votes

---
Tags: complexity-theory, terminology, turing-machines, probabilistic-algorithms
---


title: Low-degree nodes in sparse graphs

text:
# Question
Title: Low-degree nodes in sparse graphs
Let $G = (V,E)$ be a graph having $n$ vertices, none of which are isolated, and $n−1$ edges, where $n \geq 2$. Show that $G$ contains at least two vertices of degree one.

I have tried to solve this problem by using the property $\sum\_{v \in V} \operatorname{deg}(v) = 2|E|$. Can this problem be solved by using pigeon hole principle?

# Answer
Yes, it can.

You have $n-1$ edges, which means $2n-2$ holes for node-pigeons. If every node is supposed to have degree two (or more), we have to place (at least) two pigeons for each node, that makes a total of $2n$ pigeons.

By said principle, (at least) two pigeons do not find a solitary hole, which means (at least) one node is isolated or (at least) two nodes have only one edge. As no node is isolated by assumption, you have (at least) two nodes with degree one.
> 7 votes

# Answer
Since the number of edges is $n-1$, the graph is a tree. Take a starting vertex $v$ in $V(G)$. Now start walking in any direction, and keep walking, without repeating a vertex. Since $G$ is finite, and does not contain a cycle, this process will eventually stop in a vertex $u$ of degree 1. If $v$ also had degree 1, we are done. If not, start a new walk in some other direction out of $v$. This walk also ends in a vertex of degree 1.
> 3 votes

---
Tags: graphs, proof-techniques
---


# Question
Title: How many layers should a neural network have?
Are there any advantages of having more than 2 hidden layers in a Neural Network?

I've seen some places that recommend it, others prove that there is no advantage.

Which one is right?

# Answer
> 7 votes
One very good resource is the Neural Network FAQ. The question depends a lot on your problem. If the problem is linear in nature, there is no reason to have any hidden layers. If the problem is non-linear, often a single hidden layer with around 10 hidden neurons will do the trick.

There is a very similar question (with a very similar answer) at CrossValidated: How to choose the number of hidden layers and nodes in a feedforward neural network?)

---
Tags: artificial-intelligence, neural-networks, neural-computing
---


# Question
Title: How do you check if two algorithms return the same result for any input?
How do you check if two algorithms (say, Merge sort and Naïve sort) return the same result for any input, when the set of all inputs is infinite?

**Update:** Thank you Ben for describing how this is impossible to do algorithmically in the general case. Dave's answer is a great summary of both algorithmic and manual (subject to human wit and metaphor) methods that don't always work, but are quite effective.

# Answer
In contrast to what the nay-sayers say, there are many effective techniques for doing this.

* Bisimulation is one approach. See for example, Gordon's paper on Coinduction and Functional Programming.
* Another approach is to use operational theories of program equivalence, such as the work of Pitts.
* A third approach is to verify that both programs satisfy the same functional specification. There are thousands of papers on this approach.
* A fourth approach is to show that one program can be rewritten into the other using sound program transformations.

Of course none of these methods is complete due undecidability, but volumes and volumes of work has been produced to address the problem.
> 20 votes

# Answer
To elaborate slightly on the "it's impossible" statements, here's a simple proof sketch.

We can model algorithms with output by Turing Machines which halt with their output on their tape. If you want to have machines that can halt by either accepting with output on their tape or rejecting (in which case there's no output) you can easily come up with an encoding that allows you to model these machines with the "halt or halt not, there is no reject" machines.

Now, assume I have an algorithm **P** for determining whether two such TMs have the same output for every input. Then, given a TM **A** and an input **X**, I can construct a new TM **B** that operates as follows:

1. Check whether the input is exactly **X**
2. If yes, then enter an infinite loop
3. If no, then run **A** on the input

Now I can run **P** on **A** and **B**. **B** does not halt on **X**, but has the same output as **A** for all other input, so if and only if **A** doesn't halt on **X** then these two algorithms have the same output for every input. But **P** was assumed to be able to tell whether two algorithms have the same output for every input, so if we had **P** we could tell whether an arbitrary machine halts on an arbitrary input, which is the Halting Problem. Since the Halting Problem is known to be undecidable, **P** cannot exist.

This means there is no general (computable) approach to determining whether two algorithms have the same output that always works, so you have to apply reasoning particular to the pair of algorithms you're analysing. However in practice there may be computable approaches that work for large classes of algorithms, and there are certainly techniques you can use to try to work out a proof for any particular case. Dave Clarke's answer gives you some relevant things to look at here. The "impossibility" result only applies to devising a generic method that will solve the problem once and for all, for all pairs of algorithms.
> 12 votes

# Answer
It's impossible in general, but many constraints can make it possible. For example, you can check the equivalence of two straight-line code programs using BDDs. Symbolic execution can handle many other cases.
> 2 votes

# Answer
It is impossible to devise an algorithm that does prove this equality in general. Hint: reduction from the Halting problem.
> 1 votes

---
Tags: computability, formal-methods, software-engineering, software-verification
---


title: How can encryption involve randomness?

text:
# Question
Title: How can encryption involve randomness?
If an encryption algorithm is meant to convert a string to another string which can then be decrypted back to the original, how could this process involve any randomness?

Surely it has to be deterministic, otherwise how could the decryption function know what factors were involved in creating the encrypted string?

# Answer
There can be more than one ciphertext that maps back to the same plaintext. In mathematical terms, the encryption algorithm must be injective so that you can recover the plaintext for the ciphertext, but this does not prevent the ciphertext from encoding more information than the plaintext.

As a concrete example, consider modes of block cipher operation such as CBC, CTR or OFB. All these modes involve an IV (initialization vector) in addition to the plaintext, the block cipher algorithm and its key. (For CTR, the IV is called a nonce, but it plays a similar role.) The encryption function is deterministic for a given IV. The IV, on the other hand, may be chosen randomly (for CTR, it must be chosen randomly). Thus, unless the protocol specifies a deterministic method of choosing the IV (such as an agreed-upon constant), the IV is sent alongside the ciphertext. In fact, the output of the encryption software often consists of the IV followed by the cipher text *stricto sensu*. The IV itself is sent in plaintext; it does not (must not) contain any confidential information.

As another example, consider the PKCS1.5 mode (“padding scheme”) of RSA (defined in PKCS#1 version 1.5 — see p.22–25 of PKCS#1 v2.1). Simplifying a bit, this mode consists of concatenating a random string with the message, then applying the exponentiation operation. The ciphertext is $(P \mathbin\Vert M)^e \mod{n}$ where $\Vert$ is concatenation, $M$ is the message and $P$ is a padding string most of whose bits are random. To recover the message from the ciphertext $C$, apply the raw decryption operation $C^d \mod{n}$ and break up $C$ into padding (which is discarded) and message.
> 5 votes

# Answer
Not only *can* encryption schemes have randomness, but in some cases (e.g., public-key encryption), they **must** be randomized. This is not a problem since we require an encryption scheme to be **correct**, that is, for any message $m$ and any key $k$ it holds that $$\Pr \big\[\ \text{DEC} \left( \ \text{ENC}\left(k, m, R\right) \ \big) = m \right\] =1$$ over the randomness $R$.

The reason that public key schemes must be random stems from the way we define security: we don't wish the ciphertext to leak *any* information about the encrypted message. The classical example is the following. Assume that $(pk,sk)$ is the public and secret key, respectively, and that the adversary intercepts an encrypted message $c$ sent to some unit in the field. The adversary knows that the message is either "ATTACK " or "RETREAT", but doesn't know which. One thing that the adversary can do is to encrypt both messages using the public $pk$. let $c\_A = \text{ENC}\_{pk}(\text{"ATTACK "})$ and $c\_R = \text{ENC}\_{pk}(\text{"RETREAT"})$. If $\text{ENC}$ is deterministic, the adversary can find out the message with certainty by comparing $c$ to $c\_A$ and $c\_R$.

The way this notion is formally defined is known as *semantic security*:

> An encryption scheme is semantically secure if any adversary ${\cal A}$ cannot win the following game with probability noticeably greater than $1/2$:
>
> 1. A challenger ${\cal C}$ generates keys $(pk,sk)$ and sends the public key $pk$ to the adversary.
> 2. ${\cal A}$ chooses two messages of equal length $m\_0$ and $m\_1$ and gives them both to ${\cal C}$.
> 3. ${\cal C}$ uniformly picks a bit $b\in\\{0,1\\}$ and sends back $\text{ENC}(m\_b)$.
> 4. ${\cal A}$ needs to say which message was encrypted: $m\_0$ or $m\_1$, that is, he needs to output the bit $b$.

<sup> (I'm omitting the security parameter $\kappa$, which is critical for defining "negligible" or "noticable"; We need to assume that the generation of the keys depends on $\kappa$, and that the advantage ${\cal A}$ has above $1/2$ is negligible in $\kappa$, i.e., less than $\kappa^{-\omega(1)}$) </sup>
> 4 votes

# Answer
You have not stated what type of encryption we are discussing, but let me point out what is really needed for the security of the cartographic protocols (in addition what is stated in other answers).

What we really need is this: the *keys* should be generated randomly (this can be done in collaboration as in public-key cryptography like RSA or by one entity as in private-key cryptography). The randomness of the key makes sure that an adversary cannot predict the keys (and use them to break the protocol). As long as the keys look random to the adversary the protocol will be secure. Often, the keys are generated by a randomized algorithm and then given to the parties, while the encryption and decryption algorithms are not randomized but deterministic.

Also remember that being randomized doesn't mean that the process is not invertable. A simple example is the following: given $x$, randomly generate $r$, output $\langle x,r\rangle$. For inverting, we can output the first part of the pair.
> 3 votes

# Answer
Both the encryption and the decryption algorithms can be randomised as long as you can prove some theorem that encryption followed by decryption will give you the original message *most of the times*.

Why would anyone want such an encryption scheme? Because: 1) there exist situations where we don't want to be right *all the time* but only 99999999 times out of every 100000000 and 2) allowing such small errors often improves something else (such as efficiency) by a disproportionate amount.
> 1 votes

# Answer
Just to cite an example, in RSA encryption, you need to generate two primes $p$ and $q$ and an integer $e$ which will be used to create your public and private keys.

If you generate any of these values in a deterministic way, then their generation can be reproduced, potentially compromising your encryption. If these numbers are generated in a randomized way, then this is not an issue.

**Update**

As a more specific example of Ran G.'s answer, you could have a look at Elliptic Curve cryptography, where the algorithm requires a random parameter (usually called $d$, $k$ or $r$) to encrypt and decrypt messages. If the same "random" parameter is used more than once, they key can be computed from two encrypted messages. This was the problem/premise of last year's PlayStation 3 hack.
> 0 votes

---
Tags: cryptography, encryption, randomness
---


# Question
Title: After implementing a novel encryption algorithm, how would one go about analyzing its security or get help from others in doing so?
**Preface:** This question was originally asked on Theoretical Computer Science, and the kind people there referred me to this web site. It is being repeated here in an attempt to find a satisfying answer.

---

Over the years, two novel encryption techniques have come to mind and been implemented as programming libraries that could be integrated into applications. However, how to analyze their security and vulnerability characteristics has never been very clear, and their usage has been limited to mainly experimental tests. Are there tools available for automated examination of such parameters one may be interested in understanding for an encryption library? Are there bodies of people who are interested in being introduced to new encryption concepts for the purpose of executing their own personal analysis on such a process? I'm not sure where to look.

The first encryption algorithm is a mono-alphabetic simple substitution cipher. It requires two keys to operate and is designed to frustrate frequency analysis. The longer of the keys forms a table by which plain-text has a normal substitution cipher applied. Each encoded byte is then split into four values of two bits each. The second, shorter key is then used to allow a random selection from four groups of sixty-four unique bytes each. Each two bit value from the encoded byte is used to select which group of sixty-four bytes to use. Encoding has two disadvantages: the output is four times larger, and repeated data encoding may allow some frequency analysis.

The second encryption algorithm is a stream cipher like the first but internally operates on blocks of data. It utilizes two keys to operate: the first is a two-dimensional array that describes how to construct a (virtual) multidimensional grid, and the second is an initialization vector for the encoding/decoding engine. It attempts to overcome frequency analysis by encoding bytes with a window of preceding bytes (initialized from the second key). A byte with its preceding window of bytes form a multidimensional index into the aforementioned grid. Unfortunately, encoding duplicate blocks of data longer than the window size starts yielding equivalent data.

# Answer
Typically, there are a variety of steps in evaluating a new algorithm. They start with the quick review

* is it already known?
* does it vary only in nonrelevant ways from what is known?

which is commonly enough to show vulnerabilities in many amateur attempts at encryption. The point is that there are a number of well known ways to translate strings of symbols into other strings of symbols, and many of those have been evaluated in common cryptographic studies. Good books on cryptography cover these.

Then, the more intensive analyses begin. These include:

* functional inversion
* analysis of the symbol statistics
* differential cryptanalysis

and a variety of other mathematical techniques for extracting information of the keys from the intercept stream.

Also, if the technique involves nontraditional information stores (if it doesn't have keys, if it has strange communication channels and protocols, etc.), then you have to also analyse the various impersonation and interception scenarios on each channel.

For the description given, it would appear that the first cryptographic algorithm would fail the first quick view. Substitution ciphers are well known. It doesn't really matter how many times you compose substitution ciphers, their properties are the same. If you had 10 keys and did substitution 10 times before final send, it would be equivalent to a single key substitution cipher and have no better security. Unless there is some other tweak to the algorithm, that would quickly be dismissed as already known.
> 11 votes

# Answer
This is not an answer to your question. But as is often stated in crypto circles:

> Cryptographic protocols and algorithms are difficult to get right, so do not create your own. Instead, where you can, use protocols and algorithms that are widely-used, heavily analyzed, and accepted as secure. When you must create anything, give the approach wide public review and make sure that professional security analysts examine it for problems. **In particular, do not create your own encryption algorithms unless you are an expert in cryptology, know what you're doing, and plan to spend years in professional review of the algorithm.** Creating encryption algorithms (that are any good) is a task for experts only.
> 10 votes

# Answer
First, I must agree with Dave's answer: In order to be able to compose a proper cipher, one needs to be knowledgeable enough about *analyzing* ciphers. Otherwise, there is a high probability that your cipher suffers from well known attack, and you will be considered as a crank.

That being said, there are several groups that specialize in cryptanalysis. Breaking codes is their bread-and-butter. All day long they just wait for other groups to come up with new ciphers, so that they will try to break it (or improve a previous cryptanalysis, etc.). They also try to break other primitives such as hash functions.

some groups comes to my mind, but instead of listing all the people (and forgetting half of them) let me refer you to the last NIST's SHA-3 competition, where groups were (actually, *are*!) called to design hash-functions and break it. Look at the list of candidates and their designers (say of the last 15 finalists of round 2). Those people know a lot about cryptanalysis and can evaluate a new cipher. Look at their publication lists to get more information on the current state-of-the-art in cryptanalysis techniques and methods.

A little bit older but also interesting is NIST's AES competition, in which several groups provided new candidates for block-ciphers. Those groups (as well as the crypto community) also analyzed the candidate ciphers until one cipher was selected to become NIST's standard.
> 3 votes

# Answer
The answer to this problem is more general: If you need an expert to review a novel algorithm in a field with which you are not completely familiar, your best bet is to read-up on and study that field long enough until you *become that expert yourself*. And by "expert" I mean somebody that does research and publishes in that field!

If you're serious enough about your interest in an area, they you should also be willing to shoulder the challenge of trying to get some deeper insight therein. Chances are you'll find the flaws in your algorithms yourself, but you may also just as well find improvements. Most importantly, though, you will only be able to convince others to invest the necessary time to consider your work only once you've established some credibility in that area yourself.
> 1 votes

---
Tags: cryptography, encryption
---


# Question
Title: What does this performance formula mean?
I have to make a quick clustering program but the following formula is gibberish to me:

> $\operatorname{Perf}(X,C) = \sum\limits\_{i=1}^n\min\\{||X\_i-C\_l||^2 \mid l = 1,...,K\\}$
>
> where $X$ is a set of multi-dimensional data and $C$ is a set of centroids for each data cluster.

This formula is a fitness function for an artificial bee colony clustering algorithm as a substitute for k-means clustering algorithm. It is described as a total within-cluster variance or the total mean-square quantization error (MSE).

Can anyone translate it to *pseudo-code*, normal human *English*, or at least enlighten me?

# Answer
Just break it down into parts:

> $ \\{ f(l) \mid l = 1,...,K \\} $

This is a simple set construction. The above would simply create a set with all the elements from 1 to K. In your case the `f(l)` is the function:

> $ ||X\_i-C\_l||^2 $

Given the `||` means the norm, these are vectors you are subtracting (rows of the X and C matrices). So subtract the vectors, take the norm, and square it. That produces a new set, of which you want to take the minimum.

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

This part is then just the sum of above min calculation for every index $i$ from $1$ to $n$.
> 6 votes

# Answer
If you remove all short-hands resp. unfold the notation, you get

$\qquad \begin{align} \operatorname{Perf}(X,C) = \quad &\min \\{ ||X\_1−C\_1||^2, ||X\_1−C\_2||^2, \dots, ||X\_1−C\_K||^2 \\} \\ \+ &\min \\{ ||X\_2−C\_1||^2, ||X\_2−C\_2||^2, \dots, ||X\_2−C\_K||^2 \\} \\ &\ \ \vdots \\ \+ &\min \\{ ||X\_n−C\_1||^2, ||X\_n−C\_2||^2, \dots, ||X\_n−C\_K||^2 \\} \\ \end{align}$

where

* $\min$ denotes the minimum value of the operand set,
* $X\_i$ and $C\_l$ are rows or columns of the matrices (depends on the source),
* $u - v$ for vectors $u,v$ is component-wise subtraction and
* $||u||$ for a vector $u$ is a norm (which one depends on your source; if nothing else is stated, usually the Euclidian norm is meant).

So, $\operatorname{Perf}(X,C)$ finds for every row (column) of $X$ the row (column) of $C$ that is nearest, and sums up all those minimum (squared) distances. It is therefore a measure of *closeness*: if $\operatorname{Perf}(X,C)=0$ then every row (column) in $X$ has a perfect match in $C$ (because norms are non-negative).
> 3 votes

---
Tags: algorithms, terminology, evolutionary-computing
---


title: Block detection in repeated stream

text:
# Question
Title: Block detection in repeated stream
I need to recover a data block from a repeated stream of data. I'm looking to see what algorithms may already exist for this as it does not feel like a novel situation.

Here are the specifics:

1. There is an N-length block of data contained in a stream
2. The block is repeated many times in the stream
3. the data is highly corrupted, some bytes could just be wrong, where as others can be detected as missing (erasures)
4. There is a function `F(data)` which can say if a block represents valid data (the probability of a false positive is virtually zero)
5. `F` can also provide a probability value that even if the block is not valid data whether the block itself is valid (but just has too much corruption to be recovered)
6. The chance of corrupted data is very low compared to missing data

For example, say I have this data stream and wish to recover the 10 length sequence `1234567890`. The data is just a rough visual example (I can't guarantee recovery is actually possible from this bit). A `.` represents a missing byte, and `<break>` indicates an unknown block of data (no data and not length known). Note also the `Q`s as an example of corrupt data.

`23.5678901.3456789<break>2345678..1..4567QQ012345678..3456`

How can I take such a stream of data and recovery probably blocks of N data? As the actual data includes forward error recovery the block recovery need not be perfect. All it needs to do is give probable reconstructed blocks of data and the `F` function will attempt to do error recovery. Thus I expect `F` fill have to be called several times.

I'd like to find something better than simply calling `F` at each point in the stream since the error rate could be high enough that no single run block of N can be recovered -- the repetitions in the stream must be used somehow.

# Answer
I think what you want is impossible to do without further assumptions on `F`.

Consider the following, rather simple data stream for a target data length of `5`:

```
123441233512245113451255513555 ...

```

Note that not a single block contains `12345` (our original data). In order to find a proper combination of data parts, you would have check *all* combinations, in general. What is the probability that some combination other than `12345` is accepted by `F`? And this is on a stream without lost or corrupt symbols and ignoring the problem of overlaps between blocks which might by accident be valid data!

Therefore, I think keeping a buffer of size $N$ and running `F` in every time step is the best you can do. Note that you can skip evaluation of `F` if there is a corrupt symbol in the buffer (provided you can identify those). You still have the problem of overlap errors and wrong valid blocks, though.

You have more potential if `F` has nice properties, for example if it is able to identify valid *parts* of data. Then you can store only maximal valid parts and piece those together. Also, formatting the data stream can help; a simple example would be markers for the beginning of a data block (that would get rid of problems with overlaps and reduce the amount of calls to `F`). Furthermore, usual assumptions such as "error probability is small" can make waiting for a full valid copy of the data viable; many protocols break down if virtually every other symbol is corrupt.

All these are not new problems. I suggest further reading on
> 3 votes

---
Tags: algorithms, online-algorithms, communication-protocols
---


# Question
Title: When can I use dynamic programming to reduce the time complexity of my recursive algorithm?
Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that if satisfied by a recursive algorithm would imply that using dynamic programming will reduce the time complexity of the algorithm? When should I use dynamic programming?

# Answer
Dynamic programming is useful is your recursive algorithm finds itself reaching the same situations (input parameters) many times. There is a general transformation from recursive algorithms to dynamic programming known as *memoization*, in which there is a table storing all results ever calculated by your recursive procedure. When the recursive procedure is called on a set of inputs which were already used, the results are just fetched from the table. This reduces recursive Fibonacci to iterative Fibonacci.

Dynamic programming can be even smarter, applying more specific optimizations. For example, sometimes there is no need to store the entire table in memory at any given time.
> 11 votes

# Answer
If you just seek to speed up your recursive algorithm, memoisation might be enough. This is the technique of storing results of function calls so that future calls with the same parameters can just reuse the result. This is applicable if (and only if) your function

* does not have side effects and
* does only depend on its parameters (i.e. not on some state).

It will save you time if (and only if) the function is called with the same parameters over and over again. Popular examples include the recursive definition of the Fibonacci numbers, that is

$\qquad \begin{align} f(0) &= 0 \\ f(1) &= 1 \\ f(n+2) &= f(n+1) + f(n) \qquad ,\ n \geq 0 \end{align}$

When evaluated naively, $f$ is called exponentially often. With memoisation, $f(n)$ has always been computed by $f(n+1)$ already, thus only a linear number of calls remains.

Note that, in contrast, memoisation is next to useless for algorithms like merge sort: usually few (if any) partial lists are identical, and equality checks are expensive (sorting is only slightly more costly!).

In practical implementations, how you store results is of great import to performance. Using hash tables may be the obvious choice, but might break locality. If your parameters are non-negative integers, arrays are a natural choice but may cause huge memory overhead if you use only some entries. Therefore, memoisation is a tradeoff between effect and cost; whether it pays off depends on your specific scenario.

---

Dynamic programming is a completely other beast. It is applicable to problems with the property that

* it can be partitioned into subproblems (probably in more than one way),
* those subproblems can be solved independently,
* (optimal) solutions of those subproblems can be combined to (optimal) solutions of the original problem and
* subproblems have the same property (or are trivial).

This is usually (implicitly) implied when people invoke Bellman's Principle of Optimality.

Now, this only describes a class of *problems* that can be expressed by a certain kind of recursion. Evaluation of those is (often) efficient because memoisation can be applied to great effect (see above); usually, smaller subproblems occur as parts of many larger problems. Popular examples include edit distance and the Bellman-Ford algorithm.
> 9 votes

---
Tags: algorithms, dynamic-programming, efficiency, algorithm-design
---


# Question
Title: Could someone suggest me a good introductory book or an article on graph clustering?
For my pet project I need to cluster some data which could be easily represented as graph, so I want to use this as an opportunity to educate myself and play with various algorithms. I'd prefer the book on graph clustering as it often more self contained but articles are fine too. Back in the days I used to work in the field of numerical linear algebra so I'd also prefer algebraical view on things (so books which view graph as a matrix with specific properties are more accessible to me).

p.s. I've tried scholar.google.com but was overwhelmed by vast number of results.

# Answer
The book The Elements of Statistical Learning by Trevor Hastie, Robert Tibshirani and Jerome Friedman covers a lot of learning and clustering algorithms including various graph clustering algorithms. Algorithms such as Spectral Clustering are phrased algebraically, as is much of the book. The good thing is that a pdf of the book is available from the authors' website, linked above. It has an extensive bibliography to help you beyond what is presented in the book.

There's also an implementation of Spectral Clustering in R which works quite well and has lots of options.
> 4 votes

---
Tags: algorithms, graphs, reference-request, books
---