# Question
Title: Given a set of sets, find the smallest set(s) containing at least one element from each set
Given a set $\mathbf{S}$ of sets, I’d like to find a set $M$ such that every set $S$ in $\mathbf{S}$ contains at least one element of $M$. I’d also like $M$ to contain as few elements as possible while still meeting this criterion, although there may exist more than one smallest $M$ with this property (the solution is not necessarily unique).

As a concrete example, suppose that the set $\mathbf{S}$ is the set of national flags, and for each flag $S$ in $\mathbf{S}$, the elements are the colors used in that nation’s flag. The United States would have $S = \\{red, white, blue\\}$ and Morocco would have $S = \\{red, green\\}$. Then $M$ would be a set of colors with the property that every national flag uses at least one of the colors in $M$. (The Olympic colors blue, black, red, green, yellow, and white are an example of such an $M$, or at least were in 1920.)

Is there a general name for this problem? Is there an accepted “best” algorithm for finding the set $M$? (I’m more interested in the solution itself than in optimizing the process for computational complexity.)

# Answer
The problem is the well-known NP-complete problem Hitting Set. It is closely related to Set-Cover. The NP-completeness proof can found in the classic book of Garey and Johnson.

If you want to approximate it, you might want to translate your instance first to Set-Cover, and then apply an approximation algorithm for Set-Cover. However, Set-Cover cannot be be approximated by a constant factor in polynomial time, unless P=NP as shown by Lund and Yannakakis.

If you are interested in exact solutions and your inputs behave nicely, I would recommend using a fixed-parameter tractable. The running time is here not only expressed in terms of the input length $n$ but also in terms of an additional parameter $k$. If the running time is $O(f(k)\cdot n^{O(1)})$, we call the algorithm a FPT-algorithm. Here, $f(k)$ is an increasing function. So if $k$ is constant we have a polytime algorithm. The first chapter of the book by Flum and Grohe, explains an FPT-algorithm for hitting set (more precisely for $p$-card-hitting set). The algorithm is easy to implement and uses the method of bounded search trees. Still it needs to much space to explain here, basically you break down the necessary(?) brute-force search, into small pieces (when $k$ is small).
> 14 votes

# Answer
An idea that could help: if the intersection of all the sets in $\mathbf S$ in not empty, then you can pick any element $s$ in the intersection and set $M = \\{s\\}$. If the intersection is empty, find an element (color) $c$ whose occurrence in sets is maximum and replace all the sets in which it occurs by the singleton $\\{c\\}$. Keep doing this until every element's occurrence count is equal to $1$ and then set $M$ to the union of the remaining sets. For example, if $\mathbf S$ is the power set of some set $A$ then $M = A$. I might be wrong however.
> 2 votes

# Answer
Have a look at Ray Reiter's "A Theory of Diagnosis from First Principles" where he gives an algorithm for computing hitting sets, and this additional note "A correction...".

The algorithm is generally known as "hitting set tree" algorithm, it shouldn't be too hard to find an implementation. You mentioned you weren't too interested in runtime, but optimisations such as early branch termination etc. are quite critical to the implementation, and interesting as well :)
> 2 votes

# Answer
Practically speaking, one of the better ways (certainly one of the easiest) to solve instances of Set Cover/Hitting Set is mixed integer programming. This involves communicating the integer programming formulation to the solver of your choice.
> 0 votes

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


# Question
Title: Which Is a Better Way of Obtaining Scales, Gaussian Blur or Down Sampling?
In computer vision, scales are important when we carry out a scene analysis. Choosing different scales affect the result of the analysis. For example, if a face is relatively small in the scene, then the details including nose, eyes will be omitted. On the other hand, details on larger faces become relatively more salient.

I know both Gaussian Blur with different sigmas and Down Sampling on the image can generate different scales. Which is more reasonable on a cognitive sense?

# Answer
> 3 votes
Down sampling may discard relevant features, while blurring should not.

As a toy example, a down sample may remove a pixel which is a local maxima, while a blur operation will preserve the maxima by increasing the values of nearby pixels. If the local maxima corresponds to an interesting feature, it may still be discernible by the human eye after blurring.

From a computational sense, Laplacian pyramids are able to reconstruct an image precisely because a blur-subtract operation preserves the "information" in the scene.

---
Tags: machine-learning, computer-vision, image-processing
---


# Question
Title: Formally describing a new domain specific programming language
I am about to implement a domain specific language for representation of social learning conventions. Part of the implementation is a formal description of a language - its 'calculus', symbols and logical expressions.

My approach would be to describe the language by describing its grammar but there are also concepts such as relations, dialogs, expectations that require more theoretic approach and the description of the logic.

I would like to ask for an example and a literature recommendation (papers, books) that would help me with this description. I feel relatively competent approaching this task so I am not asking for a total hand holding, but help from a theoretician in this area would be GREATLY appreciated.

# Answer
There are two parts of the semantics you will need to describe:

* **static semantics**: structure of well formed programs
* **dynamic semantics**: meaning of running programmings

**Static semantics** usually take the form of type systems. I'd recommend looking at the books by Benjamin C Pierce and Robert Harper. Alternatively, you could write the rules of well-formed programs as a collection of (formal or informal) statements describing the validity conditions of your program. The formal approach taken by type systems provides a well-known framework for such specifications.

There are many formalisms for expressing the **dynamic semantics** to consider as your basis:

* denotational semantics --- gives meaning in terms of semantic domains
* operational semantics --- gives meaning in terms changes to an abstract machine states
* axiomatic semantics --- gives meaning in terms of assertions about the state of the machine
* algebraic semantics --- semantics is defined in terms of algebraic laws.

There should be plenty of books out there on these topics. A good broad introductory one is Nielson and Nielson's Semantics with Applications. A downloadable version is available from the authors' site. There is also a newer edition, but I haven't seen it.

Within each of these, there are choices to make. For example, if you decide to use operational semantics, there are large-step semantics, small step semantics, semantics based on labelled transition systems, semantics based on rewriting logic.

What kind of approach you should take will depend on what kind of language your DSL is, what kind of experience you have with designing semantics, and your personal preference.

Without any concrete details, I can help no further.
> 10 votes

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


title: Time complexity of a triple-nested loop

text:
# Question
Title: Time complexity of a triple-nested loop
Please consider the following triple-nested loop:

```
for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j)
        for (int k = j; k <= n; ++k)
            // statement

```

The statement here is executed exactly $n(n+1)(n+2)\over6$ times. Could someone please explain how this formula was obtained? Thank you.

# Answer
> 14 votes
You can count the number of times the innermost for loop is executed by counting the number of triplets $(i,j,k)$ for which it is executed.

By the loop conditions we know that: $1 \leq i \leq j \leq k \leq n$ . We can reduce it to the following simple combinatorics problem.

* Imagine $n+2$ boxes of red colour placed in an array from left to right.
* Pick any 3 boxes from the $n+2$ boxes and paint them blue.
* Form a triplet $(i,j,k)$ as follows:
    + $i$ = 1 + number of red coloured boxes to the left of first blue box.
    + $j$ = 1 + number of red coloured boxes to the left of second blue box.
    + $k$ = 1 + number of red coloured boxes to the left of third blue box.

So, we just need to count the number of ways of picking 3 boxes from $n+2$ boxes which is $n+2 \choose 3$.

# Answer
> 3 votes
for me, it's easier to notice the inner loop is executed $n-i$ times and the total number of executions in the inner loop is

$(n-i)+(n-i-1)+(n-i-2)+\ldots+1$

this can be rewritten as $\sum\_{j=0}^{n-i} n-i-j$ and is executed $n$ times, so the total number of executions is

$$ \sum\_{i=0}^{n}\sum\_{j=0}^{n-i} n-i-j=\frac{n(n+1)(n+2)}{6} $$

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


# Question
Title: Is there a search engine over Artificial Intelligence and Machine Learning -related sites?
Sometimes it is necessary to dig into Artificial Intelligence or specifically Machine Learning problems to make a research. Common googling (in my own experience) usually doesn't help much due to a lot of irrelevant or paid material among the results. Google Scholar in contrast is limited to scientific publications only, sometimes it is too narrow.

I wonder if there is a kind of dedicated search engine over AI- and ML-related sites?

# Answer
I was not able to find a mentioned search engine, but I was able to make it myself with a help of Google Custom Search. I made a custom search engine with \*.edu, \*.ac.uk, \*.edu.au and so on sites and domain zones, 145 in a total at this moment. From my point of view that search engine gives much better result pages, than an ordinary search. Also, the search index is almost spam-free and paid content -free.

There is a feature, that allows one to inspect what sites are included in the index, to comment them and to vote for or against them (to purge unrelevant site from the index, for example). Also, everyone is welcome to suggest new sites using a special form on the site. In short, it has all very basic machinery needed to make such scoped search engine to be community driven.

Try it at http://neatserpent.com/

Give me your feedback, please. Do you find it helpful and better than ordinary search engine? Would you use it?

Please, spread the word, if you like it.
> 2 votes

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


# Question
Title: Is the validity of some instance of an equational problem decidable?
Is the following FOL-problem (equality is a logical symbol) effectively decidable?

**Given.** A finite equation system $E$ and an equation $s = t$.

**Question.** Is there a substitution $\sigma$, such that $\sigma(E) \models \sigma(s = t)$?

**Some useful information.**

1. Obviously one can restrict $\sigma$ to be a ground substitution.
2. This problem is decidable: Given a finite system $E$ of
ground equations and a ground equation $s = t$, does $E \models s = t$
hold? (c.f. \[1: Corollary 4.3.6\])

**References**

\[1\] Franz Baader, Tobias Nipkow: Term Rewriting and All That, © 1998 Cambridge University Press.

# Answer
> 8 votes
This problem is known as *rigid E-unification*. This problem is NP-complete. The first proof was given by Gallier, Narendran, Plaisted and Snyder \[1\].

However a related problem, the *Simultaneous rigid E-unification* that is to find a substitution that simultaneously satisfies several instances of rigid E-unification is undecidable. This result was proved by Degtyarev and Voronkov \[2\].

**References**

1. Jean H. Gallier, Paliath Narendran, David A. Plaisted, Wayne Snyder: Rigid E-Unification: NP-Completeness and Applications to Equational Matings Inf. Comput. 87(1/2): 129-195 (1990)
2. Anatoli Degtyarev, Andrei Voronkov: The Undecidability of Simultaneous Rigid E-Unification. Theor. Comput. Sci. 166(1&2): 291-300 (1996)

---
Tags: computability, logic, decision-problem, equality
---


# Question
Title: Pumping Lemma for regular language for $a^n$ where $n$ is even fails
$$L=\\{a^n \mid \text{\\(n\\) is even}\\}$$

This is regular but fails in the pumping Lemma.

Assuming $m=4$, $w=aaaaaa$, $|w|=6$ (even). Let $w=xyz$, $x=a$, $y=aaa$. We have $|y|\>0$ and $|xy| \le m$.

Let $w\_i=xy^iz$. For $i=2$, $w\_2=xy^2z=aaaaaaaaa$. $|w\_2|=9$ therefore it is not regular.

Where am I going wrong?

# Answer
The pumping lemma states that:
there exists a pumping length $p$
such that for any word $w \in L$ of length $|w| \ge p$,
there exists a decomposition $w = xyz$
meeting certain properties.

There are two errors in your proof. The first is that the lemma states that there exists a pumping length $p$ but doesn't say how to compute it; you assume without proof that $6$ is a valid pumping length. This makes your proof incomplete, but it is not actually wrong: the pumping length can be anything larger than the number of nodes in the smallest finite automaton that recognizes the language, and this language can be recognized by an automaton with just two states, so any $p \ge 2$ is ok.

The fatal mistake is that you don't get the choice of the decomposition. There has to be some decomposition $w = xyz$ such that $\forall i, xy^iz \in L$. The one you picked doesn't work. In order to prove that the language isn't regular, you'd need to prove that no decomposition works. But there is a decomposition that works: take $x = aa$, $y = aa$, $z = aa$ (or any decomposition where $|y|$ is even).

You might have gotten confused with what happens when proving that a language is not regular. When proving the negation, the quantifiers are reversed: to prove that a language is not regular using the pumping lemma, we usually assume that the pumping lemma holds, so we *assume* the pumping lemma, and in particular we assume that for any sufficiently large word, there exists a decomposition meeting the properties, and we deduce a contradiction from that. Here, you're trying to *deduce* that the pumping lemma holds.
> 12 votes

# Answer
The simple answer is you're using the wrong approach. It's much easier to construct a regular expression or finite automation to prove that a language is regular.

This language is expressible using the following regular expression:

```
(aa)*

```

I think your issue is your assumption that the pumping length is 4. You can't just choose a pumping length- the lemma only says that for a regular language, there must *exist* one and only one pumping length, but the lemma does not help us guess what it is, nor do we need to know when disproving regularity. For proving regularity, I wouldn't use the pumping lemma at all because it is sometimes possible for a non-regular language to be pumped. Use a finite automaton or regular expression to prove regularity.
> 0 votes

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


# Question
Title: Complexity calculations, assumptions on basic costs
> **Possible Duplicate:**
> How can we assume comparison, addition, … between numbers is $O(1)$

When we calculate the time-complexity of some algorithm we make many simplifications (or assumptions) on our calculation. For instance we say that assume basic arithmetic operations are all constant time and we assume reading/writing to a memory location is constant time.

I've worked on some algorithms where these assumptions don't hold. I'm looking for the background I need to properly approach/describe these algorithms. In particular I wish to know:

1. What is the generic name for such a simplification/assumption?
2. Is there a name for the basic model of simplifications we're using? (Assuming there is a common model)

*Note: I've done work with cache-dependent/cache-oblivious algorithms. I understand how to calculate in that domain, but I'm lacking the terminology/background to properly compare/contrast such algorithm analyis with that which don't consider the cache.*

# Answer
> 1 votes
It is generally referred to as "Random Access Machine" or RAM model. This model assumes that accessing any unit of data, irrespective of its position or type, takes the same constant amount of time. Now, what you take as a "unit" of data is important. For all practical purposes, we may consider the primitive data types, integer, float and characters (but not strings) as a unit of data. A single instruction on unit data is considered to take constant amount of time.

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


title: LFSR sequence computation

text:
# Question
Title: LFSR sequence computation
I need to calculate the output of the sequence generated by this shift register but I cannot find anywhere how to do it. Everywhere the results are just given but there is no explanation how to do compute them. I know the the sequence will repeat every 2^3-1=7 times. Could anyone explain me how to do it. Thank you.

# Answer
> 2 votes
The answer seems to be simple:

First, we XOR the two least significant bits (LSB) to get the most significant bit. The two LSB are obtained by right-shifting. So, calculating in this way, we get the sequence 110, 111, 011, 001, 100, 010, 101.

---
Tags: cryptography, pseudo-random-generators, shift-register
---


title: Problem contest with matrix and DP

text:
# Question
Title: Problem contest with matrix and DP
I found this problem while I was reading an ACM problem and it is about dynamic programming. The problem says that you have a square matrix $n\times n$ filled with 1's or 0's, like this:

## $$\begin{bmatrix} 1 &1 &1 &0\\ 1 &1 &1 &1\\ 0 &0 &1 &0\\ 1 &1 &1 &1 \end{bmatrix}$$

Now you have to find the biggest square matrix inside the original matrix which is filled with only 1's. In my example, take the matrix of $((1,1)$ to $(2,2)$ $$ \begin{bmatrix} 1 & 1\\ 1 &1 \end{bmatrix} $$

But, we might have to deal with matrices of size 1000X1000 as well. So the algorithm should be efficient and use DP, although I don't know if there is other solution. My Teacher told me that it can be done by Dynamic Programming. But I didn't understand his method.

# Answer
An $O(n^2)$ algorithm is possible.

Let $A$ be the given matrix.

You compute the side of largest square with the bottom right corner at $(i,j)$, say $S(i,j)$

Now we can compute the side of the larger square for $(i+1, j+1)$ in terms of $S(i,j), S(i+1,j), S(i,j+1)$

as

$$S(i+1,j+1) = \min \\{S(i,j), S(i+1,j), S(i,j+1)\\} + 1 \quad \text{if}\quad A\[i+1,j+1\] = 1$$

and

$$S(i+1,j+1) = 0 \ \text{if }\ A\[i+1,j+1\] = 0$$

There are other (complicated) $O(n^2)$ algorithms available, which also work for rectangles and can be used for this problem.
> 6 votes

# Answer
The following finds the largest matrix dynamically in $O(n^3)$.
The algorithm first reads from the standard input which matrices of dimension 1x1 have all ones. Then it computes all the matrices of dimension 2x2 that have all ones. Then all 3x3 matrices, etc. up to all the n by n matrices (just one) that have all the ones.
When determining whether an i by i matrix has all ones you could check all 1x1 matrices in it if they all are ones. But we have already found all the (i-1) by (i-1) matrices that have ones! So you do not need to check all ones in a (i-1) by (i-1) submatrix again. Just find whether the whole submatrix has all the ones from a *has\_all\_ones* array. Every matrix of dimension dim greater than 2 is fully covered by 4 submatrices of dimension dim-1 (it is their union). If these have all ones, the whole matrix of size dim has ones everywhere.

```
#include<stdio.h>
#include<iostream>

#define MAX 100
using namespace std;

int main(){
    int n;
    cin>>n;

    //has_all_ones[dim][row][col] is true if and only if a matrix of size dim
    //starting at positions (row,col) has all ones in it
    bool has_all_ones[MAX][MAX][MAX];//dim, row, col
    for(int row=0; row<n; row++)
        for(int col=0; col<n; col++)
            cin>>has_all_ones[1][row][col];

    //compute dynamically all the matrices with all ones
    for(int dim=2; dim<=n; dim++)
        for(int row=0; row+dim-1<n; row++)
            for(int col=0; col+dim-1<n; col++){
                //now we do not have to check all the ones in a matrix
                //only the four submatrices
                has_all_ones[dim][row][col] =
                has_all_ones[dim-1][row][col] &&
                has_all_ones[dim-1][row+1][col] &&
                has_all_ones[dim-1][row][col+1] &&
                has_all_ones[dim-1][row+1][col+1];
            }

     //find the largest one
     for(int dim=n; dim>0; dim--)
        for(int row=0; row+dim-1<n; row++)
            for(int col=0; col+dim-1<n; col++)
                if(has_all_ones[dim][row][col]){
                    cout<<"The largest matrix starts at ("<<row<<", "<<col<<") and ends at ("<<row+dim-1<<","<<col+dim-1<<")."<<endl;
                    return 0;
                }

    return 0;
}

```
> 1 votes

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


# Question
Title: How to write a recursive function that with certain time complexity
I'm now doing exam revision, and from some past year exam papers, I noticed some questions that ask to write a recursive method with signature like

```
public void run(int n)

```

that must have a time complexity of like : $O(n^2), O(n^3), O(n^7), O(n^2!), O(2^n), O(9^n)$.

Can anyone give some idea on how to solve this kind of recursion questions.

# Answer
> 7 votes
I will assume the person stating the problem actually meant $\Theta$ where you write $O$; otherwise the question is trivial as Juho points out. Realising this may very well have been the point of the problem (or an intended shortcut for the observant), though.

Here is one basic idea to create an algorithm with runtime $\Theta(f(n))$: find a set of objects $S$ with $|S| = \Theta(f(n))$ and recursively enumerate it. If done correctly, this gives you a runtime in $\Omega(f(n))$; if you don't waste time, you get $\Theta(f(n))$.

Some hints for the concrete runtimes you want to achieve:

* Given a set $T$ of $n$ objects, $|T \times T| \in \Theta(n^2)$.
* Given a set $T$ of $n$ (distinguishable) objects, the set $\operatorname{Perm}(T)$ of all permutations of these objects has size $n!$.
* The set $\\{0,1\\}^n$ contains $2^n$ words.

Note that all these (simple) facts should be known from basic algorithm analysis and formal languages (and maybe combinatorics). The exam question can be solved by generalising and combining them.

# Answer
> 2 votes
The idea is quite simple. Write your function `run` and analyze its time complexity $r(n)$. Is it then so that you can find *any* nonnegative constant $c$ and input size $n\_0$ such that from which $r(n\_0) \leq cg(n\_0)$, where $g(n)$ is any particular function you desire? This idea comes from the formal definition of Big Oh. It might be helpful to build up intuition by plotting something, see here.

Here's a concrete implementation. It's not very meaningful, but it doesn't have to be.

```
void run(int n)
{
  if(n == 0) return;
  run(0);
}

```

The function is recursive and clearly runs in constant time. It is easy to verify by for example plotting, that yes, at some point $n^2$ and $n^3$ start to dominate. Hence, the the time complexity of the implementation is in both $O(n^2)$ and $O(n^3)$. Similar reasoning holds for other functions.

# Answer
> -3 votes
When you are given a problem statement there will be an input.The given input has to be countable in some way. In order to get the answer or output you got to manipulate the input in some way are the other in programming. The question is ,how many operation are you going to do on your inputs ... it depends on problem requirement .

```
For example : In an sorted array of n elements .
      1)searching can be done by checking each and every element .
      2)And using the mathematical property that array is sorted you apply a very old trick
       called  binary search .which divedes our search space into half every time we check
       our trick. This reduces our search space so as reducing the operations.

```

please read Master theorem to know how to evaluate complexity.

```
In the case 1 we have complexity in big oh notation as O(n) where n is the input .
In the case 2 we have complexity in big oh notation as O(log(n)) where n is the input .

```

For basic please refer Big Oh

Coming to the recursion , Suppose our problem be searching, let us consider the binary search .

```
int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin):
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = midpoint(imin, imax);

      // three-way comparison
      if (A[imid] > key)
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key)
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else
        // key has been found
        return imid;
    }
}

```

Firstly for searching an element say X in our input length N then we check middle element in an sorted array to see whether element to be searched(x) is greater or lesser .If it is greater we search the element from middle element(n/2) to last element N recursively .If element to be search(x) is smaller than middle we search from 1 to (n/2) ,as we know that element after middle element is bigger than middle(x

---
Tags: algorithms, time-complexity, recursion
---


title: Binary Search Tree Property

text:
# Question
Title: Binary Search Tree Property
In the book 'Introduction to Algorithms 3/e', I have found the following definition of Binary Search Tree property:

> Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $y.key \geq x.key$.

My confusion is that while implementing binary search trees we either consider that the keys of left-subtree of a node $x$ would be $\leq x.key$ **or** the keys of right-subtree of a node $x$ would be $\geq x.key$ but **not both**. That is we follow one of the two convention. But in the property they have included $=$ in both the cases. Where am I wrong?

I would appreciate any idea on this issue.

# Answer
> 7 votes
You're not wrong, but neither are they. The normal formulation is to have the left subtree values be strictly less than ($\<$) the current value and the right greater than or equal to ($\geq$) the current value, or vice versa ($\leq$ and $\>$), however using $\leq$ and $\geq$ still results in a working BST in the sense that the tree provides an ordering. (Try constructing a few, you'll see that the difference is that if you have repeated values, they can get spread over the right-most part of the left subtree and the left-most part of the right subtree instead of being in one or the other).

To see that it still works, consider the cases when searching the tree:

1. $y = x$, you've already found it, so you can stop here;
2. $y \< x$, it must be in the left subtree (if $y \<x$ then $y \leq x$);
3. $y \> x$, it must be in the right subtree.

So you can see that the operation is identical, the choice at each node remains unambiguous.

**EDIT** Just to highlight Svick's excellent point in the comments, if you're searching for all nodes with the same value, the "$\leq,\geq$" case introduces complications - it may require more than one pass to find all such nodes (a full traversal will get them all of course, if it's an inorder traversal you even get them in a row).

# Answer
> 0 votes
The equality is allowed when multiple nodes may have the same key.

Consider:

```
     c
  b     d
 a c   c e

```

In order to find all `c` elements, you have to descend both subtrees of the topmost `c`, but only the right subtree of `b`, and the left subtree of `d`.

---
Tags: terminology, data-structures, binary-trees, search-trees
---


# Question
Title: For a graph $G$ find the minimal $t$ such $G(t)=(V,E(t))$ is connected
Given a connected and directed graph $G=(V,E)$ with positive weights on the edges. for every $t\>0$ we define $E(t)$ to be the group of edges with weight lower or equal than $t$. I need to find an efficient algorithm which computes the minimal $t$ such that $G(t)=(V,E(t))$ is connected.

I can sort all the edges with $|E|\log|E|$ complexity and try to take edges out of the graph from the heaviest to the easiet one, and to check with DFS if it is still connected, but its not effiecnt enough,

Any suggestions?

# Answer
> 8 votes
1. Compute a minimum bottleneck spanning tree of the graph. (Actually just compute a minimum spanning tree, as a minimum spanning tree is a minimum bottleneck tree.)
2. Determine the maximum edge weight from MBST, this will be your $t$.
3. Remove all edges whose weight is higher.

This can be done in linear time in the sum of the number of nodes and edges (see wiki).

---
Tags: algorithms, graphs
---


# Question
Title: Find the lightest weight of a path between $u$ to $v$ that contains no more then $k$ edges (If there's one)
Given a directed and strongly connected graph $G=(V,E)$, weight function $w: E \to \mathbb{R}$ and two distinct vertices $u,v \in V$. We know that there aren't negative cycles. I need to find algorithm, efficient as possible,such that for every value of $k$, $2 \leq k \leq |V|-1$, it will find the lightest weight of a path between $u$ to $v$ that contains no more then $k$ edges (If there's one).

I don't know what to do. I want to use Bellman Ford somehow, I just don't sure how.

Thanks a lot.

# Answer
> 4 votes
Consider the dynamic programming formulation of Bellman-Ford:

$\qquad \displaystyle \mathrm{bf}(i,j) = \begin{cases} 0 &, i = 0 \land j = s \\ \infty &, i = 0 \land j \neq s \\ \min\limits\_{k \in V}\\, \big(\\, \mathrm{bf}(i-1,k) + c(k,j)\\,\big) &, \text{else} \end{cases}$

What meaning does $\mathrm{bf}(i,j)$ have, that is what does DP-matrix entry $\mathrm{bf}\[i,j\]$ contain?

> If you unfold the definition (i.e. proof by induction) you see that $\mathrm{bf}(i,j)$ is the weight of the shortest path from starting node $s$ to $j$ with at most $i$ edges -- exactly what you are looking for.

---
Tags: algorithms, graphs
---


title: Is this language LL(1) parseable?

text:
# Question
Title: Is this language LL(1) parseable?
I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language.

$$L=\\{\\,a^nb^m\mid n,m\in\mathbb N,\\\>n\ge m\\,\\}$$

Is my hypothesis true or is this language parseable with an LL(1) parser?

One can use this simple grammar to describe $L$ (of course it is isn't LL(1) parseable):

```
S -> ε
S -> A
A -> aA
A -> aAb
A -> a
A -> ab

```

# Answer
Kurki-Suonio has shown some helpful properties \[1\]:

> **Theorem 1**
> Each LL(k) grammar is unambiguous.

That means any inherently ambiguous language is not LL(1).

> **Theorem 9**
> For any $k\>1$ the grammar $G$:
>
> $\qquad \begin{align} S &\to aSA \mid \varepsilon \\ A &\to a^{k - 1} b S \mid c \end{align}$
>
> generates an LL(k) language which is no LL(k-1) language.

There you have another concrete example by setting $k=2$.

---

As for your language $L$, assume $L$ is LL(1) and consider the language

$\qquad \displaystyle L' = \\{ a^nb^m \mid n \< m \land m \> 0 \\}$.

We make the following observations:

* $L'$ is LL(1) by the grammar

$\qquad \begin{align} S &\to AbB \\ A &\to aAb \mid \varepsilon \\ B &\to bB \mid \varepsilon \end{align}$
* Neither $L$ nor $L'$ is regular (by Pumping Lemma).
* $L \cap L' = \emptyset$.
* $L \cup L' = \\{a^nb^m \mid n,m \in \mathbb{N}\\} \in \mathsf{REG}$.

In unison, these facts contradict this theorem \[2\]:

> **Theorem 9**
> If the finite union of disjoint LL(k) languages is regular, then all the languages are regular.

Thus, $L$ can not be LL(1) (and in fact not LL(k) for any k).

---

1. Notes on top-down languages by R. Kurki-Suonio (1969)
2. Properties of deterministic top-down grammars by D.J. Rosenkrantz and R.E. Stearns (1970)
> 5 votes

# Answer
Your language correspond to the famous dangling else problem and it is well known that no $LL(k)$ grammar is able to parse it. The reason is that a $LL(k)$ grammar should be able to decide if a $a$ is paired with a $b$ when the $a$ is seen and the next $k$ symbols may be $a$.

Note that to make it $LR(1)$ you can't use a grammar like

$\qquad\begin{align} S &\to aSb \\ &\to aS \\ &\to \varepsilon \end{align}$

which is ambiguous. You have to use to

$\qquad\begin{align} S &\to aS \\ &\to R \\ R &\to aRb \\ &\to \varepsilon \end{align}$

But some parser generators like yacc are able to cope with that ambiguity, but the input has to be correctly ordered for them to work. Similarly, if you left factorize the first grammar, you get Raphael's grammar

$\qquad \begin{align} S &\to aST \mid \varepsilon \\ T &\to b \mid \varepsilon \end{align}$

which has an ambiguity which doesn't prevent to generate tables for LL(1) parsers.
> 3 votes

# Answer
~~Your proposed solution does not correspond to the defined language. Take the example "ab" which is a member of $L$, but not your grammar.~~

To be a LL(1) grammar, the production rules must not contain left recursions and has to be unambiguous. The following grammar ~~satisfies~~ does not satisfy those criteria:

```
S → A
A → aAb
A → B
B → aB
B → ԑ

```

I have one redundant production rule. Let's remove it:

```
S → aSb
S → A
A → aA
A → ԑ

```

**Update:** Based on your hint, I am changing my mind. I think your hypothesis is true. I don't know how to prove correctness for this (probably  or  might help), but my rationale goes like this: If you parse an token "a" at position $p$ you can (in no way) determine which string it belongs to (either $i\_1: 0 \leq p \< m$ or $i\_2: m \leq p \< n$). But this is a required property for context-free languages, because you *have* to represent $i\_1$ using a recursion with one literal on both sides and $i\_2$ with a right recursion. This requires two different production rules and therefore a distinction. But because $i\_1$ and $i\_2$ refers to the same character, this also introduces an ambiguity which excludes the set of LL(1)-parseable grammars. Ergo, it's possible in context-free languages. It's impossible in LL(1).
> 2 votes

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


# Question
Title: what is the complexity of recurrence relation?
what is the complexity of below relation

$ T(n) = 2\*T(\sqrt n) + \log n$

and $T(2) = 1$

Is it $\Theta (\log n * \log \log n)$ ?

# Answer
> 6 votes
Yes, the answer is $\lg n \cdot \lg \lg n$:

Reason this out by expanding the recurrence and looking for a pattern:

\begin{align\*} T(n) &= 2T(\sqrt{n}) + \lg n \\ &= 2( 2T( \sqrt\[4\]{n} ) + \log(\sqrt{n}) ) + \lg n \\ &= 2\left( 2T(\sqrt\[4\]{n}) + \frac{1}{2} \lg n \right) + \lg n \\ &= 4T( \sqrt\[4\]{n} ) + 2 \lg n \\ &= 4( 2T( \sqrt\[8\]{n} ) + \lg\sqrt\[8\]{n} ) + 2 \lg n \\ &= 8T( \sqrt\[8\]{n} ) + 3 \lg n \\ \end{align\*} So as we continue expanding this and taking the square root of $n$, we will eventually bottom out where $n \< 2$. To figure out how many times we can take the square root of $n$, consider $n = 2^{\lg n}$, and on each recursive call, $n$ will have its square root taken. Ending when $n \< 2$ gives us: \begin{align\*} 2^{\frac{\lg n}{2^k}} &= 2 \\ \frac{\lg n}{2^k} &= 1 \\ \lg n &= 2^k \\ k &= \lg \lg n \end{align\*}

Giving a solution of $\lg n \lg \lg n$.

Alternatively, this can be solved via variable substitution and the Master Theorem. Substituting $m = \lg n$: \begin{align\*} T(2^m) &= 2T(2^{m/2}) + m \\ S(m) &= 2S(m/2) + m \end{align\*} At this point the Master Theorem applies, with $a=2$, $b=2$, and $f(m) = m$. Since $m^{\log\_b a} = m^{\lg 2} = m$, resulting in $f(m) = m = \Theta(m^{\log\_b a})$. Therefore case 2 of the Master Theorem applies, and the solution is $m \lg m$. Substituting $m = \lg n$ gives us $T(n) = \lg n \lg \lg n$.

Edit: fixed a typo (needed to write this to exceed the minimum number of characters).

---
Tags: asymptotics, recurrence-relation, mathematical-analysis
---


# Question
Title: Any very user friendly resources on the Baum-Welch algorithm?
I'd like to understand the Baum-Welch algorithm. I liked this video on the Forward-Backward algorithm so I'd like a similar one for Baum-Welch.

I'm having trouble coming up with good resources for Baum-Welch. Any ideas?

# Answer
> 0 votes
Though he doesn't say the name Baum Welch specifically, nor HMM's (until the very end) Jason Eisner does a great job covering Expectation Maximization here:

videolectures.net/hltss2010\_eisner\_plm/

# Answer
> 2 votes
A simple web search leads to a whole lecture by Christopher Lee. I did not watch it entirely, but it seems to be a slow, thorough take on the algorithm with an example walk-through on paper similar to the video you link (if longer).

---
Tags: algorithms, reference-request, hidden-markov-models
---


# Question
Title: Is there any theoretically proven optimal compression algorithm?
Is Huffman coding **always** optimal since it uses Shanon's ideas? What about text, image, video, ... compression?

Is this subject still active in the field? What classical or modern references should I read?

# Answer
Huffman coding is optimal for a symbol-to-symbol coding where the probabilities of every symbol are independent and known before-hand. However, when these conditions are not satisfied (as in image, video), other coding techniques such as LZW, JPEG, etc. are used. For more details, you can go through the book "Introduction to Data Compression" by Khalid Sayood.
> 9 votes

# Answer
There is a version of the Lempel-Ziv algorithm which is optimal in some scenarios. Namely, if the input comes from an ergodic Markov chain, then the asymptotic rate of the Lempel-Ziv algorithm equals the entropy. For more on that, take a look at Chapter 13 of Cover and Thomas.
> 7 votes

# Answer
Huffman compression, with certain assumptions that usually don't apply to real files, can be proven to be optimal.

Several compression algorithms compress some kinds of files smaller than the Huffman algorithm, therefore Huffman isn't optimal. These algorithms exploit one or another of the caveats in the Huffman optimality proof.

Whenever we have (a) we code each symbol independently in an integer number of bits, and (b) each symbol is "unrelated" to the other symbols we transmit (no mutual information, statistically independent, etc.), and (c) the receiver knows the probability distribution of every possible symbol, then Huffman compression is optimal (produces the smallest compressed files).

(a) symbol-by-symbol: By relaxing the binary Huffman restriction that each input symbol must be encoded as an integer number of bits, several compression algorithms, such as range coding, are never worse than, and usually better than, standard Huffman.

(b) unrelated symbols: most real data files have some mutual information between symbols. One can do better than plain Huffman by "decorrelating" the symbols, and then using the Huffman algorithm on these decorrelated symbols.

(c) known probability distribution: Usually the receiver does not know the exact probability distribution. So typical Huffman compression algorithms send a frequency table first, then send the compressed data. Several "adaptive" compression algorithms, such as Polar tree coding, can get better compression than Huffman because they converge on the probability distribution, or adapt to a changing probability distribution, without ever explicitly sending a frequency table.

Books and papers discussing such better-than-Huffman compression:
> 7 votes

# Answer
The optimal compression rate is related to the entropy of the data.

From the Wikipedia article http://en.wikipedia.org/wiki/Shannon%27s\_source\_coding\_theorem:

> N i.i.d. random variables each with entropy H(X) can be compressed into more than N H(X) bits with negligible risk of information loss, as N tends to infinity; but conversely, if they are compressed into fewer than N H(X) bits it is virtually certain that information will be lost.
> 2 votes

---
Tags: algorithms, information-theory, data-compression
---


# Question
Title: NFA for binary words that do not end in 10
> Construct an NFA over $\\{0, 1\\}$ whose language contains only words that do not end with $10$.

This is one of the first problems in the book, so it's supposedly easy. I just can't figure it out. It's easy using a DFA, but I'm not so sure using an NFA. Maybe I'm not understanding a particular concept in the NFA.

# Answer
Every DFA is also, in particular, an NFA. Therefore if you have constructed a DFA for some language, then you have a fortiori constructed an NFA for it.
> 5 votes

# Answer
If you are more comfortable with regular expressions, try to define your language as one.

> For example $(0 + 1)^\*(00 + 01 + 11) + 1 + 0 + \varepsilon$

Now convert the regular expression into an automaton with the simple method (which I assume you know).
> 1 votes

# Answer
Create one that accepts strings over $\\{0,1\\}^\*$ that end with the suffix $00$, another one for strings that end with $01$, and a third one for strings that end with $11$ then take their union.

**EDIT** Now NFA handles strings whose length $\lt 2$ and has an initial state.
> 0 votes

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


title: Error in Generating Function Solution

text:
# Question
Title: Error in Generating Function Solution
I am currently working my way through An Introduction to Analysis of Algorithms to stay sharp with recurrences as well as learn generating function techniques. However my analyses and the books analyses for the first few sample problems on ordinary generating functions differ. I've checked and rechecked \[my work as well as errata on the webpage\], but cannot see how the authors made certain leaps. For example:

Given the recurrence $a\_{n} = a\_{n-1} + 1$ for $n \geq 1$ with $a\_0 = 0$ and letting $A(z) = \sum\_{n \geq 0} a\_n z^n$ I have the following steps: $$ \begin{align\*} \sum\_{n \geq 1} a\_n z^n &= \sum\_{n \geq 1} a\_{n-1} z^n + \sum\_{n \geq 1} z^n \\ A(z) - a\_0&= zA(z) + \frac{z}{1-z} \\ A(z)(1 - z) &= \frac{z}{1-z} + a\_0\\ A(z) &=\frac{z}{(1-z)^2} + \frac{a\_0}{1-z} \end{align\*}$$

Since $a\_0 = 0$ we just end up with $$A(z) = \frac{z}{(1-z)^2} \\ a\_n = n$$.

However, the authors' derivation is the following: $$ \begin{align\*} \sum\_{n \geq 1} a\_n z^n &= \sum\_{n \geq 1} a\_{n-1} z^n + \frac{1}{1-z} \\ A(z) - 1 &= zA(z) + \frac{1}{1-z} \\ A(z) &= \frac{z}{(1-z)^2} \\ a\_n &= n\\ \end{align\*}$$ Am I crazy, how did they get $A(z) - 1$ in the 2nd step? They do the exact same thing in the next example for $a\_n = 2a\_{n-1} + 1$. Is this just a typo? I would expect them to subtract $a\_0z^0 = a\_0$. Where did that $-1$ come from?

# Answer
This answer is just so that the question is not left unanswered.

The OP is correct: the book got it wrong.
> 4 votes

---
Tags: recurrence-relation, mathematical-analysis, check-my-proof
---


# Question
Title: What is the purpose of k in the transitive closure method?
When converting a DFA to a regular expression using the transitive closure method, what is the significance of state $k$ and what values $k$ takes? If $k$ represents the intermediate states then what are the values for $k$? That is while applying the method, for which value of $k$ should we stop finding the regular expressions?

# Answer
One way you can think about the transitive closure method of converting DFAs to regular expressions (suggested by Michael Sipser in "Introduction to the Theory of Computation") is to think about converting a DFA to a regular expression by progressively ripping out states from the DFA and replacing transitions into and out of that state with new transitions labeled with regular expressions that have the same effect as entering and leaving the state. Once you have ripped out a sufficiently large number of states, you can directly read off the regular expression from the resulting automaton.

$k$ in this algorithm is used to indicate what states you have eliminated so far. You number all of the states $1, 2, 3, ..., n$, then use $k$ to indicate the numbers of all states you have eliminated at a particular point. First you eliminate state 1; then states 1 and 2; then states 1, 2, and 3; etc. Once you have $k = n$, you've eliminated all states and can just read off the answer.

If you'd like a graphical presentation of how this works, I have a set of lecture slides I used when teaching this construction. It doesn't formally specify the algorithm or prove correctness, but should give you a visual representation of what the algorithm is doing.

Hope this helps!
> 2 votes

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


# Question
Title: Find small superset of at least k of n given sets
Say we're given $n$ sets and the size of their union is $m$. We would like to construct a small set which contains at least $k$ of the $n$ given sets.

Lets assume that $m$ is less than some polynomial in $n$, i.e.: $m \< P(n)$. In this case is there an efficient (polynomial) algorithm for the optimization problem:

Find the smallest set which contains at least $k$ of the $n$ given sets.

# Answer
> 8 votes
The problem is NP-complete. Here is a reduction from 3SAT-5, an NP-complete version of 3SAT in which every variable appears exactly 5 times (and so the number of variables and number of clauses are linearly related).

We start by constructing two set systems. The first system $\mathcal{S}$ consists of 6 sets $A\_0,A\_1,B\_0,B\_1,C\_0,C\_1$ and 15 elements $D = \\{0,1\\}^4 \setminus (1,1,1,1)$, and has the following property: $$ |A\_i \cup B\_j \cup C\_k| = \begin{cases} 14 & \text{if } i=j=k=0, \\ 13 & \text{otherwise}. \end{cases} $$ The set system is given by $$\begin{align\*} A\_i &= \\{(a,b,c,d) \in D : a = i\\}, \\ B\_i &= \\{(a,b,c,d) \in D : b = i\\}, \\ C\_i &= \\{(a,b,c,d) \in D : c = i\\}. \end{align\*}$$ The only elements not covered by $A\_i \cup B\_j \cup C\_k$ are those of the form $(1-i,1-j,1-k,d)$. If $i = j = k = 0$ then there is one such element, otherwise there are two.

The second system $\mathcal{T}$ consists of $2n$ sets $X\_1,Y\_1,\ldots,X\_n,Y\_n$ and $O(n^2)$ elements, and has the following property. Call a family of $n$ sets out of $\mathcal{T}$ *proper* if it contains exactly one of each $X\_i,Y\_i$. All proper families of $n$ sets cover the same number of elements $M$, and each improper family of $n$ sets covers at least $M+1$ elements.

The set of elements consists of all unordered pairs of sets $\\{S,T\\}$ other than those of the form $\\{X\_i,Y\_i\\}$. Each set $S \in \mathcal{T}$ consists of all $2n-2$ pairs containing it. Let $\mathcal{F}$ be a family of $n$ sets, with complement $\overline{\mathcal{F}}$. The only elements not covered by $\mathcal{F}$ are those of the form $\\{S,T\\}$ where $S,T \in \overline{\mathcal{F}}$. If $\mathcal{F}$ is proper then so is $\overline{\mathcal{F}}$, and so there are $\binom{n}{2}$ elements not covered. If $\mathcal{F}$ is improper then so is $\overline{\mathcal{F}}$, and so there are fewer than $\binom{n}{2}$ elements not covered.

**The reduction.** Let $\phi$ be an instance of 3SAT-5 with $n$ variables and $m=5n/3$ clauses. For each clause $\phi\_j$ there is a copy $\mathcal{S}\_j$ of system $\mathcal{S}$. There is also a copy $\tilde{\mathcal{T}}$ of $\mathcal{T}$ in which each element is replaced by $N = 13m+1$ elements. The total number of elements is polynomial in $n$.

For each variable $x\_i$ there are two sets $X\_i^0$ and $X\_i^1$. The set $X\_i^0$ is the union of the following six sets:

* the set $X\_i$ of $\tilde{\mathcal{T}}$
* for each clause $\phi\_j$ containing $x\_i$ at the first position, if $x\_i$ appears positively, then the set $A\_0$ of $\mathcal{S}\_j$, otherwise the set $A\_1$ of $\mathcal{S}\_j$
* for each clause $\phi\_j$ containing $x\_i$ at the second position, either $B\_0$ or $B\_1$ (as above)
* for each clause $\phi\_j$ containing $x\_i$ at the third position, either $C\_0$ or $C\_1$ (as above)

The set $X\_i^1$ is defined similarly as the union of the following six sets:

* the set $Y\_i$ of $\tilde{\mathcal{T}}$
* for each clause $\phi\_j$ containing $x\_i$ at the first position, if $x\_i$ appears negatively, then the set $A\_0$ of $\mathcal{S}\_j$, otherwise the set $A\_1$ of $\mathcal{S}\_j$
* for each clause $\phi\_j$ containing $x\_i$ at the second position, either $B\_0$ or $B\_1$ (as above)
* for each clause $\phi\_j$ containing $x\_i$ at the third position, either $C\_0$ or $C\_1$ (as above)

The problem is to decide whether there are $n$ sets which together cover $13m+NM$ elements (or less).

If $\phi$ is satisfiable, say with truth assignment $x\_i$, then $\\{X\_i^{x\_i} : 1 \leq i \leq n\\}$ covers exactly $13m+NM$ elements. Conversely, suppose there is a way to cover at most $13m+NM$ elements. If the solution is improper then it covers at least $N(M+1) \> 13m+NM$ elements (considering only $\tilde{\mathcal{T}}$). If it is proper then it corresponds to some truth assignment $x\_i$, and it is easy to check that the number of elements covered is $13m+NM+Z$, where $Z$ is the number of falsified clauses. Hence $Z = 0$ and we conclude that $x\_i$ is a satisfying assignment.

---
Tags: complexity-theory, np-complete, np-hard, polynomial-time
---


# Question
Title: Proving a grammar only generates words whose alternating digit sums are multiples of three
This is homework and I'm looking for a push in the right direction. Proofs were never something I was properly taught, so now they're kind of a weak point.

Here's the problem:

> The following grammar generates numbers in binary notation ($C$ is the start symbol):
>
> $\qquad \begin{align}C &\to C 0 \mid A 1 \mid 0 \\ A &\to B 0 \mid C 1 \mid 1 \\ B &\to A 0 \mid B 1 \end{align}$
>
> 1. Prove that the alternating sums of the digits of the generated numbers are multiples of $3$. The alternating sum of $w=w\_0\dots w\_n$ is defined as $\sum\_{i=0}^n (-1)^i \cdot w\_i$. As an example, $C$ generates $1001$ via $C \Rightarrow A1 \Rightarrow B01 \Rightarrow A001 \Rightarrow 1001$ with alternating sum of $0$; clearly, $0$ is a multiple of $3$.
> 2. Prove that all such numbers (i.e., numbers whose alternating sum is a multiple of 3) are generated by the grammar.

I'm thinking I need to show that the grammar can only generate strings which are made up of repeated subsequences of digits which always add up to 0, 3, or -3. But I'm not sure how to show that it can only generate those three subsequences.

I also have worked out these thoughts:

* Consider that any even number of consecutive 1s is irrelevant, as they cancel each other out.
* Consider that all zeros are in of themselves irrelevant, as they add nothing.
* Consider then that the only relevant pattern is that of alternating 1s and zeros, and where this pattern starts and ends.

# Answer
> 4 votes
Rough hint: play around with the many equivalent models you have for regular languages.

For 1), I find problematic that the contribution of an already generated digit changes as more symbols are added to the front. Things would be easier if the grammar was right-linear.

> Convert the given grammar to an NFA and convert that one to a grammar with the simple construction, which always yields right-linear grammars. (You should have proven algorithms for both.) Determinising/minimising the intermediate automaton might also help the proof.

Then, you have to figure out an induction hypothesis on sentences that works and implies the statement (for words), and perform induction over the whole set of sentences (by the length of the derivation).

> For example, if a non-terminal $C$ can only end the derivation by deriving a $1$, then for any sentence of the form $wC$, either $w$ has even length and its alternating digit sum *plus one* divides three, or it has odd length.

For 2), build an automaton that you can easily show generates all such words.

> For instance, use a counter construction, that is count the alternating digit sum modulo three in the states.

Now you can show equivalence of this automaton and the one derived from the grammar in 1).

# Answer
> 2 votes
Here is a hint: figure out what each of the other two symbols $A,B$ generate. You can then prove part (1) by induction. This will also allow you to come up with the explicit construction needed to prove part (2).

# Answer
> 1 votes
For 1, I'd work by induction. That is I'd find a property of the strings generated by A, B and C and show that it holds for all construction. For example for C the property is that the alternating sum is a multiple of 3.

* it holds for the third production: the alternating sum of 0 is a multiple of 3
* it holds for the first production: the alternating sum of xxx0 is a multiple of 0 if the alternating sum of xxx is 0
* trying to show that it holds for the second production will give you an hint about which property you want for A

For 2, I'd first try to show that the strings generated for A and B don't have an alternating sum multiple of 3. Then I'd find a characterization of the strings not generated by A, B, C and show that they don't have an alternating sum multiple of 3 either.

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


title: Data structure for partition of a set

text:
# Question
Title: Data structure for partition of a set
A partition of a set S is a separation of the set into an arbitrary number of non-empty, pairwise disjoint subsets whose union is exactly S. What manner of a data structure should be used to represent a partition of a set if the following methods need to be optimized:

1. moving an element from one part to another, possibly an entirely new one, and
2. iterating over the parts of the partition.

A naive way of prioritizing 1 would be a hash/tree/whatever mapping from set elements to "part labels", but iterating over the parts would require O(N) for first constructing the actual parts from the labels. 2 is naively prioritized as a hash/tree/whatever set of hash/tree/whatever sets, but then moving elements around, especially to new subsets, incurs that memory management overhead.

Is there a way to get the best of both worlds? The implementation I need is Python but I imagine this is a cross-language question.

# Answer
I'm not familiar with the topic, so all I can do is give a few pointers. Manipulating partitions of finite sets is known by several names:

* union-find when you start with singletons and progressively merge sets;
* partition refinement when you start with a single set and progressively split it;
* **union-split-find** when sets can be both merged and split as in your case.

Katherine J. Lai's discusses the union-split-find problem and proposes an algorithm using B-trees that double as finger trees to represent each set. Each element is represented by a distinct integer; using consecutive values for elements that are likely to remain together is more efficient. To merge two sets, split them into non-overlapping intervals that are entirely contained in one of the sets, and join the pieces together. See her thesis for details.
> 7 votes

---
Tags: data-structures, partitions, sets
---


# Question
Title: Proving the security of Nisan-Wigderson pseudo-random number generator
Let $\cal{S}=\\{S\_i\\}\_{1\leq i\leq n}$ be a partial $(m,k)$-design and $f: \\{0,1\\}^m \to \\{0,1\\}$ be a Boolean function. The Nisan-Wigderson generator $G\_f: \\{0,1\\}^l \to \\{0,1\\}^n$ is defined as follows:

$$G\_f(x) = (f(x|\_{S\_1}) , \ldots, f(x|\_{S\_n}) )$$

To compute the $i$th bit of $G\_f$ we take the bits of $x$ with indexes in $S\_i$ and then apply $f$ to them.

> Assume that $f$ is $\frac{1}{n^c}$-hard for circuits of size $n^c$ where $c$ is a constant. How can we prove that $G\_f$ is $(\frac{n^c}{2}, \frac{2}{n^c})$-secure pseudo-random number generator?

### Definitions:

A partial $(m,k)$-design is a collection of subsets $S\_1, \ldots, S\_n \subseteq \[l\] = \\{1, \ldots, l\\}$ such that

* for all $i$: $|S\_i|=m$, and
* for all $i \neq j$: $|S\_i \cap S\_j| \leq k$.

A function $f$ is $\epsilon$-hard for circuits of size $s$ iff no circuit of size $s$ can predict $f$ with probability $\epsilon$ better than a coin toss.

A function $G:\\{0,1\\}^l \to \\{0,1\\}^n$ is $(s, \epsilon)$-secure pseudo-random number generator iff no circuit of size $s$ can distinguish between a random number and a number generated by $G\_f$ with probability better than $\epsilon$.

We use $x|\_A$ for the string composed of $x$'s bits with indexes in $A$.

# Answer
> 1 votes
Here is Ran G.'s answer mentioned in the comments: Google gives quite nice results: , .

---
Tags: cryptography, pseudo-random-generators
---


title: Counting inversion pairs

text:
# Question
Title: Counting inversion pairs
A classic application of divide and conquer is to solve the following problem:

*Given an array $a\[1\dots n\]$ of distinct, comparable elements, count the number of inversion pairs in the array: pairs $(i,j)$ such that $a\[i\] \gt a\[j\]$ and $i \lt j$.*

One approach to this is to do a Merge Sort, but also counting of the number of inversion pairs in the sub-problems. During the merge step, we count the number of inversion pairs that span across the (two) sub-problems and add to the counts of the sub-problems.

While this is good, and gives an $O(n\log n)$ time algorithm, this messes up array.

If we have the additional constraint that the array is read-only, then we can make a copy and deal with the copy, or use an additional data-structure like an order statistics balanced binary tree to do the counting, both of which use $\Theta(n)$ space.

The current question is to try and better the space, while not affecting the run time. i.e.

> Is there an $O(n\log n)$ time algorithm to count the number of inversion pairs, which works on a read-only array and uses sub-linear (i.e. $o(n)$) space?

Assume a uniform cost RAM model and that the elements take $O(1)$ space and comparison between them is $O(1)$.

A reference will do, but an explanation will be better :-)

I tried searching the web, but could not find any positive/negative answer for this. I suppose this is just a curiosity.

# Answer
> 3 votes
Here is Raphael's answer:

Chan and Pătraşcu give an $o(n\log n)$ time algorithm, but as far as I can tell from skimming the paper, they need $\Omega(n)$ space. Furthermore, Ajtai et al. prove that any (exact) $O(n)$ time streaming algorithm needs $\Omega(n)$ space. There seem to be approximations fitting your criteria, though.

---
Tags: algorithms, reference-request, arrays
---


title: Problem similar to set packing

text:
# Question
Title: Problem similar to set packing
Call a family of sets $\mathcal{F} = \\{S\_1, \dotsc, S\_k\\}$ "diverse" if each set $S\_i \in \mathcal{F}$ has at least one unique element. What are possible approaches for finding the largest diverse set $S$ in a family of sets $\mathcal{F}$?

One approach is to solve a modified set packing problem. Suppose $\mathcal{F}=\\{S\_1,\dotsc,S\_k\\}$. Let $K$ be a subset of elements, $K \subset \bigcup S\_i$, and let $\mathcal{F}\_{-K}=\\{S\_1 \setminus K,\dotsc, S\_k \setminus K\\}$. Then the maximal diverse set $S$ corresponds to the largest maximal set packing obtained from $\mathcal{F}\_{-L}$ where $L$ is the set of all non-unique elements in $\mathcal{F}$.

But, what's a good heuristic for choosing $K$? Or are there better approaches altogether?

# Answer
> 2 votes
The problem is NP-complete. This rules out an exact algorithm that works in all circumstances, but does not rule out heuristic algorithms that work well in practice, or approximations algorithm with provable approximation guarantees.

The reduction is from 3SAT. Given a 3SAT instance $\phi$ with variables $x\_1,\ldots,x\_n$ and clauses $\phi\_1,\ldots,\phi\_m$, construct the following set system. For each variable $x\_i$ there are two sets $A\_{i,0}$ and $A\_{i,1}$ and $N=n+1$ sets $B\_{i,t} = \\{\beta\_{i,t,0},\beta\_{i,t,1}\\}$, and for each clause $\phi\_j$ there is a set $C\_j = \\{\gamma\_{j,1},\gamma\_{j,2},\gamma\_{j,3}\\}$. The set $A\_{i,b}$ consists of the following elements:

* The $N+1$ elements $\alpha\_i,\beta\_{i,1,b},\ldots,\beta\_{i,N,b}$.
* For each clause $\phi\_j$ that contains $x\_i$ as the $k$th literal and is *not* satisfied by $x\_i = b$, the element $\gamma\_{j,k}$.

One can find $n(N+1)+m$ diverse sets if and only if $\phi$ is satisfiable. Indeed, given a satisfying assignment $\vec{x}$, the family $\\{ A\_i^{x\_i} : i \in \[n\] \\} \cup \\{ B\_{i,t} : i \in \[n\], t \in \[N\] \\} \cup \\{ C\_j : j \in \[m\] \\}$ is diverse: $\alpha\_i$ belongs only to $A\_i^{x\_i}$, $\beta\_{i,t,1-x\_i}$ belongs only to $B\_{i,t}$, and if the $k$th literal of $\phi\_j$ is satisfied then $\gamma\_{j,k}$ belongs only to $C\_j$.

For the converse, suppose $\mathcal{S} = \mathcal{A} \cup \mathcal{B} \cup \mathcal{C}$ is a diverse family of size at least $n(N+1)+m$, partitioned according to the type of the set. If $\mathcal{A}$ contains both $A\_{i,0}$ and $A\_{i,1}$ for some $i$, then $B\_{i,1},\ldots,B\_{i,N} \notin \mathcal{B}$. Hence $|\mathcal{S}| \leq 2n + (n-1)N + m \< n(N+1) + m$, which is impossible. Therefore $\mathcal{B}$ and $\mathcal{C}$ must contain all sets of the corresponding type, and $\mathcal{A}$ must contain $n$ sets, which together encode an assignment $\vec{x}$. Since $C\_j \in \mathcal{S}$ is diverse, by construction the assignment $\vec{x}$ satisfies clause $\phi\_j$, hence $\phi$ is satisfiable.

---
Tags: algorithms, combinatorics, heuristics
---


# Question
Title: Strategies for becoming unstuck in understanding TCS
I am a graduate student taking a course in theory of computation and I have serious trouble producing content once I'm asked to. I'm able to follow the textbook (Introduction to the Theory of Computation by Michael Sipser) and lectures; however when asked to prove something or come up with a formal description of a specific TM, I just choke.

What can I do in such situations? I guess my issue is with fully comprehending abstract concepts to the point I can actually use them. Is there a structured way to approaching a new, abstract concept and eventually build intuition?

# Answer
Abstraction is pretty much bread and butter in computer science but unfortunately it is hard to teach explicitly.

In my opinion, *understanding* concepts is more important than being able to mechanically calculate or prove stuff. Sure, you need to know your way around some elementary methods, but the meat lies elsewhere.

First of all, you have to grasp the content to some extent. To this end, I have found it useful to ask the following question whenever something is unclear to you:

* *Why* are we doing this?
* *What* are we going to use this for?
* What *similar things* does this relate to?
* How do *other sources* explain it?
* What *exactly* do I not understand?

After you have answered these questions (or discovered follow-up questions and treated them the same way) and still have problems, go to your teachers (or here). By now you should be able to formulate a focused, precisely formulated question; answering such questions is your teachers' job (and StackExchange's philosophy).

Other than that, it is exercise and experience. Try to reproduce proofs after having read them; take care to not learn them by heart but distill the important ideas from them. After some time, you should be able to reproduce all basic proofs by filling in gaps between the major steps. Even later, you will begin to see patterns in statements and proofs. This is how people look at a statement and say "Oh yeah, sure, use method X with theorem Y and then just use Z to get what you want.". It is pattern recognition fueled by years of training. Be patient.

As for basic exercises, go and find text books with some. Off the top of my head I can refer to Concrete Mathematics by Graham, Knuth, and Patashnik. This book is not only a precious toolbox for computer scientists, it also contains loads of exercises with solutions (!). Remember to attempt to solve them before looking up the answers and to reproduce answers you had to look up.

Another useful book is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. Included is a sizeable chapter on mathematical basics. It also contains many exercises; solutions are available via the linked page (Supplemental Content). There is also a video lecture by one of the authors which may go nicely with the book.

For introductore lectures regarding proofs, have a look at Linear Algebra Proofs on Khan Academy. I have not watched them, but hopefully they are both basic and helpful. There are many more proofs on Khan Academy; I just figure that linear algebra proofs might fit computer science best. Do no hesitate to watch others, too.
> 15 votes

# Answer
I sometimes find out that people that don't do well in theory, just have the basics wrong (on the first 1-3 lectures, they thought the material is very easy, so they didn't pay too much attention, but then, at lecture 5-7 things speed up and it's too late to recap).

As @fbernardo said, it might be a good idea to start from the beginning. NOT as far as FLA (there is no use in that when studying TC, IMHO), but definitely open Sipser and start solving the questions one by one, by their order. With the experience you'll get intuition and basic tools that are imperative for more advanced concepts.

If you cannot cope with Sipser's basic questions of the first chapter (not the automata chapters, if you study on TMs), then you might be lacking even more fundamental concepts, such as basic proof methods (induction, etc.) or basic set-theory and discrete math.

Good luck, anyways!
> 8 votes

# Answer
My only advice would be that you start from the beginning. In my course we use Sipser's book too, it is a good book in my opinion. But we do have a course before TC, named FLA (Formal Languages an Automaton) that gave be a better intuition and background on TC. So, again, everybody learns at different rates, and you have a very good book. Any other specific question you can always find help here. :)
> 3 votes

# Answer
You ask a general question in your title and then at least two basic/specific points in the question, and I think there are good (separate) answers to each one:

* how to prove stuff
* create formal descr of a TMs behavior

Here addressing only the 1st item (which is inherently broad & deserves it)-- its sort of the elephant in the room of STEM (science, technology, engineering, mathematics) education that gets short shrift & is often glossed over to a staggering degree. It might seem as if nobody really knows how to teach how to build proofs. This subj starts out in geometry, trigonometry and calculus classes, but is rarely a strict element of it. most teachers treat it as optional. It seems an entire class dedicated to "how to prove stuff" would be an excellent or even critical addition or change to STEM education.

Here are some refs that I turned up on a quick search for how to prove stuff, & I think there are many other good resources. Nowadays also there are probably many videos on the subject that could be turned up via searches, but I havent seen a nice comprehensive organization of "how to prove stuff" type videos.

A key part of proving is to master the basics of mathematics and use it all as tools or building parts. Eg know what a set is, what a tuple is, what the difference/similarity is, when you would use one but not the other, etc.

Another approach is to treat it like a drill. Do many practice proofs on your own, starting from easy to difficult (wish I knew of more books like this, there dont seem to be many).
> 2 votes

---
Tags: computability, education, intuition
---


# Question
Title: Compute 'insertable' letters in a regular language
Let $L$ a regular language and define the *subsequence closure* of $L$ as

$\qquad \displaystyle S(L) = \\{ w \mid \exists w' \in L.\ w \text{ subsequence of } w'\\}$.

The problem I want to solve is to find for such subsequences $w \in S(L)$ which letters can be inserted into them so that the result is also in $S(L)$. Formally:

> Given $w\_1\dots w\_n \in S(L)$, output all pairs $(i,a) \in \\{0,\dots,n\\} \times \Sigma$ for which $w\_1 \dots w\_{i} a w\_{i+1} \dots w\_n \in S(L)$.

Consider, for instance, the language$\\{ab, abc, abcc\\}$. The string $b$ is in $S(L)$ and inserting $a$ at the beginning -- corresponding to $(0,a)$ -- yields $ab \in S(L)$. On the other hand, the string $cb$ is not in $S(L)$; there is no way to convert it to a language string by insertion.

Using this language, if the input string is $b$ the possible insertions I am looking for are $(0,a)$ and $(1,c)$ at the end. If the input string is $bc$ the possible insertions are $(0,a), (1,c)$ and $(2,c)$.

The use of this algorithm is in a user interface: the user builds strings belonging to the language starting from an empty string and adding one character at a time in different positions. At each step the UI prompts the user with all the possible valid letters in all the possible insertion positions.

I have a working naive algorithm that involves a lot of back-tracking, and it is way too slow even in relatively simple cases. I was wondering if there is something better, or -- failing that -- if there are any available studies of this problem.

# Answer
The solution is to compute the DFA of the subsequence closure of the original language, and then using this DFA I just used the 'trivial' algorithm: try to insert each possible symbol in each position, if the resulting word is valid for this new DFA - i.e. belongs to $S(L)$ - then the symbol can be inserted at that position.

Using the closure DFA it should be possible to use the faster algorithm suggested by Yuval Filmus in one of the other answers; I did not try because the 'trivial' algorithm already gives good enough performances: from tens of seconds with my previous solution to sub-second execution time (computing the closure DFA only once of course).

To compute the closure DFA:

1. Create a new NFA with the same start and final states of the original DFA
2. For each transition $q\stackrel{a}{\longrightarrow}q'$ in the original DFA the new NFA has two transitions: the same $q\stackrel{a}{\longrightarrow}q'$ and a null one $q\stackrel{\varepsilon}{\longrightarrow}q'$ (where $\varepsilon$ is the null transition - this is the $\varepsilon$-shortcut)
3. Generate a DFA from this NFA using the usual system - this DFA is the closure one.

(Many thanks to Raphael for the help and for suggesting the solution)
> 3 votes

# Answer
Edit: The OP changed the question. What follows works for one interpretation of the original question.

I'm assuming you are given a DFA $A = (Q,\Sigma,\delta,q\_0,F)$. The method can be adapted to handle NFAs.

Let the word be $w = w\_1 \ldots w\_n$. For each $i \in \\{0,\ldots,n\\}$, calculate the state $s\_i$ that the automaton reaches after reading the prefix of length $i$ of $w$. For each $i \in \\{0,\ldots,n\\}$ and each accepting state $q \in F$, calculate the state $t\_{i,q}$ that the reverse automaton reaches when starting at $q$ and reading the reverse of the suffix of length $i$ of $w$. Let $T\_i = \\{ t\_{i,q} : q \in Q \\}$.

For each $i \in \\{0,\ldots,n\\}$ and each symbol $a \in \Sigma$, check whether $\delta(s\_i,a) \in T\_{n-i}$. If so, $a$ can be inserted at position $i$: $w\_1 \ldots w\_i a w\_{i+1} \ldots w\_n \in L(A)$.

The running time is $O(n(|\Sigma| + |Q|))$, and the method requires space $O(|Q|)$ (if implemented by going over $i = 0,\ldots,n$, in this order).
> 3 votes

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


# Question
Title: Is this phrase structure grammar from my textbook correct?
I just started reading "Parsing Techniques, A Practical Guide", Second Edition, by Dick Grune and Ceriel J.H. Jacobs.

On page 12, the authors start describing a set of rules that can be used to generate the set of all enumerations of names of the type "tom, dick and harry": the rules allow single names (e.g. "tom") as well as repetitions ("tom, harry, dick, dick and harry"); multiple names in an enumeration are separated by commas except the last two names which are separated by "and", so the following aren't valid: ("tom, harry, dick") or ("harry and tom and dick").

A few pages later, and after having defined some more terms and formalisms, the authors come up with the following replacement rules (parse structure grammar) to generate the sentences of the desired type:

```
0. Name -> tom | dick | harry
1. Sentence-> Name | List End
2. List -> Name | Name, List
3. , Name End -> and Name

```

In the above, **Sentence** is the start symbol.

However it seems to me that these rules can generate incorrect sentences: if we replace **Sentence** by **List End** and **List** by **Name** we end up with **Name End** for which no replacement rule is defined.

It seems to me that the 2nd line in the rules above, if replaced by

```
Sentence -> Name | Name, List End

```

would fix this problem.

Am I correct that the authors have made an oversight, and is my modification correct? Or have I misunderstood something?

I don't have a CS background and this is the first time I'm reading about parsing, so please keep that in consideration in your replies. Thanks!

# Answer
> 3 votes
You are correct, in a sense. Speaking in formal notation, you have

$\qquad \displaystyle \mathtt{Sentence} \Rightarrow \mathtt{List}\ \mathtt{End} \Rightarrow \mathtt{Name}\ \mathtt{End}$

and we can not get rid of $\mathtt{End}$. We have not generated a wrong *word*, but a sentence that can not be derived further to any word. That is not a mistake in the grammar itself (with respect to the generated language), but certainly nasty if you think of parsing.

Your modification is valid. In particular, we do not need to generate lists of length one using rule 2 (which you make impossible by your modification) because we can just alternative 1 of rule 1.

Note that the grammar given is not the greatest (for parsing). For example, it is not context-free (rule 3). A better way to implement detection of the end is to generate the list the other way round ($\\\_$ denotes a space):

$\qquad \displaystyle \begin{align} \mathsf{Sentence} &\to \mathsf{Name} \mid \mathsf{List}\ \mathtt{and}\ \mathsf{Name} \\ \mathsf{List} &\to \mathsf{Name} \mid \mathsf{List}\ \mathtt{,\\\_}\ \mathsf{Name} \\ \mathsf{Name} &\to \mathtt{tom} \mid \mathtt{dick} \mid \mathtt{harry} \end{align}$

Of course, this grammar is now left-recursive which is problematic for some parsing strategies (e.g. LL). So it may be useful to create the list from left to right after all, but keep generating the $\mathtt{and}$ at the start:

$\qquad \displaystyle \begin{align} \mathsf{Sentence} &\to \mathsf{Name} \mid \mathsf{List}\ \mathtt{and}\ \mathsf{Name} \\ \mathsf{List} &\to \mathsf{Name} \mid \mathsf{Name}\ \mathtt{,\\\_}\ \mathsf{List} \\ \mathsf{Name} &\to \mathtt{tom} \mid \mathtt{dick} \mid \mathtt{harry} \end{align}$

Now a parser working from left to right can always identify the next rule (with a lookahead of two to catch whether there is a comma behind a name).

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


# Question
Title: Random algorithm with biggest sequence that never repeats
I am going to attempt to write a random number generator using exisiting randomize algorithms. Can you suggest which algorithm has the biggest sequence that never repeats? I don't care if they are fast or slow.

# Answer
> 6 votes
If you don't want to follow Yuval's advice :), Mersenne Twister algorithm is a good random number generator and has a quite simple implementation (period of $2^{19937}−1$). See Wikipedia page for quick highlights on advantages/disadvantages. There are also many open source implementations in many programming languages.

For technical details and in-deep analysis of the algorithm see M. Matsumoto's articles that are available on his page.

---
Tags: algorithms, randomness
---


# Question
Title: Distinct variables for different clauses
In resolution theorem proving, it is normally assumed variables in different clauses are distinct. This is not something that happens automatically; it requires significant extra code and computation to implement. Given that, I'm looking for a test case for it.

The problem is, in all the test cases I've tried so far, it makes no difference. Presumably it matters only in unusual edge cases. As Wikipedia puts it, "variables in different clauses are distinct... Now, unifying Q(X) in the first clause with Q(Y) in the second clause means that X and Y become the same variable anyway."

Are there any known test cases that will actually give the wrong answer if different clauses use the same variables?

# Answer
**Edit:** I found a better example. Consider these clauses: \begin{align} & \lnot P(x) \lor P(f(x)) \\ & P(x) \\ & \lnot P(f(f(x)))\\ \end{align} Obviously, this set of clauses is contradictory. But without renaming variables, the only possible resolvent is $P(f(x))$ and no more resolvents are possible - all lead to substituting $f(x)$ for $x$, which is impossible.

---

**Edit:** Consider the meaning of clauses. Each clause is implicitly universally quantified. So the meaning of its variables isn't fixed to anything. Now let's say you have two clauses both containing $x$. If you perform resolution without renaming $x$ in one of them, then you add a meaning to $x$ which it doesn't have: you say that $x$ means the same thing in both clauses, which is not true. If you don't have distinct variables in your clauses, resolution will give you too weak conclusions.

---

(The original answer.) For example, let's have 4 clauses:

1. $A\lor B(x)$
2. $\lnot A\lor C(x)$
3. $\lnot B(c)$
4. $\lnot C(d)$

where $x, y$ are variables and $c, d$ constants. If we perform resolution on the first two without renaming $x$, we'll get $B(x)\lor C(x)$. We can proceed with $\lnot B(c)$ to get $C(c)$ but now we cannot resolve it with $\lnot C(d)$.

On the other hand, if we rename $x$ to $y$ in the second one to have disjoint set of variables, we'll get $B(x)\lor C(y)$ from the first resolution step and we can derive an empty clause using $\lnot B(c)$ and $\lnot B(d)$.
> 6 votes

---
Tags: logic, automated-theorem-proving
---


# Question
Title: What's the complexity of Spearman's rank correlation coefficient computation?
I've been studying the Spearman's rank correlation coefficient

$\qquad \displaystyle \rho = \frac{\sum\_i(x\_i-\bar{x})(y\_i-\bar{y})}{\sqrt{\sum\_i (x\_i-\bar{x})^2 \sum\_i(y\_i-\bar{y})^2}}$.

for two lists $x\_1, \dots, x\_n$ and $y\_1, \dots, y\_n$. What's the *complexity* of the algorithm?

Since the algorithm should just compute $n$ subtractions, is it possible to be $O(n)$ ?

# Answer
> 9 votes
You have to compute

* two averages,
* $2n$ differences,
* three sums with $n$ summands -- which can be computed in constant time -- each and
* one division, one multiplication and one square root.

All of this can be done in linear time if we assume elementary arithmetic operations run in constant time, therefore total time in $O(n)$ is certainly possible. Note that computing the root might screw things up.

Regarding space, you have several options:

* Store only the averages, that is two numbers ($O(\log M)$ with $M$ the maximum number). You have to recompute all differences, that is perform a total of $6n$ subtractions.
* Store the average *and* the differences, that is $2n+2$ numbers ($O(n \cdot \log M)$). This saves you $4n$ subtractions.

Which is preferable depends on your context.

# Answer
> 7 votes
You have left out a important step... The formula you have is for the pearson correlation. What makes it spearman is that x and y are the ranks for the two original variables. This ranking step must be taken into account for the complexity of the spearman correlation coefficient. Essentially you must sort each of the two variables, which will depend on your chosen sorting algorithm, followed by the calculation mentioned above.

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


# Question
Title: Known facets of the Travelling Salesman Problem polytope
For the branch-and-cut method, it is essential to know many facets of the polytopes generated by the problem. However, it is currently one of the hardest problems to actually calculate all facets of such polytopes as they rapidly grow in size.

For an arbitrary optimization problem, the polytope used by branch-and-cut or also by cutting-plane-methods is the convex hull of all feasible vertices. A vertex is an assignment of all variables of the model. As a (very simple) example: if one would maximize $2\cdot x+y$ s.t. $x+y \leq 1$ and $0\leq x,y\leq 1.5$ then the vertices $(0,0)$, $(0,1)$ and $(1,0)$ are feasible vertices. $(1,1)$ violates the inequality $x+y\leq 1.5$ and is therefore not feasible. The (combinatorical) optimization problem would be to choose among the feasible vertices. (In this case, obviously $(1,0)$ is the optimum). The convex hull of these vertices is the triangle with exactly these three vertices. The facets of this simple polytope are $x\geq0$, $y\geq 0$ and $x+y\leq 1$. Note that the description through facets is more accurate than the model. In most hard problems - such as the TSP - the number of facets exceeds the number of model inequalities by several orders of magnitude.

Considering the Travelling Salesman Problem, for which number of nodes is the polytope fully known and how much facets are there. if it is not complete, what are lower bounds on the number of facets?

I'm particularly interested in the so-called hamiltonian path formulation of the TSP:

$$min \sum\_{i=0}^{n-1}(\sum\_{j=0}^{i-1}c\_{i,j}\cdot x\_{i,j}+\sum\_{j=i+1}^{n-1}c\_{i,j}\cdot x\_{i,j})$$ s.t.

$$\forall i \neq j:\ \ 0 \leq x\_{i,j}\leq 1$$ $$\forall i \neq j\ \ \ x\_{i,j}+x\_{j,i}\leq 1$$ $$\forall j \ \ \sum\_{i=0}^{j-1}x\_{i,j}+\sum\_{i=j+1}^{n-1}x\_{i,j}\leq 1$$ $$\forall j \ \ \sum\_{i=0}^{j-1}x\_{j,i}+\sum\_{i=j+1}^{n-1}x\_{j,i}\leq 1$$ $$\sum\_{i=0}^{n-1}(\sum\_{j=0}^{i-1}x\_{i,j}+\sum\_{j=i+1}^{n-1}x\_{i,j})=n-1$$

If you have any information about polytopes of other formulations of the TSP, feel free to share that too.

# Answer
For asymptotic bounds, Fiorini, Massar, Pokutta, Tiwari, and de Wolf recently showed exponential lower bounds on the number of facets of *any polytope that projects to the TSP polytope* (the TSP polytope, being the convex hull of feasible TSP solutions). This is stronger than what you ask for, and implies that even adding extra variables will not make the TSP polytope efficiently representable.

Their paper is follow up to the classical 1988 paper by Yannakakis, who showed the same result but only for polytopes that satisfy a certain symmetry condition.
> 11 votes

# Answer
There is a library called SMAPO (short for library of linear descriptions of SMAll problem instances of POlytopes in combinatorial optimization) for a lot of polytopes including the symmetric TVP as well as the graphical TSP.

For the STSP, this is the list of number of facets for small polytopes

```
 Nodes in STSP  |  # of facets
----------------+--------------
       6        |         100
       7        |        3437
       8        |      194187
       9        |    42104442
      10        | 51043900866

```
> 4 votes

---
Tags: algorithms, optimization, linear-programming, mathematical-programming, traveling-salesman
---


# Question
Title: Historical relation between computer science and the theory of dynamical systems
I have asked this question at math.stackexchange, but I have been redirected here.

My question is, if there is any historical relation between the fields of Dynamical systems (and related fields such as Optimal control) and (theoretical) Computer science. The reason for which I ask this question is, that several older major journals, now considered to be primarily focused on theoretical computer science, were originally devoted both to computer science and to dynamical systems.

The example of such journals can be for instance Journal of Computer and System Sciences. Mainly in its beginnings (however, I am too young to remember these times), it published papers both on computer science and on system sciences, and both of the fields seemed to be of equal importance. Moreover, also the name of the journal Information and Control suggests the relation to optimal control. However, this journal was always focused mainly on theoretical computer science and information theory.

So therefore I wonder, if these fields (nowadays, up to my knowledge, considered to be substantially different) have something in common or if there is some purpose to consider these fields to be related.

# Answer
> 3 votes
Yes there did seem to be historically a strong connection between study of dynamical systems and advanced theoretical computer science, that is shifted dramatically over time. Some of this has become mainstream and incorporated into more "core CS" (for example the empirical study of algorithms running on the SAT transition point and their strong thermodynamic/physics analogies, or empirically studied behavior of differential equations too difficult to solve exactly, etc) and some of it has moved into separate areas of more "applied" research, eg simulations of complex systems. Here are some refs on the history that might be helpful:

---
Tags: history
---


# Question
Title: Turing Machine-Like Formalism for The Actor Model
Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done.

The Actor Model is sometimes mentioned as a more powerful computational-model than Turing machines (not in what it can compute, but in other aspects).

1. Is The Actor Model a full fledged Turning machine alternative as a computational model?
2. Does The Actor Model also have such a symbol-based formal computation description akin to the Turing machine?
3. Are the actors assumed to be Turing machine equivalent - since each message is processed sequentially (and atomically)?

There are many theoretical results based on Turing machines, e.g. the halting problem, decidability, relation to Gödel's incompleteness theorem etc.

Can these proofs be formally generalize to the Actor Model? Has this been done?

# Answer
> -3 votes
computer scientists generally are of the consensus that the Church Turing thesis\[1\] is correct and definitive, ie that Turing machines describe computation, and that *more powerful forms do not really exist,* and take assertions that some model is "more powerful" than Turing machines with extreme skepticism, even near hostility.\[2\] neophytes to the field who dont fully understand the concept are prey to near-marketing slogans of some theory as "more powerful" than Turing machines but those claims are rarely made by mainstream/reputable computer scientists.

but as a flip side to this, *many* models of computation are Turing complete. therefore in CS there is in practice mostly a tolerant, "live and let live" attitude with many different models of computation proliferating depending on what is most relevant and convenient for the problem studied. most basic programming models are Turing complete with basic structures such as memory, conditionals, and loops, subroutines etcetera. so more reasonable claims are, "model \[x\] is better suited to study \[y\] because \[z\]". the Actor model focuses on message passing, communication, concurrency & some security.

nevertheless there is some mostly *philosophical* debate in CS about some models being "more powerful".

\[1\] Church Turing thesis

\[2\] Interactive models of computing vs Church Turing thesis

---
Tags: terminology, computability, reference-request, programming-languages, computation-models
---


# Question
Title: What is the growth rate of the world wide web?
Is there any way to estimate how much data is added to the world wide web each second? Are there any studies about this?

# Answer
> 2 votes
There is much interesting research in this area that is ongoing. See eg

---
Tags: computer-networks
---


# Question
Title: The meaning of modulo in “formula modulo a background theory”
I have been reading some papers where I keep reading stuff like “first-order formula modulo a background theory”. Does anyone know what modulo means in this case ? Is it something like “with respect to”?

# Answer
> 8 votes
A theory, in this sense, is an equivalence relation on the formula, which states when these formula are equivalent (as in: $F$ is equivalent to $G$ iff $F$ implies $G$ and $G$ implies $F$). The theory is usually presented by a set of deduction rules, though this is not an obligation.

The word *theory* is often used in the context of rewriting systems: if you have rules to rewrite terms (which may be formulas, but the concept is more general) of the form $t \rightarrow t'$, then the induced equivalence relation $t\_1 (\leftarrow \cup \rightarrow)^\* t\_2$ (any number of rewriting steps, alternating directions as often as desired) is the equational theory of this rewriting system.

Technically, “first-order formula modulo a theory $T$” means that you are manipulating equivalence classes which are sets of formulas. Intuitively and practically, this is saying that we are manipulating formulas, but we may replace a formula by some other equivalent formula at any time.

# Answer
> 3 votes
In first order logic there are formulae that are not necessarily valid. The equality

$x + y = y + x$

does not hold for arbitrary interpretations of equality and the addition symbol. It does hold for the interpretation of $+$ and $=$ in standard arithmetic. So if we assume the theory of Peano arithmetic (or first order arithmetic, or even Presburger arithmetic), then, the first order formula is said to be true "*modulo a background theory*".

More generally, if you assume you are working with a specific theory such as a fragment of arithmetic, or a theory of strings, or lists, or any of the many logical theories that exist, the phrase "true modulo a background theory" means, you are assuming first order logic with some axioms which will not be repeated explicitly every time.

---
Tags: terminology, logic, term-rewriting
---


title: How to reduce to an NP-hard problem?

text:
# Question
Title: How to reduce to an NP-hard problem?
For an assignment I have to program an application to schedule conversations. There is an event where representatives of the elementary schools talks with the representatives of high schools. They will talk about the students that will be transferred to the highschool. There are approximately 200 elementary schools and 40 high schools that will be participating in this event. The schools already know which student is transferring to which high school. The conversations will only be between representatives of E and H from student that will be transferring to H.

The rules are:

1. The duration of each conversation is based on the amount of students per representatives.Each conversation last 5 minutes per student. If a group consist of 1 student, this conversation last 10 minutes.
2. No timeclashes
3. All the students of the same group will be scheduled together, so, a representatives will only face the same representative once.
4. Timespan is 13.00-19.00
5. The waiting time of a representative is at most 20% of his time. A waiting time is an empty timeslot between the 1st and last conversation.
6. Schedules for 2 days
7. Each representatives participate for 1 day.

The problem is that I know that this is hard to solve, but I dont know if it's NP-hard. Right now I only know this problem is similar to a Job Shop Problem. What can I do to proof that my problem is NP-hard? I read that I need to reduce a known problem to my problem. But how do I do this? I have read different articles and books, but I still don't understand the steps to do it.

# Answer
Just an extended comment.

I think that before trying to find a reduction, you should try to better formalize the problem:

* define exactly what the *parameters* of the problem are, formalize their constraints, and formalize the question;
* try to simplify (or remove) the details;

For example:

* *If a group consist of 1 student, this conversation last 10 minutes.* $\rightarrow$ it is equivalent to a group of two students, so you can remove it;
* *Timespan is 13.00-19.00* $\rightarrow$ in the other rules you use minutes, so convert the "timespan" to $T$ minutes;
* try to think if a simplified version of the problem has a quick solution or it can be still hard (e.g. if the event last only one day rules 7 and 8 can be dropped)
* express the rules with a math formula: e.g "if an elementary group $E$ of $n$ students talk with a high school group $H$ of $m$ students then the total time $TT$ required is $TT(E,H)=....$"; "the total max wait time $WT$ for group $E$ is $WT = ...$"

Furthermore there is a point that it is not clear (to me):

* suppose you have an elementary school group $E$ having $n$ students that talk with a high school group $H$ having $m$ students; what is the total time required? (1) $5 * n$ (the talk is public) or (2) $5 * ( n / m)$ (each student of E talks with a single student of H). If the talk is public, then the number of students is redundant, and you can think only in terms of total time required by a school group.
> 5 votes

# Answer
Garey & Johnson outline the following four steps for proving NP-completeness results:

1. **Show that your problem is in NP.** Informally, this means that it's possible to verify the correctness of potential solutions to your problem "quickly" - i.e., in polynomial time.
2. **Select a known NP-complete problem.** Again, Garey & Johnson provide an excellent list. They suggest that 3SAT, 3-Dimensional Matching, Vertex Cover, Clique, Hamiltonian Circuit, and Partition "...can serve as a 'basic core' of known NP-complete problems for the beginner."
3. **Construct a reduction from the known NP-complete problem to your problem.** Very informally, to construct such a reduction one might first assume the existence of a "black box" which quickly solves instances of your problem. Then, demonstrate that it's possible to quickly solve the known NP-complete problem selected in step 2 using your "black box." This implies that your problem is "at least as hard" as a known NP-complete problem. Finally, to show that your problem is "no harder" than an NP-complete problem, proceed in the opposite direction: start with a "black box" that solves the NP-complete problem, and show that you can quickly solve your problem using that box.
4. **Show that the reduction in step 3 is a polynomial reduction.** In other words, show that the "black box" solutions in step 3 take place *in polynomial time.*
> 1 votes

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


# Question
Title: Benefit of Backward Pass at compile time
We collect most of the information about possible compiler optimizations during forward pass. Is it possible to utilize the information collected in forward pass in a backward pass so as to perform better optimizations ?

Note: I have been going through the patent Compiler with cache utilization optimizations by Roch G. Archambault et al. (2004) and was wondering what kind of information might have been utilized in their backward pass.

# Answer
> 2 votes
Many major compiler optimizations use backward passes. For example, computing liveness information, which is used to do dead code elimination, usually requires a backwards pass over the CFG of a program in order to identify unnecessary statements. Partial redundancy elimination, a powerful algorithm for eliminating redundant computation or rearranging code, consists of two forward passes combined with two backward passes to determine what expressions are available (forward), what expressions are anticipated (backward), etc.

Hope this helps!

---
Tags: compilers, program-optimization
---


title: Unambiguity of Reverse Polish Notation

text:
# Question
Title: Unambiguity of Reverse Polish Notation
Lets say I have given following grammar which generates arithmetic expressions in reverse polish notation:

$G=({E},{a,+,\*},P,E)$
$P={ E \rightarrow EE+ | EE\* | a }$

I know this grammar is unambiguous.

What I do not understand is how I can prove this.

I already searched a lot to in google, etc. but everyone only says, that reverse polish notation are unambiguous, but not WHY.

Can you give me any hints?

# Answer
> 3 votes
To show that a grammar is unambiguous, it is enough to show that for any expression E, there is only one "last step" possible in any derivation of E. It is the case here : the last rule is given by the last symbol of the expression (either +, \*, or a terminal a), and the parentheses will prevent any ambiguity. Of course you can not write "$abc+$" in your grammar, it has to be $(ab)c+$ or $a(bc)+$, but this is implicit when you define a grammar.

For instance, $a(bc+)\*(bc)\*+$ is not ambiguous : the last rule is given by the last symbol +, and so on... the expression it represents is $(a\*(b+c))+(b\*c)$

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


title: Negation of nested quantifiers

text:
# Question
Title: Negation of nested quantifiers
The problem is:

$$\exists x \forall y (x \ge y)$$

With a domain of all real positive integers.

The negation is:

$$\forall x \exists y (x \< y)$$

so, if $y = x + 1$, the negation is true.

That means the negation of the negation (i.e. the original problem) is false.

My question is, that if the original problem is $\exists x \forall y (x \ge y)$, why can't I take $x = y$ and prove the problem true?

# Answer
I'll start with your last question (in the comments); namely "Why doesn't x = y satisfy the initial problem".

The answer is in the quantifiers. Read from left to right. It starts with "there exists" X. So pick an X in your head. Say X = 5. We can not pick Y here because it doesn't have a value yet and we MUST pick a value for X NOW. Now proceed to read the next quantifier which reads "for all Y". Oops. We can't say for all Y because we already set Y = X.

Actually if you are going to look for a solution that satisfies the original formula, it should be of the form "X=(some positive integer)", with Y not involved at all, as it is a bound variable (as opposed to being a *free* variable which we can choose).

However, the formula says "there is a (single, and specific) positive integer X which all integers are less than or equal to it" which is clearly false because given any positive integer X, X+1 is a positive integer which is *not* less than nor equal to it (which is what the negated formula says!).
> 11 votes

---
Tags: logic, first-order-logic
---