# Question
Title: Data structure with constant time operations
I need to use a data structure, implementable in C++, that can do basic operations, such as lookup, insertion and deletion, in constant time. I, however, also need to be able to find the maximum value in constant time.

This data structure should probably be sorted to find the maximum values and I have looked into red-black trees, however they have logarithmic-time operations.

# Answer
It is impossible to build a data structure that supports insert, maximum, and delete all in constant time. Such a data structure is a priority queue, and a priority queue with all constant-time operations can do heapsort in linear time. Since there is a superlinear lower bound on sorting, this is impossible. One of insert, maximum, or delete must be logarithmic time.

Certain species of tree (like those with lazy deletion and incremental partial rebuilding) require only insert to be linear time. A skew binomial heap requires only delete to be linear time.
> 9 votes

# Answer
I think we should start by clarifying a few things. The data structure is simply, as the name implies, the way in which the information is structured or *organized*. When you talk about performing operations such as searches, insertion, and deletions, you're really talking about the *algorithms* that operate in those structures. Different algorithms can vary in performance even if you're using the same data structure. For example, consider performing a binary search in a sorted array, which is logarithmic or `O(lg(n))`, vs sequential search in an unsorted array, which is `O(n)` or linear.

There's usually a trade-off when selecting an algorithm to operate on a specific data structure. (Using Big-O notation we get an idea of the asymptotic upper bound for the 'worst case' performance of an algorithm.) There're a few options, but none that will meet *all* the requirements at once, for the *worst* case at least. Think about it, if we had algorithms that could do *everything* in constant time, why would we need to have so many different ones? ;)

That being said, you can consider the *average* performance of some of these and you might be able to make a reasonable pick. For example, a hash table is `O(1)` for insert/delete/find on the *average* case, which could meet your requirement (depending on how flexible you're willing to be), but in the *worst* case it will be `O(n)`. The behavior of other structures (e.g. Arrays) depend on whether they're sorted or not. For example, in an *unsorted* array, you can get `O(1)` for insertion, but for searches will take `O(n)`.

You can use some domain information to make an educated guess regarding what your system will likely spend most of its time doing. For example, if you know the system will be performing searches most of the time, then you can make a tradeoff and choose an algorithm with a lower upper bound (e.g. `O(lg(n))` instead of `O(n)`) on searches, even if insertion/deletion is not as good.

Whether something is 'sorted' or not will make sense depending on the data structure you choose. For example, a tree structure is not inherently 'sorted'; the 'sorting' is produced by the method used to traverse it (e.g. pre-order, in-order, post-order).

If the structure needs to quickly report the max/min values, it might be worth keeping a cached copy of the value in order to avoid searching for it. Again, this is a tradeoff of consuming additional memory to reduce the cost of a search.

You could do something like the following (pseudo-code):

```
void SomeClass::insert(int value) {
    // add value into internal structure
    this->_values.push_back(value);

    // check cached copy
    if(value > this->_max_value)
        this->_max_value = value;
    else if(value < this->_min_value)
        this->_min_value = value;
}

```

Then you'd only need to return your cached copies when needed. Note that there's still a tradeoff here: You have to spend some time and logic keeping these cached copies up-to-date. In other words, check every point where something can be added and then updating these copies again at every point when they're deleted --which will incur a search for the max/min value from the elements that remain. The benefit of caching can quickly go away, or even become a detriment, if your system will spend most of the time adding and removing elements instead of searching. So, as mentioned previously, you should use your domain knowledge of the problem to make a best-guess and decide which tradeoffs are worth the effort.
> 0 votes

---
Tags: data-structures, efficiency, dictionaries, constant-time
---


# Question
Title: Why don't 2 GPUs double the graphics performance of a computer compared to a single GPU?
Obviously, if you have 2 GPUs, it is double the hardware, and thus it should be double the power of a single GPU (assuming all GPUs are the same, of course). So why is this not the case? I searched this question on Google and things about optimization and things came up, but I still don't understand.

# Answer
> 6 votes
When you are using two processors, not every task your GPU's encounter is parallel by nature. There are a certain portion of tasks which are strictly serial, and can be processed by only one processor at a given time.

If a set of tasks were to be 100% parallel your dual GPU set up should give double the speed (in theory).

A little mathematics for you: Ahmdal's law for speedup is given by

$$S = \frac{1}{\[B+\frac{(1-B)}{n}\]}$$, where B is the percentage of tasks that is serial in nature, n is the number of processors and S is the speedup.

Put B=0 and you wil get S, ie Speedup=2.

Practically dual GPU gives us maximum 80% speedup.

---
Tags: computer-architecture, parallel-computing, efficiency
---


# Question
Title: approximation algorithm for Travelling Salesman Problem: with a different inequality and not triangle inequality
I have the following question for the travelling salesman problem:

The TSP algorithm is to find a complete hamilton cycle with minimum cost in a weighted graph **G**. Instead of the traingle inequality, the weight function satisfies the following inequality:

```
cost(u,w) < cost(u,v) + 2 x cost(v,w)

```

Find the approximation ratio if we use the following approximation algorithm:

```
1. Select any vertex as root vertex
2. Compute a minimum spanning tree T from graph G
3. Let L be the list of vertices visited in a preorder tree walk of T
4. return the hamilton cycle H that visits the vertices in the order L

```

**My work so far**

I figured out that it is 2-approximation if it is the triangle inequality, since going directly from one vertex to another has a cost no greater than going to a vertex in between these two vertices, so `cost(H)` is not greater than the cost of the preorder tree walk and therefore no greater than twice the cost of the optimal tour.

However, inequality `cost(u,w) < cost(u,v) + 2 x cost(v,w)` would make it different than triangle inequality that going directly `from u to w` could result in higher cost than `from u to v to w` (unless `cost(v,w)=0`). I think the worst case is extra cost of `cost(u,v) + 2 x cost(v,w) - (cost(u,v) + cost(v,w))= cost(v,w)`

Any advice on this? I need to find the approximation ratio.

# Answer
> 1 votes
Review the standard proof that it's a 2-approximation if the weight function satisfies the triangle inequality. That suggests a way to upper-bound the total length of the Hamilton cycle $H$ returned by the algorithm.

Adjust that reasoning. For starters, assume that every edge in $H$ is a "shortcut edge" $(u,w)$ that was taken by skipping a single vertex $v$. What could you conclude about the cost of $H$, compared to the cost of $T$? If you do a little bit of algebra you should be able to obtain an expression.

Now generalize to arbitrary $H$.

---
Tags: algorithm-analysis, approximation, traveling-salesman
---


title: Validating authenticity of a file

text:
# Question
Title: Validating authenticity of a file
Suppose there's an entity which produces files. User A has one of those files and decides to send it to user B.

How can user B validate the authenticity of the file without communicating with the producer? Is it even possible?

# Answer
> 2 votes
It depends on what you call "without communicating". How does B know that A really exists ? Either B speaks to A, or C tells to B that A exists, and B trusts C.

So, if a trusted C exists, C may provide to B a key to authenticate A. If a trusted C doesn't exist, B can't know if A exist, and authenticate its messages makes no sense.

---
Tags: security
---


# Question
Title: pseudo clique with at least connectivity x and maximum weight of the nodes
Let $G=(N,E)$ be a undirected graph of nodes $N$ and edges $E$. Each node $n \in N$ has a weight $w(n)$. The weight of a graph is defined as the sum of the weights of its nodes, i.e., by $w(G) = \sum\_{n \in N}w(n)$. The connectivity of the graph is defined to be $c(G) = \\#E\_G / (\\#N\_G \cdot (\\#N\_G - 1)/2)$ -- this measures the fraction of edges in comparison to the maximum possible number of edges.

Given $G$ and a number $x$, I want to find the maximal-weight subgraph $G'$ which has at least connectivity $x$, i.e., I want to find $G'$ that makes $w(G')$ as large as possible, subject to the requirement that $G'$ is a subgraph of $G$ and $c(G') \ge x$. This looks like some kind of generalization of the clique problem; here I essentially want to find a "pseudo-clique". Is there any efficient algorithm for this problem?

# Answer
Your problem is NP hard, because with $x=1$ (real clique) and the same weight for each node you get the maximum clique problem, which is NP complete. You can try to find a reduction in order to use a SAT solver, or just enumerate the $2^N$ subgraphs.

Furthermore, unless P = NP, there can be no polynomial time algorithm that approximates the maximum clique to within a factor better than $O(n^{1 − \varepsilon})$, for any $\varepsilon \> 0$. Wikipédia

We can't even find a good probabilistic algorithm, unless NP is in BPP.

If your $x$ is fixed and $\<1$, look at the following article:

An Efficient Algorithm for Solving Pseudo Clique Enumeration Problem. Takeaki Uno. Algorithmica, January 2010, Volume 56, Issue 1, pp 3-16.

It considers a variant of the problem with no weights, but you can substitute each vertex by a clique of size square root of its weight, if the weights are not too big, and then apply their techniques.
> 2 votes

---
Tags: algorithms, graphs, clique
---


title: Complexity of a SAT related problem

text:
# Question
Title: Complexity of a SAT related problem
Given a set of (propositional) formulae $\Phi$, two formulae $\phi$ and $\xi$, determine whether there exists $\Psi\subseteq \Phi$ such that $\Psi\models \phi$ and $\Psi\not\models \xi$.

Question: what is the (theoretical) complexity of this problem? Is it in DP?

# Answer
> 2 votes
Given a propositional formula $\varphi(\vec{x}, \vec{y})$, consider $\psi = \exists \vec{y} \ \forall \vec{x} \ \varphi(\vec{x}, \vec{y})$.

Let $\Delta = \\{ y\_0 \leftrightarrow \top, y\_0 \leftrightarrow \bot, \ldots, y\_m \leftrightarrow \top, y\_m \leftrightarrow \bot \\}$. Then $\psi$ is true iff there exists $\Gamma \subseteq \Delta$ such that $\Gamma \nvDash \bot$ and $\Gamma \vDash \varphi(\vec{x}, \vec{y})$.

Therefore the problem is $\Sigma^\mathsf{P}\_2$-hard. $\mathsf{DP} \subseteq \Delta^\mathsf{P}\_2$, so unless $\mathsf{PH}$ collapses the problem is not in $\mathsf{DP}$.

---
Tags: complexity-theory, satisfiability, propositional-logic
---


# Question
Title: How to sort $N$ fractions from finite set
> We have $10^5$ fractions: $\frac{p}{2^q}$ such that $0 \leq p,q \leq 10$.
> Find (fast) algorithm which sorts them.

I ask you to look at my proposition and tell me your ideas. $\frac{p}{q}$ is represented as the ordered pair $(p, q)$.

On input we have an array `a`.

**My idea:**

```
for i = 1 to n
do t[i] = a[i].first * 2^(10)
countsort (t)
bring results from t to a (remember about / 2^10)

```

**II Idea:**

```
for i = 1 to n do
   t[i] = a[i].first * 2^(10)
{ now we have only integer numbers }
sort t by counting (as bucket use bits)
for i = 1 to n do
   a[i] = t/2^10

```

In this way we have O(n + log (10 * 1024)n) = O(14n).
What about this solution ?

# Answer
You can sort all $11^2$ possible fractions, and create a table mapping $p/2^q$ to its position in this ordering, and another table going the other way. Then you can use counting sort to handle $N$ fractions in time $O(11^2 + N)$. (Here the underlying constant is universal, not depending on the size of the domain.)
> 2 votes

---
Tags: algorithms, sorting
---


# Question
Title: Merging of two convex polygon chains in O(log n)
Assume I have a polygon chain implementation which is backed by a key-value store which stores the position of a point inside the chain as key and the point itself as value. So a polygon chain of the points $p\_1\rightarrow p\_2\rightarrow p\_3$ is stored as $\\{0\Rightarrow p\_1,1\Rightarrow p\_2,2\Rightarrow p\_3\\}$. The key-value store is implemented with a data structure which allows the operations split and join in $O(\log n)$ time.

I want to join the chain $P = p\_1\rightarrow p\_2\rightarrow p\_3$ and the chain $Q = q\_1-\>q\_2-\>q\_3$ to a chain $p\_1\rightarrow p\_2\rightarrow p\_3\rightarrow q\_1\rightarrow q\_2\rightarrow q\_3$.

Is there a way to join two polygon chains in logarithmic time without updating the keys? If I do a simple join, I get a problem with duplicated keys, so the keys of $Q$ have to be updated before the join, but this destroys my logarithmic time approach as I need linear time for updating the keys.

Am I wrong here already?

If not, is there a way to keep the logarithmic time?

# Answer
You are asking for a data structure for sequences (aka vectors or arrays) that permits efficient concatenation. I suggest using any standard binary tree data structure, e.g., AVL tree, red-black tree, splay tree, treap, etc. They support $O(\lg n)$ time concatenation and $O(\lg n)$ time lookups. The differences between them come down to details related to implementation complexity and constant-factor differences in running time.

With these algorithms, the keys are not stored explicitly. Instead, they are implicit. To lookup key $i$, you search for the $i$th leaf from the left, but the key $i$ is never stored anywhere. Thus, when concatenating two trees, there is no need to renumber the keys. You can find the $i$th leaf in $O(\lg n)$ time: augment the data structure so that each node keeps a count of the number of leafs underneath it; then it's clear how to traverse the tree during a lookup (whether to go left or right at each node is an easy decision, given the information stored in each node).
> 3 votes

---
Tags: data-structures, time-complexity, computational-geometry
---


# Question
Title: Research regarding algorithm generation/discovery/heuristics
Say I have a specification of preconditions and postconditions for a function. Is there a field of computer science that studies the automated generation of functions that satisfy those specifications?

For example: Preconditions:

* I is a list
* Q is a binary relation specifying a total order on the elements in I

Postcondition:

* O is a list
* There exists a bimap B (and its complement B') such that
    + O\[B\[j\]\] = I\[j\], and
    + O\[j\] = I\[B'\[j\]\],
    + for every j, 0 \<= j \< n,
* For every x, 0 \< x \< n, Q(O\[x - 1\], O\[x\]) is true.

The set of functions that satisfy this (I hope unambiguous) specification are the sorting algorithms. So, how do we get a computer to take this specification, and give us a sorting algorithm?

# Answer
The phrase to look for is "program synthesis". There's lots of literature in the programming literature on this topic; I suggest using Google Scholar to search through the literature and find relevant publications.

These days one hot approach is using "program sketching". In program sketching, the programmer specifies a template for the code: partial code, with some holes left blank. The tool then automatically tries to fill in those holes in a way that is consistent with the preconditions/postconditions, or is consistent with some provided test cases. There's lot of literature on this topic. For an introduction to this line of work, I'll suggest the following tutorial:

The Sketching Approach to Program Synthesis. Armando Solar-Lezama. Tutorial at PLDI 2012.
> 2 votes

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


# Question
Title: How can an approximation ratio be less than 1?
A question in my algorithms text-book requires that we,

> Describe an efficient $(1 - \frac{1}{k})$ -approximation algorithm for this problem.

It is my understanding that $(1 - \frac{1}{k})$ being $p(n)$ is the approximation ratio and that an approximate solution differs from an optimal solution by a factor of $p(n)$. In that case, if $p(n)\< 1$ wouldn't the approximation be better than optimal?

How can the approximation ratio be less than $1$?

# Answer
> 4 votes
For maximization problems, if the optimal solution is $O^\*$ and the worst possible approximate solution is $O$, then the standard way is to consider $O^\*/O$ as the approximation ratio. But in some text books, the ratio $O/O^\*$ is considered for both minimization and maximization problems and it causes the ratio to be smaller than 1.

You may refer to Approximation Algorithm for more details.

---
Tags: algorithms, terminology, approximation
---


# Question
Title: Merge two series of sorted number, one much longer than the other
This is the problem:

> Merge two sorted series of numbers. Their lengths are $n$ and $m$, respectively, but $n \gg m$. Your algoritm should take $O(m \log(n/m))$ comparisons.

I have come up with this algorithm:

```
1. Choose n/m "special" elements among n elements.
2. for i = 1 to m do
    2.1 Using binary search find block (between two special elements)
        where m_i should be inserted - time O(log(n/m))

    2.2 Using binary search in found block, find exact position for $m_i$. -
       O(log m)

```

Step 2.1 takes time $O(\log(n/m)$ and step 2.2 time $O(\log m)$, so I get in total a runtime in $O(m (\log n/m + \log m))$. How do I get rid of the $O(\log m)$ term?

Here's a sketch of the algorithm:

As you can see I have a problem - O(log m). How to eleminate it ?

# Answer
> 3 votes
What exactly does $n \gg m$ mean for your professor?

If it means $m \in o(n)$, then you *are* allowed $O(\log m)$ time for step 2.2. Note that $\log(n/m) = \log n - \log m$. If $m \in o(n)$, the target runtime bound simplifies to $O(m \log n)$; a summand $m \log m$ is dominated by this.

If $m \in \Theta(n)$ is allowed -- arguably, $m = n \cdot 10^{-10}$ would fulfill "a lot smaller" -- you can have that $\log n/m \in O(1)$ and the runtime bound is $O(m)$. It's quite clearly impossible to perform this task in time $O(m)$, so I think we can safely ignore this case for the purpose of this exercise.

But here is something more for you to think about.

In step 1, you need to specify "special"; if you don't pick the elements according to your sketch, the rest won't work out. So we *have* to select the elements $i(n/m)$. In order to do this in $o(n)$ time and perform binary search efficiently, we need the series to be stored as *arrays*.

We can not copy all values to a new array in the required time. We can not insert values into an array, either. So how is this to work at all?

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


title: Finding common edges of two graphs

text:
# Question
Title: Finding common edges of two graphs
Is there any algorithm that finds the common edges and vertices between two graphs? Its not a common subgraph problem though, the edges which are common between the two graphs may not be connected to each other, may be far apart. How to find all the common edges in the graph? Like finding the common subgraphs between two graphs such that none of the subgraphs are connected to each other. Like these two graphs, the black and the blue part are the uncommon part...

# Answer
This appears to be the maximum subgraph isomorphism problem: given graphs $G,H$, you want to find the largest pairs of subgraphs $G',H'$ that are isomorphic (where $G'$ is a subgraph of $G$ and $H'$ is a subgraph of $H'$ and $G'$ is isomorphic to $H'$). Then the edges of $G',H'$ are common to both $G$ and $H$. Apparently, this problem has been applied in chemistry, which might be of interest to you given the diagram you showed.

In the comments you asked about the case $G$ and $H$ both have two common subgraphs which are not connected to each other. The maximum subgraph isomorphism solution will automatically find those. Nothing requires $G'$ or $H'$ to be connected. Thus, in your case, the optimal solution will have $G'$ consist of two disconnected components, and $H'$ consisting of the same two components. So, this problem already does what you want.

This problem is NP-hard for general graphs, so the general expectation is that there's not likely to be any efficient algorithm that can handle large, general graphs. However, you have two aspects that offer room for hope. First, it appears that your graphs are relatively small, so there might algorithms that are acceptable for graphs that are about the size of the examples in your diagram: even exponential-time algorithms might be practical. Second, and more importantly, it looks like you aren't dealing with arbitrary graphs. As Tom van der Zanden accurately explains:

> The graphs shown in the example are both trees and they appear to be models of molecules. While of course molecules (like benzene) can have cycles, depending on what molecules the OP is interested in the problem may not be NP-hard.

So, I suggest you search the research literature to see if there's been work done on the maximum subgraph isomorphism problem for trees. There might be algorithms that have been described in the algorithms literature that you could use.
> 1 votes

---
Tags: graphs
---


# Question
Title: Minimal size of a context-free grammar which defines $L_n=\{a^k\mid 1\le k\le n\}$
I am looking for the minimal size of a context-free grammar which defines the finite language $$L\_n=\\{a^k\mid 1\le k\le n\\}.$$ The size of a grammar is defined as the total length of all right-hand sides of the rules.
For example a grammar with $$S\to A\_1A\_1\\A\_1\to A\_2A\_2\\A\_2\to A\_3A\_3\\A\_3\to A\_4A\_4\\A\_4\to aa$$ has size $5\cdot 2=10$.
It is well-known that the minimal context-free grammar which defines the language only accepting the word $a^k$ has size $\Theta(\log k)$ (see the example above for the construction of the word $a^{32}$). Now, I am interested in the size of a grammar constructing all strings $a^k$ ($1\le k\le n$) for a given $n$. By the information above it is easy to create a grammar for $L\_n$ of size $$\Theta(n+\sum\_{k=1}^{n}\log k)=\Theta(\log n!)=\Theta(n\log n)$$ since we can create all words by a grammar of size $\Theta(\log k)$ and connect those grammars with a start rule of size $n$ (one symbol for each word). But since the final grammar is allowed to share nonterminals this construction is clearly not optimal. Maybe the smallest grammar has asymptotically the same size, but i don't know. Any help?

# Answer
> 6 votes
There is a grammar of size $O(\log n)$ using repeated squaring.

Let's start with the simpler case $n = 2^m$: $$ \begin{align\*} &S \to a B\_0 B\_1 \dots B\_{m-1} \\ &B\_i \to A\_i | \epsilon && (0 \leq i \leq m-1) \\ &A\_i \to A\_{i-1}A\_{i-1} && (1 \leq i \leq m-1) \\ &A\_0 \to a \end{align\*} $$ Here $A\_i \to a^{2^i}$ and $B\_i \to a^{2^i}|\epsilon$.

More generally, suppose $n-1 = 2^{d\_0} + 2^{d\_1} + \cdots + 2^{d\_\ell}$, where $d\_0 \> d\_1 \> \cdots \> d\_\ell$. The corresponding grammar is: $$ \begin{align\*} &S \to a B\_{d\_0} | a C\_0 B\_{d\_1} | a C\_1 B\_{d\_2} | \cdots | a C\_{\ell-1} B\_{d\_\ell} | aC\_\ell \\ &C\_j \to C\_{j-1} A\_{d\_j} && (1 \leq j \leq \ell) \\ &C\_0 \to A\_{d\_0} \\ &B\_i \to B\_{i-1} A\_{i-1} | B\_{i-1} && (1 \leq i \leq d\_0) \\ &B\_0 \to \epsilon \\ &A\_i \to A\_{i-1}A\_{i-1} && (1 \leq i \leq d\_0) \\ &A\_0 \to a \end{align\*} $$ Here $A\_i \to a^{2^i}$, $B\_i \to \\{a^k : 0 \leq k \< 2^i\\}$ and $C\_j \to a^{2^{d\_0} + \cdots + 2^{d\_j}}$.

As an extra property, both grammars are unambiguous.

# Answer
> 3 votes
This is a solution using repeated squaring, developed independently of that of Yuval Filmus. My purpose was to get as small a size as possible, not just low complexity. The resulting grammar is ambiguous, unlike that of Yuval Filmus.

The size obtained is bound by: $3\lfloor\log\_2 (n-1)\rfloor+4$
This is about as low as one can get given that the squaring alone will require about $2\log\_2 (n-1)+2$ size in optimal situations, when $n-1=2^p$

We define: $L\_n=\\{a^k\mid 1\leq k\leq n\\}$
$H\_n=\\{a^k\mid 0\leq k\leq n\\}$

Note that $L\_n=aH\_{n-1}$ and $H\_n=L\_n\cup\\{\epsilon\\}$

We can define recursively the rules

$A\_p\to A\_{p-1}A\_{p-1}$

with a base case $A\_0\to a \mid \epsilon $

Recall that a non-terminal can be read as the set of strings that derive from it. The advantage of squaring a set $A\_k$ that contains $\epsilon$ is that $A\_k$ is contained in the square $A\_kA\_k$ : $A\_k\subseteq A\_kA\_k$

Taking the first $p+1$ such rules with $A\_p$ as initial non-terminal symbol, we have a grammar that generates $H\_{2^p}$ for any $p\geq 0} with a very small size.

That makes size $2$ (or is $\epsilon$ with size 0 ?) for the base rule and size $2$ for the other rules, thus $2(p+1)$ for the grammar size for $H\_{2^p}$

We see that using $\epsilon$ is convenient, but it is not supposed to be in the final language, so we take one terminal $a$ aside, to be concatenated in the end.

Instead of considering $L\_n$, we consider $H\_{n-1}$, since $L\_n=aH\_{n-1}$

Now, to get a grammar for $H\_{n-1}$ we consider the decomposition of $n-1$ into a sum of powers of two. For that one uses the binary representation of $m=n-1$ as:

$$m=n-1=\sum\_{i=0}^{i=q}m\_i2^i \text{ where } q=\lfloor\log\_2 (n-1)\rfloor$$

Then you take in your grammar all the $q+1$ rules defining $A\_i$ for $i\in\[0,q\]$, with a total size of $2(q+1)$

Then you add a last rule

$S\to A\_{i\_1}\ldots A\_{i\_k}\ldots A\_{q}$ where the indices $i\_k$ are all the indices such that $m\_{i\_k}=1$, the last one being of course $q$. The length of the right-hand side is at most $q+1$.

This addition of this last rule with $S$ as initial symbol defines a grammar for $H\_{n-1}$.

To get a grammar for $L\_n$, we must concatenate it to $a$, which can easily be achieved by adding $a$ to the right-hand side of the last rule which becomes:

$S\to aA\_{i\_1}\ldots A\_{i\_k}\ldots A\_{q}$

This rule has a size which is $1$ more than the previous version, thus is upperbounded by $q+2$.

With the $q+1$ rules with total size $2(q+1)$ defining the $A\_i$, we have a total of $q+2$ rules with a size upperbound of $3q+4$.

Taking $S$ as initial symbol, this grammar generates the language $L\_n$, with $q=\lfloor\log\_2 (n-1)\rfloor$.

Note: one thing here was inspired by Yuval Filmus: it was to use a single very long rule of size at most $q+2$ for the last one, rather than a CNF equivalent which nearly doubles the size to $2q+2$. Without this change the multiplicative constant would be $4$ instead of $3$.

# Answer
> 0 votes
I'm not sure if I understand correctly, but is there just a trivial $O(N)$ way to do this?

$A = a$

$S\_0 = ""$ (I mean the empty rule, or $a^0$.)

$S\_1 = S\_0A$

$S\_2 = S\_1A$

$S\_3 = S\_2A$

$\cdots$

Please tell me if I misunderstood your problem (and feel free to ignore or delete my answer in that case).

# Answer
> 0 votes
There is a simple grammar of size $\Theta(n)$:

$\qquad\displaystyle\begin{align\*} A\_1 &\to a \\ A\_i &\to aA\_{i-1} \mid a, \quad 2 \leq i \leq n \end{align\*}$

with starting symbol $A\_n$. The right-hand sides sum up to $3(n-1) + 1 = 3n - 3$.

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


# Question
Title: Bias of first values produced by a family of RNGs
Suppose I'm doing a large number of **pseudo-random but deterministic** experiments, where each experiment requires generating several random numbers.

I'm approaching this by having each experiment use a **random number generator seeded with a random-looking seed** \- e.g. hash of the index of the experiment. This is especially convenient for parallelizing my experiments.

I'm wondering if this is a sound way to get good randomness. In particular, this article points out at the end that **the first value** returned by e.g. Java's random generator (LCG) **is highly biased** even if you vary the seed.

How can I avoid this bias? Is it sufficient to throw away one or two numbers, as that article suggests? Is there any research on this topic? (I wasn't able to find the right keywords)

Would, e.g., Mersenne Twister behave better?

# Answer
> 2 votes
Yes. This general approach (use a hash of the index as seed to your prng) is a sound way to perform repeatable but pseudorandom experiments.

The most critical factor is to choose the pseudo-random number generator wisely, so that its statistical properties are sufficient for the kind of simulations you are doing. Some pseudo-random number generators are especially awful: for instance, on some platforms `rand()` is terrible (its least significant bit alternates between 0 and 1), and Excel's `RAND()` has been criticized in the statistical literature. So, choose wisely. But this issue is more a matter of choosing a suitable pseudo-random generator, which is something you need to do anyway.

It's important to include the hashing step. If you don't do that, then you're feeding closely related seeds into the pseudo-random generators. For some pseudo-random generators, bad things might happen: you might get closely related outputs. For instance, that's exactly what the article you mentioned is warning about, when you use Java's `Math.random()`. Using a good hash function will fix this, because now the seeds to the pseudo-random generator will look unrelated (each bit will be different with probability about 1/2, etc.).

In particular, if you're concerned about this risk, one extremely effective solution is to use a strong cryptographic hash function (e.g., SHA256) as your hash. This ensures that the resulting seeds will look entirely unrelated. After all, any detectable relationship in the resulting seeds would likely count as a "break" of the cryptographic hash function, and would be huge news. So, heuristically, if you use a cryptographic hash function to hash the index and use its output as the seed, you're likely on safe ground. This can be formalized using the random oracle model, but I'll spare you the technical details -- you can read more about that sort of analysis in the cryptographic literature if you really want, but in the interests of space, I'll spare you all the mathematics.

I expect that using a good hash will be more effective/reliable than throwing away the first few numbers, and more effective than trying to choose a different pseudo-random number generator. Those alternatives are a crapshoot: they might work, but they might not. In contrast, there is sound science behind the "hash the index and use the result as a seed" approach.

---
Tags: randomness, pseudo-random-generators
---


# Question
Title: Simplest Turing-complete ruleset for Markov algorithm
Is there an example of a *particular ruleset* for a Markov algorithm that is Turing-complete? If so, what is the simplest example of such a ruleset?

# Answer
Rule 110 is universal, and can be expressed as a Markov algorithm.

In particular, Rule 110 corresponds to the Markov system with alphabet $\\{0,1,\verb!^!,|,\\$ \\}$ and a pair of bits for each element in the automaton. The pair of bits records the current status of that element (empty or filled) and the previous status. Elements are updated by doing a left-to-right scan; the marker $|$ keeps track of where we are in the scan, $\verb!^!$ indicates the start of the string, and $\\$$ indicates the end of the string. We obtain the following $2^6 + 2^2 + 2^6 = 132$ rewriting rules:

* $uv|wxyz \to uvxt|yz$ where $t = \text{Rule110}(u,x,z)$,
* $|uv\\$ \to vv\\$ $
* $\verb!^! uvwxyz \to \verb!^! vv|wxyz$

where $u,v,w,x,y,z$ are meta-variables that range over $\\{0,1\\}$. In other words, the first bullet item corresponds to $2^6$ rewriting rules: $00|0000 \to 0000|00$, $00|0001 \to 0001|01$, etc.; the second bullet item corresponds to $4$ rewriting rules, corresponding to all possible ways to assign $0$ or $1$ to $u$ and $v$; and the third bullet item corresponds to $2^6$ more rewriting rules.

What's going on with this crazy re-writing system? It's actually not as ridiculous as it looks. For a cellular automaton with $n$ elements, we start with a string of length $2n+2$ of the form $\verb!^! 0x\_1 0x\_2 0x\_3 \dots 0x\_n \\$ $, where each $x\_i$ is $0$ or $1$ according to whether that element is empty or filled.

The interpretation of the pair of symbols $uv$ is that the current status of the element is given by $v$, and the previous status is given by $u$. We scan over the elements from left to right, updating the status of each element. The marker $|$ indicates where we are in the scan right now. Notice that we need to keep track of both the previous and current state of each element, which is why I use a pair of bits for each element rather than one bit per element.

The first bullet item takes care of the left-to-right scan. The second bullet item makes sure that the scan terminates, and removes the $|$ marker. The third bullet item ensures that if there is no $|$, then we re-start the scan starting at the left.

---

You can also play a similar trick with any Turing machine, and thus emulate a universal Turing machine with a Markov algorithm.

Suppose we have a Turing machine with tape alphabet $\Gamma$ and finite state space $Q$. Then the Markov system has alphabet $\Sigma = \Gamma \cup Q \cup \\{\text{\<}\\}$. The idea is that the string $t\_1 t\_2 \cdots t\_i \text{\<} q t\_{i+1} \cdots t\_n$ corresponds to a configuration of the Turing machine that has $t\_1 t\_2 \cdots t\_i t\_{i+1} \cdots t\_n$ on its tape, has state $q$ in its finite-state control, and where the head is positioned over $t\_i$ in the tape. The marker $\text{\<}$ indicates the current position of the head.

Then it's easy to write a finite set of rewriting rules that correspond to the operation of the Turing machine. In particular, the behavior of the Turing machine depends only on the symbol under the head and the state of the finite control. Thus, we'll get a set of rewriting rules of the form $t \text{\<} q u \to t' u \text{\<} q'$ (for transitions where the head moves right) and $s t \text{\<} q \to s \text{\<} q' t'$ (for transitions where the head moves left). Since the finite-state control has only finitely many state transitions, we'll need only finitely many rewriting rules in the Markov algorithm.

Finally, we can apply this to your favorite universal Turing machine. The smaller the universal Turing machine, the simpler the resulting Markov algorithm will be.
> 8 votes

---
Tags: computability, turing-machines, computation-models, turing-completeness, term-rewriting
---


title: Register Transfer Activity

text:
# Question
Title: Register Transfer Activity
In a simple architecture(not considering parallel architecture) how exactly this can be performed in a single clock cycle: P:R1 \<- R2, R2 \<-R1 where R1 and R2 are registers and P is a control variable.

I do not exactly understand when does this microoperation gets completed on the rising edge of the beginning of the cycle or just before clock transition.

# Answer
One way this can be performed in a single cycle is through register renaming. If the processor supports register renaming, no data needs to be moved: one simply renames which register is called R1 and which one is called R2.

If the processor doesn't support register renaming, the other option is that the data can simply be swapped between the two registers.
> 1 votes

---
Tags: computer-architecture, parallel-computing, shift-register
---


# Question
Title: Karloff's algorithm applied to sparse graphs
I'm given a graph $G = (V, E)$ with $|V| = N$ and $|E| = m \ge N^{1+c}$ edges for some constant $c \>0$. $G$ is called a $c$-dense graph.

Karloff \[1, p.6\] has given a map-reduce algorithm called "Finding an MST of a Dense Graph Using Map-Reduce" which finds an MST of $G$ by randomly partitioning the vertices into $k$ different equally sized sets $V\_i$ and then finding a MST for $V\_i \cup V\_j$ for all $i,j$.

will it provide correct output if we will apply this algorithm to a sparse graph, i.e., a graph for which $|E| \< N$, instead of a $c$-dense graph? Will it work correctly? If it will, why is the paper making the assumption here $|E| = m \ge N^{1+c}$, if their algorithm works for sparse graphs too?

---

1. A Model of Computation for MapReduce. Howard Karloff, Siddharth Suri, Sergei Vassilvitskii. ACM-SIAM Symposium on Discrete Algorithms, 2010.

# Answer
I would suggest reading Theorem 5.1 and Lemma 5.1 on the same page in the paper. They answer both your questions.

The proof of Theorem 5.1 in the paper does not use the density of $G$. It will therefore also work for sparse graphs.

You are asking about the motivation behind the assumption of $G$ being dense. In this context the assumption is that a dense graph does not fit into the memory of a single machine. Lemma 5.1 and the conclusions after it show that the input size to the reducers is small enough to fit into the memory.
> 2 votes

---
Tags: algorithms, search-algorithms, parallel-computing, spanning-trees, mapreduce
---


# Question
Title: Is there a computation that takes the same amount of time to run on any computer?
I'm looking for research that has been done towards finding types of computations that take the same exact amount of time to run, regardless the amount of computing power one has.

I've been thinking about also computations that might require external factors - for example being able to hash tomorrow's newspaper is a type of computation that takes the same amount of time.

However I'm looking for something that can run on computers with certainty (tomorrow's newspaper might not come out at all).

Any thoughts?

**EDIT** what I'm looking for is not something that runs in *exactly* the same amount of time. For example, a computation that counts to 10 would be ok, as it would roughly take 10 seconds on every computer. What I need is a way to arrive at a certain result only after having waited 10 seconds. Imagine that I have a password protected key, and the only way to see the password was to wait 10 seconds.

# Answer
> 1 votes
I suspect you might be interested in timed-release cryptography, where some secret is released to the world only after a specific point in time, and having a faster computer doesn't help you learn the secret any quicker.

If you search on timed-release cryptography, time-lock cryptography, and time capsule cryptography on Cryptography.SE, you'll find a bunch of information on the topic. For instance:

I suspect it might also be possible to achieve what you want by using the Bitcoin block-chain, transactions with a user script, and some cleverness.

# Answer
> 0 votes
I am not certain of what you are after, so I am giving you below pointers to various related areas of research that may answer your quesry. To be true, they fit your examples more closely than the tags you have chosen. But then, I do not see how your examples and your tags can fit together. So I am waiting for your reaction (after all, it is related to reactive programming) to understand better, and possibly suggest changing the tags.

It seems that what you are after is event driven programming. There is a wikipedia page on event driven programming and another one on event-driven architecture. The flow of execution is controled by events, which may be external events. All you expect from the computer is to be fast enough so as to be ready for the next event. So this type of programming is alsi linked to real-time programming, when events external to the computer are taken into consideration.

It is unclear whether you are concerned with external events, since you give the newspaper example, and then say that it might be a bad example, because you cannot be sure of external events. But these techniques can use all kinds of events, including internal interrupts, mouse clicks, clock driven signals, etc.

It is also linked to reactive systems, synchronous programming languages and dataflow programming.

There has been considerable research on this topic, and a large number of programming languages and formalisms were developed. Among others, you may look for programming languages such as Esterel, Lustre, or Signal.

I guess these references should give you enough starting point, if my answer meets what you are looking for.

---
Tags: computability, time-complexity
---


# Question
Title: Can you increase data rate by increasing number of bits?
My question is on data rate and baud rate.

data rate = baud rate * n

The question is, can you keep on increasing the data rate by increasing baud rate or number of bits.

I believe it can be increased by increasing the baud rate but what about the latter part?

# Answer
> 2 votes
Theoretically you can, but in reality you can not. The problem in raising the number of bits one symbol represents is that you have to space the symbol levels closer and closer together. Therefore even small amounts of random noise lead to misinterpreted symbols. A first attempt at calculating the maximum data rate is *Nyquist's formula*:

maximum data rate \[bit/s\] = $2H\cdot log\_{2}(V)$

Where $H$ is the bandwidth in $Hz$ and $V$ is the number of symbol values.

This formula indicates that unlimited data rate can be achieved when enough symbol levels are used, but, as we have already seen, that is not possible because of random noise. *Shannon's formula* takes that into account:

maximum data rate \[bit/s\] = $H\cdot log\_{2}(1 + S/N)$

Where $S$ is the signal strength and $N$ is the noise level.

---
Tags: data-structures
---


# Question
Title: What is the best complexity of finding a minimum in a matrix?
Given a matrix $\mathsf{a}$ of size $K\times N$, what is the best complexity of finding the minimum value?

Here is a pseudo code:

```
function find_min(a)
    imin, jmin = 1, 1
    for k = 1 to K
        for n = 1 to N
            if a[k, n] < a[imin, jmin]
                imin = k
                jmin = n
    return imin, jmin

```

The above function needs $O(K\cdot N)$ operations. However, I think we can reduce the complexity to $O(\lg K\cdot N)$ using a heap. Am I right? Can we do better than a heap? If so, what is the best complexity of such a function?

# Answer
> 5 votes
You can't find the minimum without reading all values, due to an adversary argument. The adversary pretends that the matrix is the zero matrix, that is, whenever you ask for some value in the matrix, it answers zero. If you haven't queried some entry, then the algorithm cannot distinguish between two possibilities: that the matrix is entirely zero, or that it is zero apart from the entry, which has value –1. The minimum in both cases is different, so the algorithm can't be correct.

---
Tags: algorithms, time-complexity, asymptotics
---


title: Pairs distance to ordering?

text:
# Question
Title: Pairs distance to ordering?
Thanks to anon for contributing this wording:

Every permutation $\pi:\\{1,\cdots,n\\}\to\\{1,\cdots,n\\}$ induces an $n\times n$ array $A(\pi)$ of the absolute differences, whose $ij$ entry is $|\pi(i)-\pi(j)|$. I want an algorithm which takes as input a (possibly only-partially-filled in) $n\times n$ array $D$, and outputs a permutation $\pi$ that maximizes the number of entries common to both $D$ and $A(\pi)$.

---

---

Wording I can follow:

I'm looking for an algorythm that yields a permutation $P$ of the given set $L$.

Where $P$ minimally violates a given set of constraints $C$.

Where constraints $C$ each specify an absolute offsets for the indexes of a pair of elements of $L$.

For example:

Where:

$L = \\{w, x, y, z\\}\\C = \\{\\{w, x, 2\\}, \\{y, w, 1\\}, \\{y, z, 2\\}\\}$

Then a valid answer would be $P = \\{w, y, x, z\\}$

Because, as described in $C$:

$w$ and $x$ are now $2$ "index positions" apart.

$y$ and $w$ are neigbours at $1$ apart.

$y$ and $z$ also being $2$ apart.

---

The data for $C$ may contain contradictions, therefore the result may be an estimate.

Q: What is a good way to solve this?

---

---

I wondered about an approach where $L$ values are placed randomly along a 1D line. $C$ describing the end connections and rest length of connecting springs. Simulated until at rest. Could this produce a reasonably accurate result?

What other aproaches are recommended for finding $P$ from $L$ and $C$?

# Answer
Apparently, we're given a collection of equations of the form

$$|x\_i - x\_j| = c\_{i,j},$$

where the $c\_{i,j}$ are given and $x\_1,\dots,x\_n$ are the unknowns to solve for. We want to look for a valid solution that satisfies all of the equations, and where the values of $x\_1,\dots,x\_n$ are a permutation of $1,2,\dots,n$.

The kind of algorithm to use will probably depend upon how many equations we're given and the structure of the corresponding graph. However, here is a simple case to start with, to give you some intuition:

Suppose that we are given a complete set of $n(n-1)/2$ equations: i.e., for all $i,j$, we are given $c\_{i,j}$. Then there is a polynomial-time algorithm to recover the $x\_i$'s. Basically, we'll leave $x\_1$ as a variable, and we'll try to express every other $x\_i$ in terms of $x\_1$. Define $\delta\_i$ so that $x\_i = x\_1 + \delta\_i$. Here's how the algorithm works:

1. Guess $\delta\_2$. Note that it is either $c\_{1,2}$ or $-c\_{1,2}$, so there are only two possibilities.
2. Guess $\delta\_3$. Again, there are only two possibilities: $c\_{1,3}$ or $-c\_{1,3}$.
3. Check that $|\delta\_2-\delta\_3| = c\_{2,3}$; if this doesn't hold, discard your current guess. (This will eliminate $1/2$ of the wrong guesses.)
4. Guess $\delta\_4$; there are only two possibilities.
5. Check that $|\delta\_2-\delta\_4| = c\_{2,4}$ and $|\delta\_3-\delta\_4|=c\_{3,4}$; if either doesn't hold, discard the current guess. (This will eliminate at least $1/2$ of the wrong guesses.)
6. Continue in this way, alternately guessing $\delta\_i$ and then checking the equations $|\delta\_j-\delta\_i|=c\_{j,i}$ hold for all $j=2,3,\dots,i-1$.

What's the running time? The expected running time to list all possible combinations for $\delta\_2,\dots,\delta\_n$ is $O(n)$. In particular, at each step, we double the number of combinations we need to consider (since there are two possibilities for the guess), but then we halve the number of combinations we need to consider (since $1/2$ of the wrong guesses can be discarded by virtue of the fact that they violate at least one of the known equations). Thus the expected number of guesses that remain at the $i$th step is a constant independent of $i$, which implies the running time bound above.

Finally, once you have a combination $\delta\_2,\dots,\delta\_n$, you can test whether it leads to a viable solution by checking all possible values of $x\_1$, inferring the implied values of $x\_2,\dots,x\_n$ (using the known values for $\delta\_2,\dots,\delta\_n$), and then checking whether they are a permutation of $1,2,\dots,n$. Each combination takes $O(n^2)$ time to check, so the overall running time of the algorithm is $O(n^2)$. This can probably be reduced further, but it's enough to make it already a polynomial-time algorithm.

Now what if we're not given all of the equations? Then we can apply a similar strategy, but the running time will depend upon the number of equations we're given and the structure of the graph they correspond to. There's also some degree of freedom in the order that you guess $\delta\_i$ values; it's not clear what the optimal strategy is, but probably it will involve looking for small highly-connected regions of the graph and starting with them first. The best approach might depend upon the specific distribution on problem instances that arises in your practical setting.
> 1 votes

---
Tags: algorithms, data-structures, partial-order
---


# Question
Title: Please explain a greedy algorithm in a naive manner
I am a beginner in the topic of algorithms. I have a query about Greedy Algorithms.

From what I understand, if there is a function and we are supposed to find its maxima/minima, if we find the local maxima/minima, we become 'greedy' and declare that as the global maxima/minima.

I suppose that is wrong?

# Answer
Greedy algorithms are those in which we construct the optimum solution piece by piece.

After identifying a part of the optimum solution (this is intuitive by nature and problem dependent), try to add or subtract elements from it to see whether it still remains optimum.

I guess you should study Matroid Theory and Linear Programming Duality if you are very interested in the mathematics of greedy algorithms.

Try going through these problems on your own and practicing other problems related to these: Maximal Independent Set in a Tree, Disjoint Set (Interval Scheduling), Interval partitioning, 0-1 Knapsack and Fractional Knapsack.

What you are asking is about the Hill Climbing problem specifically. The Wikipedia page provides enough discussion about it, but if you are a newcomer in the world of algorithms I suggest you start out with the above problems first.
> 1 votes

# Answer
In simple words, an algorithm is normally considered "greedy" if

1. it builds solutions step by step without backtracking
2. in each step it picks what's best in the current state.

To learn more about it, check this pdf out.

---

The animated gif above illustrates a greedy algorithm for finding the path that adds up to the biggest number.

It does so by choosing the node with the biggest number at each step. (Since the actual solution is the 7-3-99 path, the greedy approach fails to bring forth the correct path.)

This is why greedy algorithm may not always yield the right solution to a certain instance of a problem.

The gif animation was created by Swfung8 on Wikipedia for the article on Greedy Algorithm.
> 7 votes

# Answer
Your understanding is completely wrong: what you describe is known as hill climbing or gradient descent in the continuous case, and local search in the discrete case.

The best way to understand what greedy algorithms are is by an example. Consider the following optimization problem:

> Given a set $S$ of positive integers and a number $n$, choose a subset of $S$ of size $n$ with the maximal sum.

For example, if $S = \\{3,5,2\\}$ and $n = 2$, then the optimal solution is $\\{3,5\\}$. Here is the greedy algorithm for this problem:

> Repeat $n$ times: take the maximal element remaining in $S$.

Continuing our earlier example, the algorithm first takes $5$, and then $3$.

At every step in time, a greedy algorithm chooses the "best" element, according to some strategy. In this case, the best element is the largest one. While in this case the greedy algorithm produces the optimum, in many other cases the result is not optimal but "typically" good, often with provable guarantees. Also, in some cases there might be several reasonable interpretations of "best" to choose among.

If you're interested further in greedy algorithms, I recommend taking up a textbook or consulting online resources.
> 5 votes

# Answer
Greedy algorithms can be used whenever you can think of the solution to the problem being reached in steps. The strategy is then just to choose the next step that looks best in some (usually simple, "local") sense, without ever undoing a step and trying an alternative path.

The classical example is finding a minimal cost spanning tree of a graph. One strategy is to start with just the vertices, and succesively add the cheapest arc that doesn't create a cycle (to get a tree in the end). That this *does* give a minimal spanning tree is nice. But even if the solution isn't optimal, with a "reasonable" definition of steps and selection of alternative step you should get some solution that isn't *too* bad.
> 5 votes

# Answer
Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. Example: "Coin changing problem".

**Brute force approach**: Enumerate all possible representations selecting the one with the least number of coins. Using Fibonnaci coins: { 1, 2, 3, 5 } and amount $8.

```
8 = 5 + 3
8 = 5 + 2 + 1
8 = 5 + 1 + 1 + 1
8 = 3 + 3 + 2
8 = 3 + 3 + 1 + 1
8 = 3 + 2 + 2 + 1
8 = 3 + 2 + 1 + 1 + 1
8 = 3 + 1 + 1 + 1 + 1 + 1
8 = 2 + 2 + 2 + 2
8 = 2 + 2 + 2 + 1 + 1
8 = 2 + 2 + 1 + 1 + 1 + 1
8 = 2 + 1 + 1 + 1 + 1 + 1 + 1
8 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

```

There are 13 representations overall; 8 = 5 + 3 is optimal.

**Greedy algorithm** The cashier's algorithm return the largest coin smaller than or equal to the amount and then proceed in analogous fashion for the remaining amount.

Using Fibonnaci coins: { 1, 2, 3, 5 } and amount $8.

The greedy algorithm make the best local choice and then blindly plough ahead. This technique is only applicable if the problem exhibits optimal substructure: an optimal solution contains within it optimal sub-solutions to sub-problems. Not all optimizations problems can be solved with greedy algorithms.

A recursive implementation in SML

```
(* change : int -> int list *)
func change n =
     if 5 <= n then 5 :: change(n - 5)
else if 3 <= n then 3 :: change(n - 3)
else if 2 <= n then 2 :: change(n - 2)
else if 1 <= n then 1 :: change(n - 1)
else []

```
> 0 votes

---
Tags: algorithms, terminology, greedy-algorithms
---


title: Model paths by regular languages

text:
# Question
Title: Model paths by regular languages
I want use DFA to describe a sequence of movements in a 2D-space (language will be the path accepted by automaton in a particular case).

That is a typical modeling problem: how can I encode a sequence of 2D movements in a DFA?

Infact, walking through DFA or NFA seems a process analogous to walk through point of a maps.

A naives example could be: State like point in space coordinate (x,y); and Transitions with an alphabet of "up, down, etc". That's direct approach is impracticable beacuse "the number of locations is infinite or simply too many". I'm looking for a better and more efficient encoding.

Are there any study about using regular languages for coding path, or movements?

# Answer
If the number of locations (e.g. points or regions) are finite, naively, you can say that these locations are my states and you can directly use a DFA with an alphabet containing UP, DOWN. But you already said it's impracticable for your case.

Then, let's look into where the number of locations is infinite or simply too many. Basically, in this case, you need to recognize that the sequences UP-DOWN, UP-UP-DOWN-DOWN, UP-UP-UP-DOWN-DOWN-DOWN ... etc. are equivalent because equal number of UP and DOWNs gets you back to the starting point. This is the classical example of non-regular languages. Therefore I suggest you looking into other automata such as counter machines if they are sufficient to capture your intentions.
> 4 votes

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


# Question
Title: Which all nodes will qualify as an ancestor?
I was going through the fundamentals of tree structure and the definition for *ancestor* is as follows:

> A node u is an ancestor of v if there is a path from u to v.

Consider the node `11`. Is node `2` (not the root, the other one on the left) an ancestor of node `11`? It is strictly not a grandparent of `11`, however, there does exist a path between these nodes. This is confusing to me, because this would also imply that the sibling nodes (`5`) of `11` would qualify as an ancestor.

# Answer
> 4 votes
The root-2 is an ancestor of 11 (it's the great-grandparent) but you're asking about the 2 on the left, which is not an ancestor. There is no directed path from that node to 11 since the left-2 has no outgoing edges. Paths must respect the direction of the edges. Siblings are not ancestors for the same reason.

(Sometimes, we want to talk about a path that ignores the edge directions. These are usually referred to as something like "paths in the underlying undirected graph".)

# Answer
> 1 votes
Consider the nodes in a tree as cities and the path connecting them as roads.
If the paths are directed, the roads are one way. On a undirected tree, the roads are two way.

In the sample you have provided, there is no road from the city 2 (which is not root) to 11. So 2 is not at all related to 11 and not a parent.
But the cities 2, 7 and 6 have roads to 11. The city 6 is the most closer one (parent), 7 is bit farther (grand parent) and 2 (root node) is most farthest (great grand parent).
This distance means that, you have traverse (travel) more from root node to 11, than other existing paths.

Keep tracking of parents of a node will be helpful, especially in inserting a new node before that node and deleting the node.

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


# Question
Title: Does Thompson's algorithm produce optimal NFAs?
I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of states?

For instance, consider this example. I have the regular expression $(a|b)$. According to this website, Thompson's algorithm converts it to the following NFA:

```
   o--->o
  /ε  a  \ε
>o        O
  \ε  b  /ε
   o--->o

```

However, the following NFA is smaller and seems like it would also be equivalent:

```
   o
 a/ \ε
>o   O
 b\ /ε
   o

```

Why doesn't Thompson's algorithm output the latter NFA? What did I miss here? Is that Thompson's construction algorithm not optimized at all?

# Answer
> 5 votes
I had this same doubt when I was studying the Thompson's construction. As I see I am not the only one, I will try to solve the mystery.

Consider the regular expression: $$(a|b)|(c|d)$$

With Thompson's construction we generate first:

and then

Now let's use the noxwox's construction that you suggested. First we have:

And finally:

Can you see the difference? I had a first suspicion watching these two results. Then I reviewed the Thompson's constructions and I noticed something interesting. We can see the NFAs as directed graphs and the Thompson's construction guarantees a graph whose nodes have at most two successors.

So here starts my conclusion: Generating the data structure to store a NFA obtained by Thompson's construction is very easy because it is a set of nodes with two pointers each. If we use nowox's construction we don't know a priori the numbers of successors of each node and we have to change dynamically the amount of memory reserved for each node or be inefficient in the memory management. From this point of view the Thompson's construction algorithm guarantees a graph that is easy and fast to generate in a computer and I think that the additional computational cost of having more states than the NFA generated by nowox's construction is overshadowed by the backtracking mechanic of the NFAs.

# Answer
> 11 votes
Minimizing NFAs is known to be PSPACE-hard: Meyer and Stockmeyer showed that given an NFA, it is PSPACE-hard to find the *size* of the minimal equivalent NFA, and Jiang and Ravikumar showed that given a DFA, finding the *size* of the minimal equivalent NFA is PSPACE-hard. Later some hardness of approximation results were proved, showing that it is even hard to *approximate* the size of the minimal equivalent NFA. See these lecture notes by Artem Kaznatcheev for more details.

Since a regular expression can be converted to an NFA of comparable size using Thompson's algorithm, these hardness results show that we can't expect any efficient algorithm to convert an regular expression to a minimal-size NFA.

# Answer
> 5 votes
Thompson's algorithm has no chance to output an optimal NFA, simply because a regular language can be given by several different regular expressions. Just try the regular expression $(a + b)^\*(a + b)^\*(a + b)^\*$ on the tool given in reference. You will end up with a 22-state NFA, very far from the optimal 1-state NFA.

# Answer
> 2 votes
The minimal NFA for an regular expression `(a|b)` as you described would be below:

```
    a, b
>o ------> O

```

Basically this automaton can be produced by Antimirov's construction based on partial derivatives of regular expressions. For this construction you need a procedure to determine the *equivalence* of two regular expressions, which is known to be hard (Sorry no magic here!). However, if you relax the absolute minimality guarantee, you can use a procedure determining *similarity* of two regexs, which is efficient, so you can construct a near-minimal NFA.

A starting point for derivatives of regular expressions can be found here: http://www.mpi-sws.org/~turon/re-deriv.pdf

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


# Question
Title: Dynamic Programming Travel Planning Problem
You want to visit n cities: $0 → 1 → 2 → · · · → n$.

For traveling between city $i$ and $i + 1$ $(0 ≤ i \< n) $ you need to choose between two modes of transportation: train or plane. You are starting at the train station of city $0$ and want to end up at the airport of city $n$.

The cost of transferring between the train station and the airport of city $i$, either direction, is $b\_i$. The cost of traveling from city $i$ to city $i+1$ via train is $t\_i$ and by plane $p\_i$.

You need to use to use the plane and train exactly $n/2$ times. Assume that $n$ is divisible by $2$. Design an $O(n^2)$ dynamic programming algorithm that finds the cost of an optimal solution to the travel planning problem.

What I have so far is what I think is a solution to the problem without considering the $n/2$ constraint.

$Cost(x, i, y) = \begin{cases} \begin{cases}t\_i & y=0\\ p\_i + b\_i & i-y=0 \end{cases} & i=1 \\ min\begin{cases} \begin{cases} min\begin{cases}p\_i + Cost(P, i-1,y-1) \\ p\_i + b\_i + Cost(T, i-1,y-1) \end{cases} & y \> 0 \\ inf & y=0 \end{cases} \\ \begin{cases} min\begin{cases} t\_i + Cost(T, i-1,y)\\ t\_i + b\_i + Cost(P, i-1,y) \end{cases} & i-y \> 0\\ inf & i-y = 0\end{cases} \end{cases} & 1 \< i \< 0 \\ min\begin{cases}p\_i + Cost(P, i-1,y-1) \\ t\_i + b\_i + Cost(T, i-1,y) \end{cases} & i=n \end{cases}$

The values of $x$ correspond to different scenarios for which station at $i$ you are located at.

$x = P$

$x = T$

The value of $y$ is the number of plane rides and $i-y$ is the number of train rides $0 \le y \le i$

To get the optimal cost with $n/2$ plane rides you would call $Cost(x,i,\frac{x}{2})$

# Answer
Hint: For each $0 \leq i \leq n$ and $0 \leq t \leq i$, calculate the optimal route between city $0$ and city $i$ using $t$ plane rides and $i-t$ train rides.
> 2 votes

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


# Question
Title: How do I tell if a comparison network sorts?
I am presented with a comparison network. How can I determine if the comparison network is a sorting network? In the image below there is an example of a selection sort and insertion sort network. The intent is to have a comparison network and sort numeric values. If I test 2^n values in this case 2^8. This is a lot of work|non-efficient way to test it. I'm looking for a mathematical model/proof to verify this is a valid sorting network.

# Answer
> 11 votes
In general, verifying whether a particular comparison network is indeed a correct sorting network is a Co-NP complete problem. If you want to check by testing, then you need to try exponentially many tests.

In particular, there exist sorting networks that sort all but a single value correctly, so you can't hope to test whether the network is correct or not simply by feeding it a few inputs.

One standard method is to test whether it correctly sorts all $2^n$ inputs that are composed solely of zeros and ones. If it does, then it turns out that it will sort all inputs (even ones that aren't limited to zeros and ones). However, this requires exponentially many tests. Moreover, the number of tests cannot be reduced significantly: for zero-one inputs, it is possible to prove that at least $2^n-n-1$ tests are needed, in order to verify that the sorting network is correct.

Alternatively, one can use tests where the inputs are permutations of $1,2,\dots,n$. This reduces the number of tests needed somewhat, but you still need exponentially many tests. In particular, $C(n, \lfloor n/2 \rfloor)-1$ tests are necessary and sufficient.

For proofs of these facts, see the following papers:

On the Computational Complexity of Optimal Sorting Network Verification. Ian Parberry. Parle'91 Parallel Architectures and Languages Europe, 1991.

Bounds on the size of test sets for sorting and related networks. Moon Jung Chung and B. Ravikumar. Discrete Mathematics, vol 81, pp.1--9, April 1990.

# Answer
> 7 votes
Quoting your question:

> I'm looking for a mathematical model/proof to verify **this** is a valid sorting network.

While D.W.'s (excellent) answer deals with the general case, I will consider your specific example. A network of this form with $n$ inputs can be shown to be a sorting network by induction: (see image for illustration)

1. $n=1$ input is always sorted;
2. Assume that a network of size $n-1$ of this form is a sorting network, and consider a network of size $n$.
    1. The left-most "diagonal" will always correctly bring the largest element to the $n$-th position (in your case, $b\_8$);
    2. You are left with a smaller, similar network with the remaining $n-1$ elements;
    3. This smaller network will sort all the remaining elements by the inductive hypothesis.

# Answer
> 6 votes
When you look on a general sorting network, you might have no idea how to proof that it sorts every sequence of values (having the right length for the sorting network) correctly. But I've learned about this nice trick, how to simplify the task:

# The 0-1-principle

When a sorting network sorts every sequence (with the right length) consisting only of "0" and "1" correctly, then it sort any sequence (with the right length) correctly. Of course "0" and "1" are placeholders for any distinct elements in the domain of the sorting network.

So you can construct a proof like this:

1. Take two distinct elements from the domain of the sorting network and call them "0" and "1", so that "0" \< "1"
2. Construct all binary strings with the exact length of the sorting network
3. In these strings substitute the 0-bit and the 1-bit with "0" and "1"
4. Apply these strings to the sorting network
5. Each string must be sorted to something like 000..01...1

# Testing $2^n$ values

For an exhaustive test of a sorting network of length $n$ you usually would have to test all input combinations. But with the *0-1-principle* you can bring this down to $2^n$ tests (testing all binary strings of length $n$).

# Can we do it cheaper?

Unfortunately we probably can't get much cheaper than exhaustive testing, at least not when using a Turing machine to construct the proofs. Of course when you look an a specific sorting network, you might have a creative idea how to make a simple proof. But in general an algorithm for constructing such proofs is very likely as complex as testing all binary strings. The reason for this is that proofing sorting network is related to the NP complete complexity class as outlined in the other answers.

"Much cheaper" in this context means "polynomial time". It might be possible to find an algorithm that can do it "slightly" faster than exponential time but still needs more than polynomial time. See the comments for an example: Running in $2^{\sqrt n}$ steps is (slightly) faster than exponential time but still (much) slower than polynomial time.

# Prospect / Outlook

## Is your brain a Turing machine

A philosophical consequence is: When you believe that you can find a creative proof for the correctness of each sorting network, then you are also believing that you brain is very likely not a Turing machine.

## Parallel sorting

The "0-1 principle" is also used to proof the correctness of parallel sorting algorithms. I have a (hopefully) nice presentation about this on Github.

## Correcting the sorting network

If one of the strings is incorrectly sorted (so you have proven the sorting network wrong), you can use this to construct a sorting network without that bug. Just add an additional comparison on the position of the "1-0 border" in the wrong result string.

---
Tags: sorting
---


# Question
Title: Is the front-side bus multiplier the same as how many transfers it does per second?
### What I am doing:

I've been reading there about front-side busses (FSB) and their cycles per second (MHz) vs. bandwidth (Millions of Transactions per second or MT/s).

### What I've understood:

FSB's MHz is the actual speed it does *per cycle*, however, the speed *per second* depends on how many *cycles* it does per second

### What I need:

Can we by some way say that the CPU multiplier amount is the same *amount of cycles it does per second* that we can tell that if the *FSB is 800MHz* and the *multiplier is x4*, it's capable of transferring up to \*(800\*4)MT/s\*?

### Why I assumed that?

Because of Wikipedia telling me that:

> In computing, the clock multiplier (or CPU multiplier or bus/core ratio) measures the ratio of an internal CPU clock rate to the externally supplied clock. A CPU with a 10x multiplier will thus see 10 internal cycles (produced by PLL-based frequency multiplier circuitry) for every external clock cycle

# Answer
No. You're not cancelling your units correctly.

The wikipedia article is talking about something else. (The cycles/sec of the front-side bus vs. the cycles/sec of the processor.)

The Transfers (or Transactions) per second is given by:

$$ \frac{\mathrm{Transactions}}{\mathrm{cycle}} \times \frac{\mathrm{cycles}}{\mathrm{second}} = \frac{\mathrm{Transactions}}{\mathrm{second}}. $$

*MHz* is millions of cycles per second (cycles/second), not speed per cycle.

The calculation you do in your section "what I need." is correct: If the front-side bus is running at 800 million cycles/sec, and can do 4 transfers per cycle, then it can do 800M * 4 = 3200M transfers/second.
> 4 votes

---
Tags: computer-architecture
---


# Question
Title: Showing that the set of DTMs that run forever is not Turing-recognizable
The language A, that is all DTMS that run forever on input.

Would this not just be the HALT problem?

Therefore no reduction or proof is necessary, other then stating that?

ANSWER FOUND: I think i have it, if it was Turing Recognizable, then it would be possible to determine when HALT should reject and therefore HALT would be decidable. Since it is not-decidable, then A must be not Turing Recognizable.

# Answer
This is *not* the halting problem, the halting problem is the set of TMs that **do** halt, the language $A$ is the set of TMs that **don't** halt. It's the *complement* of the halting problem.

You also seem to be mistaken in that the halting problem is recognizable, it's just not decidable.
> 2 votes

---
Tags: computability, turing-machines, halting-problem, semi-decidability
---


# Question
Title: Could the Halting Problem be "resolved" by escaping to a higher-level description of computation?
I've recently heard an interesting analogy which states that Turing's proof of the undecidability of the halting problem is very similar to Russell's barber paradox.

So I got to wonder: mathematicians did eventually manage to make set theory consistent by transitioning from Cantor's naive formulation of the field to a more complex system of axioms (ZFC set theory), making important exclusions (restrictions) and additions along the way.

So would it perhaps be possible to try and come up with an abstract description of general computation that is more powerful and more expressive than Turing machines, and with which one could obtain either an existential proof or maybe even an algorithm for solving the halting problem for an arbitrary Turing-machine?

# Answer
You cannot really compare. Naive set theory had paradoxes that were eliminated by ZFC set theory. The theory has to be improved for consistency, as a basic assumption of scientific work is that consistency is achievable (else reasonning becomes a chancy business). I suppose mathematicians expected it had to be possible, and worked to resolve the issue.

There is no such situation with computation theory and the halting problem. There is no paradox, no inconsistency. It just so happens that there is no Turing machine that can solve the TM halting problem. It is simply a theorem, not a paradox.

So it may be that some breakthrough in our understanding of the universe will lead to computation models beyond what we can envision now. The only such event, in a very weak form, that remains within the TM realm, was possibly quantum computing. Other than this very weak example that touches complexity (how long does it take?) rather than computability (is it feasible?), I doubt anyone on this planet has a clue that computability beyond TM is to be expected.

Furthermore, the halting problem is a direct consequence of the fact that Turing machines are describable by a finite piece of text, a sequence of symbols. This is actually true of all our knowledge (as far as we know), and that is why speech and books are so important. This is true of all our techniques to describe proofs and computations.

So even if we were to find a way to extend the way we compute, say with the T+ machines. Either it would mean that we have found a way of expressing knowledge beyond writing finite document, in which case the whole thing falls out of my jurisdiction (I claim absolute incompetence) and probably anyone else's. Or it would still be expressible in finite documents, in which case it would have its own halting problem for T+ machines. And you would be asking the question again.

Actually that situation does exists in reverse. Some types of machines are weaker than Turing machines, such as Linear Bounded Automata (LBA). They are quite powerful though, but it can be shown exactly as it is done for TM that LBA cannot solve the halting problem for LBA. But TM can solve it for LBA.

Finally, you can imagine more powerful computational models by introducing oracle, that are devices that can give answers to specific problems, and can be called by a TM for answers, but unfortunately do not exists physically. Such oracle-extended TM is an exemple of the T+ machine I considered above. Some of them can solve the TM halting problem (abstractedly, not for real), but cannot solve their own Halting problem, even abstractedly.
> 16 votes

# Answer
Well, you can always consider a Turing machine equipped with an oracle for the ordinary Turing machine halting problem. That is, your new machine has a special tape, onto which it can write the description of an ordinary Turing machine and its input and ask if that machine halts on that input. In a single step, you get an answer, and you can use that to perform further computation. (It doesn't matter whether it's in a single step or not: it would be enough if it was guaranteed to be in some finite number of steps.)

However, there are two problems with this approach.

1. Turing machines equipped with such an oracle can't decide their own halting problem: Turing's proof of the undecidability of the ordinary halting problem can easily be modified to this new setting. In fact, there's an infinite hierarchy, known as the "Turing degrees", generated by giving the next level of the hierarchy an oracle for the halting problem of the previous one.
2. Nobody has ever suggested any way in which such an oracle could be physically implemented. It's all very well as a theoretical device but nobody has any clue how to build one.

Also, note that ZFC is, in a sense, weaker than naive set theory, not stronger. ZFC can't express Russell's paradox, whereas naive set theory can. As such, a better analogy would be to ask whether the halting problem is decidable for weaker models of computation than Turing machines. For example, the halting problem for deterministic finite automata (DFAs) is decidable, since DFAs are guaranteed to halt for every input.
> 18 votes

# Answer
# Warning: A philosophical / non-rigor answer

This might get a little bit "philosophical", but I think it fits the spirit of your question.

# A non-repeatable machine

A corner stone of the proof of the halting problem is that a Turing machine behaves like a function: For the same input it always gives the same output. If you remove this property, you don't have to deal with the "general" halting problem, in the sense that the machine can discover its own properties. But you also loose a lot of the desirable theoretical properties of such a machine.

# Removing properties

It's a little bit like going from set theory to category theory: You loose some of the "paradoxons" by losing the limitations. But the result is much more difficult to handle.

In this case it means: You would have no idea if the machine presents you the "correct" result. As soon as you can always decide which result is correct, you have to deal with some kind of "halting problem" by applying the machine to itself and construct a contradiction. So such a machine would probably not be very useful.
> 2 votes

# Answer
The Halting Problem was not formulated to express the limitations of Turing Machines, but rather to express a limitation of *all* logic systems which can be expressed using a finite number of symbols. Once a logic system has the ability to express the solutions to problems of certain complexity, it will also have the ability to express problems it can't solve. Any extension of a logic system sufficient to express solutions to all of the problems it couldn't solve before will also include the ability to express new problems it can't solve.

Given any particular "Enhanced Turing Machine" specification, it would be possible to specify a "Super-Enhanced Turing Machine" which could examine a program for the ETM and report whether it would halt, but the SETM would only be able to analyze programs for the ETM--it wouldn't be able to analyze SETM programs. There's no way to define a machine that can analyze programs for itself and determine whether they halt because the act of adding new features would create new requirements for a self-analyzer, and there's no way to make the features "catch up" to the requirements.
> 2 votes

# Answer
Such machines have been envisioned, and are called super-Turing machines. Several major classes of super-turing machine are

* Real number machines (i.e. analog computers)
* Turing machines given infinite time
* Nondeterministic turing machine

Not all super-turing machines can solve the halting problem (Nondeterminnistic turing machines, in particular, cannot). However, the conceptual machines have been created, at least in thought experiments.
> 0 votes

---
Tags: computability, turing-machines, computation-models, halting-problem
---


# Question
Title: Showing NP-hardness by reducing from a search problem
I'm comfortable with showing NP-completeness of a decision problem: just take some problem that is known to be hard and reduce it to your new problem. This establishes NP-hardness of the new problem.

But we can also have NP-hard search problems. For example, it is claimed in the introduction of this paper, that finding a $k$-coloring of a $k$-colorable graph is NP-hard for $k \geq 3$. Let me call 3-COL-SEARCH the problem in which we are given a 3-colorable graph $G$, and have to output a valid 3-coloring for $G$.

For concreteness, suppose $X(G)$ is asking for the minimum number of operations to achieve something fancy for a graph $G=(V,E)$. We wish to show computing $X(G)$ is NP-hard. Technically, I should be able to do this by a reduction from 3-COL-SEARCH.

But what would we show in the reduction now? If this was a decision problem (3-COL) we are reducing from, perhaps we'd be showing "the graph $G$ is 3-colorable if and only if $X(H) \leq |V|$, where $H$ is some new graph we construct". But now I'm confused: would we show "we can find a 3-coloring for the 3-colorable graph $G$ if and only if $X(H) \leq |V|$"?

Is there perhaps some paper or resource that gives an example of such a reduction as well? I'd guess this is not so exotic.

# Answer
Basically, you pick any convenient decision problem known to be NP-complete and reduce from that problem to 3-COL-SEARCH. In other words, informally, you prove that if it was possible to solve 3-COL-SEARCH in polytime, then it'd also be possible to solve that other problem in polytime.

For your particular example, a very convenient choice of decision problem is 3-COLORABLE. It's known that 3-COLORABLE is NP-complete. Now you just need to reduce 3-COLORABLE to 3-COL-SEARCH. The reduction will be super-easy: take the hypothetical algorithm for 3-COL-SEARCH, run it on the graph, check whether it has output a valid 3-coloring or not, and if yes, output "Yes", otherwise output "No". This will be a valid solution to the decision problem 3-COLORABLE, if the hypothetical algorithm correctly solves 3-COL-SEARCH.

Usually you can do the same thing with other NP-hard problems: often there is a natural decision problem associated with it, so you prove that the decision problem is NP-complete and then find a reduction from the decision problem to your search problem.

---

The other thing that's going on in your example is that, the way you defined 3-COL-SEARCH, it's a promise problem. A promise problem is one where we have a promise that the input will be within some set -- and the algorithm is allowed to do anything it likes on other inputs. Promise problems can be a bit counter-intuitive, or at least harder to think about, from a complexity-theory perspective, so if you're able to frame your problem so it's not a promise problem, I think that will usually be cleaner.
> 2 votes

---
Tags: reductions, np-hard, search-problem
---


title: From context-free to context-sensitive

text:
# Question
Title: From context-free to context-sensitive
I have a context-free language $L(G)$. I'm reading in a book that $L(G') = L(G) - \\{{\epsilon}\\}$ is context-sensitive but I cannot find a proof or confirmation of this fact; moreover, in other texts the production $S\to\epsilon$ is allowed (as long $S$ isn't on the right hand side of any production) I'm quite confused.

The book is *Formal Models of Computation: The Ultimate Limits of Computing* by Arthur Charles Fleck and the passage in question says:

> Given two context free grammars $G\_1$ and $G\_2$ first determine if $\epsilon\in L(G\_1)$ and $\epsilon\in L(G\_2)$. If so, $L(G\_1)\cap L(G\_2) \neq \emptyset$, otherwise $L(G\_1) - \\{{\epsilon}\\}$ and $L(G\_2) - \\{{\epsilon}\\}$ are context-sensitive.

Maybe what the book says is that they are also context sensitive (since the set of context-free languages is properly contained in the set of the context-sensitive)?

# Answer
> 4 votes
Saying that CF grammars are properly contained in CS grammars is not quite correct, at least according to some authors (Hopcroft-Ullman 1979, page 223). Their reason is that the CS languages cannot contain the empty word $\epsilon$, at least according to a strict definition of what a CS grammar is: the right-hand side must be at least as long as the left-hand side. Other definitions of CS grammars, such as given in wikipedia, do allow the rule $S\to\epsilon$, provided $S$ never appears in a right-hand side. The purpose is to allow CS languages to contain the empty word, so that they define the same family of languages as the linear bounded automata (LBA). And it also makes CF languages a subset of CS languages.

Context-free (CF) languages can contain the empty word.

Thus, for an author belonging to the strict school (no $\epsilon$ in CS languages), only $\epsilon$-free CF languages are contained in the CS languages.

From what I read in your question, my understanding is that the authors of your book belong to the strict school. So they will not consider a CF language as CS, unless they first remove the empty word, which does not change their CF character as shown in the answer by D.W. that indicates how to obtain the CF grammar $G'$ from the CF grammar $G$.

Apparently the author is analyzing the intersection of two CF grammar, and wants to use the fact that (for him) $\epsilon$-free CF languages are contained in the CS languages. So he considers separately the case when the intersection contains $\epsilon$, and the case when it does not contains it. If it does no contain it, he can remove it from the two languages, and then consider them CS languages, for whatever he is doing.

That is my explanation of what you are reading. Of course, a larger piece of context would help ascertain that view. Or even better, the definition of CS language they give.

# Answer
> 2 votes
It's a straightforward to show that if $L\_1$ is context-free, then $L\_2 = L\_1 \setminus \\{\epsilon\\}$ is also context-free. Take any context-free grammar for $L\_1$, then find nullable variables (variables that can derive $\epsilon$). In particular, the following is a basic theorem that's useful:

Theorem. If $L$ is a context-free language, then $L \setminus \\{\epsilon\\}$ has a context-free grammar with no $\epsilon$-productions.

My claimed result follows immediately from the theorem. The proof of the theorem follows by building an algorithm to identify all nullable variables of the context-free grammar, then change them so they can no longer derive $\epsilon$ and fix up the rules. You can find the detailed proof in standard textbooks: it goes under the name of removing $\epsilon$-productions.

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


# Question
Title: Devising an Algorithm for Linear Combination with Column Restrictions
**Application:**

We intend to factor an integer $N$ using a variation of the rational sieve.

This involves constructing a congruence of squares modulo $N$ from a set of linear relations $$x - N = y$$ where $x$,$y$ are $B$-smooth. The standard method to obtain such relations is to traverse $f(x) = x - N$ using a highly-optimized Sieve of Eratosthenes for all primes $p \< B$ to reveal smooth values $y = f(x)$. This is essentially the same method used for the Quadratic Sieve (QS) and the modern General Number Field Sieve (GNFS).

The problem with this method lies in the rapidly vanishing probability of smoothness for large values of $x$ and/or $y$. This requires us to sieve vast ranges of useless integers to obtain a few smooth ones.

Alternatively, there is a way to directly generate smooth relations. Represent $N$ as a sum of $n$ $B$-smooth integers in $m$ different ways, where $n \approx m$. This can be done efficiently using the package-merge algorithm for the coin collector's problem. Then use a specialized linear algebra algorithm to produce an integer linear combination of these sums that has all but two of its addend coefficients equal to zero, thus forming the equation $x + y = zN$. Rearrange this to $x - zN = -y$. Then if the coefficients used to produce $x$,$y$ are on the order of $B$, this provides a smooth relation for our congruence matrix with good probability.

If this can be done efficiently, it would *seem* to admit a fast method of factoring integers.

\begin{align\*} \hline \end{align\*}

**Definitions:**

* Let $\rho(n)$ denote the set of unique prime factors of an integer $n$.

**Inputs:**

* An arbitrarily large integer $N$ to be factored.
* A smoothness bound $B$ and corresponding factor base $P = \\{-1\\} \cup \\{p \in \mathbb{N} \mid p \leq B \text{, $p$ is prime}\\}$.
* An arbitrary finite set of integers $K \subset \mathbb{Z}$ with $k\ \bot\ \ell\ \ \forall\ k,\ell \in K$.
* A vector $s \in \mathbb{Z}^{n}$ with entries comprising $n$ unique addends $s\_{j}$, $\rho(s\_{j}) \subset P$, $0 \< j \leq n$.
* A set of $m$ row vectors $M = \\{v\_{1}, v\_{2}, \dots, v\_{m} \in \mathbb{Z}^{n+1} \mid \rho(v\_{ij}) \subset P,\ \forall i\leq m, j\leq n\\}$, forming an $m \times (n + 1)$ matrix of integer coefficients $v\_{ij}$ initialized such that $$\sum\_{j=1}^{n} v\_{ij}s\_{j} = v\_{i,n+1}N$$ for each row vector $v\_{i}$. In practice, $m \approx n$.

For example, suppose $N = 14$ and $s = \[2^{0}, 2^{1}, 2^{2}, 2^{3}\]$; then we could have a row $v\_{0} = \[0, 1, 1, 1, 1\]$ corresponding to the binary representation of $1N$. In practice, $s$ could comprise any variety of $B$-smooth integers.

**Desired Output:**

* A row vector $w \in \mathbb{Z}^{n+1}$ that is an integer linear combination of the vectors in $M$ that has all of its first $n$ entries equal to zero except for two, and has its last entry $w\_{n+1}$ either 1, prime, or coprime to every element $k \in K$.

In practice, we insert $w\_{n+1}$ into $K$ after each execution of the algorithm for a given $N$.

\begin{align\*} \hline \end{align\*}

**Example Input:**

$$N = 35$$ $$B = 13$$ $$K = \varnothing$$ $$s = \[3^2, 2^5, 2^4, 2^3, 2^2, 2^1, 2^0\]$$

\begin{align\*} M = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & -1 & -1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & -1 & 1 & 1 \\ -4 & 3 & -1 & -1 & 0 & 0 & -1 & 1 \\ 4 & 0 & 0 & 0 & 0 & 0 & -1 & 1 \\ \end{bmatrix} \end{align\*}

\begin{align\*} \hline \end{align\*}

**Example output 1:** $w = \[2, 6, 0, 0, 0, 0, 0, 6\] \implies (2)3^2 + (6)2^5 = (6)35$

**Example output 2:** $w = \[-13, 0, 0, 0, 0, 6, 0, -3\] \implies (-13)3^2 + (6)2^1 = (-3)35$

**Example output 3:** $w = \[0, 4, 0, 0, 0, 6, 0, 4\] \implies (4)2^5 + (6)2^1 = (4)35$

\begin{align\*} \hline \end{align\*}

**Question:**

Given inputs $N$, $B$, $K$, $s$, and $M$, what is the maximum number of arithmetic steps required to find an output or to determine that none exists? Essentially, I am looking for an efficient algorithm or heuristic and its worst-case time complexity. The "specialized linear algebra algorithm" I mention in the introduction does not yet exist; it's what I'm trying to find.

Ultimately, we want to obtain the set of all unique outputs mutually respecting the constraint on $w\_{n+1}$.

# Answer
> 1 votes
Your problem can be solved in about $O(n^3 \log(nB))$ time on average, using the following procedure:

* Guess the two indices of the two non-zero entries. In other words, guess indices $y,z$ such that $w\_i =0$ for all $i \notin \\{y,z\\}$.
* Find an integer linear combination of the vectors in $M$ that are zero in all of the first $n$ positions except for $y,z$. Note that this can be done using Gaussian elimination: each position that must be zero corresponds to a linear equation, and we have $n-2$ linear equations in $m$ unknowns. If a non-trivial solution exists, Gaussian elimination can find it. When $m \ge n-2$, this is expected to have a non-trivial solution with high probability, under a heuristic assumption that the matrix entries are random. More specifically, I recommend that you throw away the last column of the matrix and work with integers modulo $N$. Then, you're looking for an integer linear combination of vectors that are non-zero modulo $N$ in all of the first $n$ positions except for $y,z$. Gaussian elimination can be done modulo $N$, and any solution modulo $N$ can be extended to one over the integers (by adjusting the last column, you can add or subtract an appropriate multiple of $N$ so that everything works out over the integers).
* Check that the resulting $w\_{n+1}$ is either prime or co-prime to everything in $K$.

What's the running time of this procedure? The Gaussian elimination step takes $O(n^3)$ time. With constant probability, there exists a non-trivial solution to the set of linear equations. Finally, a random integer is prime with probability at least $1/\log(nB)$ (by the prime number theorem, and using that the last entry of $w\_{n+1}$ is at most $nB$), so heuristically, we expect the last step to succeed with probability about $1/\log(nB)$. Therefore, with $O(\log(nB))$ iterations, we expect to find a solution that satisfies all of the conditions. Each iteration takes $O(n^3)$ time, so the total running time is $O(n^3 \log(nB))$.

I don't know whether this can be improved.

P.S. Why is $w\_{n+1}$ at most $nB$? Well, from the integer linear combination modulo $N$, we get $w\_1,\dots,w\_n$ that satisfy

$$\sum\_{j=1}^n w\_j s\_j = 0 \pmod N.$$

By letting $w\_{n+1} = -(\sum\_{j=1}^n w\_j s\_j)/N$, we thereby find a vector $w$ that satisfies

$$\sum\_{j=1}^n w\_j s\_j = w\_{n+1} N,$$

which is a solution of the desired form. Now how large can $w\_{n+1}$ be? Well, bounding each term in the sum and using that $w\_1,\dots,w\_n$ were reduced modulo $N$, we find

$$|\sum\_{j=1}^n w\_j s\_j| \le \sum\_{j=1}^n |w\_j s\_j| \le \sum\_{j=1}^n NB = nNB.$$

It follows that $|w\_{n+1}| \le nB$.

---
Tags: algorithms, time-complexity, number-theory, linear-algebra, factoring
---


title: Inferring Social Ties

text:
# Question
Title: Inferring Social Ties
In some papers, they proposed a model in which the joint posterior probability was modeled as\[1\]: $$ P(Y|\textbf{X},G) = \frac{P(\textbf{X},G|Y)P(Y)}{P(X,G)} \propto P(\textbf{X}|Y) \cdot P(Y|G)$$ where $\textbf{X}$ is attribute vectors set and $Y$ is the labels of all the edges in the network.

I know the meaning of the first equal sign which can be applied with *Bayesian Theorem*. But I feel confused about the third term, $P(\textbf{X}|Y) \cdot P(Y|G)$. How this term comes out?

\[1\]: J. Tang, T. Lou, and J. Kleinberg, “Inferring social ties across heterogenous networks,” in Proceedings of the fifth ACM international conference on Web search and data mining - WSDM ’12, 2012, p. 743.

# Answer
This model seems a little confusing due to the role of $G$ and I didn't find their definition of $P(Y|G)$ very sound.

You can consider it the following way:

$$P(Y|\textbf{X},G) \propto P(\textbf{X}|Y) \cdot P(G|Y) \cdot P(Y) = P(\textbf{X}|Y) \cdot \[P(G|Y) \cdot P(Y)\] \propto P(\textbf{X}|Y) \cdot P(Y|G)$$
> 0 votes

---
Tags: machine-learning
---


# Question
Title: Two Disjoint Turing-recognizable languages do not have a decidable language
Let languages $A, B$ be defined as $$\begin{align} A &= \\{\langle M\rangle\mid M(\langle M\rangle)=reject\\}\\ B &= \\{\langle M\rangle\mid M(\langle M\rangle)=accept\\} \end{align}$$ In other words, $A$ is the set of descriptions of TMs which reject their own descriptions and $B$ is defined similarly. The languages $A$ and $B$ are disjoint, and are both Turing-recognizable. Prove that there does not exist a decidable language $C \subseteq \Sigma^\*$ such that $A \subseteq C$ and $B \subseteq \overline{C}$, the complement.

# Answer
Suppose there was a decidable language, $C$, of TM descriptions such that $A\subseteq C$ and $B\subseteq \overline{C}$. Since $C$ was assumed to be decidable, there is a decider TM, $D\_C$, for it. Then either $\langle\\,D\_C\\,\rangle\in C$ or $\langle\\,D\_C\\,\rangle\in \overline{C}$. Let's run $D\_C$ on its own description:

* If $\langle\\,D\_C\\,\rangle\in C$, then $D\_C$ will accept $\langle\\,D\_C\\,\rangle$ and hence $\langle\\,D\_C\\,\rangle\in B\subseteq \overline{C}$, a contradiction.
* In a similar way, if $\langle\\,D\_C\\,\rangle\in \overline{C}$, we again reach a contradiction, that $\langle\\,D\_C\\,\rangle\in A\subseteq C$.

Since we reach a contradiction in either case, we can conclude that there is no such $C$, as desired. This non-existence, by the way, has a name: we say that $A$ and $B$ are recursively inseparable.
> 3 votes

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


title: NP Complete Subset GCD Proof

text:
# Question
Title: NP Complete Subset GCD Proof
$SubsetGCD$ is described by the following:

instance: A set of positive integers $S$ and an integer $k$
question: does there exist a subset $S'$ of $S$ of size $k$ such that $GCD(S') = GCD(S)$

Prove that $SubsetGCD$ is np complete.

The hint for the problem is to reduce $VertexCover$ to $SubsetGCD$

I know what I'm supposed to do. Given an instance of $VertexCover$ convert it into the form of $SubsetGCD$ such that there exists a vertex cover of size $k$ if and only if there exists a subset $S'$ of size $k$ such that $GCD(S') = GCD(S)$

Since the vertex cover and subset are of size $k$ I feel like the vertices should correspond to the members of $S$ so that the vertex cover itself is the subset $S'$

Therefore, the important part is how to define the edges connecting the verticies. I've tried edges if the GCD of the endpoints is GCD(S), if the GCD of the endpoints is not GCD(S), edges connected to a vertex must be have GCD(S) and can't have a GCD greater than GCD(S) for all immediate neighbours etc.

I've also tried reducing Clique to the Subset GCD problem with no luck. Any help would really be appreciated!

# Answer
Hint: Associate each edge $e$ with a prime $p\_e$, and each vertex $v$ with a number $n\_v \in S$. Choose $n\_v$ so that the GCD of $\\{n\_v : v \in A\\}$ encodes the set of edges covered by the vertices in $A$.

If you get stuck, try first showing that SubsetLCM is NP-complete. (LCM is Least Common Multiple.)
> 1 votes

---
Tags: np-complete, reductions, decision-problem, np
---


title: Shaefer's Dichotomy Theorem

text:
# Question
Title: Shaefer's Dichotomy Theorem
Could you please resolve a confusion with Schaefer's theorem for me? Namely, why does it not imply many problems in P are NP-complete? For example, primality testing surely cannot be reduced to one of the six classes in the theorem, so why does that not imply it's NP-complete?

# Answer
> 2 votes
Primality testing is not of the form $\text{SAT}(S)$ for a finite set $S$ of finite-arity relations over the Boolean domain. Thus, it's not covered by Shaefer's theorem, and Shaefer's theorem says nothing about the hardness of primality testing. See this answer: https://cs.stackexchange.com/a/43831/755.

See also Why does Schaefer's theorem not prove that P=NP? for a more detailed explanation.

---
Tags: complexity-theory, np-complete, satisfiability
---