title: generating pi using Machin like formula

text:
# Question
Title: generating pi using Machin like formula
Back in 2002, using this arctan formula for pi discoverd by Stoemer:

$$ \pi = 176 \arctan(1/57) + 28 \arctan(1/239) - 48 \arctan(1/682) \\ + 96 \arctan(1/12943)$$

and I assume using this series for arctan:

$$ \arctan(x) = x - \frac{x^3}{3} + \frac{x^5}{5} - \frac{x^7}{7} + \frac{x^9}{9} - \dotso $$

$\pi$ was generated to 1.2 trillion digits on a super computer, using 64 nodes of a HITACHI SR8000/MPP, in about 157 hours (it took 400 hours for another 4 term formula). Link to web site announcing the result:

https://web.archive.org/web/20150225043658/http://www.super-computing.org/pi\_current.html

I assume each initial term was 480GB, which translates to 1,030,792,151,040 hexadecimal digits, corresponding to the articles stated accurate size of 1,030,700,000,000 hexadecimal digits. Since each node had 16GB of ram, this meant the numbers had to be streamed on and off hard drives. The terms decrease in size with each iteration, but only a tiny fraction of the total time will be spent with terms that fit in each node's ram.

Using the $\arctan$ series seems like it should be fairly straightforward, basically $term\[i+1\] = term\[i\] \cdot (1/z^2)$, where $z$ is 57, 239, 682, or 12943. The terms are combined (adding and subtracting), then divided by $(2i+1)$.

The terms are kept as large vectors (fixed point array), while the divisors are scalars (relatively small fixed number of bits), so the division is similar to long hand division where a multi-digit dividend is divided by a single digit divisor, with the quotients being generated by multiply + shift to speed up the process, explained next.

Dividing by a constant can be sped up using multiply by "magic" number and right shift some number of bits. For the sequence of divisors, 1, 3, 5, 7, ..., the "magic" numbers are generated dynamically (requires two actual divides), since the same divisor is being used across a large vector term.

A "magic" number $M$ is in the range: $$\frac{2^{N+L}}{divisor} \leq M \leq \frac{2^{N+L} + 2^L}{divisor}$$ where $L$ is $\big \lceil \log\_2{divisor} \big \rceil$, and $N$ is set to produce the required precision. If interested, there's a SO Q&A about this:

https://stackoverflow.com/questions/41183935

Using this method, my system (Intel 3770K 3.5 ghz, Win 7 Pro 64 bit, assembly code) is able to generate 1 million digits (in binary) in about 140 seconds. Update - using 6 threads on the 4 core 3770K to overlap operations, this time was reduced to 48 seconds. With more cores and threads, the series could be split up into separate components, in addition to overlapped operations.

However, the team effort to produce 1.2 trillion digits back in 2002 was much faster than the straight forward method I describe, and involved much more complex code, taking over 75,000 lines of code. I've tried searching to get an idea of what was involved, but not having any luck. One issue is that much faster (and simpler to implement using a big int library) Chudnovsky based formulas have been used since then.

http://en.wikipedia.org/wiki/Chudnovsky\_algorithm

in which case optimized implementations can generate 1 million digits of $\pi$ in about 8 seconds on my system (apparently without using parallel calculations or multi-theading)

I can find articles about optimized implementations of Chudnovsky like formulas, but I haven't found anything like this for the Machin like formulas based on arctan. I'm wondering if anyone here would know of a web site that might explain how arctan based formulas could be optimized.

---

Update, there were 4 terms and 64 nodes, each with a lot of memory, to compute the terms in parallel. Consider the $(1/57)$ term being calculated using just 4 of the nodes. The initial phase: node 0: $(1/57^2)$, node 1: $(1/57^4)$, node 2: $(1/57^6)$, node 3: $(1/57^8)$, after this initial phase, each node multiplies it's term by $(1/57^8)$, picking up $\approx 46.7$ bits per iteration.

If all 64 nodes computed the $(1/57)$ term, each node multiplies it's term by $(1/57^{128})$, picking up $\approx 746.6$ bits per iteration, which translates into $\approx 4.45$ billion iterations for 1 trillion digits. $57^{128}$ would fit in a 12 x 64 bit word (96 byte) divisor. Karatsuba could be used for extended precision multiply / shift ("magic" numbers) to produce quotients from such divisors.

The team probably analyzed the computing load for each of the 4 terms and distributed the generation accordingly. Still this doesn't sound like 75,000+ lines of code to implement so there was more to it.

# Answer
I cannot remember where I learned the trick for doing this. It doesn't seem very well publicised. It may have been from a Richard Brent paper (seems likely). Nonetheless, here goes...

There are a few principles which are helpful to remember if you're working with extremely large integers:

1. Avoid division of a large integer by a large integer.
2. Try to multiply integers of similar magnitudes.

Large integer division is typically done using an iterative algorithm (e.g. Newton-Raphson), so you want to avoid that where possible. What this means in practice is that it is probably cheaper to calculate a numerator and denominator separately, and then conclude with a final division. This appears to be standard practice for evaluating Machin-like formulae.

Large integer multiplication is typically done using a FFT-based algorithm (e.g. Schönhage–Strassen, Fürer) for large enough integers, which has better complexity if the number of bits in each of the multiplicands is approximately the same. This suggests a divide-and-conquer algorithm for evaluating numbers which are essentially large products.

The basic idea is this. Suppose you want to calculate the series:

$$\sum\_{i=0}^{n} \frac{P(i)}{Q(i)}$$

You can calculate the two half-series:

$$\frac{P\_1}{Q\_1} = \sum\_{i=0}^{\left\lfloor n/2\right\rfloor} \frac{P(i)}{Q(i)}$$ $$\frac{P\_2}{Q\_2} = \sum\_{i=\left\lfloor n/2\right\rfloor +1}^{n} \frac{P(i)}{Q(i)}$$

Then:

$$\frac{P}{Q} = \frac{P\_1 Q\_2 + P\_2 Q\_1}{Q\_1 Q\_2}$$

It should be obvious how to turn this into a recursive algorithm.

That's the general approach, but once you're thinking along these lines, there are some obvious optimisations that you can do with the arctan series in particular:

$$\arctan\left(\frac{1}{x}\right) = \frac{1}{x} - \frac{1}{3x^3} + \frac{1}{5x^5} - \frac{1}{7x^7} \cdots$$

The numerators are all one, and the denominators have a structure that you can exploit if you're careful. I'll leave this for you to discover.

**EDIT** Small test program in Haskell, didn't try to optimise it.

```
module MachinLike where

import Data.Ratio

arctanSeries :: Int -> Int -> Int -> (Integer,Integer)
arctanSeries x i j
    | i == j = let c = 2*i+1
               in (if even i then 1 else -1,
                   fromIntegral c * (fromIntegral x)^c)
    | otherwise = let m = (i+j) `div` 2
                      (p1,q1) = arctanSeries x i m
                      (p2,q2) = arctanSeries x (m+1) j
                  in (p1*q2 + p2*q1, q1*q2)

-- I'm just guessing on the appropriate number of terms in
-- each series. Proper numeric analysis is needed.
--
-- Also, in case it's not obvious, this isn't the final step
-- that you'd do if you were serious about high accuracy.
approxPi :: Int -> Double
approxPi n
    = let (p1,q1) = arctanSeries 57 0 n
          (p2,q2) = arctanSeries 239 0 (n `div` 4)
          (p3,q3) = arctanSeries 682 0 (n `div` 11)
          (p4,q4) = arctanSeries 12943 0 (n `div` 227)
      in fromRational ((176 * p1)%q1)
       + fromRational ((28 * p2)%q2)
       - fromRational ((48 * p3)%q3)
       + fromRational ((96 * p4)%q4)

```

And running it:

```
*MachinLike> :set +s
*MachinLike> approxPi 500
3.141592653589793
(0.28 secs, 799,354,048 bytes)

```

Do remember that the 75,000 lines of code mentioned probably includes large slabs of what you'd typically find in a multiprecision integer library. In a real implementation, the final division steps would involve an iterative algorithm with increasing precision on each iteration.

By the way, another little hint as to how to speed this up: Dynamic programming.
> 2 votes

# Answer
Perhaps they used

$\text{arctan}\frac{1}{x}=i\sum\limits\_{m=1}^{\infty}\frac{1}{2m-1}\left(\frac{1}{\left(1+2ix\right)^{2m-1}}-\frac{1}{\left(1-2ix\right)^{2m-1}}\right)$

or

$\text{arctan}\frac{1}{m}=m\sum\limits\_{k=0}^{\infty}\frac{\left(4k+3\right)m^2-\left(4k+1\right)}{\left(16k^2+16k+3\right)m^{4\left(k+1\right)}}$
> 1 votes

---
Tags: algorithms, numerical-algorithms, program-optimization
---


# Question
Title: Equivalence of states between two "quasi-deterministic" strongly connected Büchi automata accepting the same $\omega$-language
Hope someone can point me to the right direction to solve this problem.

**Premise.** I call *quasi-deterministic Büchi automaton* (qDBA) a Büchi automaton $B = \langle S, \Sigma, S\_0, \delta, F \rangle$, where $S$ is the set of states, $\Sigma$ the alphabet of transition labels, $S\_0 \subseteq S$ the set of initial states, $\delta: S \times \Sigma \rightarrow S$ a partial transition function, and $F \subseteq S$ the set of accepting states. That is, a Büchi automaton where the only place of nondeterminism is in the initial state, while the transition function is deterministic. An $\omega$-word is accepted by $B$ iff any of the infinite runs induced by the word on $B$ passes infinitely many times through some states of $F$.

Given a qDBA $B$ and a state $s \in S$, let $B/s = \langle S, \Sigma, s, \delta, F \rangle$ denote the deterministic Büchi automaton accepting all the $\omega$-words inducing runs of $B$ starting from $s$ (where $s$ may also be a non-initial state in B). Two states $s\_1$ of the qDBA $B\_1$ and $s\_2$ of the qDBA $B\_2$ are *equivalent* iff the language of the $\omega$-words accepted by $B\_1/s\_1$ is the same as the one accepted by $B\_2/s\_2$.

Finally, I say that $B$ is *strongly connected* if for any two states $s\_1$ and $s\_2$ there is a finite path connecting $s\_1$ to $s\_2$ and vice versa.

**Question.** Let $B\_1 = \langle S\_1, \Sigma, S\_{0,1}, \delta\_1, F\_1 \rangle$ and $B\_2 = \langle S\_2, \Sigma, S\_{0,2}, \delta\_2, F\_2 \rangle$ be two strongly connected qDBAs accepting the same $\omega$-language, $L(B\_1) = L(B\_2) = L$. I want to prove that for every state $s\_1 \in S\_1$ there exists at least one state $s\_2 \in S\_2$ equivalent to $s\_1$.

Does this property hold in general? I tried to construct counterexamples to this property, but in every case I could think of, in order to falsify the conclusion, I always needed either to drop the assumption that $\delta\_2$ was a deterministic transition function, or that $B\_2$ was strongly connected.

I have a strong sense this property should hold. It might even be trivial, but maybe I am using the wrong vocabulary and I cannot find this result.

**My intuition so far.** Suppose there are two $\omega$-words $w'$ and $w''$ accepted by $B\_1/s\_1$. Since $B\_1$ is strongly connected, one can construct accepted words by starting with the first symbols of $w'$, then taking a path back to $s\_1$, then continuing with some symbols from $w''$, then back to $s\_1$, and again following $w'$ in any combination. Since $B\_2$ also accepts all of these combinations but has a finite number of states, the runs corresponding to these words must eventually reach some state $s\_2$ from which both $w'$ and $w''$ are possible continuations of the runs. This must hold for every set of words accepted by $B\_1/s\_1$. But I am not able to turn this (possibly wrong) reasoning in general, formal terms. Could you please help me do so, if possible?

# Answer
> 1 votes
Your property does not hold.

Consider the following languages over $\Sigma = \\{a,b\\}$:

* There are infinitely many $a$s at even positions in a word
* There are infinitely many $a$s at odd positions in a word

Both are representation as DBAs with the same set of states (of size 3). We can build DBAs for them that only differ in their initial states.

If we want to build an automaton for the disjunction of these languages, we can do so by taking both initial states for both of them as new initial states. This gives us a qDBA $B\_1$.

The disjuction is equivalent to the language "there are infinitely many $a$s", for which a DFA $B\_2$ only needs two states, each of which have the same language.

Now, $B\_1$ and $B\_2$ are a counter-example to your conjecture.

---
Tags: automata, buchi-automata, connected-components, omega-automata
---


# Question
Title: How to extend Bellman-Ford to solve the $k$ shortest path routing?
Browsing the wikipedia I got to this page where it is said:

> Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm and extend them to find more than one path.

The same statement is somewhat repeated in the hall of fame of algorithms:

> To find the shortest path one can use shortest path algorithms such as Dijkstra’s algorithm or Bellman Ford algorithm and extend them to find more than one path

Then, the Wikipedia (i.e., the first link, not the second) goes into proving how it is possible to extend Dijkstra's algorithm to solve the loopy variant (i.e., where non-simple paths are allowed). The extension is absolutely simple as it simply consists of allowing each node to be expanded up to $k$ times, with $k$ the number of paths to find to the goal state. This idea, indeed, was generalized by Rina Dechter to consider heuristics as well:

However, I never heard of any extension of Bellman-Ford for solving neither the loopy nor the loopless variants of the $k$ shortest path routing problem. Moreover, I'm not aware of any algorithm that can solve this problem in the presence of negative edge costs.

The only variant I can think of for extending Bellman-Ford is observing that upon termination the cost of the optimal path of one designated vertex to all the other vertices $v\in V$, $d\_v$, is known so that one could run sort of a Recursive Best-First Search to enumerate all paths. Maybe is this what the authors of those pages mean?

Thus, my questions are:

1. What is the way to extend Bellman-Ford to solve the $k$ shortest path routing problem?
2. Are there any algorithms out there for solving the $k$ shortest path routing problem with negative edge costs (provided there are no negative cycles)? Note that neither Eppstein's nor Yen's algorithm can deal with negative edge costs.

This is all I know about the subject and please note that my questions are a result of my ignorance so that I would be very grateful if any answer is provided or any link I could follow.

Cheers,

# Answer
It seems that we can use the following generalization of Bellman-Ford. Let's store a set $Pt\_{v}$ of $k$ numbers for each vertex $v$ of graph $G$ which initially are all equal to $+\infty$. The only exception is a vertex $s$ (the vertex from which all paths are calculated). Its set $Pt\_{s}$ should be initialized to a single value of $0$ and $k-1$ values of $+\infty$.

Now let's run $k \cdot |V|$ iterations of relaxations (instead of $|V| - 1$ iterations like in usual Bellman-Ford) and try to maintain the following invariant. After $i$-s iteration for each vertex $v$ the $j$-s least number from $Pt\_{v}$ should be not greater than the length of the $j$-s shortest path from $s$ to $v$ containing not more than $i$ edges. This invariant will be maintained by means of proper edge relaxations. For each $(u, v)$ edge relaxation we should assign $Pt\_{v}$ to a set of $k$ least numbers from a set $Pt\_{v} \cup \\{x + weight(u, v)|x\in Pt\_{u}\\}$.

So after all $|V|-1$ iterations each set $Pt\_{v}$ will contain $k$ shortest paths from $s$ to $v$. The proof of correctness for this algorithm should be literally the same as for usual Bellman-Ford.

This is a loopy algorithm. Its time complexity is $O(|V|\cdot|E|\cdot k^2)$ (because single edge relaxation can be done in $O(k)$ time using a selection algorithm).
> 3 votes

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


# Question
Title: Knapsack dynamic programming complexity issue for $W=1$, is it $O(n)$?
The 0-1 knapsack problem is given by

$$\begin{align}&\text{maximize } \sum\_{i=1}^n v\_ix\_i,\tag{P1}\\\& \text{subject to } \sum\_{i=1}^n w\_i x\_i \leq W,\\\&\text{and } x\_i \in \\{0,1\\}.\end{align}$$

Running the dynamic programming algorithm for this problem would give an optimal solution in $O(nW)$.

If I define $p\_i=w\_i/W$, I get the following knapsack problem:

$$\begin{align}&\text{maximize } \sum\_{i=1}^n v\_ix\_i,\tag{P2}\\\& \text{subject to } \sum\_{i=1}^n p\_i x\_i \leq 1,\\\&\text{and } x\_i \in \\{0,1\\}.\end{align}$$

Running the dynamic programming algorithm for this problem would give an optimal solution in $O(n)$. This is not true, isn't it?

# Answer
The running time is $O(nW)$ if all weights are *integers*. This is because the dynamic programming table is indexed by possible weights of subsets. If all weights are integers, then since we are only interested in subsets whose sum of weights is at most $W$, there are only $W+1$ weights of subsets that could possibly interest us. This is where the $W$ factor in the running time is coming from.

Dividing all weights by $W$ accomplishes exactly nothing. You haven't changed the problem, so the required time for solving it is remains exactly the same.
> 1 votes

---
Tags: time-complexity, knapsack-problems
---


# Question
Title: Complement of a DFA without final states
Let $L\_1=\\{Q,\Sigma,q\_0,\delta,Q\\}$ be a DFA that accepts a language $L$ and where all the states are also final states. If we want a DFA that accepts the complement of $L$, we swap its accepting states with its non-accepting states, that is $\overline{L\_1}=\\{Q,\Sigma,q\_0,\delta,Q-Q\\}$. In this case we have a DFA without final states. Is this still a DFA? Is it regular?

# Answer
It's common to write DFAs which don't have transitions on every symbol. These are called "incomplete" DFAs, and there is really nothing wrong with them as long as it is understood that they are incomplete. But they don't satisfy all of the requirements of algorithms which require complete DFAs, and the complement algorithm you are using is one of those. (There are many other such algorithms. For example, Hopcroft's state minimization algorithm doesn't work on incomplete automata, at least without some adjustment.)

If the DFA you are referring to is complete and has no non-accepting states, then it must be the case that it recognises $\Sigma^\*$ so that its complement is the empty set. But I have a hunch that's not the case.

You can always convert an incomplete DFA into a complete DFA by adding a single non-accepting state with a looping transition on every symbol. (This is usually called the "sink" state, because there is no way out.) Then for every other state which has no transition on one or more symbols, you add all the missing transitions with the sink state as a destination. Since the sink state is non-accepting and non-escapable, this operation does not in any way alter the language recognised by the DFA.

Once you've done that, it is (probably) no longer the case that every state in the DFA is accepting; there is now one non-accepting state. And the complement algorithm will make that non-accepting state accepting, and all the other states non-accepting, which will produce the complement of the language.
> 21 votes

# Answer
If I understood it correctly, then $L$ contains every possible string, because no matter what the input is, $L\_1$ will terminate on a final state.

Since $L\_1$ accepts every possible string, its complement should accept no strings, hence the empty language.
> 4 votes

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


# Question
Title: For given reduction f, can show "if f(x) in 4NAE then x in 3SAT", but not "if x is not in 3SAT then f(x) not in 4NAE"
*Claim: $3SAT \le\_p 4NAE $, where reduction $f$ is defined as such: given a 3CNF formula $\varphi$, add to each clause a new literal $z$ (where $z$ is same literal for each clause), and return new formula $f(\varphi)$.*

It seemed pretty easy to show that $\varphi\in 3SAT\Rightarrow f(\varphi)\in 4NAE$:

* If $\varphi \in 3SAT$, then every clause in $\varphi$ contains at least one $T$ literal. In $f(\varphi)$, let the added literal $z=F$. Then every clause in $f(\varphi)$ contains at least one $T$ and one $F$ literal, so $f(\varphi)\in 4NAE$.

Here's where I'm confused: At first, I thought that if $\varphi \notin 3SAT \Rightarrow f(\varphi) \notin 4NAE$.

We know $\varphi \notin 3SAT$ iff any non-contradictory assignment of literals has at least one clause with all false values. However, assuming there is no clause in $\varphi$ containing all true literals, then if $f(\varphi)$ adds $z=T$ to each clause, wouldn't $f(\varphi)$ belong to $4NAE$?

On the other hand, I thought of this argument to show that $ f(\varphi)\in 4NAE \Rightarrow \varphi\in 3SAT$:

* Suppose $f(\varphi)\in 4NAE$, where $x\_i$ represents original literals in $\varphi$ and $z$ is added literal from reduction. Let $Y$ represent a satisfying assigment of $f(\varphi)$.

+ If $z=F$, then for any clause $(x\_1 \vee x\_2 \vee x\_3 \vee z)$ in $f(\varphi)$, we know that either $x\_1$ or $x\_2$ or $x\_3$ had to be ***true***. Thus, the original clause $(x\_1 \vee x\_2 \vee x\_3)$ in $\varphi$ would evaluate as true, and so $\varphi$ contains satisfiable assignment.
    + if $z=T$, then for any clause $(x\_1 \vee x\_2 \vee x\_3 \vee z)$ in $f(\varphi)$, we know that either $x\_1$ or $x\_2$ or $x\_3$ had to be ***false***. Now define the assignment $Y '$ to be identical to $Y$ except with every literal negated, and remove all $z$'s. Then $(\bar x\_1 \vee \bar x\_2 \vee \bar x\_3)$ contains at least one true literal. So $Y'$ is a satisfiable assignment of $\varphi $, and $\varphi \in 3SAT$.

Basic logic says *if p then q* should be equivalent to "*if not q then not p*". So obviously I'm making some mistakes or assumptions here. I just don't see where.

# Answer
The error is in this paragraph:

> We know $\varphi \notin \mathsf{3SAT}$ iff any non-contradictory assignment of literals has at least one clause with all false values. However, assuming there is no clause in $$ containing all true literals, then if $()$ adds $=$ to each clause, wouldn't $()$ belong to $\mathsf{4NAE}$?

Here's your argument, broken into steps:

1. Suppose $\varphi \notin \mathsf{3SAT}$. Thus, every assignment for $\varphi$ has at least one falsified clause.
2. Suppose there was some assignment in which each clause contains a falsified literal. Then $f(\varphi) \in \mathsf{4NAE}$, by choosing $z=T$.

I fail to see the contradiction here. Indeed, if there is some assignment in which each clause contains a falsified literal, then if you complement it, you get a satisfying assignment, as you show in your post. This means that if (1) holds, then (2) cannot possibly hold.

You argument is basically saying "what if I had an unsatisfiable $\varphi$ together with an assignment in which each clause contains a falsified literal". If such a $\varphi$ existed, then your reduction wouldn't have been sound. Fortunately, no such $\varphi$ exists. It's true that you have to rule out the existence of such $\varphi$, which you do by showing that if (2) holds then (1) doesn't hold.
> 1 votes

---
Tags: complexity-theory, reductions, logic, 3-sat
---


# Question
Title: Determining if we can balance these graph weights
Let $G$ be a complete directed graph with $n$ vertices. Each vertex $v$ has a weight $w(v)\>0$, such that the sum of all vertex weights is $n$. We have that the edge $e$ from $u$ to $v$ has a weight $0 \leq w(e) \leq w(u)$.

We say that these weights can be balanced, if there exists a directed spanning tree, $T$, and function on the edges of $T$, $f$, where $0 \leq f(e)\leq w(e)$, such that for every vertex $v$, we have that $$w(v) + \sum\_{e \in I\_v} f(e) - \sum\_{e \in O\_v} f(e)=1$$ where $I\_v$ is the set of all edges in $T$ going into $v$, and $O\_v$ is the set of edges in $T$ going out from $v$.

Is determining whether the weights can be balanced a known problem? It sounds like a network flow problem, but I'm not too familiar. What's an algorithm which could solve this?

# Answer
> 1 votes
This solves the problem if the function $f$ is not constrained to the edges of a spanning tree.

You can think of your problem as a flow problem where each vertex $u\in V$ "generates" $w(u)$ units of flow and "sinks" 1 unit of flow.

To reduce this problem to a standard flow formulation you can create a new directed graph $G' = (V', E')$ in which each edge $e \in E'$ has a capacity $c(e)$:

* $V' = V \cup \\{s,t\\}$, where $s$ is a new "source" vertex and $t$ is a new "sink" vertex.
* For each $v \in V$, add to $E'$ the edge $(s,v)$ with capacity $w(u)$.
* For each edge $e \in E$, add $e$ to $E'$ with capacity $c(e) = w(e)$.
* For each $v \in V$ add to $E'$ the edge $(v,t)$ with capacity $1$.

Compute the value $f^\*$ maximum flow from $s$ to $t$ in $G'$. If $f^\* = |V|$ then your all units of flow can be generated and sunk (one unit from each vertex $u \in V$), therefore your problem problem admits a solution. If $f^\* \< |V|$ your problem admits no solution (to see this you can show that you can convert any feasible solution to your original problem to a flow of $|V|$ in $G'$).

---
Tags: algorithms, graphs
---


title: Convertion from NFA to DFA

text:
# Question
Title: Convertion from NFA to DFA
I have converted nfa to dfa. But when I checked with some examples, it looks like it is wrong.

```
This is the full question.
Convert the nfa defined by
δ(q0, a) = {q0, q1}
δ(q1, b) = {q1, q2}
δ(q2, a) = {q2}
δ(q1, λ) = {q1, q2}
with initial state q0 and final state q2 into an equivalent dfa.

```

First, I made a table.

```
             a          b
ɸ            ɸ          ɸ
{q0}         {q0,q1}    ɸ
{q1}         ɸ          {q1,q2}
{q2}         {q2}       ɸ
{q0,q1}      {q0,q1}    {q1,q2}
{q1,q2}      {q2}       {q1,q2}
{q0,q2}      {q0,q1,q2} ɸ
{q0,q1,q2}   {q0,q1,q2} {q1,q2}

```

Finally, I have drawn dfa according to table above.  The bold line is accepting state.

Thanks for your help/

# Answer
It looks like you have 3 symbols in your language: a, b, and \lambda. But your transition table only has the symbols a and b. You need to add \lambda to your transition table and integrate that into your diagram. That should help some.
> 1 votes

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


# Question
Title: Computing all paths from root to the leaf nodes in a tree
I have a this tree, i want to print out all paths from root to all child nodes:

NOTE: ***I wanted to come up with a solution that does not involve passing state between recursive calls.***

```
    a
  / | \
  b c  d
 / \    \
e  f    g
      / / | \
      h i j k

```

This is the my code to create and print the paths.

```
class Node:
    def __init__(self, data, children=[]):
        self.data = data
        self.children = children

tree = Node(
    "A",
    children=[
        Node("B", children=[Node("E"), Node("F")]),
        Node("C"),
        Node("D", children=[Node("G", [Node("H"), Node("I"), Node("J"), Node("K")])]),
    ],
)

```

i want to enumerate all the paths to reach from root node to all leaf nodes.This is what i have come up with.

```
def paths(root):
    x = []
    if root.children:
        for c in root.children:
            for el in paths(c):
                x.append(c.data + el)
    else:
        x.append("")
    return x

a = paths(tree)
print(a)

```

i get this output:

```
['BE', 'BF', 'C', 'DGH', 'DGI', 'DGJ', 'DGK']

```

This is partially correct, what is missing is the root node 'A' in all the paths, I am not able to think how to get that, even after thinking for 2 hours straight. I know why is it happening(because I start from child nodes of the root). what i cannot get is how to encode the root node itself.

**I hope this pseudocode is clear:**

```
function paths(N):
  path <- empty list
  if the node(N) has children
     for every child node `(C)` of `N`
        for every path `(P)` in paths(`C`)
           add to path <- `C.data` + `P`
   otherwise
      add to path <- + ""
   return path

```

# Answer
The problem is that each node is adding its children to the list of paths. Instead, you can modify your recursive function so that each node only adds itself.

That is, $paths(v)$ returns a list $L\_v$ of all paths from $v$ to the leaves of the subtree rooted in $v$.

If $v$ is a leaf, then the list $L\_v$ returned by $paths(v)$ contains a single path consisting of $v$ itself.

If $v$ is not a leaf and $u\_1, \dots, u\_k$ are its children, then $paths(v)$ returns the union of $k$ lists $L'\_{u\_1}, \dots, L'\_{u\_k}$, where $L'\_{u\_i}$ is obtained by prepending $v$ to every path in $L\_{u\_i}$.
> 1 votes

---
Tags: trees, python
---


# Question
Title: Is there a computer which can simulate all computers?
I have looked for proof that a machine cannot compute itself in more than realtime (Which would allow infinite computing speed) and I came to the conclusion that it is impossible for any computer to simulate all other computers. However, I lack proof of this intuition.

So the idea is that the state of every (modern, non-quantum) computer can be represented as a finite bitstring (just every state of registers, memory cells, and hard-drive...). However, in order to predict what this computer would do given any state, you would need a longer or at least equally long (in some trivial cases this might work) bitstring. But since there is always a bigger computer (with a longer bitstring - representation) there is no computer which can compute all computers.

However, I am wondering about the following:

Let $f$ be a function which maps a computable function $g$ and a valid input $i\_g$ of that function $g$, to the result of $g$ given $i\_g$:

$$f(g,i\_g) = g(i\_g)$$

Can you proof that:

$$\exists i\_f: f(f, i\_f) \mbox{ does not halt, while } f(i\_f) \mbox{ does.}$$

Note that $i\_f$ is just a bitstring, and $g$ can be represented by a program and therefore can be a bitstring too...

# Answer
I think you're looking for Stephen Wolfram's principle of Computational Irreducibility, which applies not just to simulating computers but simulation of any physical process that is computationally irreducible. It suggests that you can only simulate a computer in real time with an equally powerful or more powerful computer. I'm not aware if there are any mathematical proofs of this principle but this paragraph from his 1984 paper seems applicable:

> One expects in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, so that they can simulate any physical system. This is the case if in all physical systems there is a finite density of information, which can be transmitted only at a finite rate in a finite-dimensional space. No physically implementable procedure could then short cut a computationally irreducible process.

See also the full paper or the definition of computational irreducibility.
> 1 votes

# Answer
Your intuition sounds wrong to me. It's not surprising you couldn't prove it, because it isn't true. Roughly speaking, it is possible to find a computer that can simulate all other computers.

A universal Turing machine can simulate any other Turing machine, and can be used to simulate any other program in any Turing-complete language. Thus, there is a reasonable sense in which it can simulate all other computers, if we make precise what we mean by "computers" in a particular way (e.g., if we accept the Church-Turing thesis).

If you want to know whether it is possible to simulate another computer *and* also do it faster, that's a different matter. You'd have to formalize what you mean by "faster" to make that question well-defined.

Your question at the end of the post is not well-formed; computability is a property of languages, not of a single value (like $f(f,i\_f)$). Also, you defined $f$ to be a function of two arguments, so $f(i\_f)$ doesn't type-check.
> 20 votes

# Answer
You are using intuition about real computers and trying to apply it to Turing Machines. Real computers have limits that Turing Machines do not.

When it comes to Turing machines, the increase in the size of the data set is not an issue. A Turing machine has an infinitely long tape, so adding a finite amount of extra data to it is no problem. All you need to do is show that for any given Turing Machine, there exists a "reified" version which encodes the rules of the original machine as data on the tape. This was proven by Alan Turing.

When it comes to *real* machines, which have finite limits, the story is much more complicated. For starters, no real computer is actually Turing Complete. They are actually finite automata, limited by things like memory. The "Turing Completeness" of real computers really argues that the abstract instruction set is theoretically unbounded (for example, you could hook it up to a tape drive of arbitrary length).

When you look at this different domain, the story fits more with your intuition. Computers tend to be unable to run faster than themselves. However, there is a devil in the details of how you define this. Optimization creates really complicated corner cases. For example, if I consider the loop in C++:

```
int m = 0;
int n = 0;
for(int i = 0 ; i < 1000000000; i++) {
    for (int j = 0; j < 1000000000; j++) {
        for (k = 0; k < 1000000000000; k++) {
            n = n + 1;
        }
    }
}
std::cout << "M is " << m << std::endl;

```

It would take a very long time for the computer to "run" this. It has to do a giant nested loop which takes a long time. However, if we reify this, permitting the computer to effectively look at the source code (or machine code, or whatever), its easy to see that that big loop does not affect the value of m. We can skip the loop entirely.

The ability to do this is at the root of all compilers. And, indeed, it gets done at runtime as well. Consider the java code

```
int sum = 0;
for (int i = 0; i < myArray.length; i++) {
    sum += myArray[i];
}

```

By the rules of the language, we are obliged to check that myArray\[i\] does not access a value past the end of myArray. We are supposed to check it every time. However, this is slow. So most java runtime environments are smart enoguh to recognize the bytecode emitted by the sort of pattern and only do the array length check once. Thus we have a case where simply executing the byte code as written is slower than reifying it into instructions, analyzing them mathematically, and emitting a new "faster" program.

Of course, its trivial to show that there must be at least one program which is as-fast-as-possible.

While I wont get into the details of it, microprocessors do this as well. No processor currently produced *actually* runs x86 or x64 instructions. x86 is an abominably slow instruction set. Instead, they all analyze the x86 instructions and emit "microcode" which is much faster to execute. For example, the microcode can show opportunities to pipeline which aren't always valid for a string of instructions, but can be shown to be valid for this one.
> 1 votes

# Answer
This depends on the parameters of the question asked. If you are talking about Turing Machines, then:

* Any Turing machine can be represented as a bitstring (as you know). The description of the Turing machine is equivalent to the description of the program (code and state) currently running on that Turing Machine.
* Any set of inputs can be represented as a bitstring (obviously)

Therefore, any Turing machine can indeed simulate any other Turing machine: Simply copy the code, state, and inputs for the current program from one Turing machine to the other, done.

There are a couple variations on this question that complicate issues, and it seems like you might be asking about one of these variations:

1) Rather than Turing machines, which are a theoretical construct which does not actually exist (since the material to construct a real Turing machine would be potentially infinite and there are not infinite atoms in the universe), use a real-life "computer", as we understand it. In particular, a "computer" can be modelled as a RAM (Random Access Memory) bitstring and a ROM (Read-Only Memory) bitstring; the RAM is the state and inputs, the ROM is the code. Indeed, one computer could simulate another computer simply by copying the RAM and ROM from one machine to another. The problem is that a computer has a fixed maximum size of RAM and ROM based on the materials used in construction. Since technology is continuously improving, it is reasonable to suppose that there will never be a machine which can simulate any arbitrary machine, because that machine would need to have more RAM and/or ROM capacity not only than any machine ever created, but also will ever be created, and that's (probably) impossible.

2) A Turing machine which not only can simulate ANY other Turing machine, but also can simulate EVERY other Turing machine. Like, all at once. That is not possible, as follows:

Any Turing machine can be described by a bitstring, as we know. The bitstring is of arbitrarily long but finite length (it is both required and important that the description of a Turing machine is finite). However, these are the only restrictions on the description of a Turing machine; in particular, the set of possible representations of possible Turing machines is infinitely large. Therefore, the bitstring representation of a Turing machine that can represent the infinitely large set of all Turing machines must be an infinitely long bitstring (due to information theory). This violates the premise above that all Turing machines must be representable by a finitely long bitstring.
> 0 votes

---
Tags: computability
---


# Question
Title: The total length of input to a pushdown automata which accepts by empty stack is an upper bound on the number states and stack symbols
I was going through the classic text *"Introduction to Automata Theory, Languages, and Computation" (3rd Edition) by Jeffrey Ullman ,John Hopcroft, Rajeev Motwani*, where I came across few statements about a pushdown automata (PDA) which accepts by empty stack, as:

***1. $n$, the total length of the input, is surely an upper bound on the number of states and stack symbols.***

***2. One rule could place almost n symbols on the stack.***

The following statements were made while the authors were about to make some notes about the decision properties of CFLs(Context Free Languages)

Now here are some points by which I am possibly able to contradict the claim rather than proving it correct.

1. Suppose $n$, is the total length of the input, but as per the design of the PDA it might so happen that to accept the input string all the states of the PDA is not involved, so by this we can't say that $n$ is an upper bound on the number of states the PDA has.
2. Though the PDA accepts by empty stack, it might so happen that a transition function adds more than $n$ elements on the top of the stack, but at the end on consuming the $n$ input symbols we can stay on the particular state and use epsilon transitions to just remain in the same state and pop the elements from the stack till it becomes empty. So how can we say that $n$ is an upper bound on the number elements on the stack? We arrive at a contradiction...

I don't understand where I am making the mistake, because the same statements are written in the 3rd edition of the book without any changes being made from the second edition which makes it probable that the statement is correct.

I have attached the corresponding portion of the text below:

# Answer
That section is not talking about parsing. The algorithms referred to are algorithms for converting between CFGs and PDAs of different types. The question is, as usual, "what is the computational complexity of the algorithm", and the response is, as usual, expresseded in terms of the size of the input -- *to the algorithm*.

The input to an algorithm which converts a PDA to a CFG is the PDA, and the size of the input -- the metric stick for the algorithm's complexity -- is the size of the \*PDA". That's what the authors intend *n* to be.

How does one measure the size of a PDA? Simple: you write the PDA out as a string in some PDA definition language, and count symbols in the description. That's a completely fair procedure, because in order to call the conversion algorithm on the PDA, it's necessary to give the converter an input which represents the PDA.

Given that definition, the claims are not at all surprising. Every state and every alphabet symbol must be present at least once in the PDA description, so the size if that description is an upper bound. Similarly, it is possible that most of the description of the PDA is the description of a single rule, which could push almost `n` symbols.
> 2 votes

---
Tags: formal-languages, automata, context-free, pushdown-automata, upper-bound
---


# Question
Title: ip/tcp packet decoding without wireshark
How can we manually read and interpret packets properly without using wireshark?

Now from the Ethernet header I know that the Destination MAC Address should be at the 5th byte (after converting bits/bytes). So from this data, I thought it would be 4a onwards. However, in reality it's `00:17:f2:d0:4c:82`.

Same goes for the IP source destination. For instance, the source should be at 13-16 bytes. According to the readings, I guess it should be `0800` onwards. But in reality, it is on `0a 32 e7 85` but I don't get why? I am just confused on how to interpret this data correctly or maybe I am understanding the general header structure incorrectly.

https://ntquan87.wordpress.com/2015/08/17/reading-packet-hex-dumps-manually-no-wireshark/

# Answer
My guess is that what you are seeing is a Level 2 Ethernet frame and therefore the preamble is missing. Also the Ethernet checksum seems to be missing. In this case everything seems to line up (the packet type inside the Ethernet frame, the IPv4 version, the IPv4 packet length, the packet type, i.e. TCP, inside the IP packet, ...). Then you'd read your packet as in the picture.

The TCP payload is

```
474554202f20485454502f312e300d0a
557365722d4167656e743a2057676574
2f312e31312e340d0a4163636570743a
202a2f2a0d0a486f73743a207777772e
696574662e6f72670d0a436f6e6e6563
74696f6e3a204b6565702d416c697665
0d0a0d0a

```

and decodes to:

```
GET / HTTP/1.0
User-Agent: Wget/1.11.4
Accept: */*
Host: www.ietf.org
Connection: Keep-Alive

```

which is coherent with the fact that the destination port is 80.
> 5 votes

---
Tags: computer-networks, communication-protocols, bit-manipulation, tcp, ip
---


# Question
Title: Would a sparse NP-Complete language imply L = NP?
Would a sparse NP-Complete language imply L = NP?

**Update: Thanks to Noah Schweber for clear and comprehensive answer. Having thought about it more, one would need a logspace reduction from NP-complete to L-complete for NP=L. \[4\] below does not directly address this.**

Here is my proof attempt:

\[1\] Assume there exists a (sparse NP-Complete language).

> Mahaney's theorem is a theorem in computational complexity theory proven by Stephen Mahaney that states that if any sparse language is NP-Complete, then P=NP.

https://en.wikipedia.org/wiki/Mahaney%27s\_theorem

\[2\] In other words, (sparse NP-Complete language) implies (P = NP).

\[3\] From \[1\] and \[2\] (P = NP).

\[4\] (P = NP) implies (P-complete = NP-complete).

\[5\] From \[3\] and \[4\] (P-complete = NP-complete).

\[6\] From \[1\] and \[5\] there exists a (sparse P-Complete language)

> In 1999, Jin-Yi Cai and D. Sivakumar, building on work by Ogihara, showed that if there exists a sparse P-complete problem, then L = P."

https://en.wikipedia.org/wiki/Sparse\_language

\[7\] In other words, (sparse P-complete problem) implies (L = P).

\[8\] From \[6\] and \[7\] (L = P).

\[9\] From \[3\] and \[8\] (L = NP).

# Answer
> 5 votes
Your claim \[4\] is wrong - the issue is with the term "$X$-complete" for a complexity class $X$.

Stricly speaking, barring specific convention the phrase "$X$-completeness" doesn't pin down a single notion: we also need to specify the **reducibility notion** involved. For example, Cai/Sivakumar look at P-completeness with respect to **logspace** and **NC** many-one reductions, while "NP-complete" refers to **polynomial-time** many-one reductions. Changing the reducibility notion changes the completeness (and hardness) notion - for a silly example, everything in P is NP-complete with respect to exponential-time Turing reductions.

So the implication "P=NP implies P-complete=NP-complete" is a non-sequitur, since the implicit reducibility notions are different. P=NP **does** imply (say) "P-complete w/r/t logspace reductions = NP-complete w/r/t logspace reductions," but that's a completely different thing.

---
Tags: np-complete, p-vs-np
---


# Question
Title: Grammars and Parsing: Ambiguity in Sequences
**BACKGROUND**

I am writing a grammar and parser for a domain-specific language. There is a specific form of expression that, while simple, is giving me headaches.

Given terminals:

* "a": KEYWORD
* "b": INTVAL
* "c": DECVAL
* "d": STRVAL

Given rules:

* "E": VALUE \<- INTVAL
* "F": VALUE \<- DECVAL
* "G": VALUE \<- STRVAL
* "H": VALUES \<- VALUE
* "I": VALUES \<- VALUES VALUE
* "J": LINE \<- KEYWORD VALUES

Not complicated, right? This specific subset of terminals and rules should be able to parse the following line:

* KEYWORD DECVAL DECVAL DECVAL DECVAL

In other words, a keyword followed by one or more values should be a grammatically-correct line. DECVAL tokens should reduce to VALUE tokens, which are in turn aggregated into a series of VALUES, at which point the line reduces under rule "J".

**PROBLEM**

However, consider the following parse state, after the first two tokens have been shifted and the lookahead is the next DECVAL:

* KEYWORD DECVAL | DECVAL

This is a shift-reduce conflict, because it could shift the lookahead DECVAL under rule "F" or reduce the DECVAL on top of the stack under the same rule ("F"). By default, most parsers will perform the shift--in which case the series will never reduce because there is a DECVAL too "deep" on the stack.

**QUESTION**

But how would you (for example) define a precedence in such a way as to indicate a specific rule should reduce when in conflict with itself? Is that even a good idea? Based on my own limited understanding, there should be a way to restructure the grammar rules, right? But it's not obvious to me what that is.

# Answer
> 0 votes
This parser state

```
KEYWORD DECVAL DECVAL
               ^
               |---------- Lookahead

```

is not a conflict because a shift action is not possible. There is no production in which A `DECVAL` follows another `DECVAL`. There is not even a production in which a `VALUE` follows another `VALUE`. Before the lookahead `DECVAL` can be shifted, the `DECVAL` at the top of the stack must be reduced to something which can be followed with `DECVAL`.

---
Tags: formal-grammars, compilers, parsers
---


title: Bipartite Graph in a Digraph

text:
# Question
Title: Bipartite Graph in a Digraph
How do you find a sub-digraph in a digraph such that the in degree and out degree of each vertex is 1. My professor told in the class that an algorithm can be build for it using bipartite matching but I have not able to do so. I am just looking for hints on how to proceed because I am kind of stuck on where to start.

# Answer
> 1 votes
Any simple cycle satisfies the conditions, so you can use any standard algorithm for finding cycles in a directed graph.

For example: decompose into strongly connected components. Pick one component. Start following an arbitrary walk through vertices within that component. As soon as you hit a vertex the second time, you can construct a cycle.

---
Tags: bipartite-matching, bipartite-graph
---


# Question
Title: How to write suitable three address code for switch-case statements?
I want to translate a java switch-case statement to intermediate representation of the three address code form. Three address code or TAC is a form of intermediate representation where each instruction contains at most three addresses and one operator. An address is a name such as x (stored in the symbol table), compiler generated temporary such as $t\_{1}$ or a constant such as 3.14 or ‘s’. A name could refer to a variable, label, etc. If you have an arithmetic statement

> (3 * w) + y

then the corresponding TAC would be

> $t\_{1}$ = 3 * w
>
> $t\_{2}$ = $t\_{1}$ \+ y

Now, when it comes to switch statements, my textbook (the Dragon Book for Compilers), gives a translation of this form:

for a switch-case statement of this type:

switch E

case V1: S1

...

case Vn-1: Sn-1

default: Sn

Assuming the first translation is used, at the code generation stage (when we convert 3AC to machine code), the code generator will interpret the instructions as a sequence of conditional and unconditional jumps with intervening labeled statement blocks. It would translate them into the machine code (say x86) version of the same. When these instructions are executed by the processor, it handles each jump sequentially to determine the correct labeled block to be executed. But, I have also read that the machine code translation of a switch-case statement includes a jump table that allows the processor to execute the entire switch statement in one go. So, then which version is used?

I wanted to post this on stackoverflow but I do not have enough reputation to post an image.

# Answer
Some more things to look at:

First, mixed table/branch approach. Say you have cases 1, 2, 3, 4, 5, 6 and 999,999,999. You might check for 999,999,999 first, then use a table for the rest. And remember for the table approach that you need to check if the case is within the table. So take a table for 0-5, compare if case ≥ 6, if not you use the table, if yes, you handle the remaining case.

Second, probably most important: Binary search. Say you have cases 1-20. First you compare against 10. Branch to a second compare block if the case is \>10. That alone halves the average number of comparisons needed.

Third, take advantage of one comparison usually giving multiple results. If you know that x = 1, 2 or 3, then you need only one comparison with 2 and two conditional branches.
> 2 votes

# Answer
Both translations are valid. There's no way to answer - the compiler will choose one, using whatever strategy it uses. It is typical for a compiler to choose between those two options based on performance considerations, using some heuristics to try to predict which will perform better.
> 1 votes

---
Tags: compilers
---


# Question
Title: Partitioning connected graphs in the plane
This is a geographic problem, where we have several connected graphs embedded on the plane, where none of them have overlapping edges/nodes.

How can we divide the plane using line segments in such a way that each subdivision contains exactly one connected component?

I was thinking of generating a voronoi diagram using the endpoints, but this presents some issues:

1. Long edges are not guaranteed to be in the correct partition.
2. The border becomes very complex (There is a separate line segment for most points)

Is there an algorithm that creates less complex borders?

The input would be a planar graph with multiple connected components, where each node has coordinates associated to it.

The output would be a subdivision for the bounding box given by the graph, which divides the plane using line segments.

Example solution using red lines  I'm looking to minimize the amount of line segments required, but optimality is not required.

# Answer
> 1 votes
This is not a full answer to your question, but at least you'll have something working.

**Step 1.** Calculate minimal bounding axis-aligned boxes for each connected component, and also a minimal "outer" bounding box for all the components.

**Step 2.** Try to split the outer bounding box by horizontal or vertical segment in such a way that this segment doesn't intersect with any bounding boxes for components - this can be done by analyzing coordinates of bounding boxes only. If that is not possible then split the outer box in halves horizontally or vertically. After splitting recalculate bounding boxes for components which were split as well.

**Step 3.** Repeat the Step 2 recursively for each box, which contains more than one component.

**Step 4.** After the Step 3 you'll have a partition of the original outer box into rectangles, each of which contain only one connected component (or part of it). Remove all the edges in this partition, for which both adjacent rectangles contain the same component. After this step you'll have a partition of the outer box, but it won't be a optimal one, and it'll consist of axis-aligned segments only.

**Step 5.** Amend the partition, replacing axis-aligned segments by arbitrary segments, trying to minimize the total number of segments - *I don't know how to do that regularly for now*.

# Answer
> 0 votes
What about taking the convex hull of every connected component?

The two operations you can do after this is :

1. There are 2 convex hulls but these components can be divided by a single line
2. The convex hulls of 2 separate connected components intersect

For (1), we can take the centre of both of the convex hulls, draw a line joining them (call it AB). A line that passes the midpoint of AB should be able to separate them.

For (2), Say line AB and CD intersect at X. AB is the line in hull 1, CD is the line in hull 2.

Now there are a couple of scenarios here: 1. AB and CD crosses such that the point B is inside hull 2 and point D is inside hull 1 (imagine 2 rhombuses (diamonds?) coming together from the corners to form a tinier rhombus). In this case, add B to hull 2 and add A to hull 1. Note that now the hulls will no longer remain convex. 2. AB and CD crosses such that the point B remains inside hull2 but neither C nor D is inside hull 1 (imagine a line cutting off a corner). Again in this case, just add point B to hull2 (thereby making hull2 lose its convex property)

And repeat for all line segments until it converges.

Or something of this sort..

# Answer
> -2 votes
I'm not sure what "connected" here mean?

-If it means fully connected then that's finding cliques (a problem widely known to used in GIS applications)

-If it's just connected somehow (not indep vertices), then what D.W. clearly implying in his comment is the min-cut problem (ur lines r all zero cuts no edges passing through them) \*** added 17/4/2020 This Q is dated to Mar 2019, Who brought it into top after one year. I don't like this, I feel deceived and questioning credibility. –

---
Tags: computational-geometry
---


# Question
Title: How to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages
I think this is a basic topic in complexity, but I would like to ask how to understand co-$\mathcal{L}$ where $\mathcal{L}$ is a class of languages. From the definition of my textbook, $$co-\mathcal{L} = \\{ \overline{L} \mid L \in \mathcal{L} \\}$$

and where $\overline{L}$ is the complement. From what I read in an earlier part of my textbook, the complement of $L$ is equal to $\Sigma^\* - L$.

However, say that $\mathcal{L}$ is NP. An instance of a language $L$ that is in $\mathcal{L}$ is the set of graphs with Hamiltonian paths. However, in this case, its complement $\bar{L} \in$co-$\mathcal{L}$ is the set of graphs without Hamiltonian paths, i.e. $\bar{L} \in $co-NP.

But is the set of graphs without Hamiltonian paths equal to $\Sigma^\* - L$ (following the definition of complement) ? In this case, we would be including some strings $\in \Sigma^\* - L$ that do not represent graphs.

Another example is $A\_{TM}$, which represents the language

$$\\{\langle M,w\rangle \mid M \text{ accepts input } w \\}$$

In this case, does $\overline{A\_{TM}}$ represent $\Sigma^\* - A\_{TM}$?. If this is the case, we would be including in $\overline{A\_{TM}}$ several strings that do not represent TM's, or that refer to other input that is not equal to $w$. Or rather, does $\overline{A\_{TM}}$ represent the language

$$\\{\langle M,w \rangle \mid M \text{ diverges on input } w \\}$$

# Answer
We typically think of instances to problems as being in some format. There are several ways to think of this. Consider for example $A\_{TM}$, in which the input is a pair $\langle M,w \rangle$. The three most obvious are:

1. Every input string can be decoded into an input pair $\langle M,w \rangle$.
2. Inputs not of the form $\langle M,w \rangle$ don't belong to the language.
3. We think of $A\_{TM}$ as a promise problem: inputs $\langle M,w \rangle$ where $M$ accepts $w$ are Yes instances, inputs $\langle M,w \rangle$ where $M$ doesn't accept $w$ are No instances, and we don't care about other inputs.

If you take complementation, here is what you get under each interpretation:

1. $\overline{A\_{TM}}$ consists of all inputs strings which, when decoded to $\langle M,w \rangle$, are such that $M$ doesn't accept $w$.
2. $\overline{A\_{TM}}$ consists of inputs not of the form $\langle M,w \rangle$, and of those of the form $\langle M,w \rangle$ such that $M$ doesn't accept $w$.
3. $\overline{A\_{TM}}$ is the promise problem corresponding to option 1.

While these different interpretations look different, in practice the difference is very slight, given that it is easy to recognize that the input is of the correct format. For example, given interpretation 2, consider the following two languages: $\overline{A\_{TM}}$, and $\widetilde{A\_{TM}}$, the language of all pairs $\langle M,w \rangle$ such that $M$ doesn't accept $w$. These two languages differ in malformed inputs, that is, outputs not of the form $\langle M,w \rangle$. Since such inputs are easy to detect, we have an algorithm for $\overline{A\_{TM}}$ iff we have one for $\widetilde{A\_{TM}}$, and furthermore, the complexity of both algorithms is very similar.

For this reason, we typically ignore such issues, and implicitly work under the "promise problem" interpretation: the input is assumed to be of the form $\langle M,w \rangle$. Purists can think of the first interpretation instead, which from this point of view behaves identically.

More generally, whatever interpretation you choose, you still formally have to describe what encoding is used for $\langle M,w \rangle$. We typically don't bother, since all reasonable interpretations are inter-reducible, and so don't change the computability or complexity of the problem. That said, the difference between weak NP-hardness and strong NP-hardness lies exactly in which input representation is being used.
> 3 votes

---
Tags: complexity-theory, np, complexity-classes
---


title: Saturated sets in bipartite graph

text:
# Question
Title: Saturated sets in bipartite graph
Let $G=(X\cup Y, E)$ be an unweighted bipartite graph. We are given that for every $W\subseteq X$ it holds that $|W|\leq |N(W)|$, where $N(W)$ is the *neighborhod* of $W$ in $Y$ (aka Hall's marriage condition).

My goal is to find a subset $W^\*\subseteq X$ with $|W^\*| = |N(W^\*)|$, if such a subset exists (obviously it need not exist). Since I'm not aware of a formal name for this property, I'd refer to such a $W^\*$ as a *saturated set*.

Questions:

1. Is this property widely known? Does it have a different name?
2. Assuming the marriage condition holds, it is straightforward to show that every union of saturated sets is also saturated. One interesting problem is to find the maximum saturated set. I describe below a somewhat naive solution with runtime $O(|V|\cdot |E|)$, but I suspect it can be solved even faster. Any idea?
3. Allegedly, a weakly easier problem is to find *a saturated set*, not necessarily the maximum one (again, assuming the marriage condition holds). Can we solve this problem faster than $O(|V|\cdot |E|)$?

---

**Edit:** Here's a sketch for the algorithm I mentioned above: Assume the marriage condition holds for $G$. Then, as said, with a bit theory work we can show that

Lemma: Let $G$ be a bipartite graph satisfying the marriage condition. Then, every union of saturated sets is also saturated.

The Lemma suggests that there exists a unique maximum saturated set. The question can hence be stated differently:

> *Given a node $x\in X$, determine whether it participates in a saturated set or not*.

If the answer is yes, then it also participates in the maximum saturated set. The pseudo algorithm goes as follows:

1. Run the Hopcroft–Karp algorithm to find a maximal matching $M$ that covers $X$ in $O(\sqrt {|V|}|E|)$ time. Such a matching exists due to the marriage condition.
2. For every node $x\in X$,
    * Temporarily add a node $x'$ to $X$, which is connected to every neighbor of $x$. Call the graph we obtain $G\_x$.
    * Notice that $M$ is a partial matching of $G\_x$ that is almost maximal (up to one edge); thus, we can find a maximal matching $M\_x$ for $G\_x$ by finding an augmenting path in $G\_x$, in $O(|V|+|E|)$ time (same details as in Hopcroft–Karp).
    * If $|M|\<|M\_x|,$ continue. Else, if $|M|=|M\_x|$, add $x$ to the returned set.

The analysis follows from first principles. If there exists any saturated set $W\subseteq X$ with $x\in W$, i.e., $|W|=|N\_G(W)|$ then $$ |W\cup \\{x'\\}|=|W|+1 = |N\_G(W)|+1=|N\_{G\_x}(W)|+1, $$ so $W\cup \\{x'\\}$ violates the marriage condition in $G\_x$. Consequently, $|M|=|M\_x|$. We can analogously show that if $x$ does not participate in any saturated set, then $|M\_x|=|M|+1$.

# Answer
Let's fix a maximal matching $M$. Let $Z\subseteq Y$ be the set of nodes that are not matched to nodes in $X$. We can see a node $x\in X$ belongs to a saturated set if and only if there does not exist an alternating path from $x$ to a node in $Z$, i.e., a path $xy\_1x\_1\cdots y\_kx\_kz$ where $(x\_i,y\_i)\in M$ and $z\in Z$ (the proof is similar to the correctness proof of your algorithm).

So you can add directions to all edges in $E$ such that edges in $M$ have the direction from $X$ to $Y$ while edges not in $M$ have the direction from $Y$ to $X$, then the nodes in $X$ that are not reachable from any node in $Z$ make up the maximal saturated set. You can run a simple BFS to see which nodes in $X$ is reachable from nodes in $Z$. The time complexity is $O\left(\sqrt{|V|}|E|\right)$.
> 3 votes

---
Tags: algorithms, graphs, bipartite-matching, bipartite-graph
---


title: Delaunay to Voronoi ... and back?

text:
# Question
Title: Delaunay to Voronoi ... and back?
Learning about Voronoi Diagrams, one quickly finds out that Delaunay Triangulations are clearly the easiest way to generate them from a set of points.

How about the other way around? Given a subdivision of (2D) space, how to determine unknown generators? Are there any common ways to do this?

Things I could think of were, assuming an underlying Delaunay triangulation, equal distances to Voronoi Vertices/"Delaunay Circumcenters", resulting in a system of quadratic equations.

Or searching for circles in the graph given by the Voronoi Vertices, and determining the center of the resulting polygons.

There is also a relationship to k-means clustering, as clusters defined by k-means, being the generators, yield a Voronoi Diagram in turn. This would leave me having to determine k and populate the regions with elements that are precisely not equidistant to two means.

I feel likely to be missing something very obvious and I would be happy for any direction in which to get started.

# Answer
> 2 votes
Unfortunately, you cannot generally reconstruct the generators from Voronoi polygons. Look at the four simple examples below: all have the same two Voronoi cells but different placement of the generators.

---
Tags: computational-geometry, voronoi-diagrams
---


# Question
Title: Minimal number of changes to make string into concatenation of $k$ palindromes
The following question is taken from leetcode: 1278. Palindrome Partitioning III

> You are given a string $s$ containing lowercase letters and an integer $k$. You need to:
>
> 1. First, change some characters of $s$ to other lowercase English letters.
> 2. Then, divide $s$ into $k$ non-empty disjoint substrings such that each substring is a palindrome.
>
> Return the minimal number of characters that you need to change to divide the string.

So I did find the cost array to make a string to a palindrome. Something like below:

\[('bcccdefg', 4), ('ccde', 2), ('ccdef', 2), ('ef', 1)\] # (character, cost to make it a palindrome)

I am thinking whether this can be done using knapsack recurrence relations, where profit will be cost and weight will be length of the substring; the total backpack weight will be the length of the main string. Though I am not sure what to do with $k$. Do I need 3 states, or are 2 states enough?

Is my thinking correct? If no, what is the right way to write a recurrence relation for this?

# Answer
Let $s=s\_1 s\_2 \dots s\_n$. Suppose that you already know, for each substring $s\[i:j\]=s\_is\_{i+1}\dots s\_k$ of $s$, the minimum number $D(i,j) $ of character substitutions needed to make $s\[i:j\]$ palindrome. These values can be found in $O(n^2)$ time using dynamic programming since $D(i,j) = 0$ if $i\>j$ and $D(i,j) = D(i+1,j-1) + \mathbb{1}\_{s\_i \neq s\_j}$ if $i \le j$.

Your problem exhibits the optimal substructure property. Suppose that you already known the beginning position $i$ of the last substring $s\[i:n\]$ of $s$ in an optimal partition: clearly you will need to make $D(i,n)$ changes in order to transform $s\[i:n\]$ into a palindrome. You are then left with the prefix $s\[1:i-1\]$ of $s$. This prefix still needs to be partitioned into $k-1$ nonempty substrings that are palyndromes. Fortunately this is exactly an instance of the problem you were trying to solve in the first place. You can exploit this property as follows:

Define $OPT\[j,h\]$ as the minimum number of character substitutions needed in order to partition $s\[1:j\]$ into $h$ substrings, each of which is non-empty and palindrome. If no such partition can exist, regardless of the number of character substitutions, let $OPT\[j,h\]=+\infty$.

By definition $OPT\[0,0\]=0$ (since $s\[1:0\]$ is the empty string) and, for $h=1,\dots,k$, $D\[0,h\] = +\infty$.

Moreover, for $i=1,\dots,n$ and $h=1, \dots, k$: $$ OPT\[j,h\] = \min\_{i=1,\dots,j} \left\\{ OPT\[i-1,h-1\] + D(i, j) \right\\}. $$

This gives you a dynamic programming algorithm with time complexity $O(k n^2)$. The optimal solution to your original problem is $OPT\[n,k\]$.
> 1 votes

---
Tags: dynamic-programming, recurrence-relation
---


# Question
Title: What is the time complexity of this piece of code?
```
def find_perms(s):
    """
    Finds permutations of the given string.
    >>> find_perms("abc")
    ['cab', 'acb', 'abc', 'cba', 'bca', 'bac']
    """
    if len(s) == 1:
        return [s]
    elif len(s) == 2:
        return [s[0]+s[1], s[1]+s[0]]
    else:
        perm = find_perms(s[0:len(s)-1])
        last_char = s[len(s)-1]
        lst = []
        for strings in perm:
            for index in range(len(strings)+1):
                string = strings[:index] + last_char + strings[index:]
                lst.append(string)
        return lst

```

I am trying to figure out the time complexity of this piece of code as I'm working on studying coding questions and their time complexity and I managed to solve this permutation problem using recursion as was required but I am wondering how do I accurately determine the big-$O$ time complexity for this as it is a mix of recursion followed by an iterative loop. I would really appreciate some helpful input on this.

# Answer
> 0 votes
Let $f(n)$ be the answer for an input of size $n$. then we have the following equation:

$f(n) = f(n - 1) + (n - 1)! * n = f(n - 1) + n!$

That's because you call the function for an input of size $n - 1$ which gives $f(n - 1)$, then you iterate over all permutations of size $n - 1$ which there are $(n - 1)!$ such permutations, and then you iterate over the position of the new element, which there are $n$ such positions. This gives us:

$f(n) = \[\sum\_{i=1}^n i!\] \< (n + 1)!$

You can easily prove this by induction. So $f(n) = O((n + 1)!)$.

---
Tags: algorithm-analysis, time-complexity, recursion, big-o-notation, python
---


# Question
Title: Would the following grammar be ambiguous?
I have the grammar $S = aSbS|bSaS|\varepsilon$. When I was first looking at the problem I thought it was unambiguous. When I looked at the answer it said that it was ambiguous. The solution it gave was:

$S \rightarrow aSbS \rightarrow a\varepsilon bS \rightarrow a\varepsilon b\varepsilon \rightarrow ab$

$S \rightarrow aSbS \rightarrow aSb\varepsilon \rightarrow a\varepsilon b\varepsilon \rightarrow ab$

This doesn't make sense to me though because aren't these both producing the same parse tree?

# Answer
> 4 votes
Indeed, both of those derivations produce the same parse tree.

A grammar is ambiguous iff it has two different *leftmost* derivations for a sentence. (Equivalently, if it has two different *rightmost* derivations.) Only one of the provided derivations is leftmost, so these two derivations do not constitute a demonstration of ambiguity.

The grammar *is* ambiguous, though:

$$\begin{align}&S\to aSbS \to abS \to abaSbS\to ababS \to abab\\ &S\to aSbS \to abSaSbS \to abaSbS \to ababS \to abab\\ \end{align}$$

---
Tags: formal-grammars, parsers
---


# Question
Title: can we do binary search to solve quadratic equation?
Suppose i have a quadratic equation like this, `2x^2 - 4x - 5 = 0`, the solution here is x1=2.87 and x2=-0.87. I tried this python snippet to find the non-negative solution(2.87) by setting range 0 to 1000 and it worked but how to find the negative one too?. I tried the range -1000 to 0, but no luck!

```
def solve():
    low, high=0,1000
    while (high-low)>10e-5:
        x = (low+high)/2
        fx = 2*(x**2)-4*x-5
        if fx>0:
            high=x
        else:
            low=x

    return low

print(solve())

```

Or I am doing this whole thing wrong? ***What is the strategy to work with negative ranges and floating numbers in binary search?***

# Answer
> 1 votes
Consider the value of `fx` on line 6.

```
def solve():
    low, high=-1000,0
    while (high-low)>10e-5:
        x = (low+high)/2
        fx = 2*(x**2)-4*x-5
        if fx<0:
            high=x
        else:
            low=x

    return low

print(solve())

```

or

```
def solve():
    low, high=-1000,0
    while (high-low)>10e-5:
        x = (low+high)/2
        fx = 2*(x**2)-4*x-5
        if fx>0:
            low=x
        else:
            high=x

    return low

print(solve())

```

---
Tags: binary-search
---


# Question
Title: Constructing a data structure supporting prioritized key lookup
so this is more or less a shot in the dark as I am feeling stuck. Maybe some of you have an idea which helps.

Here is the problem description (pseudo formal):

I want to have a structure $T = \\{ \hat{x\_1}, \hat{x\_2}, ... \\}$ with $\hat{x\_i} = (p\_i, k\_i, v\_{k\_i})$.

$p\_i \in \mathbb{N}$ can be interpreted as an associated priority. They can be considered unqiue.

$k\_i \in \mathcal{K}$ a *key index*, $d := |\mathcal{K}|$ is not required to be negligibly small, though generally $d \lt\lt |T|$

$v\_{k\_i} \in \mathcal{V}^{(k\_i)}$ a partial key over some universe associated with the given key index. As a little pace killer, this key may not be hashable. The only requirement is totally ordered.

Considering an array $y = \[v\_i\], i \in \mathcal{K}$, the structure should be capable of supporting the following operations efficiently:

$lookup(T, y) \rightarrow \underset{x\_i \in T : y\[k\_i\] = v\_{k\_i}}{arg max}( p\_i )$, i.e. the node $\hat{x\_j}$ with a partial key matching and the highest associated priority.

$succ(T, y) \rightarrow lookup(T \backslash \\{\hat{x\_j}\\}, y)$, i.e. the successor (in terms of priority) of a node $\hat{x\_j}$ matching $y$

Ultimately I would also like efficient insertion and deletion (by priority).

(For insertion: The selection of $k\_i$ for each node is another point of research and can by chosen at the time of insertion. It is essentially possible that this key index is subject to change if it *helps* the overall structure. But it is also not required that all key indices in $\mathcal{K}$ are supported for each node, i.e. one might need to insert a node which is only queryable by a single $k\_i$.)

The key indices are somewhat causing a headache for me. My research so far includes standard priority search trees and dynamic variations thereof. I also found this very interesting, though very theoretical, paper which takes care of the increased dimensionality (kind of) caused by the d-dimensional keys.

I know that I can construct d-dimensional binary search trees with a query complexity of $O(d + n log(n))$. These should definitely yield a gain though I am not capable of mapping the priority problem to it (Ref).

But I guess the complexity can be reduced even further if we consider that fact, that each node is only storing partial keys anyway.

My approach so far is somewhat naive as it simply creates a hash map for each key index in $\mathcal{K}$ and queries each hash map upon lookup. It then aggregates all the results and sorts them by priority. This works fine for hashable keys but a fallback structure has to be used whenever they are not (I am using binary search trees).

**Edit:**

To clarify: I would like to find a solution which is sub $O(d log(n))$ for queries.

The successor problem can be solved in at least $O(d)$, even if using some kind of tree. See this resource for an overview.

# Answer
One approach is to use $d$ binary search trees, one tree per element in $\mathcal{K}$.

The tree for $k \in \mathcal{K}$ stores all items $\hat{x\_i} = (p\_i, k\_i, v\_{k\_i})$ such that $k\_i=k$, keyed on the value $v\_{k\_i}$.

To insert an item, insert it into the appropriate tree. This can be done in $O(\log n)$ time.

The lookup operation can be done by searching in each binary tree, and taking the best match. When searching in the tree for $k \in \mathcal{K}$, you search for the key $y\[k\]$. This takes $O(d \log n)$ time.

The successor operation can be implemented similarly to the lookup operation, and also takes $O(d \log n)$ time.

You can speed up the operations to take expected $O(1)$, $O(d)$, and $O(d)$ time (respectively) by replacing each binary search tree with a hash table.
> 1 votes

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


# Question
Title: Using Brzozowski's derivatives method to construct a minimal DFA
so I am currently learning about dfa and nfa and i came across the following question which requires me to use Brzozowski's derivatives method to construct a minimal DFA recognizing the language defined by the rational expression below. I am having quite a bit of trouble understanding how Brzozowski's derivatives works and how I would apply it to the expression below. Could someone please show me step by step how I would do it alongside and explanation.

What seems to be the main problem is that I am not sure how to derive the derivative such as `dR/da`.

```
X = (aa + b)* ab (bb)*

```

# Answer
> 4 votes
The Brzozowski derivative of a language $L$ with respect to a symbol $a$ consists of all words $w$ such that $aw \in L$.

In your case, $L$ is the language generated by the regular expression $X$. Instead of solving your exact exercise, I will show how to compute the other Brzozowski derivative, with respect to $b$. A word generated by $(aa+b)^\*ab(bb)^\*$ has the form $$ x\_1 \ldots x\_n ab (bb)^{2m}, $$ where $n \geq 0$, $x\_i \in \\{aa,b\\}$, and $m \geq 0$. The only way that this can start with $b$ is if $n \geq 1$ and $x\_1 = b$. Taking away $b$, we are left with $$ x\_2 \ldots x\_n an (bb)^{2m}, $$ a collection of words which is described by the regular expression $(aa+b)^\*ab(bb)^\*$, the same one we started with.

Computing the derivative with respect to $a$ is slightly more complicated since there are two different cases, but I'll leave you to ponder that.

You might have also learned some rules for computing the derivative. In that case, you can compute the derivative by applying them mechanically.

# Answer
> 0 votes
From the definition above also know that . Provide the simplified expressions \[R\]D ε = R for the following derivatives of : 0 ) 1R = ( +1 * A. \[R\] D1 B. \[R\] D10 C. \[R\] D11

---
Tags: finite-automata, regular-expressions, nondeterminism, computer-algebra
---


# Question
Title: Can a Turing Machine simulate every possible Turing Machine?
Related to my answer on this question, I'm not sure of a detail.

Assume you have a Turing Machine which simulates all possible Turing Machines all at once (meaning it does not "page" its data, i.e. it can't erase data from one "process" to write data from another "process"; it must keep all "processes" "in memory" at the same time). Then, this Turing Machine must simulate itself, because it is a Turing Machine and the definition of this machine is that it simulates all possible Turing Machines. It must also simulate the simulation of itself, and the simulation of that, and so on, infinitely recursive. Therefore, this Turing Machine must have infinite data on its tape.

My question is, can this Turing Machine exist, and why or why not?

# Answer
Your conclusion "this Turing Machine must have infinite data on its tape" is not accurate. Everything up to that point is basically fine, but that one statement is not correct.

Turing machines never have an infinite amount of data on the tape at any one time. At any point in time, they have a finite amount of data on the tape. However, this amount might increase over time without limit. That's not the same as saying that at any point the amount is infinite.

An analogy: imagine I start counting out loud 1, 2, 3, 4, 5, 6, etc., without ever stopping. At any point in time, the number I said aloud is finite. However, there is no fixed upper bound on these numbers; they increase without limit.

It's the same with such a Turing machine. Call this machine $M$. It simulates all Turing machines in parallel, but crucially, each simulation proceeds at a reduced speed. $M$ itself will be one of the machines being simulated, but at a reduced speed: say, 1000x slower (just to make up a number). So, $M$ is simulating $M$ running 1000x slower. That means it is also recursively simulating $M$ running 1000000x slower, and so on. (And because the simulated $M$ is running slower, it writes to the tape more slowly, so the size of the tape grows slower.)
> 5 votes

# Answer
What you describe is a standard technique in computability theory called dovetailing. At each step of execution, dovetailing only requires a finite amount of data to be stored on the tape.
> 4 votes

---
Tags: turing-machines
---


# Question
Title: What is the formalism to prove statements about uniqueness of functions with certain signatures
Suppose I want a function like

`f: ((A, B) -> C) -> A -> B -> C`

A statement I've often seen made is that f has just one implementation, namely the 'curry function', i.e. `g => a => b => g(a, b)`

Taken at face value this doesn't seem to actually be true, I can always define f as acting differently from this in special cases, e.g. I can say it is `g => a => b => g(a, b)` except when `A = B` and then I define it as `g => a => b => g(b, a)`.

Nonetheless, it's intuitively clear enough what is meant by 'has just one implementation'.

I would like to know the correct formalism in which statements like the above can be proven.

At a guess I would suspect it is category theory? The above feels a bit like the notion of a natural transformation, but I don't really see the details.

# Answer
I'm sure there is a connection to category theory, but you can actually do it with (what I consider to be ) a simpler tool: parametricity.

They basic idea is that, when a language has the property that polymorphic types do the exact same thing for each type they're instantiated to (i.e. there's no typecase construct), we can prove very powerful properties about the language, in the form of a logical relation.

This prevents exactly the "special case" implementation that you describe in your question. It's also worth mentioning that these implementations are all *extensionally* equal: they might look different but produce equal results for equal inputs. e.g. you can replace any term $t$ with $(\lambda x \ldotp x) t $ and get an equivalent function.

The statements about functions only from their type are generally called *free theorem*, named after the paper that introduced the idea: Theorems for Free by Phil Wadler. If you're interested in this area, I highly recommend the paper, since it's a good introduction to the subject.

The idea behind this actually goes much further back than that paper, to John Reynolds work with System F and the "abstraction theorem" but it took a while before the idea became popular.

You can actually generate free theorems at http://free-theorems.nomeata.de/, although it might take a bit of massaging to get useful information from the theorems they give there.

If you're interested in parametricity used to prove things other than free theorems, like type safe, then Amal Ahmed's thesis is the best introduction I've seen. She really does a good job of describing semantic types: the type of a program is actually a property of how it runs and what it produces, and what we call "types" are a syntactic approximation of these more general semantic types.
> 4 votes

---
Tags: type-theory
---


# Question
Title: How to prove quantum circuit identity in Qiskit?
I am working on a simple quantum circuit identity. I proved it on paper with the tensor product, but i'm having trouble showing that with qiskit. I know I need to measure them somehow but i don't know how. Can someone help? :)

# Answer
> 2 votes
You can check whether the unitary matrices are equivalent.

```
def circuits_equivalent(a, b):
    au = Operator(a)
    bu = Operator(b)
    return au.dim == bu.dim and np.allclose(au.data, bu.data)

```

---
Tags: circuits
---


# Question
Title: Algorithm to find array elements that a[i] > 2a[j] with i<j
Im trying to find an algorithm which returns array elements that a\[i\] \> 2a\[j\] with i \< j in O(nlogn). I can think how to implement this algorithm using double for but i cant implement it in O(nlogn). Does anyone have an idea about how to implement that?

# Answer
Hint: First, try to come up with an algorithm which counts number of inversions in a given array. There is a classical well-known algorithm for such problem.
> 0 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, time-complexity, data-structures
---


title: Simple pathes in an acyclic graph

text:
# Question
Title: Simple pathes in an acyclic graph
How to answer on many requests by type:

> Count amount simple paths passing through chosen edge in an acyclic undirected graph using dynamic programming?

# Answer
Since the graph is acyclic, we know that it is a forest - which means that, there is at most $1$ simple path between two nodes. Now, simply root the graph at one vertex of the edge, remove the edge, and run a dynamic programming algorithm to find the number of vertices in the subgraph, call it $v\_a$. Similarly, do the same for the other vertex of the edge, call it $v\_b$. The answer is $v\_a\*v\_b$, since the simple path between every $2$ nodes is a different simple path.

Proof: Clearly every simple path we consider passses through the chosen edge. The only other simple paths are the ones where both the nodes are chosen in the same subgraph, which clearly does not pass through this edge.
> 1 votes

---
Tags: graphs, dynamic-programming
---


# Question
Title: Understanding definition of NP and co-NP
From some of the texts I read, one definition of NP is: "An equivalent definition of NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine." and that we have the following, where $n$ is the length of the input:

$$ \text{NP}=\bigcup \text{NTIME}(n^k) $$

This means that one way a problem can be shown to be $\in \text{NP}$ is if we can construct a non-deterministic TM $N$ using a polynomial time verifier $V$ on a certificate $C$, or:

TM $N$: on input $x$ of problem instance:
1. non-deterministically guess a certificate $C$ given $x$
2. if V accepts $C$, accept

But if I use the definition $\text{NP}=\bigcup \text{NTIME}(n^k)$, wouldn't this imply that $\text{co-NP} \subseteq \text{NP}$, since I can construct a TM $N'$ that can recognize co-NP:

TM $N'$: on input $x$ of problem instance:
1. non-deterministically guess a certificate $C$ given $x$
2. if V accepts $C$ for any branch, reject
3. if all branches reject the guessed certificates, accept

In this case, since all branches of $N'$operate in polynomial time, $N'$ should also be able to solve problems for co-NP in non-deterministic polynomial time.

But since it is not yet sure if NP=co-NP, how should I understand the definition $\text{NP}=\bigcup \text{NTIME}(n^k)$?

# Answer
> 7 votes
Nondeterministic machines are only allowed to behave nondeterministically in a limited way: very briefly, "Accept iff some branch has \[property\]" is permitted but "Accept iff no branch has \[property\]" is not. Unlike with deterministic machines, there's a fundamental element of asymmetry here. Your $N'$ is not, in fact, a nondeterministic Turing machine.

Rather, it's a "co-nondeterministic Turing machine" (if that were a term). Unsurprisingly, co-NP is exactly the set of languages accepted by some co-nondeterministic Turing machine, and the fact that NP=co-NP is open means exactly that it is **not currently known** whether nondeterministic and co-nondeterministic machines can compute the same things in polynomial time.

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


# Question
Title: On an array of sets, Data structure to handle Interval insert, Interval erase, Interval sum of size query
Consider an array of sets. As you know a set must not have multiple elements. I need a data structure to handle following queries:

1. Insert element `x` to all sets on interval \[ L, R \].
2. Erase element `x` from all sets on interval \[ L, R \].
3. Query the sum of sizes of sets on interval \[ L, R \] of the array.

Is there any data structure to handle it in something better than $O(n \cdot q)$ Time/Memory complexity? (Something like $q \cdot log(n)$, $q \cdot \log ^ 2(n)$ or $q \cdot sqrt(n)$ where $q$ is the number of queries and $n$ is the size of the array).

Update: interval \[ L, R \] means the interval of indices of the array from index L to index R.

# Answer
> 1 votes
I am assuming that inserting a value $x$ to a set already containing it does nothing, which is how sets usually work. Then this can be solved in amortised $\mathcal{O}(\log n \log q)$ time per query, with $\mathcal{O}(n + q \log n)$ memory usage.

Assume you have $n = 2^{h}$ sets (this is not limiting, add some unused sets if you need to). We will build a segment tree on the sets: build a perfect binary tree of size $2n-1$, and index the nodes such that node $1$ is the root, the children of node $i$, $1 \leq i \< n$ are nodes $2i$ and $2i+1$, and nodes $n, \dots, 2n-1$ are the leaves. Each vertex represents some interval of the sets, with leaf $i+n$, $0 \leq i \< n$ representing the $i$th original set (0-indexed), and each vertex representing the union of the intervals its children represent.

We will store in every node two sets: one containing every value occurring in every set of its interval, but not in every set of its parent's interval, called $all\[i\]$, and one containing every value occurring in some, but not all of the sets in its interval, called $some\[i\]$. We also store an integer $sum\[i\]$, which is $|all\[i\]|$ times the size of the node's interval, plus the sums of its children.

First note that this data is sufficient to answer queries of type 3 in $\mathcal{O}(\log n)$ time. Say we want to count the total size of the sets in interval $\[a, b\]$. DFS down from the root, and at every node,

* If that node's interval is disjoint of $\[a, b\]$, return 0
* If that node's interval is contained in $\[a, b\]$, return $sum\[i\]$.
* Otherwise, return $|all\[i\]|$ times the size of the intersection of $\[a, b\]$ and this node's interval, plus the return values of recursive calls to this node's children.

Clearly storing the data this way requires at most $\mathcal{O}(n + q \log n)$ memory:

* We initially need $\mathcal{O}(n)$ memory.
* In a query of type 1, we at worst add $x$ to $\mathcal{O}(\log n)$ sets in our tree, since in segment trees, for any interval $\[a, b\]$ there are at most $\mathcal{O}(\log n)$ nodes, such that their interval is contained in $\[a, b\]$, but the interval of their parent isn't.
* In a query of type $2$, say we delete $x$ from interval $\[a, b\]$. If $x$ doesn't occur in $a-1$ and doesn't occur in $b+1$, this operation in fact frees memory. Thus it always uses at most as much memory as two insertions, as we can extend the interval to be deleted until $x$ doesn't occur in $a-1$ and $b+1$, and then re-insert $x$ to the sides.
* Queries of type $3$ are read-only, and use no memory.

How to perform operations 1 and 2? First note that we do everything in DFS-order, so updating the stored value is trivial: it's just the sum of the stored values of this node's children, plus the size of this node's interval times the size of this node's first set. So we only need to consider how to update the sets.

For this time complexity, we need amortised analysis. We will use a potential function with value

\begin{equation\*} f = \sum\_{i = 1}^{2n-1} |some\[i\]| \log q \end{equation\*}

With this potential function, it costs **no time** to delete $x$ from interval $\[a, b\]$, if $\[a, b\]$ is the interval of some node $i$, and $x \in some\[i\]$, and we do not care about updating ancestors of $i$ for now. Deleting $x$ from $some\[i\]$ takes $\mathcal{O}(\log q)$ time, but the potential decreases by $\log q$. Then recurse to the children of $i$. If $x \not \in some\[j\]$ for either child $j$, then if $x \in all\[j\]$, delete $x$ from $all\[j\]$, otherwise return. This wastes $\log q$ time, but with large enough constants, the potential decrease covers that.

In operation 1, say we want to insert $x$ to interval $\[a, b\]$. We DFS down from the root, and at every node,

* If that node's interval is disjoint of $\[a, b\]$, return.
* If that node's interval is contained in $\[a, b\]$, first delete $x$ from the interval for either free if $x \in some\[i\]$, or at the cost of $\mathcal{O}(\log q)$ otherwise, then add $x$ to $all\[i\]$ in $\mathcal{O}(\log q)$.
* Otherwise, first recurse to the node's children. Then, update whether $x$ appears in $all\[i\]$ and $some\[i\]$ in $\mathcal{O}(\log q)$ time. If $x \in all\[j\]$ for both children $j$, you have to remove it from $all\[j\]$ for both children, but this is again just $\mathcal{O}(\log q)$ time.

Thus insertion takes $\mathcal{O}(\log n \log q)$ amortised time, since cases 2 and 3 occur at most $\mathcal{O}(\log n)$ times. For deletion, very similarly, we again DFS and at every node,

* If that node's interval is disjoint of $\[a, b\]$, return.
* If that node's interval is contained in $\[a, b\]$, delete $x$ from the interval for either free if $x \in some\[i\]$, or at the cost of $\mathcal{O}(\log q)$ otherwise.
* Otherwise, first recurse to the node's children. Then, update whether $x$ appears in $all\[i\]$ and $some\[i\]$ in $\mathcal{O}(\log q)$ time.

Here's a C++ implementation:

#include <iostream>
#include <vector>
#include <set>
using namespace std;
using ll = long long;

class SegTree {
    private:
        vector<set<int>> all, some;
        vector<ll> sum;
        int h = 1;

        // returns 2 if x in all[i], 1 if x in some[i] and otherwise 0
        int val(int i, int x) {
            return all[i].count(x) ? 2 : some[i].count(x);
        }
        void update(int i, int x, int len) {
            int va = val(2*i, x), vb = val(2*i+1, x);
            if (va == 2 && vb == 2) {
                some[i].erase(x);
                all[i].insert(x);
                for (int c : {2*i, 2*i+1}) {
                    all[c].erase(x);
                    sum[c] -= len / 2;
                }
            } else {
                all[i].erase(x);
                if (va || vb) some[i].insert(x);
                else some[i].erase(x);
            }
            sum[i] = (ll)all[i].size() * len + sum[2*i] + sum[2*i+1];
        }

        // [a, b) is query interval, [ia, ib) is the node's interval
        ll recGet(int a, int b, int i, int ia, int ib) {
            if (b <= ia || ib <= a) return 0; // intervals are disjoint
            if (a <= ia && ib <= b) return sum[i]; // contained in query interval
            int mid = (ia + ib) >> 1;
            ll res = (ll)all[i].size() * (min(ib, b) - max(ia, a));
            res += recGet(a, b, 2*i, ia, mid);
            res += recGet(a, b, 2*i+1, mid, ib);
            return res;
        }

        void recErase(int a, int b, int x, int i, int ia, int ib) {
            int v = val(i, x);
            if (b <= ia || ib <= a || v == 0) return;
            if (v == 2) {
                all[i].erase(x);
                sum[i] -= ib - ia;
                if (ia < a) recInsert(ia, a, x, i, ia, ib);
                if (b < ib) recInsert(b, ib, x, i, ia, ib);
            } else {
                int mid = (ia + ib) >> 1;
                recErase(a, b, x, 2*i, ia, mid);
                recErase(a, b, x, 2*i+1, mid, ib);
                update(i, x, ib-ia);
            }
        }

        void recInsert(int a, int b, int x, int i, int ia, int ib) {
            if (b <= ia || ib <= a || all[i].count(x)) return;
            if (a <= ia && ib <= b) {
                if (some[i].count(x)) recErase(a, b, x, i, ia, ib);
                all[i].insert(x);
                sum[i] += ib - ia;
            } else {
                int mid = (ia + ib) >> 1;
                recInsert(a, b, x, 2*i, ia, mid);
                recInsert(a, b, x, 2*i+1, mid, ib);
                update(i, x, ib-ia);
            }
        }
    public:
        SegTree(int n) {
            while(h < n) h <<= 1;
            all.resize(2*h);
            some.resize(2*h);
            sum.resize(2*h, 0);
        }

        ll query(int a, int b) { return recGet(a, b+1, 1, 0, h); }
        void erase(int a, int b, int x) { recErase(a, b+1, x, 1, 0, h); }
        void insert(int a, int b, int x) { recInsert(a, b+1, x, 1, 0, h); }
};

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

    SegTree seg(n);
    for (int i = 0; i < q; ++i) {
        int t, a, b;
        cin >> t >> a >> b;
        --a; --b;

        if (t == 3) {
            cout << seg.query(a, b) << '\n';
        } else {
            int x;
            cin >> x;
            if (t == 1) seg.insert(a, b, x);
            else seg.erase(a, b, x);
        }
    }
}
```

# Answer
> 0 votes
You can achieve an $O(\log(n))$ time complexity per each query with $O(M \cdot \log(n))$ memory footprint, where M is a maximum number of elements which were simultaneously stored in our data structure.

The main idea is to use segment tree with lazy propagation and store a pair $\<Set, sz\>$ in each node of this tree. Where $Set$ is a set (presented by hash table) of all elements which belong to all sets of corresponding segment. And $sz$ is a sum of sizes of all sets of a corresponding segment.

---
Tags: data-structures
---


# Question
Title: Prove or disprove, If A ≤p B and B is NP-hard, then A is in NP-hard
Intuitively if A can reduce to B, and B is NP-Hard, A might be NP Hard but maybe not. If there is a way to solve A that does not involve reducing to B, it might be faster.

How do I formally disprove this statement using a counter example or some well known algorithms, or using some other technique?

# Answer
> 1 votes
Let A be the empty language. It is trivially reducible to, say 3SAT: transform any input into the formula $a \land \lnot a$. But only the empty language is reducible to the empty language, thus A is not NP-hard.

If P = NP, then any nontrivial language is NP-hard, thus it will be really hard to find counterexamples where both A and its complement are nonempty.

---
Tags: complexity-theory, p-vs-np
---


# Question
Title: Solving the recurrence of recursive insertion sort
I have solved that the recurrence of running time of the algorithm given as

$$ T(n) = \begin{cases} \Theta(1) & \text{if n=1} \\ T(n-1)+\Theta(n) & \text{otherwise} \end{cases} $$

So the question is that solve the recurrence that I have solved above.

So this is my answer.

**Case 1**

Show that $T(n) = \Theta(n)$

Guess $T(n) \le dn^2 $

$T(n) \le d(n-1)^2 + cn$

$ = d(n^2-2n+1)+cn $

$ = dn^2 - (2d-c)n + d $

it solves when $d \ge (2d-c) n $, which is same as $ \frac{d}{2d-c} \ge n $

When $ \frac{d}{2d-c} \ge n $ , then $T(n) = O(n^2) $

---

So this process is equally in Case 2 which is showing $T(n) = \Omega (n^2)$.

Can you please check whether my approach is right?

Thanks for your help.

# Answer
Why do u need to guess? T(n) = T(n-1) + cn {c is a const} T(n) = T(n-2) +c(n-1) +cn = T(n-3) +c\*\[(n-2)+ (n-1) + n\] .....

Keep going this way till u reach the arithmetic sequence (2+...+(n-1)+n\]. So,

T(n) = T(1) + c\* n(n-1)/2 = O(n2)

You may check any Algorithms book or lecture notes on solving recursive equations; we don't usually guess, there r rules and this one is trivial.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, recurrence-relation
---