title: Min cost max flow in bipartite run time

text:
# Question
Title: Min cost max flow in bipartite run time
I have a bipartite graph with $|E|=O(|V|^2)$, a super-source and a super-sink. I am looking for the min-cost max-flow (the max-flow of all possible max-flows that has the minimum cost).

For the sake of my question, denote $n=|E|$.

Are there algorithms that will run in $O(n^2)$, or even $O(n\log(n))$, or for that matter anything less than $O(n^3)$? In my case, $n$ is ~100,000, so $O(n^3)$ is impractical for me.

'Extra' questions (should these go under a separate question?):

1. Do any of these supper multi-graphs (I have 2 edges from my super-source node to each of the "blue" nodes in my bipartite graph, and 2 edges from each of the "red" nodes to my super-sink node)?
2. Are there efficient implementations of such algorithms (that run in less than $O(n^3)$, and support multi-graphs) in C++, C, or Python?
3. If the answer is 'no', what are popular approximation algorithms and their associated run times?

# Answer
Assuming your edges have unit capacity, but non-unit costs, you can reduce this to a maximum-weight bipartite matching, that is, the assignment problem. For this, just make a copy of each vertex. The assignment problem can be solved in $O(n^{1.5})$ time.
> 2 votes

# Answer
I'm most familiar with the Cost-Scaling Algorithm by Goldberg. I'm pretty sure it behaves like $O( n^2 \log n \log U)$, where $\log U$ is (essentially) the number of bits in the representation of the edge costs.

This link provides a nice review.
> 0 votes

# Answer
You can solve this in $\mathcal{O}(n\log{}n)$

Edit: I've retracted this claim for now, until further notice.

Given amounts of supply and demand, and a cost matrix from supply to demand:

1. Sort the edges by cost
2. For each edge in order of cost:
    * Calculate the minimum of the remaining amount in the supply and demand nodes
    * Subtract from the supply and demand nodes
    * Assign it to the edge

The complexity is dominated by sorting the edges.

You can probably adapt this to almost any language, but javascript seems like the most commonly available vm for now, so here's an implementation:

const compare = (a, b) => a[0] - b[0];
const amount_to_node = amount => [amount];

/* Single commodity, maximum flow, minimum cost optimizer, msand@seaber.io */
function optimize(supplies, demands, costs) {
  const supply_nodes = supplies.map(amount_to_node);
  const demand_nodes = demands.map(amount_to_node);

  const num_supplies = supplies.length;
  const num_demands = demands.length;
  const edges = [];

  for (let from = 0; from < num_supplies; from++) {
    const f = costs[from];
    const supply = supply_nodes[from];
    for (let to = 0; to < num_demands; to++) {
      const demand = demand_nodes[to];
      const cost = f[to];
      edges.push([
        cost,
        supply,
        demand,
        from,
        to,
      ]);
    }
  }

  edges.sort(compare); // Most expensive part of the function

  const num_edges = edges.length; // = num_supplies * num_demands;
  for (let e = 0; e < num_edges; e++) {
    const edge = edges[e];
    const supply = edge[1];
    const demand = edge[2];
    const amount = Math.min(supply[0], demand[0]);
    supply[0] -= amount;
    demand[0] -= amount;
    edge[5] = amount;
  }

  return edges;
}

const supplies = [12, 23];
const demands = [7, 17];
const costs = [[3, 6], [5, 7]];
console.log(optimize(supplies, demands, costs));
```

> 0 votes

---
Tags: graphs, optimization
---


# Question
Title: Shortest Path in Layerwise Complete Graph
Consider a directed $k$ partite graph $G$ with a source node $s$ and a sink node $t$. Each vertex in the graph is labeled with a positive integer value. Both the source and sink are labeled with $0$. There are directed edges from the $s$ to all vertices in partition $0$. There are directed edges from all vertices in partition $k$,, ie, the last partition to $t$. $G$ is layerwise complete that is, in addition to the above, there is a directed edge from all vertices in partition $i$ to all vertices in partition $i+1$, ie, adjacent partitions form complete bipartite graphs. An edge between any two nodes is labeled with a negative integer value or with $0$.

There could also be directed edges between nodes in partitions $m$ and $n$ where $1 \leq m, n \leq k, m \lt n, n \neq (m+1)$, and labeled with a negative value. This is depicted in the following figure where there are two edges between partition $1$ and partition $3$ indicated with dashed lines. Non adjacent partitions do not form complete bipartite graphs. They only comprise edges as indicated. In the figure, the edge labels are shown with negative values, wherever edges are not labeled with values, they are labeled with $0$ by default.

Consider all paths from $s$ to $t$. The length of this path would be calculated as the addition of all the integer labels of the nodes on this path and the addition of the edge labels if there is an edge between any pair of vertices in this path. For example, the length of the path taking the first vertex from each partition would thus be $0 + 50 + 30 + 50 + 0 -8$, where the negative value of $-8$ corresponds to the edge between nodes labeled with $50$ and $50$. Similarly, if we took the first vertex from partition $1$, the last vertex from partition $2$ and the first vertex from partition $3$, the length of this path would be $0 + 50 + 40 + 50 + 0 - 6$, where the $-6$ value corresponds to the edge between the first vertex in partition $1$ and partition $2$. The $0$ values correspond to the source and sink vertices.

Find the shortest path from $s$ to $t$ taking exactly one vertex from each $k$-partition where the length would be calculated as described.

**Attempt :** I converted the node weights for a pair $(a, b)$ into edge weights where each edge weight would be the sum of the node value of $b$ deducting the edge cost between $a$ and $b$. This works for edges between successive partitions and produces the correct shortest path in cases where the edges are only between such. However, if I use the same approach for edges between different non successive layers it doesn't work. What would be an algorithm to find the shortest path and the transformation?

# Answer
> 2 votes
Your problem is NP-hard, by reduction from clique. Given a graph $G=(V,E)$ and a number $k$, we construct a graph with $k$ internal layers, each containing $|V|$ vertices. All vertices in a layer are connected to all vertices in the following layer. The weight of an edge is $0$ if the corresponding edge is not in $G$, and $-1$ otherwise. We also add shortcut edges corresponding to edges in $G$ with weight $-1$. The graph $G$ has a $k$-clique iff the shortest path in the new graph has length $-k(k-1)/2$.

---
Tags: algorithms, data-structures, search-algorithms, shortest-path
---


title: why is $O(n^2)$ equal to $n^{1.5}$?

text:
# Question
Title: why is $O(n^2)$ equal to $n^{1.5}$?
I am learning this MIT course, which gives this formula

$$O(n^2) = n^{1.5}$$

is there a table to calculate this? like $O(n^{1.5})$, $O(n^{5})$ ?

what x takes would have O(x) give $c \cdot n$ where c is a constant,

# Answer
The formula is wrong. The notation $f = O(g)$ is asymmetric, and has the meaning $f \in O(g)$. For more, check our reference question on Landau notation. Other relevant reference questions are this one and this one.
> 3 votes

---
Tags: algorithms, big-o-notation
---


title: Translation of diagnosis problem to SAT

text:
# Question
Title: Translation of diagnosis problem to SAT
I have the following diagnosis problem:
h(A): z1 = not(in1)
h(D): z2 = not(in2)
h(B): z3 = z1 or z2
h(C): out1 = not(z3)
h(E): out2 = not(z3)

This is an image of the system:

I have an observation where I know that:
in1 = false
in2 = false
out1 = true
out2 = true

I want to check if {B} is a diagnosis of the system, meaning that I assume that A,D,C,E are valid, while I don't assume the same about B.
This I want to turn into a sat problem. So first I map each variable in my system to a literal:
in1: 1
in2: 2
z1 (the output of A): 3
z2 (the output of D): 4
z3 (the output of B): 5
out1: 6
out2: 7

So to check if {B} is a diagnosis of the system (meaning that if I remove the assumption about {B} the system will be OK) I create a CNF like so:

not(1) AND not(2) AND 6 AND 7 - this represents my observations, the variables whose value I know for sure.

Now I want to add a representation for my constraints. For example, I know that 6 = not(5), but I don't know the value of 5 (because I can't assume the validity of component B).
My question is how do I add this knowledge to my CNF representation? If I add "not(5)" to my CNF then I assume the output of B is always false, and this isn't correct.

Thank you very much.

# Answer
In order to express $x = \lnot y$ in CNF form, you add the clauses $$ x \lor y, \lnot x \lor \lnot y. $$ In order to express $x = y \lor z$ in CNF form, you add the clauses $$ \lnot y \lor x, \lnot z \lor x, \lnot x \lor y \lor z. $$ In order to express $x = y \land z$ in CNF form, you add the clauses $$ \lnot x \lor y, \lnot x \lor z, \lnot y \lor \lnot z \lor x. $$
> 1 votes

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


# Question
Title: DFA for a language that accepts the addition of multiple of 2 and multiple of 5
I am trying to draw a DFA that accepts the following language:

$L=\\{a^{2i+5j} : i , j \geq 0\\}$

I started out by drawing an NFA, which I can then convert to a DFA but I am not sure if my NFA is correct.

# Answer
I'm not sure if this NFA is correct since both outgoing options from q0 are 'a', which means that you would not know to which node to go to. Wikipedia also defines an NFA as an FA when "each of its transitions is uniquely determined by its source state and input symbol", and less relevant "reading an input symbol is required for each state transition". The transistions of node q0 are not uniquely defined in this case.

Furthermore, even if two outgoing 'a's are allowed, once you have gone to q2, no multiples of 2 are possible anymore in your NFA.

That said, I do not know if you can really draw a good NFA since your definition of L allows for quite some correct multiples of a. You could start by making a list of all possible options: $$\[0,2,4,6,8,10\] \\;for\\; (i \geq 0 , j= 0)\\ \[0,5,10,15,20\] \\;for\\; (i=0,j\geq 0) \\ \[7,9,11,13,15\] \\;for\\; (i\geq1, j=1)\\\$$ From which you can quickly deduce that after 4, every even and uneven numbers are possible. Which gives the following NFA:

But I'm actually guessing you just wish to parse every multiple of 5 or 2, with tokens of either "aa" or "aaaaa". In which case you need the following NFA:

This works, since a parser would restart after 5 'a' s since no other state can be reached. Furthermore, it can parse "aaaa", since it remembers the last accepting state, which would be q2, and starts over with the 'leftover' bit of "aa". Which it can parse again.

Normally you would also have to take into account the fact that a parser is greedy, however, this parser is rather simple, as such this is not a problem. However, in long strings of 'a' you would only get tokens of "aaaaa" until the end. At that point it might parse tokens of 2 in the case of leftover strings of "aa" or "aaaa".

SIDENOTE: Do not start your NFA with an accepting state of q0, since that means you could have infinitely many empty tokens.
> 0 votes

# Answer
All natural numbers are expressible in the form $2x+5y$, except for $1,3$. You can check this directly, of use the solutino of the Frobenius problem for two denominations. Therefore another way to write your language (assuming the alphabet is $\\{a\\}$) is $$ \overline{\\{a,a^3\\}}. $$ You can construct a DFA for this language using 5 states, that count up to 4 and then saturate.

If you want to implement the constraint $2x+5y$ directly as an NFA (which is more economical for larger values of $2,5$), then you construct the following NFA:

* States: $q\_0,a\_1,b\_1,b\_2,b\_3,b\_4$.
* Initial state: $q\_0$.
* Final states: $\\{q\_0\\}$.
* Transition function: $$ \begin{array}{c|cccccc} q & q\_0 & a\_1 & b\_1 & b\_2 & b\_3 & b\_4 \\\hline \delta(q,a) & a\_1,b\_1 & q\_0 & b\_2 & b\_3 & b\_4 & q\_0 \end{array} $$

In words, there is a 2-cycle and a 5-cycle sharing a vertex $q\_0$, which is also the initial state and the unique final state.
> 2 votes

# Answer
Yes, the NFA looks correct to me.
> -1 votes

---
Tags: finite-automata
---


# Question
Title: Evolving expert systems with machine learning
Expert systems seem to have been left at the wayside a little bit in the 21st century. In fact, *expert-systems* was not even a tag on this site (until I just created it). The traditional focus in expert systems has been on rule based systems and logical resolution via, for example, 2-SAT backward chaining. Have there been attempts to integrate modern machine learning with traditional expert systems theory?

# Answer
I have been interested in this question and started simple experiments. The idea is to have a basic axiom set that cannot be changed combined with dynamic extension and sensor input. Genetic algorithms add axioms. There can be many sets existing at the same time. In an additional step integration of the sets is attempted by replacing n-ary predicates with (n+m)-ary predicates.

Example: virtual rats learn ways through mazes. There are several mazes and rats can learn any of them. Each maze defines a mapping of sequences of go-left/straight/right decisions to reward/n-reward consequences. The height of the reward also depends on the number of rats that found the way before. The variation is maintained because there is competition, so when a rat variant knowing one maze becomes frequent then knowing a less commonly known maze would become more valuable. In addition to the mazes, there are regularities in the dynamics of the environment, something like: type-1 maze will change to type-2 after 100 runs and change back after 50 runs. This allows the integration of different strategies because switching after frustration is usually good thanks to the relative stability of conditions.

I did not get beyond initial steps before I had to focus completely on a commercial project again. But I would love to resume work on the idea. If you find more information, please let me know: peter.krall@red-queen-innovations.eu
> 1 votes

---
Tags: machine-learning, expert-systems
---


# Question
Title: Bubble Sort with "while" loop - why is average case n^2?
If Bubble Sort is written as:

```
    while True:
        False
        for i in (0 to n - 2):
            if list[i] > list[i + 1]:
                swap.(list[i], list[i + 1])
                True
    return list

```

*(where `n` is `len(list)`)*

Seems to me that in the **worst** case (a list in descending order):

* the `while` loop runs $n$ times
* the `for` loop runs $n - 1$ times per `while` loop $∴$ there will be $n^2 - n$ `comparisons`
* the list is in decreasing order so there will ultimately be $(n^2 - n)/2$ `swaps`
* $∴$ worst case is $O(n^2)$

In the **best** case (a list already sorted):

* the `while` loop runs $1$ time
* there will be $n - 1$ `comparisons`
* the list is already sorted so there will ultimately be $0$ `swaps`
* $∴$ best case is $\Omega(n)$

So for the **average** case...

* the `while` loop will run *more than* $1$ time but ***less than* $n$ times**
* there will be *more than* $n - 1$ but *less than* $n^2 - n$ `comparisons`
* there will be *more than* $0$ but *less than* $(n^2 - n)/2$ `swaps`, depending on the state of the list
* $∴$ how can we show that the average case is also $n^2$ and $\Theta(n^2)$?

I don't understand where $n^2$ can be observed?

Is it because the number of `swaps` will **always** be equal to $(n^2 - n)/x$, where $x$ is determined by the state of the list?

And, as stated here (and in other places), on **average**, *with uniform distribution*, the number of swaps would be $(n^2 - n)/4$, which is half the worst case?

I'm confused `:(` Any help would be appreciated! **Thank you**.

# Answer
> 6 votes
Let's prove a more general result:

> Any sorting algorithm which only swaps adjacent elements makes $\Omega(n^2)$ swaps on average.

Let us assume that the elements being sorted are $1,\ldots,n$, and their positions are $i\_1,\ldots,i\_n$. We need to move element $j$ from position $i\_j$ to position $j$. Each swap changes the position of two elements by 1. It follows that the number of swaps is at least $$ \frac{1}{2} \sum\_{j=1}^n |i\_j - j|. $$ The marginal distribution of each $i\_j$ is uniform over $\\{1,\ldots,n\\}$, hence the expected number of swaps is at least $$ \frac{1}{2n} \sum\_{i=1}^n \sum\_{j=1}^n |i-j| = \frac{n^2-1}{6}. $$

# Answer
> 3 votes
There is an ambiguity in the specification of the bubble sort algorithm given in the start of the post. In fact, there are multiple versions of the bubble sort algorithm.

### Variations of bubble sort.

One simple version is presented in exercise 2.2. of CLRS, version 2 which does $n-1$ iterations, where each iteration performs one less comparison than the iteration before.

Another simple version is presented in this Wikipedia article, which stops once no swap is performed in an iteration.

There are two improved versions. The first one combines the advantage of the two simple versions. The other one goes further to identify more elements that have been settled down in each iteration.

It goes without saying that it is important to specify which version of the bubble sort we are talking about. It becomes critical when we want to analyse the time-complexity.

While specifying which version of the bubble sort should be critical, all complexity-analysis in this answer does not depend on any particular version, thanks to the usage of inversion number.

### Number of swaps

Regardless of which version of bubble sort is used for a given list, the number of swaps is the same.

**Lemma**. The number of swaps performed by a bubble sort on a given list is the inversion number of the given list.
**Proof**: Each swap of two adjacent elements decreases the inversion number by 1. The inversion number of a sorted list is 0.

What is the bound for the number of swaps performed by a bubble sort, assuming all elements in the input list are distinct?

* In the best case when the input list is sorted, no swap is used.
* In the worst case when the input list is sorted reversely, $n(n-1)/2$ swaps are used.
* Suppose each permutation of all elements is equally likely to be given as the input list. For each pair $p$ of indices, if it is an inversion for a permutation $\sigma$, then it is not an inversion for the corresponding permutation that is $\sigma$ with the elements at $p$ switched. So $p$ is an inversion for half of all permutations. That means $p$ is an inversion with a probability of $\frac12$. Since there are $n(n-1)/2$ pairs of indices, there are $\frac12n(n-1)/2$ inversions in an list on average. That is, $n(n-1)/4$ swaps are performed by bubble sort on average.

### Number of comparisons.

Since a swap can only happens only when there is a comparison (that finds an inversion), the number of comparisons must be no less than the number of swaps. The number of swaps given above provides a lower bound for the number of comparisons. The number of comparisons is at most $(n-1)^2$. These holds regardless of which version of bubble sort is used.

* In the best case when the input list is sorted, all versions except the one in CLRS use $n-1$ comparisons.
* In the worst case when the input list is sorted reversely, $\Theta(n^2)$ comparison are used.
* Suppose each permutation of all elements is equally likely. $\Theta(n^2)$ comparison are used on average.

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


# Question
Title: Word factorization in $O(n^2 \log n)$ time
Given two strings $S\_1, S\_2$, we write $S\_1S\_2$ for their concatenation. Given a string $S$ and integer $k\geq 1$, we write $(S)^k = SS\cdots S$ for the concatenation of $k$ copies of $S$. Now given a string, we can use this notation to 'compress' it, i.e. $AABAAB$ may be written as $((A)^2 B)^2$. Let's call the weight of a *compression* the number of characters appearing in it, so the weight of $((A)^2 B^2)$ is two, and the weight of $(AB)^2 A$ (a *compression* of $ABABA$) is three (separate $A$s are counted separately).

Now consider the problem of computing the 'lightest' compression of a given string $S$ with $|S|=n$. After some thinking there is an obvious dynamic programming approach which runs in $O(n^3 \log n)$ or $O(n^3)$ depending on the exact approach.

However, I have been told this problem can be solved in $O(n^2 \log n)$ time, though I cannot find any sources on how to do this. Specifically, this problem was given in a recent programming contest (problem K here, last two pages). During the analysis an $O(n^3 \log n)$ algorithm was presented, and at the end the pseudo quadratic bound was mentioned (here at the four minute mark). Sadly the presenter only referred to 'a complicated word combinatorics lemma', so now I have come here to ask for the solution :-)

# Answer
If I'm not misunderstanding you, I think the minimum cost factorization can be calculated in $O(n^2)$ time as follows.

For each index i, we will calculate a bunch of values $(p\_i^\ell, r\_i^\ell)$ for $\ell=1,2,\ldots$ as follows. Let $p\_i^1\ge 1$ be the smallest integer such that there is an integer $r\ge 2$ satisfying $$S\[i-rp\_i^1+1, i-p\_i^1\] = S\[i-(r-1)p\_i^1+1, i\].$$ For this particular $p\_i^1$, let $r\_i^1$ be the largest $r$ with this property. If no such $p\_i$ exists, set $L\_i=0$ so we know there are zero $(p\_i^\ell,r\_i^\ell)$ values for this index.

Let $p\_i^2$ be the smallest integer strictly bigger than $(r\_i^1-1)p\_i^1$ satisfying, likewise, $$S\[i-r\_i^2p\_i^2+1, i-p\_i^2\] = S\[i-(r\_i^2-1)p\_i^2+1, i\]$$ for some $r\_i^2\ge 2$. Like before, take $r\_i^2$ to be the maximal one having fixed $p\_i^2$. In general $p\_i^\ell$ is the smallest such number strictly bigger than $(r\_i^{\ell-1}-1)p\_i^{\ell-1}$. If no such $p\_i^\ell$ exists, then $L\_i=\ell-1$.

Note that for each index i, we have $L\_i=O(\log (i+1))$ due to $p\_i^\ell$ values increasing geometrically with $\ell$. (if $p\_i^{\ell+1}$ exists, it's not just strictly bigger than $(r\_i^\ell-1)p\_i^\ell$ but bigger than that by at least $p\_i^\ell/2$. This establishes the geometric increase.)

> Suppose now all $(p\_i^\ell,r\_i^\ell)$ values are given to us. The minimum cost is given by the recurrence $$\mathrm{dp}(i,j) = \min\left\\{\mathrm{dp}(i, j-1) + 1, \min\_\ell \left(\mathrm{dp}\left(i,j - r\_j^\ell p\_j^\ell\right) + \mathrm{dp}(j-r\_j^\ell p\_j^\ell+1,j-p\_j^\ell)\right)\right\\}$$ with the understanding that for $i\>j$ we set $\mathrm{dp}(i,j) = +\infty$. The table can be filled in $O(n^2 + n\sum\_j L\_j)$ time.

We already observed above that $\sum\_j L\_j = O(\sum\_j \log (j+1)) = \Theta(n\log n)$ by bounding the sum term by term. But actually if we look at the whole sum, we can prove something sharper.

Consider the suffix tree $T(\overleftarrow{S})$ of the reverse of $S$ (i.e., the prefix tree of S). We will charge each contribution to the sum $\sum\_i L\_i$ to an edge of $T(\overleftarrow{S})$ so that each edge will be charged at most once. Charge each $p\_i^j$ to the edge emanating from $\mathrm{nca}(v(i), v(i-p\_i^j))$ and going towards $v(i-p\_i^j)$. Here $v(i)$ is the leaf of the prefix tree corresponding to $S\[1..i\]$ and nca denotes the nearest common ancestor.

This shows that $O(\sum\_i L\_i)=O(n)$. The values $(p\_i^j,r\_i^j)$ can be calculated in time $O(n+\sum\_i L\_i)$ by a traversal of the suffix tree but I will leave the details to a later edit if anyone is interested.

Let me know if this makes sense.
> 1 votes

# Answer
There is your initial string S of length n. Here is the pseudo-code of the method.

```
next_end_bracket = n
for i in [0:n]: # main loop

    break if i >= length(S) # due to compression
    w = (next_end_bracket - i)# width to analyse

    for j in [w/2:0:-1]: # period loop, look for largest period first
        for r in [1:n]: # number of repetition loop
            if i+j*(r+1) > w:
                break r loop

            for k in [0:j-i]:
                # compare term to term and break at first difference
                if S[i+k] != S[i+r*j+k]:
                    break r loop

        if r > 1:
            # compress
            replace S[i:i+j*(r+1)] with ( S[i:i+j] )^r
            # don't forget to record end bracket...
            # and reduce w for the i-run, carrying on the j-loop for eventual smaller periods.
            w = j-i

```

I intentionally gave little details on "end brackets" as it needs lot of steps to stack and unstack which would let the core method unclear. The idea is to test an eventual further contraction inside the first one. for exemple ABCBCABCBC =\> (ABCBC)² =\> (A(BC)²)².

So the main point is to look for large periods first. Note that S\[i\] is the ith term of S skipping any "(", ")" or power.

* i-loop is O(n)
* j-loop is O(n)
* r+k-loops is O(log(n)) as it stops at first difference

This is globally O(n²log(n)).
> -1 votes

---
Tags: dynamic-programming, word-combinatorics
---


# Question
Title: Is $L = \{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not accept}\ 010 \} $ Turing recognizeable?
I'm working on the following problem:

> Is the following language Turing recognizable (recursively enumerable) ?
>
> $$L = \\{ \langle \langle \ M\ \rangle \rangle \ | \ M \ \text{does not \> accept}\ 010 \\} $$

The way I see it: Suppose that a machine $M$ loops forever on $010$. If a $TM$ recognizes $L$, it should accept $M$ in that case. But that means that it should know if $M$ loops forever or not, which is not possible. So, $L$ is not Turing recognizable.

Is my proof correct, and can it be more formal?

# Answer
You are presenting an argument which falls short of being a proof. In particular, it is not clear why a Turing machine recognizing $L$ should know whether $M$ loops forever or not; indeed, it is not so clear what do you mean by *know* in this context.

Here is one way a proof could go. Suppose that $L$ were r.e. The language of Turing machines which do accept $010$ is also r.e. By running both machines in parallel, we can *decide* whether a given Turing machine accepts $010$, i.e., we could solve the halting problem, which we know is undecidable. Therefore $L$ cannot be r.e.
> 1 votes

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


# Question
Title: Copying items in arrays while checking their indexes
> Array $P$ of length $n$ is a permutations of $\\{0, ..., n-1\\}$
>
> Write a code, which would in $O(n)$ create an array $R$ of length $n$, so for values $x\_i, x\_j \in P$, $R\[x\_i\] \< R\[x\_j\]$ if $x\_i$ is on the left of $x\_j$ ($i\<j$).

This is a algorithmization problem that's recurring in the final's test each year and I'm stuck with it for weeks. I know that I'm supposed to show my work before asking here, but I didn't know how to start.

Could you at least point me to the right direction? What technique do I use, dynamic programming? Is this a problem for a specific algorithm?

# Answer
All you're looking for is some mapping between the elements of $P$ and their indexes, that can be found in $O(1)$ for each element of $P$. Suppose given $p\_i \in P$, you can use the fact that $p\_i \in \\{0, \dots n-1\\}$, and that no $p\_j \in P$ exists s.t $p\_j = p\_i$ (other than $j=i$).

How will you do it? Set $R\[x\]$ to the index of element $x \in P$.

* Since $x$ is unique, no elements of $R$ will be overridden.
* Suppose $p\_i , p\_j \in P$, and $p\_i$ occures before $p\_j$ ($i\<j$). Then $R\[p\_i\] = i$ and $R\[p\_j\] = j$, and it holds that $R\[p\_i\]\<R\[p\_j\]$

You should be able to take it from here.
> 1 votes

# Answer
Hint, try to determine which element of $R$ should be mapped to 0.

Then try to determine which element of $R$ should be mapped to 1. You will get the idea.

---

Here is the pseudocode.

Input: array $P\[0\], P\[1\], \cdots, P\[n-1\]$, which is a permutation of $0, 1, \cdots, n-1$.

Output: array $R\[0\], R\[1\], \cdots, R\[n-1\]$, which is a permutation of $0, 1, \cdots, n-1$ such that if $i\<j$, then $R\[P\[i\]\] \< R\[P\[j\]\]$.

Procedure: For $i$ in 0 to $n-1$ inclusive, let $R\[P\[i\]\]=i$.
> 0 votes

---
Tags: time-complexity, arrays
---


# Question
Title: Determining the number of walks between two vertices in a graph
> > Given a graph G and a set of vertices $(v\_1, v\_2)$.

How can you determine whether there is $\textit{one}$ unique walk between $v\_1$ and $v\_2$?

# Answer
The following answer assumes that by *walk* you mean *path*. If you really mean walk, then if $v\_1$ and $v\_2$ are connected, there are always infinitely many walks between $v\_1$ and $v\_2$. (A path is a walk without repeated vertices.)

Run DFS from $v\_1$, and consider the resulting DFS tree. We can assume that $v\_2$ appears in the tree, since otherwise there is no path between $v\_1$ and $v\_2$. There is always one path from $v\_1$ to $v\_2$, namely along the tree edges. When is this path unique?

Let us show that the path is unique iff there are no back edges whose target is between $v\_1$ (inclusive) and $v\_2$ (exclusive). (The target of a back edge is the vertex closer to $v\_1$.)

Suppose first that there is a back edge from $y$ to $x$. The following is another path from $v\_1$ to $v\_2$: $$ v\_1 \leadsto x \to y \leadsto v\_2, $$ where $\leadsto$ is a path along the tree edges, $x \to y$ is the back edge. (There are really three different cases here: $y$ above $v\_2$, below $v\_2$, and equal to $v\_2$.)

In the other direction, suppose that $p$ is a path from $v\_1$ to $v\_2$ which is not solely along tree edges. The first edge in $p$ which is not a tree edge must be a back edge. A short case analysis (considering the direction in which the back edge is taken) shows that the target of the back edge must be between $v\_1$ (inclusive) and $v\_2$ (exclusive).
> 2 votes

---
Tags: graphs
---


# Question
Title: Efficiently deciding whether TM accepts all inputs in at most $k$ steps
I want to decide if a deterministic TM $A=(Q, \varGamma, \delta, q\_s, q\_h)$ halts on every input in at most $k$ steps. If the TM $A$ stops after $k$ steps, then the positions $A$ can reach are limited by $2k$. Thus I can create a NFA with state set:

$$ Q' \subseteq \\{1,\dots,k\\} \times Q \times \varGamma^{2k} \times \varGamma \times \\{-k,\dots,k\\} $$

which keeps track of all necessary information to simulate $M$ with a suitable transition function. This construction is exponential in $k$ and I wonder if this can be avoided by using a PDA. Does the stack give ma enough information to avoid this exponentail blow up?

# Answer
> 3 votes
Given a 3CNF formula on $n$ variables, we can construct in polynomial time a Turing machine with polynomially many states $a(n)$ that accepts a truth assignment and in polynomial time $b(n)$ checks whether it satisfies the formula, and if so, enters an infinite loop. If you believe ETH, then checking whether this machine halts on all inputs in $b(n)$ steps should take time $2^{\Omega(n)}$, indicating some kind of exponential blow-up.

---
Tags: turing-machines, finite-automata
---


# Question
Title: Guarantees on computing $a+x(b-a)$ in floating point
I want to implement the function $f(x,a,b) = a + x(b-a)$ where all the inputs are floating point (doubles, say), such that (a) $f(0,a,b)=a$ exactly; (b) $f(1,a,b)=b$ exactly; (c) $f(x,a,b) \le f(y,a,b)$ whenever $x \le y$; and preferably (d) it is accurate (correct up to rounding) for $0 \le x \le 1$.

Implementing $f(x,a,b)=a+x(b-a)$ directly does not work because for example $f(1.0,-1.0,\operatorname{prev}(1.0)) = 1.0$ (where $\operatorname{prev}(a)$ is the floating point number before $a$). And $f(x,a,b)=b-(1-x)(b-a)$ has the same issue.

Now $$f(x,a,b) = (1-x)(a+x(b-a))+x(b-(1-x)(b-a))$$ has the first two properties.

* Does it have property (c)?
* How accurate is it?
* Is there a more performant way to do this?

# Answer
> 1 votes
Here is a proposed alternative $$f(x,a,b) = \operatorname{ifelse}(x\<0.5, a+x(b-a), b-(1-x)(b-a))$$ which also satisfies (a) and (b), but it is not accurate near $0.5$. It also satisfies (c) except maybe at $\operatorname{prev}(0.5)$ and $0.5$.

For example with double-precision arithmetic we compute $f(0.5,-1.0,\operatorname{prev}(1.0))$ to be `-1.11e-16` but it is actually `-5.55e-17`, so out by a factor of 2.

It's worth noting that the implementation proposed in the question gets this example correct.

# Answer
> 1 votes
In general, you can exclude cases x ≥ 0.5 as Doris shows: Find an implementation g (x, a, b) which is good for 0 ≤ x ≤ 0.5. If x ≥ 0.5 then 1 - x is calculated exactly without rounding error, so let f (x, a, b) = g (x, a, b) if x ≤ 0.5, and f (x, a, b) = g (1-x, b, a) if x ≥ 0.5.

a + x (b - a) is reasonably accurate if b and a have the same sign. Problem is b, a having different signs (because then there is some x where f (x, a, b) should be very close to zero, and there the smallish absolute error turns into a huge relative error, again as Doris showed - except that will happen for any a, b with different sign for *some* 0 ≤ x ≤ 1).

So assume a, b have opposite sign. Let S = round (b - a), that is the result of floating-point arithmetic. It can be shown that if abs(b) ≥ abs(a) then s = ((S - b) + a) is calculated without rounding error, and therefore b - a = S - s (calculated as real numbers). But if abs(a) ≥ abs(b) then s = ((S + a) - b) is calculated without rounding error, and again b - a = S - s. All this improves the situation, because we can calculate (a + xS) - xs, which is better because we handled the rounding error in b - a.

If you did the calculation in double precision (53 bit mantissa), then you can round both x and S to single precision (24 bit mantissa) and you get two numbers whose predict is exact. Let $x = x\_{hi} + x\_{lo}$, $S = S\_{hi} + S\_{lo}$, then $xS = x\_{hi}S\_{hi} + x\_{hi}S\_{lo} + x\_{lo}S\_{hi} + x\_{lo}S\_{lo}$. The first of the products is calculated exactly without rounding error, and the others are small. So we can calculate a + xS with less rounding error:

$a + xS ≈ (a + x\_{hi}S\_{hi}) + x\_{hi}S\_{lo} + x\_{lo}S\_{hi} + x\_{lo}S\_{lo}$

# Answer
> 0 votes
Linear interpolation is a deceptively simple problem, for which, based on a literature search, no comprehensive nor definitive (i.e. with proven properties and error bounds) treatment seems to have been published to date. My previous attempt to contact a French researcher who has worked on formal proofs for similar "trivial" problems did not yield a response. The following discussion is based on running various arithmetic arrangements with a large number (billions) of test cases. In terms of the basic operations used in such rewrites, one should consider fused multiply-add (FMA) along with additions and multiplications.

It should be noted that due to the issue of subtractive cancellation, accurate results cannot be achieve when $a$ and $b$ are of opposite sign without the use of some form of extended precision. The initial portion of this answer therefore assumes that $a$ and $b$ have like signs. Likewise it is assumed that none of the intermediate computation leads to underflow, which in my test framework is guaranteed by limiting the range of $a$ and $b$ appropriately. All variants discussed in the following handle the end cases $x = 0$ and $x = 1$ correctly.

```
(1 - x) * (a + x * (b - a)) + x * (b - (1 - x) * (b - a))

```

is the formula suggested in the question above. It is non-monotonic, that is, property (c) does not hold, as simple random test cases show. My tests suggest an error bound of $2.75$ ulp for this formula.

A question on accurate and monotonic linear interpolation very similar to the present one was previously asked on the companion site Math Stack Exchange. The accepted answer there proposes the following arrangement:

```
ifelse (x < 0.5, a + x * (b - a), b - (1 - x) * (b - a))

```

My tests indicate (but *cannot* prove) that this variant is monotonic, including in the vicinity of $0.5$. Error seems to be bounded by $2$ ulps. Personally, I have subsequently adopted a modified form of this, taking advantage of FMA:

```
ifelse (x <= 0.5, fma (b - a, x, a), fma (b - a, x - 1, b))

```

Note the slightly different guard condition. Again, this variant appears to be monotonic according to my tests, and the error bound seems to be $1.5$ ulps. A very fast version for situations where monotonicity doesn't matter is the following:

```
fma (b, x, fma (-a, x, a))

```

This provides an apparent error bound of $1$ ulp, but is easily shown to be non-monotonic via random test cases.

One way of addressing the issue of subtractive cancellation when the signs of $a$ and $b$ differ (which in the worst case leads to results that are off by a factor of $2$ as noted by Doris), is to perform the intermediate computations in double native precision, using techniques originally developed by Knuth and Dekker.

My own FMA-enhanced attempt at this is shown as C-family code below. Tests indicate it provides monotonicity and an error bound of $0.501$ ulp, that is, results are nearly correctly rounded. It might be more convenient and faster to use built-in higher precision for this approach if available, as in gnasher729's answer.

```
typedef struct {
    T lo, hi;
} T2;

/* compute x+y, with |x| >= |y| */
T2 add_x_ge_y (T2 x, T2 y)
{
    T2 z;
    T r, s, e;
    r = x.hi + y.hi;
    e = x.hi - r;
    s = ((e + y.hi) + y.lo) + x.lo;
    z.hi = e = r + s;
    z.lo = (r - e) + s;
    return z;
}

T2 aa, ax, bx, tt, rr;
/* -a*x */
ax.hi = -a * x;
ax.lo = fma (-a, x, -ax.hi);
/* b*x */
bx.hi = b * x;
bx.lo = fma (b, x, -bx.hi);
/* a - a*x, Since x <= 1, |a| >= |a*x| */
aa.hi = a;
aa.lo = 0;
tt = add_x_ge_y (aa, ax);
/* a - a*x + b*x */
rr = ifelse (fabs (tt.hi) >= fabs (bx.hi), add_x_ge_y (tt, bx), add_x_ge_y (bx, tt));
return rr.hi + rr.lo;

```

---
Tags: floating-point
---


# Question
Title: Efficient Algorithms for Destroyed Document Reconstruction
I am not certain this is the proper site for this question however I am mainly looking for resources on this topic (perhaps code). I was watching TV and one of the characters had a lawyer who destroyed his documents using a paper shredder. A lab tech said that the shredder was special.

I am not familiar with this area of computer science/ mathematics but I am looking for information on efficient algorithms to reconstruct destroyed documents. I can come up with a naive approach that is brute force fairly easily I imagine but just going through all the pieces and looking for edges that are the same but this doesn't sound feasible as the number of combinations will explode.

Note: By destroyed documents I am talking about taking a document (printed out) and then shredding it into small pieces and reassembling it by determining which pieces fit together.

# Answer
> 2 votes
Your problem is NP-Complete, even for strips (n strips yields (2n)!) used, so people use heuristics, transforms like Hough and morphological filters (to match continuity of text, but this heavily increases complexity for matching) or any kind of genetic / NN search, Ants Colony Optimization.

For summary of consecutive steps and various algorithm I recommend An Investigation into Automated Shredded Document Reconstruction using Heuristic Search Algorithms.

The problem itself may end up in nasty cases, when document is not fully sharp (blurred, printed with low resolution) and strips width is small and cut by physical cutter with dulled edges, because standard merging methods like panorama photo sticher gets lost and yield improper results. This is due to lost information by missing small strips, otherwise if you have full digital image cut into pieces, it is as hard as Jigsaw puzzle, non-digital image falls into approximate search.

To make algorithm automatic another problem is pieces feeding, rarely you can give axis aligned strips, so to start process it is nice to input all stripes as one picture with pieces lay by hand, this imposes another problem (this one is easy) to detect blobs and rotate them.

By special shredder instead of stripes yield very small rectangles. For comparison, P-1 class shredder gives stripes 6-12mm wide of any length (about 1800mm^2), class P-7 gives rectangles with area less than 5mm^2. When you get rectangles instead of stripes, problem yields (4n)! permutations, assuming one one-sided document, if there are lots of shreds from unrelated documents (no pictures, text only) in one bag, problem is not really tractable.

---
Tags: image-processing
---


# Question
Title: If-Then with disjunctions (OR) in Integer Linear Programming (ILP)
I have the following constraints I'm trying to model in Linear Integer Programming. I will try out diverse solvers for this later, but first I need to model the problem.

Given the integer variables: x1, x2, x3, x4, y1, y2, y3, y4, I have the following constraints:

```
IF (y1 ≤ y3 ≤ y2  OR  y1 ≤ y4 ≤ y2)
THEN (x1 ≥ x4  OR  x2 ≥ x3)

```

Additionally for all of these variables I have upper and lower bounds.

I think I have to use the "big M" technique, but I'm not sure how to handle the logical OR in the IF condition and in the THEN condition and how to built up one complete model.

Does anyone of you know how to resolve this? Many thanks in advance.

# Answer
You have the following condition:

```
IF ((y1 <= y3) AND (y3 <= y2)) OR ((y1 <= y4) AND (y4 <= y2))
THEN (x1 >= x4) OR (x2 >= x3)

```

For each logical term, you'll need a new binary variable. At each "level" of the logical statements, you'll use the binary variables from the previous level. So:

1. `z1 = 1` iff `y1 <= y3`
2. `z2 = 1` iff `y3 <= y2`
3. `z3 = 1` iff `z1 = 1 AND z2 = 1`
4. `z4 = 1` iff `y1 <= y4`
5. `z5 = 1` iff `y4 <= y2`
6. `z6 = 1` iff `z3 = 1 AND z4 = 1`
7. `z7 = 1` iff `x1 >= x4`
8. `z8 = 1` iff `x2 >= x3`

Then you'll have a constraint that says:

9. if `z3 = 1 OR z6 = 1` then `z7 = 1 OR z8 = 1`

Let's take one type of constraint at a time.

**`z1 = 1` iff `y1 <= y3`:**

```
y3 - y1 + 1 <= Mz1
y1 - y3 <= M(1 - z1)

```

The logic is: If `y3 > y1 - 1`, i.e., `y3 >= y1`, then `z1` must equal 1. If `y1 > y3 + 1`, i.e., `y1 > y3`, then `z1` must equal 0.

Note that if the `y` variables are continuous, not integer, then replace the `1`s with some small number. This isn't ideal from a numerical perspective though.

Constraints 2, 4, 5, 7, and 8 are similar.

**`z3 = 1` iff `z1 = 1 AND z2 = 1`**:

```
z1 + z2 <= 2z3
z3 <= z1
z3 <= z2

```

The logic is: If `z1` and `z2` both equal 1, then `z3` must equal 1. If either of them equals 0, then `z3` must equal 0.

Constraint 6 is similar.

**if `z3 = 1 OR z6 = 1` then `z7 = 1 OR z8 = 1`:**

```
z3 + z6 <= 2(z7 + z8)

```

The logic is: If `z3 = 1` or `z6 = 1`, then `z7` or `z8` must equal 1.
> 1 votes

---
Tags: linear-programming, integer-programming
---


# Question
Title: In what sense a type of parser is less power than the other?
I am learning LR(0), SLR(1), CLR(1) and LALR(1) parsers. I know how parsing tables of each of them is formed. If x \< y means parser x is less "powerful" that parser y, then, I read, the relationship between these parsers can be shown as:

> LR(0) \< SLR(1) \< CLR(1) \< LALR(1)

However, I am not very clear about exactly what being "powerful" means. I can guess following possibilities for being less powerful:

a. Cannot accept valid string
b. Accept valid string very late
c. Cannot reject invalid string
d. Reject invalid string very late
f. Involves SR, RR conflict for some grammars

**Doubts**

1. I know point 5 holds for sure. However what exact effect a conflict have on parsing? Do we say that parser is non deterministic and/or requires backtracking to steps involving conflict or we simply say parser of certain type cannot be simply prepared for given grammar?
2. Which of first four (a,b,c,d) holds? I tried solving one example, for which I prepared both SLR(1) and CLR(1) parsing table. I SLR(1) parsing table had reduce move for state `2` and terminal `)`, whereas CLR(1) did not. I took an invalid string for which SLR(1) was able to incorrectly reduce when stack top was state `2` and next input symbol was `)`. But eventually it failed to shift `)`. So, in the end rejecting the string. However, CLR(1) rejected the string right away without incorrectly reducing. Is this what all can happen? Or there can be an invalid string which SLR(1) may incorrectly accept (point c)? Or points (a) and (b) do also hold?
I feel only point (d) holds. Also SLR(1) and CLR(1) can accept valid string in same number of steps (that is, point b does not hold). Am I right with what I feel?

# Edit

I concluded following for above points (a) through (d). Need someone to confirm:

**(a)** SLR(1) always accept valid strings as it will be able to correctly do shift reduce moves for such strings. So, point (a) is incorrect.

**(b)** Accepting valid strings late can only happen when valid string causes traversing through incorrect reduce moves of SLR(1) parsing table. However, this never happens. Valid strings can never be accepted by going through incorrect reduce move cells of parsing table. Those are only hit by invalid strings. Hence, point (b) is also wrong.

**(c)** SLR(1) can never fail to reject invalid string as it will always fail to shift some terminal in such string. So, point c is also not correct.

**(d)** SLR may reject some invalid strings late since it may do incorrectly do some reductions. So only point d is correct.

**Another (possibly last) doubt**

Though in (c) above, I said SLR(1) can never fail to reject invalid string, I doubt its correctness. If a parser accepts invalid string, we simply say that the parser does not implement that grammar, right? But my doubt is whether such parser always involve SR / RR and such "conflict is the only reason to fail to reject invalid string"? We know that SLR can do some incorrect reductions. So, "can't such incorrect reduction be reason for acceptance of invalid string"? Or in other words, for some invalid string, can't SLR shift all of it (so that no terminal will remain un-shifted in the end), and finally do incorrect reduction of whole invalid input string to starting symbol S, thus accepting invalid string? After all we know SLR parser may do some incorrect reductions. Then, why it cant do incorrect reduction of whole invalid input string to the start symbol?

# Answer
> 3 votes
Assuming that by "CLR" you mean "canonical LR", then you have the order wrong; the correct containment order is

$LR(0) \< SLR(1) \< LALR(1) \< CLR(1)$

A possibly more meaningful way of saying that is that if we define $G\_X$ to be the set of context-free grammars which can be parsed with algorithm $X$, then

$G\_{LR(0)} \subset G\_{SLR(1)} \subset G\_{LALR(1)} \subset G\_{CLR(1)}$

That containment sequence does not apply to *languages*. If we say that $L\_X$ is the set of languages for which there is a grammar in $G\_X$, then we will find that

$L\_{LR(0)} \subset L\_{SLR(1)} \subseteq L\_{LALR(1)} \subseteq L\_{CLR(1)}$

For all of these parsing algorithms, the fact that the algorithm cannot produce a conflict-free parsing table for a particular grammar means that that grammar cannot be parsed with that algorithm. The word "accept" is quite confusing here: an algorithm produces a parser from a grammar (or fails to do so); the parser then accepts those sentences which are in the grammar's language. If an algorithm produces a parser for a grammar, then that parser will be 100% precise: it will accept all sentences in that grammar's language and reject all other sentences.

Furthermore, all these LR parsers have linear time and space complexity (in the size of the sentence to be recognised), and all of them reject invalid inputs at the earliest possible point, which is as soon as the prefix of the input cannot be the prefix of any sentence in the language. It is true that some of the parsers may perform extra reduce actions before reporting failure, but that is not considered in the definition of a grammar's "power".

---
Tags: automata, context-free, formal-grammars, compilers, parsers
---


# Question
Title: Is $L=\{\langle M\rangle\mid L(M)\subseteq HP\}\in coRE$?
My intuition is that $L\notin coRE$, but I haven't managed to prove that $HP \le L$, as previously I only saw reductions from $HP$ or from $\overline{HP}$ with $f$ such that $f((\langle M\rangle,x))=\langle M\_x\rangle$, while $M\_x$ performs some simulation of $M$ on $x$.

(The answer eluded me for some time, so I started writing a question here. After I found the surprisingly simple answer, I decided to post it (Q&A-style) anyway.)

# Answer
We would show that $HP \le L$.

Let $f:\Sigma^\*\rightarrow \Sigma^\*$ be a function such that for any $x\in \Sigma^\*$: $$f(x)=\langle M\_x\rangle$$ while $M\_x$ is a TM that accepts $x$ and rejects every other word.

$f$ is computable, as it only requires writing the encoding of a very simple TM.

Now, for any $x\in \Sigma^\*$:

* $L(M\_x)=\\{x\\}$
* If $x\in HP$, then $\\{x\\}\subseteq HP$, and so $\langle M\_x\rangle \in L$.
* Otherwise, $x\notin HP$, and then $\\{x\\}\not\subseteq HP$, and so $\langle M\_x\rangle \notin L$.

Therefore, indeed $HP \le L$.

Thus, it must be that $L\notin coRE$, because otherwise the reduction would imply that $HP\in coRE$, which is false.
> 1 votes

---
Tags: computability, reductions
---


title: Spanning trees on disconnected graphs

text:
# Question
Title: Spanning trees on disconnected graphs
Can anyone please help me out with my query: can disconnected graphs have minimum spanning trees?

# Answer
No, because by definition trees are connected. However, one might talk about *spanning forests* when referring to a collection of trees each of which is a spanning tree of some disconnected graph.

Wikipedia has some discussion on spanning forests and related definitions.
> 1 votes

# Answer
A spanning tree, by definition, has the same vertices as the graph it spans. Since such a tree is an induced subgraph and, since trees are (by definition) connected, the graph itself must be connected.

Note this applies to any spanning tree, not just a minimal one (i.e., an MST).
> 1 votes

---
Tags: graphs, minimum-spanning-tree
---


# Question
Title: How to find sum of maximum K elements in range in array
Recently, I came up to the following problem:

Given array $A$ of size $n$ and integer $k$, We should answer $Q$ questions of the type: for given range $\[l, r\]$ we should find sum of the $k$ maximum elements over all $A\_i$ such that $l \leq i \leq r$.

Trivial solution would be to sort all values in the range and iterate over the k biggest elements, however this has complexity $O(QN\log N)$. After some searching on the internet, I found out that this can be solved by segment trees, however I couldn't think of proper use of segment trees for this problem.

Is it possible to solve this problem in complexity better than $O(QN\log N)$

# Answer
This answer refers to the version of the question in which the interval $\[l,r\]$ refers to the *values* of the elements rather than their *indices*.

Without preprocessing: You can extract all elements in the range $\[l,r\]$ in linear time. You can then use the linear time selection algorithm to find the $k$'th largest element, and then you can easily find the sum of the $k$ maximum elements. Overall, you can answer each query in $O(n)$.

With preprocessing: Sort the array, and compute running sums. Given $l,r$, locate the subset of the array corresponding to this range using binary search, and then use the running sums to compute the sum of the $k$ largest elements in $O(1)$. Overall, this uses $O(n\log n)$ preprocessing and $O(\log n)$ time per query.
> 5 votes

# Answer
This answer refers to the version of the question in which the range $\[l,r\]$ refers to indices of the array, and in which we have $Q$ queries. The question asked whether we could beat $O(Qn\log n)$.

Without preprocessing: Using the linear time selection algorithm, you can answer each query in $O(n)$, for a total of $O(Qn)$, which is better than $O(Qn\log n)$.

With preprocessing: Assume for simplicity that $n$ is a power of 2. We consider $\log n$ layers, the first consisting of $n$ intervals of length 1, the second of $n/2$ intervals of length 2, and so on: the $k$th consists of $n/2^k$ intervals of length $k$. We sort all of the intervals in $O(n\log n)$ by "merging up the tree". At query time, we partition the input interval into $O(\log n)$ stored intervals, and them return the answer in $O(k\log n)$ by merging the $k$th largest elements from each.

We can improve the query time as follows. Along with the layered intervals, we also compute their running sums. Let us consider the $O(\log n)$ layered intervals $I\_1,\ldots,I\_m$ whose union is the given interval $\[l,r\]$. The $k$ largest elements of $\[l,r\]$ are composed of the $k\_1,\ldots,k\_m$ largest elements in $I\_1,\ldots,I\_m$. If we could determine $k\_1,\ldots,k\_m$, then we could compute the answer in $O(m) = O(\log n)$ using the running sums.

We can determine $k\_1,\ldots,k\_m$ as follows. For each element $x \in I\_1$, we can count how many elements are larger than $x$ in time $O(m\log k) = O(\log n \log k)$ using binary search. By doing binary search on the top $k$ elements of $I\_1$, we can determine $k\_1$ in time $O(\log n \log^2 k)$. Continuing in this way, we can determine $k\_1,\ldots,k\_m$ in time $O(\log^2 n \log^2 k)$.

This solution has preprocessing time $O(n\log n)$ and query time $O(\log^2 n \log^2 k)$.

We can obtain other tradeoffs by varying the fan-in of the tree. Suppose that the fan-in is $n^{1/d}$. For each internal node in the tree, we sort each interval-of-intervals within its children. At level $i$ we have $n^{i/d}$ vertices, each has $n^{2/d}$ intervals-of-intervals, each of length at most $n^{1-i/d}$, so sorting all intervals-of-intervals at level $i$ takes time $n^{1+2/d}$, for a total preprocessing time of $O(dn^{1+2/d})$. In query time, we can break $\[l,r\]$ into a union of $O(d)$ intervals, for a total query time of $O(d^2\log^2 k)$.

Stated differently, for each $\epsilon \> 0$ this gives an algorithm with preprocessing time $O(\epsilon^{-1} n^{1+\epsilon})$ and query time $O(\epsilon^{-2} \log^2 k)$.
> 5 votes

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


# Question
Title: What is the difference between object detection, semantic segmentation and localization?
I've read those words in quite a lot of publications and I would like to have some nice definitions for those terms which make it clear what the difference between object detection vs semantic segmentation vs localization is. It would be nice if you could give sources for your definitions.

# Answer
I read a lot of papers about, Object Detection, Object Recognition, Object Segmentation, Image Segmentation and Semantic Image Segmentation and here's my conclusions which could be not true:

Object Recognition: In a given image you have to detect all objects (a restricted class of objects depend on your dataset), Localized them with a bounding box and label that bounding box with a label. In below image you will see a simple output of a state of the art object recognition.

Object Detection: it's like Object recognition but in this task you have only two class of object classification which means object bounding boxes and non-object bounding boxes. For example Car detection: you have to Detect all cars in a given image with their bounding boxes.

Object Segmentation: Like object recognition you will recognize all objects in an image but your output should show this object classifying pixels of the image.

Image Segmentation: In image segmentation you will segment regions of the image. your output will not label segments and region of an image that consistent with each other should be in same segment. Extracting super pixels from an image is an example of this task or foreground-background segmentation.

Semantic Segmentation: In semantic segmentation you have to label each pixel with a class of objects (Car, Person, Dog, ...) and non-objects (Water, Sky, Road, ...). I other words in Semantic Segmentation you will label each region of image.
> 19 votes

# Answer
Since this issue is still not quite clear even now in 2019, and it might help new ML-Learners choose, here is a very good image showing the differences:

(localisation is the bounding box around the "sheep" class, after a classification of the image has been done)  source: Towardsdatascience.com
> 11 votes

# Answer
I believe just "localization" means "single object classification + localization using a 2D or 3D bounding box".

"Object detection" is localizing + classifying all instances of known object classes in question.

Semantic Segmentation is basically per-pixel classification.

Also wrt involved metrics (source: https://devblogs.nvidia.com/parallelforall/deep-learning-object-detection-digits/ )

Precision is the ratio of the accurately identified objects to the total number of predicted objects (ratio of true positives to true positives plus false positives).

Recall is the ratio of the accurately identified objects to the total number of actual objects in the images (ratio of true positives to true positives plus true negatives).

mAP: a simplified mean Average Precision score based on the product of the precision and recall for DetectNet. It’s a good combined measure for how sensitive the network is to objects of interest and how well it avoids false alarms.
> 3 votes

# Answer
The term localization is unclear. I will therefore discuss the terms object detection and semantic segmentation.

In object detection, each image pixel is classified whether it belongs to a particular class (e.g. face) or not. In practice, this is simplified by grouping pixels together to form bounding boxes therefore reducing the problem to deciding if the bounding box is a tight fit around the object. As pixels can belong to multiple objects (e.g. face, eye), they can hold multiple labels at the same time.

On the other hand, semantic segmentation involves assigning class labels to each image pixel. While they allow for better localizing accuracy as they do not incorporate the bounding box simplification, they strictly enforce a single label per pixel.
> 2 votes

# Answer
Semantic segmentation: It is the task of clustering parts of images together which belong to the same object class. eg:detecting road signs
> -2 votes

---
Tags: terminology, computer-vision
---


# Question
Title: How to understand the recurrence relation and time-complexity of StoogeSort?
I have the following problem of recurrences and divide-and-conquer. Consider the algorithm, called StoogeSort in honor of the immortals Moe, Curly and Larry. The swap operation $(x,y)$ exchanges the values of $x$ and $y$.

```
Algorithm StoogeSort:
procedure StoogeSort(A[0...n −1])
    if n = 2 ∧ A[0] > A[1] then
        swap(A[0], A[1])
    else if n > 2 then
        m = ceil(2n/3)
        StoogeSort(A[0...m−1])
        StoogeSort(A[n−m ...n−1])
        StoogeSort(A[0...m−1])
    end
end

```

The problem demands the following:

* Show that the algorithm correctly orders the array A of n elements.
* Would it work correctly if we replaced ceil($\frac{2n}{3}$) with floor($\frac{2n}{3}$)? Justify your answer.
* Give a recurrence for the number of comparisons between elements of A that StoogeSort performs with n elements.
* Solve the recurrence for the number of comparisons. (Hint: skip functions ceil and functions floors, solve exactly the result.)
* Show that you execute at most $ {n}\choose{2} $ swap operations. (Hint: How many comparisons are required to locate the element in position k if it is at start?)

I intuit that item two works changing ceil by floor so if the length of the arrangement is odd it does not matter if I take the larger half at the beginning or after the middle of the arrangement. But how do I show this?

I have the following help:
For the first bullet, use induction: It is easy to see it works for 1 or 2 items. Prove that if it works for $n−1$ or fewer items, then it also works for n items. For the 3rd & 4th bullets, $c\_1=0$, $c\_2=1$ and $c\_n=3c\_m$. For the final bullet, show that any pair of items is never swapped more than once.

How should I interpret the help for bullets 4 and 5? Thanks in advance.

# Answer
> 3 votes
Here are some more hints:

* The algorithm partitions the array $A$ into three parts $B,C,D$ such that $|C| \geq |B|,|D|$ and then sorts $BC$ (the array formed by the first two parts), $CD$ (the array formed by the last two parts), and then $BC$ again. Show that for any such partition, the result is sorted. You can use the 0-1 principle.
* When $n=4$, the algorithm sorts $a\_1,a\_2$, then $a\_3,a\_4$, then $a\_1,a\_2$. You can easily give an example showing that this doesn't work.
* You should be able to solve this yourself.
* The recurrence in the preceding bullet involves $m = \lceil \frac{2n}{3} \rceil$. This part asks you to replace $m$ with $\frac{2n}{3}$, and then solve the recurrence using the master theorem.
* For a permutation $\pi$, the number of *inversions* is the number of pairs $i\<j$ such that $\pi(j)\<\pi(i)$. A permutation can have at most $\binom{n}{2}$ inversions (this is the number of pairs $i \< j$). Each swap operation reduces the number of inversions by 1.

---
Tags: algorithms, algorithm-analysis, divide-and-conquer
---


# Question
Title: Understanding Correctness of Bidirectional Dijkstra
I'm trying to understand the correctness of the bidirectional version of Dijkstras algorithm as mentioned here on slide 10:

https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%20shortest%20path%20algorithms.pdf

For a contradiction, they consider an $s-t$ path $p$ that is shorter than the minimum sum $\mu$ of tentative distances from the forward and backward search.
The next step I don't understand: there is an edge $(v,w)$ on this path, such that:

1. $dist(s,v) \< top\_f$
2. $dist(w,t) \< top\_b$

Where do these relationships come from?

From what I see, after stopping, it holds that $\mu \leq top\_f + top\_b$.

So if we consider any edge $(v,w)$ of $p$, we have that

$dist(s,v) + length(v,w) + dist(w,t) \< top\_f + top\_b$

We can leave out that edge to get the inequality

$dist(s,v) + dist(w,t) \< top\_f + top\_b$

But from this, I can't derive these two relationships.

I appreciate any help! Thanks!

# Answer
I came across these slides where on slide 23 another proof is given, however the idea of this proof is the same as in the slides of my original post.

But this still doesn't show, why $dist(s,v)$ and $dist(w,t)$ need to be less than $top\_f$ and $top\_b$ respectively.

EDIT: Note that with this proof $dist(s,v) \leq top\_f$ and $dist(w,t) \leq top\_b$ hold, since both vertices have already been settled. I'm in doubt, whether the original statement $dist(s,v) \< top\_f$ and $dist(w,t) \< top\_b$ is actually correct and therefore I'm marking this question as 'answered'. However if anyone finds an explanation, feel free to answer!
> 1 votes

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


title: proving L1* ∪ L2* ⊆ (L1∪L2)*

text:
# Question
Title: proving L1* ∪ L2* ⊆ (L1∪L2)*
x∈ L1\* ∪ L2\* ⇔ x∈ L1\* ∨ x ∈L2\* ⇔ x ∈(L1)\* ∨ x∈(L2)\* ⇔ x ∈L1\* ∪ L2\* ⇔ x∈(L1∪L2)\*

Is it enough to prove it this way?

# Answer
> 4 votes
No. Your proof of $A\iff B$ is to claim that

$$A\iff \text{something} \iff \text{something else} \iff A \iff B\\,.$$

The first two stages are irrelevant, since you get back to $A$. The final stage just asserts as true the exact thing you're supposed to be proving.

Try instead to prove that every string in the first language is in the second.

# Answer
> 1 votes
Let us prove more generally that if $A \subseteq B$ then $A^\* \subseteq B^\*$. Indeed, if $w \in A^\*$ then $w$ can be written in the form $w = w\_1 \ldots w\_n$ (possibly $n = 0$), where $w\_1,\ldots,w\_n \in A$. Since $A \subseteq B$, also $w\_1,\ldots,w\_n \in B$, and so $w \in B^\*$.

You take it from here.

# Answer
> 1 votes
Let $x$ be a word in $L1^\* \cup L2^\*$. Then either $x \in L1^\*$ or $x \in L2^\*$ (or both, but we do not have to consider that separately). Without loss of generality, let's assume $x \in L1^\*$.

Then we have that $L1 \subseteq L1 \cup L2$. Using the proof by Yuval Filmus, you can prove that this implies $L1^\* \subseteq (L1 \cup L2)^\*$.

Therefore, every $x \in L1^\*$ is in $(L1 \cup L2)^\*$.

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


# Question
Title: Does |xy| ≤ p in the pumping lemma count for all i?
While learning about the pumping lemma, I came across the following question:

Given the language L is $ a^n(0|1)^\* $ with $ c\_0 \cdot c\_1 = n $, where $ c\_0 $ indicates the amount of zeros present, use the pumping lemma to prove that this language is not regular. Examples of valid words in L are `0`, `1`, `a01`, `aa001`, etc...

In regular english: a word with leading `a`s, followed by any amount of either `0` or `1` characters, where the amount of zeros multiplied by the amount of ones needs to match the amount of `a`s.

My initial attempt was the following:

* Pick w as $ a^p0^p1 $. This obviously holds since $ p \cdot 1 = p $.
* Split w into xyz as $ x = \epsilon $, $ y = a^p $, $ z = 0^p1 $.
* Show that $ xy^2z = a^{2p}0^p1 $ does not hold, since $ p \cdot 1 \ne 2p $.

However, the answer key instead opts to introduce two new variables $ m \geq 0 $, $ n \gt 0 $, then splits on $ x = a^m $, $ y = a^n $, $ z = a^{p-n-m}0^p1 $ (splitting the sequence of a into three parts). Then, they too use $ i = 2 $ to show that $ xy^2z = a^{m}a^{2n}a^{p-n-m}0^p1 = a^{p+n}0^p1 $, which is not a member of the language (since n was more than 0).

As far as I can see, my attempt adheres to the $ |xy| \leq p $ condition of the pumping lemma: x is empty and $ |y| = p $. As such, I was under the impression that my answer was correct.

However, the huge increase in complexity of the answer in the answer key leads me to believe that this is not a valid approach. I have the sneaking suspicion this is because my answer actually *does* violate the $ |xy| \leq p $ condition.

Is my attempt a correct way to prove that the language is not regular? If not, what misconception/mistake did I make along the way?

# Answer
> 2 votes
Your mistake is in the following step:

> * Split $w$ into $xyz$ as $x = \epsilon$, $y = a^p$, $z = 0^p 1$.

You're not allowed to choose how $w$ splits into $xyz$. You should show that for *any* way of splitting $w$ into $xyz$ such that $|xy| \leq p$ and $y \neq \epsilon$, there exists $i$ such that $xy^iz \notin L$.

Here is a similar "proof" that the language $01^\*$ isn't regular:

* Pick $w$ as $01^p$.
* Split $w$ into $xyz$ as $x = \epsilon$, $y = 0$, $z = 1^p$.
* Show that $xy^2z = 0^21^p$ is not in the language.

The proof of the pumping lemma will choose a different splitting, for example $x = 0$, $y = 1$, $z = 1^{p-1}$.

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


title: Difference between DPDA and NPDA?

text:
# Question
Title: Difference between DPDA and NPDA?
What are the major differences between Deterministic Push Down Automata and Non-deterministic Push Down Automata? Which one is faster and how? Also what are the drawbacks of DPDA with respect to NPDA. Can anyone quote an example and explain these concepts.

# Answer
> 8 votes
The main (and only) difference between DPDA and NPDA is that DPDAs are deterministic, whereas NPDAs are non-deterministic. With some abuse of notation, we can say that NPDAs are a generalization of DPDAs: every DPDA can be simulated by an NPDA, but the converse doesn't hold (there are context-free languages which cannot be accepted by a DPDA).

The main advantage of DPDAs is that we can simulate them much more easily with our deterministic computers (real hardware is always deterministic). In fact, simulating general DPDAs is not fast enough for most purposes, and so when parsing code we usually use LALR grammars which are weaker than DPDAs.

# Answer
> 2 votes
In **Deterministic Push Down Automata** it is always defined that at for a particular input it will be going to a specific state but in case of **Non-deterministic Push Down Automata** for a specific input it may go to different states ...

# Answer
> 1 votes
In DPDAs, only one move is possible when reading any input from any state but, in NPDAs, there can be multiple moves possible for an input symbol from a state. DPDAs are less powerful than NPDAs. There are Context Free Languages, such as the language of palindromes, that can be accepted by NPDAs but not by DPDAs.

# Answer
> -2 votes
The transition function delta is almost single-valued for DPDA , multi-valued for an NPDA.

---
Tags: automata, pushdown-automata
---


title: Reliability of a service

text:
# Question
Title: Reliability of a service
Assume that I need to determine the reliability of a service. The service includes component **a** (software reliability=0.95) and component **b** (software reliability=0.98). I have 2 computers: Computer **A** (hardware reliability=0.99) and Computer **B** (hardware reliability=0.99).

I have two following cases:

> Case 1: Deploy both **a** and **b** on computer **A**. For this case, the service reliability is around **0.923**.
>
> Case 2: Deploy **a** on computer **A**, and **b** on computer **B**. For this case, the service reliability is around **0.912**

I really wonder why the service reliability in case 2 is lower than in case 1. The thing is **A** and **B** have the same hardware reliability. Can someone clarify that?

# Answer
> 1 votes
In Case 1, for the service to not fail we need three things to not fail: computer **A**, component **a** and component **b**. In contrast, in Case 2 we also need computer **B** to not fail. Plainly the probability in the latter case is smaller, by a factor of 0.99.

You can calculate the non-failure probability by just multiplying the non-failure probabilities for the relevant objects:

* Case 1: $0.99 \cdot 0.98 \cdot 0.95 = 0.92169$.
* Case 2: $0.99 \cdot 0.99 \cdot 0.98 \cdot 0.95 = 0.9124731$.

# Answer
> 1 votes
Ignore the software reliability for now, and only focus on the machines.

In case 1 there is only one machine that can fail, and it fails 1% of the time.

In case 2 there are *two* machines that can fail. However, even if just one fails the service goes down. The chance that at least one machine fails is $1 - 0.99^2 = 1.99\\%$. So instead of spreading the risk we've just made our service more liable to fail.

There are two components to making a system reliable despite hardware failure:

1. Spreading out risk of failure across multiple machines.
2. Making the system robust to failure of some machines.

In the exercise we do have #1 but are missing #2.

---
Tags: software-engineering, reliability
---


title: Doubt on Floating Point Representation

text:
# Question
Title: Doubt on Floating Point Representation
$1-2^{-23}$ and $2-2^{-22}$ both represents floating point representation or normalised representation.But are those two represent same value or both have different value? Is floating point representation same as IEEE representation??

# Answer
> 2 votes
> Is floating point representation same as IEEE representation?

Well, not exactly. Floating point is more the abstract idea for "a fractional number" (of arbitrary magnitude) or rather "a number of varying precision.

On the other hand, IEEE(754) is a specific implementation of this idea. Other standards exist and all of them implement "floating point" numbers.

---
Tags: computer-architecture
---


# Question
Title: Closure properties of a non-regular language under complement?
* Assume I have L1 which is a regular language, so we know since regular language is closed under complement, the complement of L1 is also a regular language.
* But let's say if the complement of L1 is a non-regular language, is it safe to conclude that L1 is a non-regular language as well?

Since I'm trying to prove a language L1 is not a regular language, and the pumping lemma doesn't work well with this case. But I can easily prove the complement of L1 is not regular, I'm wonder if that option is possible.

# Answer
Yes, non-regular languages are closed under complement as well.

Suppose the complement of L1 is a non-regular language. If L1 is regular, then "the complement of L1 is also a regular language", which is not true. Hence L1 cannot be regular.

More generally, suppose we have defined a collection of languages as myLanguages. Then

myLanguages are closed under complement $\Longleftrightarrow$ non-myLanguages are closed under complement

For example, we have

* non-context-free languages are not closed under complement.
* non-context-sensitive languages are closed under complement.
* non-deterministic-context-free languages are closed under complement.
> 1 votes

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


# Question
Title: Using the decision problem, PATH in order to solve the optimization problem, SHORTEST-PATH in polynomial time
So, if I were using a black-box decision algorithm, `PATH` in which I could say, "does a path of weight `k` exist in this graph from `S` to `V`", problably the typical way one would solve the optimization problem of shortest path is to start at `k` at zero and increment until `PATH` returns true. But since paths start at `-inf` shouldn't we be starting there? (Thus making this optimization problem not solvable in polynomial time)

I know this isn't right, I'm just having a hard time seeing which part I am missing here.

# Answer
For non-negative weights $0$ is a lower bound and thus sufficient. For arbitrary weights you can binary search in $\[l,u\]$, for a lower bound $l=\sum\_{a\in A\mid d\_a\<0} d\_a$ and an upper bound $u=\sum\_{a\in A\mid d\_a\>0} d\_a$ on the length of any simple path.
> 2 votes

---
Tags: shortest-path, np
---


# Question
Title: What is the closed-form expression for $T_n = \left(\sum_{i=1}^{n-1}7 T_i\right) + 1$ where $T_1 = 1 ?$
**Problem:**

> Find the closed-form expression for$$ T\_n = \left(\sum\_{i=1}^{n-1}7 T\_i\right) + 1 \tag{1} $$where $T\_1 = 1 .$

Calculating this sum I came up with the following result: $$ T\_n = 8^{\left(n-1\right)} \tag{2} \\,,$$ but is this result correct?

I know the sequence is:$$ \begin{align} T\_1 & = 1 \\ T\_2 & = 8 \\ T\_3 & = 64 \\ & ~~\vdots \end{align} $$

**Questions:**

1. What would be the closed-form of $T\_n ?$
2. What would be the best way to find it?

# Answer
> 2 votes
After calculating a few values, you can guess the solution and then easily prove it by induction. Another way to find it is to use "creative cancellation": $$1 + 7 (T\_1 + \cdots + T\_{n-1}) = T\_n = (T\_n + \cdots + T\_1) - (T\_{n-1} + \cdots + T\_1).$$ Hence if you put $S\_n = T\_1 + \cdots + T\_{n-1}$, you deduce $$ S\_n = 8S\_{n-1} + 1. $$ In order to make this homogeneous, take $R\_n = S\_n + c$: $$ R\_n = S\_n + c = 8S\_{n-1} + 1 + c = 8(R\_{n-1} - c) + 1 + c = 8R\_{n-1} + 1 - 7c. $$ Choosing $c = 1/7$, this gives $R\_n = 8R\_{n-1}$, and so $R\_n = 8^{n-1} R\_1$. Now $R\_1 = S\_1 + 1/7 = T\_1 + 1/7 = 8/7$, and so $R\_n = 8^n/7$.

It follows that $S\_n = (8^n-1)/7$ and $T\_n = S\_n - S\_{n-1} = (8^n - 8^{n-1})/7 = 8^{n-1}$.

---

Let me conclude by giving a combinatorial interpretation for the recurrence. I will show that $T\_n$ is the number of base-8 numbers of length $n-1$. Indeed, any such number is either 0, or starts with a non-zero digit followed by a number $i \< n-1$ digits long.

---
Tags: recurrence-relation, recursion
---


# Question
Title: Proof emptiness for PDA is $\mathcal{O}(n^3)$
It is well known that the emptiness problem vor PDAs is in $\mathcal{O}(n^3)$. I couldn't find a good paper proving this theorem. Furthermore a proof for VPAs would be fine for me as well if that is easier.

Do you maybe have a book or paper I should investigate?

**EDIT:** This looks interesting but a formal proof from a book or paper would be great!

# Answer
Start with an arbitrary PDA. Convert it to a PDA which pushes at most two symbols to the stack at each step — this only incurs a linear blow-up. Convert the PDA to a CFG using the standard construction, described in this answer. Since the PDA pushed at most two symbols at each step, the CFG has size $O(n^3)$ (for each transition $p \stackrel {a,\gamma} \to q$, where $a$ is a letter and $\gamma$ is a word in the stack alphabet, we have to enumerate over $|\gamma| \leq 2$ states, hence the number of transitions is at most the original number of transitions times $|Q|^2$). Convert the CFG to Chomsky normal form with linear blow-up. Then use the linear time algorithm described in this answer to check whether the CFG generates an empty language or not.

Summarizing:

* Convert the PDA to one in which at most two symbols are pushed to the stack at each move (linear blow-up).
* Convert the new PDA to a CFG (cubic blow-up).
* Convert the CFG to Chomsky normal form (linear blow-up).
* Check emptiness of the CFG in Chomsky normal form (linear time).

You can probably skip the step in which you convert the CFG to Chomsky normal form by modifying slightly the algorithm described in the second answer.
> 2 votes

---
Tags: formal-languages, reference-request, pushdown-automata
---


# Question
Title: 3-SAT with negative-literals in each clause
Does a 3-SAT problem, where in each clause there is at least a negative-literal, always has a solution?

After looking at it, seems to me that the answer is yes, but maybe there is something I am not seeing.

# Answer
> 1 votes
Consider the all-zeroes assignment, $x\_1=x\_2=\cdots=x\_n=0$.

What if all clauses have a positive literal?

---
Tags: 3-sat
---


title: How Fibonacci LFSR work

text:
# Question
Title: How Fibonacci LFSR work
What is "Fibonacci" about the Fibonacci LFSR? If I read right, Fibonacci LFSR means that it depends on its two last states, but from the example in Wikipedia it doesn't look like two states are taken in consideration (ie. XORing the taps in the current state, shifting and inputing the left bit..). What am I missing?

# Answer
> 1 votes
"In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state." wiki quote.
Its output depends on state and polynomial, not two states.

The name come (afair) from Fibonacci work on recurence relation, his sequence, and further interest in characteristic polynomials of generating sequences, but the one who gave closed form solution to Fibonacci numbers and researched characteristic equation (the one used in generator with possibly minimal monic to make longest period), was Lucas. I cannot find any reference why it is called Fibonacci LFSR, but it is inventors will to name it.

The same stands for LFG - lagged Fibonacci generator was (in multiplicative form) introduced by Marsaglia to overcome deffects of additive one.

The real interest in random generation was started by Galton (if it matters Romans did toss coins and stored bits), random numbers by Pearson, first PRNG is attributed to von Neuman, first working one to Lehmer, as for Fibonacci his insights are nice, but he started his sequences to count rabbits with no connection to PRNG whatsoever.

Of you are interested in history of PRNG, History of uniform random number generation is nice.

# Answer
> 1 votes
If you take the "standard" Fibonacci sequence, starting with $0,1$, and take the terms modulo $2$ (or, equivalently, $x\_n=x\_{n-1}+x\_{n-2} \mod 2$) then you get

$0,1,1,0,1,1, \dots$

and from this sequence you can read off the values of a $2$-bit LFSR: $01\rightarrow 11 \rightarrow 10 \rightarrow 01$ (MSB first).

Longer LFSRs can be constructed in a similar manner using recursion rules that look further back in the sequence e.g. $x\_n=x\_{n-2}+x\_{n-3} \mod 2$ gives a $3$-bit LFSR:

$0,0,1,0,1,1,1,0,0,1, \dots\\ 001 \rightarrow 010 \rightarrow 101 \rightarrow 011 \rightarrow 111 \rightarrow 110 \rightarrow 100 \rightarrow 001$

---
Tags: pseudo-random-generators
---


title: First half of context-free palindromes

text:
# Question
Title: First half of context-free palindromes
If $L\subseteq\Sigma^\*$ is a regular language, then $\text{mir}(L) = \\{ww^R \mid w\in L\\}$ is context-free. This is a nice exercise.

Question: does the reverse hold? Thus, if $\text{mir}(L)$ is context-free, do we always have $L$ is regular?

# Answer
Yes.

---

Sándor Horváth, J. Karhumäki and H. C. M. Kleijn characterized the context-free languages consisting only of palindromes in their paper Results Concerning Palindromicity, 1987.

**Theorem**. A context-free language $L\subseteq\Sigma^\*$ is palindromic, iff it is of the form $$ L= \bigcup\_{x\in\\,\Sigma\cup\\{\lambda\\}}\\{uxu^R : u\in L(x)\\}$$

where the $L(x)$ is a regular language uniquely determined by $L$ for all $x \in\Sigma\cup\\{\lambda\\}$.

---

In particular, the theorem tells that a context-free languages that consists of only palindromes of even length must be of the form $\\{uu^R : u\in L\\}$ for some regular language $L$.
> 4 votes

# Answer
I believe the answer should be affirmative. Here are some ideas on how to prove this.

We can remove from the grammar any nonterminals which are unreachable or produce only finite languages (we can assume that $L$ itself is infinite). Now suppose that $S \Rightarrow^\* xAy$. If $|x| = |y|$, then $x = y^R$ and $L(A) \subseteq \mathsf{PAL}$, where $\mathsf{PAL}$ is the language of all palindromes. If $|x| \> |y|$ then $x = y^R z$, and then $L(A)z^R \subseteq \mathsf{PAL}$. Similarly, when $|x| \< |y|$ there is a word $w$ such that $wL(A) \subseteq \mathsf{PAL}$.

Now suppose $A \Rightarrow^\* xAy$. We want to understand what happens when $|x| \neq |y|$, say $|x| \> |y|$. We will only consider the case $L(A) \subseteq \mathsf{PAL}$, but the others should be similar. Suppose $A \Rightarrow^\* w$. Thus $x^\ell w y^\ell = \bar{y}^\ell \bar{w} \bar{x}^\ell$ for all $\ell$ (we use $\bar{w}$ to denote the reversal of $w$). By considering large enough $\ell$, we can find $I,J$ such that $x^I = \bar{y}^J$, and so $x,\bar{y}$ are powers of the same word $z$, say $x = z^i$ and $y = \bar{z}^j$. Using $k = i-j$, this means that $$ z^{\ell i} w \bar{z}^{\ell j} = z^{\ell j} \bar{w} \bar{z}^{\ell i} \longrightarrow z^{\ell k} w = \bar{w} \bar{z}^{\ell k}. $$ Thus we can write $\bar{w} = z^r s$, where $z = st$. This gives $$ t z^{\ell k-r-1} = \bar{z}^{\ell k-r-1} \bar{t} \longrightarrow t(st)^{\ell k-r-1} = (\bar{t}\bar{s})^{\ell k-r-1} \bar{t} = \bar{t} (\bar{s}\bar{t})^{\ell k-r-1}, $$ that is, $s$ and $t$ are palindromes. This kind of structure must hold for every $w$ generated by $A$, and we conclude that $L(A) \subseteq \bigcup\_s z^\* s$, where $s$ goes over all decompositions $z = st$ with $s,t \in \mathsf{PAL}$. This should imply that $L(A)$ is, in fact, regular (via Parikh's theorem).

A similar argument shows that if a production for $A$ has two nonterminals on the righthand side, then $L(A)$ is regular. Therefore we have some regular nonterminals, and the other nonterminals only participate in productions of the form $A \to xB$, $A \to Cy$, and $A \to z$. We can also convert the productions involving regular nonterminals to this form.

Consider now a derivation starting at $S$. In order to simulate its first half using an automaton, we can try the following strategy. We will be reading the complete word (both halves) from both directions at once. If the left pointer has advanced $i$ steps and the right pointer $j$ steps, then we want to have read from the input the first $\min(i,j)$ symbols. We can implement this in a finite automaton as long as $|i-j|$ is bounded (we have to store in memory this many symbols, or at least their count).

If $|i-j|$ is not bounded, then by the pigeonhole principle our derivation contains subderivations of the form $A \Rightarrow^\* xAy$ with $\bigl| |x|-|y| \bigr|$ unbounded. As pointed out above, this can happen only for the regular nonterminals, but by setting up the productions correctly, we can ensure that this doesn't happen.

While the ideas above are somewhat sketchy, I believe that they can probably be fleshed out to prove Hendrik Jan's conjecture.
> 2 votes

# Answer
Consider a context-free grammar that generates only palindromes. What do its right hand sides look like? Each can contain only one nonterminal that generates a language with size \> 1; so we can expand all other nonterminals away to produce a grammar with only right hand sides with at most one nonterminal. Each of these generates a language of the form $w\_1. L. w\_2$ where $L$ is a language of palindromes, and $w\_1, w\_2$ are terminal strings at least one of which is empty.

At this point I'll do some handwaving and say that such a grammar can be normalized into a linear grammar in which all right hand sides are palindromes.

Halve all right hand sides of this grammar to obtain a regular grammar for the halves of its words.
> 0 votes

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


# Question
Title: Is there any tiny tips to find counter example string for proving some language is not a CFL?
When I prove some language is context free, It is too hard to find example string. Is there any tips? It takes too many time or eventually give up.

# Answer
> -1 votes
The pumping lemma for CFGs can often be used to show a language is not a CFL.

---
Tags: formal-languages
---


# Question
Title: Turing recognizable language between languages that aren't recognizable?
Let $L\_{1},L\_{2}$ be languages that are not Turing recognizable, and let $L$ be a language such that $L\_{1} \subseteq L \subseteq L\_{2}$.

Is $L$ also not Turing recognizable?

I am inclined to believe it is, but I really have no idea how to show this. It seems that non-recognizable languages have very little about them that could be used to solve a problem like this. Ideas?

# Answer
The answer is **no**, of course.

Consider, for instance, the following languages:

* $L\_1 = \\{ \langle M \rangle \\# \langle M \rangle \mid \\, \text{$M$ is a TM which does not halt on input $\langle M \rangle$} \\}$
* $L = \\{ \langle M \rangle \\# \langle M \rangle \mid \\, \text{$M$ is a TM} \\}$
* $L\_2 = L \cup \\{ \langle M \rangle \\# w \mid \\, \text{$M$ is a TM which does not halt on input $w$} \\}$

Then it is easy to see neither $L\_1$ nor $L\_2$ are recursively enumerable (i.e., Turing-recognizable), despite $L$ being even context-sensitive. (In fact, you could even make $L$ context-free by replacing the second $\langle M \rangle$ with its reversed copy.)

---

The upshot is that set inclusion (on its own) tells us very little about the sets involved being recursively enumerable or not, unless the symmetric difference between them is finite. In the case of $L\_1 \subseteq L \subseteq L\_2$, we *do* know, for instance, that $|L \setminus L\_1|$ or $|L\_2 \setminus L|$ being finite implies that $L\_2$ is also not recursively enumerable.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Is it reasonable to consider a book's table of contents as a hierarchical collection? if yes, what does the root node represent?
this book "Fundamentals of Python: Data Structures 1st Edition" says

> data items in hierarchical collections are ordered in a structure resembling an upside-down tree. Each data item except the one at the top has just one predecessor ... A file directory system, a company's organizational tree, and a book's table of contents are examples of hierarchical collections

each hierarchical collection has a root node, is it reasonable to consider a book's table of contents as a hierarchical collection? if yes, what does the root node (`one at the top`) represent?

# Answer
The root node is the entire book. Its children are chapters. Their children are sections. And so on.

This is reflected in the standard numbering system, in which chapters are labeled by numbers, sections are labeled by numbers within chapters, and so on.

As an example, we can take the table of contents of the book you mention. The root has 15 children: an introduction, 12 chapters, an appendix, and the index. The first child (introduction) is a leaf. The second child has 9 children, which are the various sections: basic program elements, control statements, and so on. The first child (basic program elements) has 19 children, all leaves: programs and modules, an example python program, and so on.
> 2 votes

---
Tags: data-structures
---


# Question
Title: AVL Tree - Print ascending using in-order
Trying to understand how to write proof of correctness. Searched over the internet on how to write proof of correctness but can't find a good solution for it.

The following sorting algorithm is proposed using the AVL tree: AVL input of all elements, and printing them in order.

**Algorithm - Sort AVL (A\[1..n\])**

T -\> Empty AVL Tree.

* for each 1 \<= i \<= n

insert A\[i\] to T.

print T elements by using in-order fashion.

Prove the correctness of the algorithm by showing the in-order scan of binary tree is always in ascending order.

# Answer
AVL trees, like all other binary search trees, have the following guarantee:

> Suppose that $v$ is a node with left child $l$ and right child $r$. If $x$ is a node in the subtree rooted at $l$ and $y$ is a node in the subtree rooted at $r$ then $key(x) \leq key(v) \leq key(y)$.

Using this, you can easily prove by induction that the inorder traversal of a binary search three produces a list of keys in nondecreasing order.
> 1 votes

---
Tags: data-structures, sorting, avl-trees
---


# Question
Title: Acceptance problem for CFGs is not regular
Let $ACFG$ be the language of all encodings $(C,x)$ where $C$ is a context-free grammar that generates a language containing $x$, i.e. $ACFG$ is the acceptance problem for context-free grammars.

It is easy to show that $ACFG$ is decidable. Parsing algorithms like CKY are proof of this fact.

Are $ACFG$ also regular? Is it also context-free? I would guess nay to both, but how would one formally show these facts?

# Answer
> 1 votes
Let's prove a more general result:

> Let $\phi\colon \\{0,1\\}^\* \to 2^{\\{0,1\\}^\*}$ be an arbitrary function mapping binary strings to languages over the binary alphabet. Suppose that the range of $\phi$ is infinite. Then the language $L\_\phi = \\{(x,y) : y \in \phi(x)\\}$ is not regular.

(The language is over the alphabet consisting of $0,1$ as well as parentheses and comma.)

For the proof, we use Myhill—Nerode theory. Let $(x\_n)\_{n \in \mathbb{N}}$ be encodings of languages such that $\phi(x\_i) \neq \phi(x\_j)$ for $i \neq j$. Then the words $(x\_i,$ and $(x\_j,$ are inequivalent modulo $L\_\phi$: taking any word $y \in \phi(x\_i) \Delta \phi(x\_j)$, the word $y)$ separates the words $(x\_i,$ and $(x\_j,$.

Interestingly, $L\_\phi$ could be context-free. Let $\phi(0^n) = \\{1^n\\}$ and $\phi(w) = \emptyset$ if $w$ contains $1$. Then $L\_\phi = \\{(0^n,1^n) : n \in \mathbb{N}\\}$, which is context-free.

---
Tags: context-free
---