# Question
Title: Reducibility: Show that SUBSET SUM is reducible to the following problem A
> A: Given nonnegative integers x1,...,xn (written in binary), and an integer k, can the net expenses be balanced using k or fewer checks? (Suppose that A is in NP).
>
> Purpose: to reveal that SUBSET SUM reduces to A so that A is NP-complete (since SUBSET SUM is NP-complete).

Let me construct A as follows:

1. We can find the balanced net expense using SUBSET SUM.

* The balanced net expense = (x1+x2+...+xn)/n

2. There will be some algorithm to compute k.

What I wonder is that as we see the algorithm above A seems to be a harder problem than SUBSET SUM because A uses SUBSET SUM within its algorithm. Is this fact enough to support the idea that SUBSET SUM is reducible to A?

Thank you for your time.

# Answer
You can consider the numbers $x\_i$ as signed integers representing how much each person owes (if the number is positive) or how much each person needs to receive (if the number is negative). Then you have $\sum\_{i=1}^n x\_i = 0$ and the goal is to make all numbers $0$.

Notice that you can always settle debts with at most $n-1$ checks: pick an $i$ such that $x\_i\>0$ and move $x\_i$ from $i$ to an arbitrary $j \neq i$. Delete $x\_i$ (now $0$) from the instance. You are left with another instance of the same problem in which you need settle debts between $n-1$ people. Repeat recursively until you are left with only one person (in which cases no transactions are needed).

Suppose now that you can partition the set $\\{x\_1, \dots, x\_n\\}$ into two non-empty sets $S\_1$ and $S\_2$ such that $\sum\_{x \in S\_1} x =0$ (and hence $\sum\_{x \in S\_2} x = 0$). Then you can solve $S\_1$ and $S\_2$ separately using at most $|S\_1|-1 + |S\_2|-1 = n-2$ checks.

The converse is also true: if you can balance debts using at most $n-2$ checks, then you can partition $\\{x\_1, \dots, x\_n\\}$ into non-empty $S\_1$ and $S\_2$ with $\sum\_{x \in S\_1} x = \sum\_{x \in S\_2} x = 0$. To see this, build the graph $G=(V,E)$ in which $V=\\{1, \dots, n\\}$ and there is an undirected edge $(i,j)$ if $i$ and $j$ exchange at least one check. Since $|E| \le n-2 = |V|-2$, the graph $G$ has at least $2$ connected component. If $C$ is a connected component then the sum of the integers $x\_i$ such that $i \in C$ must be $0$. Let $S\_1 = \\{x\_i \mid i \in C\\}$ and $S\_2 = \\{x\_1, \dots, x\_n\\} \setminus S\_1$.

This shows that you can reduce the variant of partition in which the sum of the integers is $0$ (and you need to find a non-trivial partition) to your problem. To see that this variant remains $\mathsf{NP}$-hard, consider an instance of partition $\\{y\_1, \dots, y\_n\\}$ in which each integer $y\_i$ is positive, and add two additional integers $y'$ and $y''$ with $y'=y''= -\frac{1}{2}\sum\_{i=1}^n y\_i$. Clearly, any non-trivial partition $A,B$ of $\\{y', y'', y\_1, \dots, y\_n\\}$ must place $y'$ in $A$ and $y''$ in $B$, or vice-versa, showing that the sum of the elements in $A \cap \\{ y\_1, \dots, y\_n\\}$ is $\frac{1}{2}\sum\_{i=1}^n y\_i$ (and the same holds for $B$). Conversely, given any partition $A,B$ of $\\{y\_1, \dots, y\_n\\}$, the partition $A \cup \\{y'\\}$, $B \cup \\{y''\\}$ is a solution to our variant.
> 2 votes

---
Tags: time-complexity
---


# Question
Title: Regular expression without 00 as a substring
I want to create a regular expression for the language:

$L=\\{w \in \\{0,1\\}\mid w \text{ does not contain 00 as a substring}\\}.$

I've tried various things, but I can't seem to get the correct regular expression.

# Answer
First, let's start by enumerating the building blocks of length 2.

```
S = { 01, 10, 11, 00 }

```

We can immediately remove `00`

```
S = { 01, 10, 11 }

```

Next, notice `10 + 01` will create a sequence of `00`. So, let's remove `01` (10 could also be removed.

```
S = { 10, 11 }

```

Our basic solution is `(10 + 11)*`

However, this does not account for Empty Set + 0 + 1. It also does not account for odd length strings.

Final Solution

```
(E + 0 + 1)(10 + 11)*

```
> 0 votes

# Answer
It should be something like this:

> $0?(10?)^\*$

Accepts the empty string.

> $0(10?)^\*|(1^+0?)^+$

Does not accept the empty string.
> 1 votes

# Answer
Any of the following should work:

1. $(1+01)^\*(0+\epsilon)$
2. $(0+\epsilon)(1+10)^\*$
3. $1^\*(011^\*)^\*(0+\epsilon)$
4. $(0+\epsilon)(11^\*0)^\*1^\*$
> 1 votes

---
Tags: regular-expressions
---


# Question
Title: UCS and Dijkstra's algorithm do both of them give the minimal cost between two vertices?
i tried both algorithm to find the shortest path with minimal cost between two vertices,but most of the time Dijkstra gives a different path and the cost is smaller than the cost for the path UCS gives, is this right or there is something wrong with my code?

edit: here's the code for both algorithms implemented in java p.s the graph has two- way edges

```
public void UCS(Vertex source, Vertex goal) {

        source.setDistance(0);
        PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>(20,
            new Comparator<Vertex>(){

                //override compare method
                public int compare(Vertex i, Vertex j){
                    if(i.getDistance() > j.getDistance()){
                        return 1;
                    }

                    else if (i.getDistance() < j.getDistance()){
                        return -1;
                    }

                    else{
                        return 0;
                    }
                }
            }

        );

        queue.add(source);

        Set<Vertex> explored = new HashSet<Vertex>();
        boolean found = false;

        //while frontier is not empty
        do{

            Vertex current = queue.poll();
            explored.add(current);

            if(current.getName().matches(goal.getName())){
                found = true;

            }

            for(Vertex child: current.getAdjacentCities()){

                Edge e = findEdge(child, current);

                double cost = e.getCost();
                child.setDistance(current.getDistance() + cost);

                if(!explored.contains(child) && !queue.contains(child)){

                    child.setDistance(cost+current.getDistance());
                    child.setPath(current);
                    queue.add(child);

                }
                else if((queue.contains(child))&&(child.getDistance()>(current.getDistance()+cost))){
                    child.setPath(current);

                    child.setDistance(current.getDistance()+cost);
                    // the next two calls decrease the key of the node in the queue
                    queue.remove(child);
                    queue.add(child);
                }

            }
        }while(!queue.isEmpty()&&(found==false));

```

Dijkstra:

public void dijkstra(Vertex fromCity)
    {
        for (Vertex v : vertices)
        {
            v.setDistance(Integer.MAX_VALUE);
            v.setPath(null);
        }

        Vertex fromLocal = findVertex(fromCity);
        fromLocal.setDistance(0);

        PriorityQueue<Vertex> heap = new PriorityQueue<>();
        heap.add(fromLocal);

        while (!heap.isEmpty() )
        {
            Vertex u = heap.poll();

            for (Vertex adjacent : u.getAdjacentCities())
            {
                Edge e = findEdge(u, adjacent);
                double newDistance = u.getDistance() + e.getCost();

                if (newDistance < adjacent.getDistance())
                {
                    heap.remove(adjacent);
                    adjacent.setDistance(newDistance);
                    adjacent.setPath(u);
                    heap.add(adjacent);
                }
            }
        }
    }
}
```

# Answer
This is not the right place to ask for people to review your code, but it's perfectly normal for Dijkstra's algorithm and Uniform Cost Search (BFS) to return different paths. Indeed, a shortest path on a weighted graph is not necessarily the one that uses less edges.

As an example you can consider the graph $G=(V,E)$ with $V=\\{s,u,v\\}$, $E=\\{(s,u), (u,v), (s,v) \\}$ and weights $w(s,u)=w(u,v)=1$, $w(s,v)=3$.

The shortest path from $s$ to $v$ w.r.t. the edge weights is $s \to u \to v$ and has weight $2$. The shortest path w.r.t. the hop-distance (i.e., the number of used edges) is $s\to v$.
> 1 votes

---
Tags: graphs, search-algorithms, artificial-intelligence, java, dijkstras-algorithm
---


# Question
Title: Big o notation for sublinear algorithm in streaming algorithm
Excuse me if this is obvious.

At 1:55 of this Coursera video on streaming algorithms (see pasted image below for relevant slide), the professor mentions sublinear storage. I get the $N^{\alpha}$ but I don't get the $log^{O(1)} N$. I take it that $O(1)$ is a constant which we could set it as $k$ for example.

* Does he mean that we can have $(log N)^k$ or taking $log N$ a total of $k$ times? I have read the sublinear portion of wikipedia which makes me believe it it is more like $(log N)^k$
* How does this relate to $N^{\alpha}$ mentioned on the same line? Is this an alternate notation or another possible space complexity for other streaming algorithms?

# Answer
A function $f$ is $\log^{O(1)}N$ if there exists a constant $k$ such that $f(n) \leq \left(\log N\right)^k$ (and not $\underbrace{\log … \log}\_{k\text{ times}} N$), so you were right on this point.

The notation $N^{\alpha}$, $\alpha \< 1$ is NOT another notation for $\log^{O(1)}N$ but another complexity family. If you chose $0 \< \alpha \< 1$ and $0 \< k$, $\log ^kN$ will always be $o(N^{\alpha})$.
> 2 votes

---
Tags: space-complexity, streaming-algorithm
---


# Question
Title: Can you have an approximation that is higher than the optimal for a maximum value and a lower than the optimal for a minimum value?
I was reading this page on approximation ratios and the author says that for a problem looking for a:

* **maximum**, an approximation algorithm will give us a value **lower than this optimal maximum**
* **minimum**, an approximation algorithm will give us a value **higher than this optimal minimum**

Is it possible to get the opposite?

* an approximation algorithm will give us a value **higher than this optimal maximum**
* an approximation algorithm will give us a value **lower than this optimal minimum**

If they exist,

* why would such algorithms not be used (as I don't see them mentioned)?
* Isn't getting a range with $\pm$ of the optimal good enough?

# Answer
No, it's not possible, by definition of a maximum: it means that no other solution has higher value (and same thing for minimum).
> 2 votes

# Answer
In a maximization problem w.r.t. some measure $m$, the *optimal* value is the maximum value $m(s)$ attainable among all feasible solutions $s$.

It is meaningless to ask for an algorithm that returns a feasible solution $s'$ such that $m(s') \> m(s)$ since no such $s'$ exists.

The case of minimization problems is symmetric.
> 2 votes

---
Tags: approximation
---


# Question
Title: Minimal modification of sequence that removes all local minima
Consider a trail as a sequence of land heights representing the elevation along the trail. A pit is any position in the trail surrounded by higher terrain on both sides. For example, in the sequence \[1000, 600, 1700, 900, 900, 1400, 600\], positions 1, 3 and 4 are all pits (elevations 600, 900 and 900 respectively).

We would like to fix the trail such that it includes no pits, but we wish to do it with the minimal amount of additional sand units. In the example above the solution would be: \[1000, 1000, 1700, 1400, 1400, 1400, 600\]. We added a total of 400+500+500=1400 sand units.

Assumptions:

* The sequence length $n$ may be large
* Terrain levels are always in the range $\[0, k\]$, where $k$ is much smaller than $n$.

> How do I solve this efficiently?

# Answer
> 1 votes
Let $a\_i$ denote the $i$-th elevation and let $a^\*\_i$ the $i$-th elevation after the minimum amount of sand has been poured in order to remove all pits.

Let $p$ be a pit in the input instance. The solution must pour at least $s^\*\_p = \min \\{a\_{p-1}, a\_{p+1}\\} - a\_p$ units of sand in $p$. Indeed, if less than $s^\*\_p$ units of sand were poured we would have: $$ a^\*\_p \< a\_p + s^\*\_p = \min \\{a\_{p-1}, a\_{p+1}\\} \le \min \\{a^\*\_{p-1}, a^\*\_{p+1}\\}, $$ showing that $a^\*\_p$ is a pit in the final configuration and yielding a contradiction.

Moreover, the solution that pours exactly $\min \\{a\_{p-1}, a\_{p+1}\\} - a\_p$ units of sand in each pit $p$ of the input instance is feasible, and hence is optimal (since it matches the above lower bound).

To see that the solution is feasible, let $a'\_i$ the final amount of sand in position $i$ and let $s\_i = a'\_i - a\_i$. Notice that if $i$ is an endpoint of the trail we have $s\_i=0$. Otherwise $s\_i = \max \\{ \min \\{a\_{i-1}, a\_{i+1}\\} - a\_i, 0 \\}$.

If $i$ is initially a pit, then $i-1$ and $i+1$ cannot be pits and hence $s\_{i-1}=s\_{i+1} = 0$. It follows that $$a'\_i = a\_i + s\_i = \min \\{a\_{i-1}, a\_{i+1}\\} = \min \\{a\_{i-1} + s\_{i-1}, a\_{i+1}+s\_{i+1}\\} = \min \\{a'\_{i-1}, a'\_{i+1}\\},$$ showing that $i$ is no longer a pit in the final configuration.

If $i$ is not initially a pit, then $s\_i=0$ and: $$ a'\_i = a\_i + s\_i = a\_i = (a\_i - a\_{i+1}) + a\_{i+1} \ge s\_{i+1} + a\_{i+1} = a'\_{i+1}, $$ hence $i$ cannot become a pit in the final configuration.

---
Tags: algorithms
---


title: How to prove (un)decidability

text:
# Question
Title: How to prove (un)decidability
Let's say we have a string **s** , a code size limit of **b** bytes and a time limit **t**, the question is then whether or not it is possible to construct an algorithm that prints the string within the time limit when a program is given **no input**.

**In other words - is this problem decidable or undecidable?**

I was thinking of reducing the Halt problem when it is given no input, but I'm a bit unsure of whether I should concider the byte size and time limit as input as well, or how I should conquer this problem.

Thank you.

# Answer
> 3 votes
The problem is decidable. You can enumerate the (finitely many) programs that use at most $b$ bytes.

For each such candidate program $P$, you can check whether $P$ is valid program (for any reasonable representation) and execute it for up to $t$ time steps. Eventually you either find a program that prints $s$ (and accept) or you run out of programs (and reject).

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


# Question
Title: Diagram to represents words having as many $0$ as $1$
> Give the diagram of transitions of a Turing machine to a ribbon which accepts the language on the alphabet $\\{0, 1\\}$ of the words which contain as many $0$ as of $1$. (Note well that the $0$ and the $1$ can appear in any order.)

This problem is similar to $\\{0^n 1^n : n \in \mathbb{N}\\}$ except the fact that we mix up all the $0$'s and $1$'s and can be solved with a simple pushdown automata. An instance of an accepting word on the tape would be $010011000111$ and a rejecting word would be $010111$.

I am confused how to set that up. I have thought building a transition with two states :

1. $q\_0$ would be the starting starting which is also the accepting state.
2. $q\_1$ would be the rejecting state.

I have thought using the transition function which will move left when I meet a $0$, move right when I meet a $1$ and using the symbol $\\\\$$ whenever a state has been visited.

Am I on the right track? How to build such diagram?

# Answer
> 1 votes
The starting state must be different than the accepting state or you will end up accepting all words.

As for an indication to solve your problem, you should consider multiple states of the Turing Machine:

* searching for a $0$ or a $1$;
* already encountered a $0$ (replaced with a special symbol $\\\\$$), searching for a $1$ to replace it with $\\\\$$;
* already encountered a $1$ (replaced with a special symbol $\\\\$$), searching for a $0$ to replace it with $\\\\$$;
* returning to the beginning of the word.

If, when searching specifically for a $0$ or a $1$ (in the two middle states), you encounter a blank symbol, it means that you reached the end of the word without encountering one of the searched symbol, so you can reject the word. If, when searching for either a $0$ or a $1$ (the first state) you encounter a blank symbol, it means you already replaced all $0$'s and $1$'s with $\\\\$$'s, so you can accept the input.

Here's a way to do it, with the previous 4 states (with 2 additionnal states for accepting and rejecting). Note that there may be more efficient way to do it.

---
Tags: turing-machines
---


# Question
Title: Reduction from Clique to IS degree at most 4
This is from the Algorithms textbook by Dasgupta,C. H.Papadimitriou,andU. V. Vazirani question 8.6 (b) that asks:

Edit:

> And missing from the pic as @Nathaniel points out in his answer below: "3SAT remains NP-complete even when restricted to formulas in which each litteral appears at most twice".

My reduction from Clique:

Definition of clique: fully connected graph/subgraph

So given G=(V,E) and a goal g it returns a clique of size g fully connected.

The complement graph G’ would contain an IS of size g of the same vertices.

So given a graph G, with degree at most 4, as input to Clique, the largest possible clique would be of size 5 vertices per the definition. Let's assume g=5 as input to the Clique problem.

Make the complement graph G’ =(V, E’) where uv in E’ not in E and call ISdeg4 on G’ with g=5.

If there is an IS of size g=5 in G’, then those 5 vertices make up a clique in G so return that to Clique.

Else returns no which I can return to Clique.

ISdeg4 is in NP:

Returns a set of vertices which are an IS.

In O(n+m) I can check that none of the v's in the IS have an edge to another v in the IS.

So ISdeg4 can be used to solve Clique problems for G=(V,E) with degree at most 4.

Edit: The above is not a solution since the reduction from Clique to ISDeg4 only solves a subset of Clique problems where an input G=(V,E) is at most degree 4.
Thus, I want to know if anyone has a reduction from a known NP-Complete graph problem rather than 3SAT-\> IsDeg4 which I was able to understand after seeing the solution given by my teacher.

# Answer
As you stated, this is not a correct reduction, because you would need to solve Clique for any graph (or prove that Clique with graphs of degree at most 4 is $NP$-complete).

Actually, the question 8.6.b stands true if the graph have degree at most 3. I think the intention of the author for solving this exercice is to use the remark stated at the beginning of the exercice (which you cropped): "$\textsf{3SAT}$ remains $\textsf{NP}$-complete even when restricted to formulas in which each litteral appears at most twice".

You should then make a reduction from $\textsf{3SAT-2LITmax}$ (a convenient name I came up for the problem I just described), using the same kind of reduction to prove $\textsf{NP}$-hardness of $\textsf{IS}$ from $\textsf{3SAT}$.
> 1 votes

---
Tags: np-complete, reductions, np
---


# Question
Title: Bipartite Graph to solve the wolf river crossing problem
I have just started studying about bipartite graphs and there is an example that bipartite graph can be use to solve the wolf, cabbage, and the sheep river crossing problem, as a kid i had fun solving this question, now I was wondering how can we describe the problem in bipartite graph, as to describe it we need to divide the problem into two disjoint and independent sets, I am getting very confused as how it can be done?

It will be helpful, if someone can help me understand it as there is no information about this wolf river crossing problem on the internet.

# Answer
> 2 votes
I have never really imagined solving this problem with a graph, but it is an interesting point of view.

My guess is that the graph you have to create is a bipartite graph with 16 vertices, each vertex representing the state of the situation, that is representing where is each of the different actors of the problem: the wolf, the goat, the cabbage and the boat. Each actor have two positions possibles (each side of the river), so $2^4 = 16$ different configurations. You might then delete forbidden configurations, representing a case where the wolf is alone with the goat or the goat alone with the cabbage.

Now, you can add an edge between two vertices $v$ and $w$ if and only if you can go from $v$ to $w$ by crossing the river with the boat, with one actor from wolf/goat/cabbage on board.

The graph is indeed bipartite, because there are no edges between two vertices where the boat is on the same side.

Solving the problem now results in finding a path between the two vertices where the four actors are on each side of the river.

# Answer
> 1 votes
I think the best bet is to create a set of vertices which are permissible states (on one bank or the other), with the edges representing permitted transitions between them. Note that the presence of the farmer is also part of the state, so the two parts of the bipartite graph are nodes with & without the farmer. So this is a variation on the previous answer that **limits the created nodes**. Using the state on the starting bank and coding the presence or absence of each component in to a binary tuplet (farmer, wolf, sheep, cabbage) we have the permitted states: $$\begin{array}{c} & \text{with farmer} & \text{without farmer} \\ \text{initial state}& (1,1,1,1) & \\ & (1,1,1,0) & \\ & (1,1,0,1) & (0,1,0,1)\\ & & (0,1,0,0) \\ & (1,0,1,1) & \\ & (1,0,1,0) & (0,0,1,0) \\ & & (0,0,0,1) \\ & & (0,0,0,0) &\text{target state}\\ \end{array}$$

(As you may notice, the no-farmer states govern what is permissible; by inference, the state on the other bank eliminates some with-farmer states). Then the edges represent feasible journeys:

, and the problem is finding a path between the initial and target states.

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


# Question
Title: how does the program change the clock speed of the processor?
bios is a program that checks all devices and starts the bootloader. but how does the CPU sync with the motherboard if the CPU clock settings are stored in the BIOS?

1. Does the BIOS have CPU clock frequency settings?
2. how does the BIOS adjust the clock speed of the processor if it's just a program?
3. does the BIOS synchronize the internal clock of the processor with the external clock on the motherboard?
4. does the processor first start on the external clock, and after synchronization - on its own internal clock frequency?
5. does the change in the CPU clock speed mean its own internal clock due to heating problems (throttling)?
6. How can the operating system change the clock speed of the processor? does it really change the cpu settings or put some limits on the task scheduler? (Are Linux and Windows the same with this?)

I am completely confused about how the processor actually syncs at startup and sets the clock speed? please explain me. answer as processor clock = base clock * multiplier. I do not understand

# Answer
> 1 votes
This is different for any processor. You should consider going to the Intel, ARM and AMD websites and looking for the right manuals. That’s what I would do if I had to answer the question, and that’s what I recommend you should do.

---
Tags: computer-architecture, cpu
---


# Question
Title: Number of paths starting from a given edge using adjacency matrix
I want to write the algorithm that takes the adgacency matrix of a directed connected graph without any cycles, then for each edge computes the number of paths starting from that edge. Also note that there is at most one edge between two nodes.

For example consider the graph depicted below:  For instance, we want to count the number of paths starting from edge $b$. They are: $b, bd, bdf, bdfg, bh$. So $F(q0, q2)=5$. ($F$ is the function that runs the counting algorithm). As another example $F(q4, q5)=2$.

Note that I want to count these paths for every two distinct nodes. So the output must be a matrix.

How should I write the algorithm? And what will be the complexity of that?

# Answer
> 1 votes
Note that counting the number of (non empty) paths starting from edge $(q\_1, q\_2)$ is the same as counting the number of (possibly empty) paths starting from vertex $q\_2$. That way, the answer can be given as an array of size $|V|$ for a graph $G = (V, E)$ instead of a matrix of size $|V| \times |V|$.

Knowing that fact, here is an algorithm to compute this array $a$:

* compute a topological sort $(v\_1, …, v\_n)$ of $G$ (this is possible because $G$ is supposed to be acyclic);
* for $k$ from $n-1$ to $1$, set $a\[v\_k\] = 1+\sum\limits\_{v \text{ adjacent to }v\_k} a\[v\]$, since $(v\_k, v)\in E$, that means that $v$ appears after $v\_k$ in the topological sort, so the value $a\[v\]$ has already been computed. Moreover, if the sum is empty, it means that $v\_k$ is a sink node, meaning it has no exiting edge, so the only path is the empty path.

The algorithm has a total complexity $O(|V| + |E|)$, which is optimal.

Now, note that the complexity of the previous algorithm suppose you know the adjacency list of the graph $G$. If you only know the adjacency matrix of $G$, then I suggest you first compute the adjacency list of $G$ (time complexity $O(|V|^2)$).

---
Tags: algorithms, graphs, graph-traversal, adjacency-matrix
---


# Question
Title: Turing machine without return equivalent to Finite Automaton, PushDown Automaton or Turing Machine?
I have seen that a *Turing machine without return* is a Turing machine $M$ which at each stage of its calculation systematically moves its read / write head to the right.The aim of the exercise is to understand the computing power of Turing machines without return. If a language $L$ is recognise by a Turing machine without return, can we say that $L$ is also equivalent in recognising by a finite automaton, a pushdown automaton or by a Turing Machine? I would tend to say that the $L$ language can be recognized by a Turing machine with no return if and only if $L$ can be recognized by a pushdown automaton because the stack can simulate the movement to the right on tape of the Turing Machine.

# Answer
> 1 votes
Informally, a pushdown automaton has a way to store and use an infinite amount of memory (the stack). In a Turing machine, the only way to store an infinite amount of memory is to write it on the tape. But in a Turing machine without return, you cannot go back to the cells that you have already written, so that memory can never be used.

That means that a Turing machine without return cannot be "as powerful" as a pushdown automaton. The solution is a finite automaton.

If you want a more formal proof, you can start with the formal definition of a Turing machine without return, note that you can dismiss what you write on the tape (because you can't go back), and construct a finite automaton that recognize the same language as the Turing machine.

---
Tags: turing-machines, pushdown-automata
---


# Question
Title: Minimal number of states for an NFA of all different words
Given $\Sigma =\\{0,1,@\\}$, I am looking at a language $L=\\{u@v | u,v\in \\{0,1\\}^k\wedge u\neq v\\}$. So $u,v$ have only $0,1$s, same length $k$, yet are different.

Also, for me $k$ is a known constant. So the language ìs regular (at most $(2^k)\cdot (2^k-1)$ words).

I want to build the most efficient NFA for $L$. So far, I have been able to cone up with an NFA of $O(k^2)$ states, but I want to find one with $O(k)$ states. Of course one could argue that as $k$ is constant, its the same as $O(1)$, but assuming $k$ is a constant parameter - that is, given a value of $k$, I construct $L$ and an NFA for $L$ with $O(k)$ states.

My idea to use $k^2$ states:

* A path for each index, as $u$ and $v$ of size $k$... they differ means there is at least one $1\leq i \leq k$ where they differ at that character.
* Read '0' in $i$th character and '1' in $i+k+1$th character (due to '@'). Or other way.
* In between make sure that $u$s length and $v$s length is $k$. Which characters you read in between? I don't care.

But this will give me around $2k$ states (I can do a bit less, but still $O(k)$) for each index. Total $O(k^2)$, as there are $k$ indices.

I would ask for a way to improve my idea, to use $O(k)$ states. Or maybe a totally different approach.

# Answer
Here is a matching $\Omega(k^2)$ lower bound.

Consider any NFA for your language. Let $Q\_i$ be the set of states $q$ such that:

1. There is some word $w$ of length $i$ such that the NFA could be at state $q$ after reading $w$.
2. There is some word $z$ such that starting at $q$, after reading $z$ the NFA could be at an accepting state.

Since all words in $L$ have the same length, the sets $Q\_i$ must be disjoint.

Now let $i \in \\{0,\ldots,k\\}$. For every word $w \in \\{0,1\\}^i$, let $Q\_i(w) \subseteq Q\_i$ be the set of states that the NFA could be in after reading $w$. I claim that if $w\_1 \neq w\_2$ then $Q\_i(w\_1) \neq Q\_i(w\_2)$. Indeed, the NFA behaves differently after reading $w\_1$ and $w\_2$: it accepts $w\_1 0^{k-i} @ w\_2 0^{k-i}$ but rejects $w\_2 0^{k-i} @ w\_2 0^{k-i}$. It follows that $2^{|Q\_i|} \geq 2^i$, and so $|Q\_i| \geq i$. Therefore the NFA has at least $$ \sum\_{i=0}^k i = \Omega(k^2) $$ many states.
> 6 votes

# Answer
I don't understand how you could do this in less than $2^k$ states. Your description of your plan doesn't fit at all with how I understand NFAs. You talk about reading to the $i$th character, as if you had some kind of random access, but an NFA must read symbols in order, and any knowledge it needs from those symbols must be reflected as part of the state it transitions to afterwards.

Following is my argument that at least $2^k$ states are required.

Let $q\_x$ be the state the machine reaches after reading $x \in \\{0,1\\}^k$, and let $u,v\in \\{0,1\\}^k\wedge u\neq v$. Is it possible that $q\_u=q\_v$? No, because there is at least one set of remaining symbols that $q\_u$ must accept, and that $q\_v$ must reject: namely, a repetition of $v$.

Therefore, $q\_x$ must be unique for each $x$. Since $x$ is $k$ items long, there are $2^k$ unique $x$s, each needing their own distinct $q\_x$.

This is a lower bound; in practice you will need at least $k$ more states to use while consuming $v$, and one for consuming the $@$ symbol.
> -2 votes

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


# Question
Title: Prune and search Algorithm for Generating a Bottleneck Spanning Tree
I'm trying to wrap my head around a prune-and-search algorithm for returning a bottleneck spanning tree, currently I'm selecting the median weight of all the edges, then divide the original graph G into two graphs containing the edges which are less than or equal to the median or greater than.

After separating the graphs, I test the median weight against the original graph (G) to see if it is a bottleneck value. I'm stuck on what to do, if the median is not a bottleneck value, I was thinking maybe I could compact the graph of edges with weights less than the median - but the cut of a compacted graph would still have the weights so the median wouldn't change. I'm thinking I need to form an MST at some point as well?

So far I have something like:

```
def F(G):
  m = find_avg_weight_of_edges(G)
  G_le_m = get_g_w_edge_weight_less_than_or_eqal_to(G,m)
  G_gt_m = get_g_w_edge_weight_greater_than(G,m)
  if is_bottleneck_value(G,x):
    T = F(G_le_m)
  else:
    # note quite sure what to do...
    # I can't remove the less than or equal to edges
    # since they are needed to make up the MST
    # but if I don't remove them m won't change
    # maybe some kind of reduce/scc function?
return T

```

# Answer
Let $b$ is the bottleneck edge of $MBST$, and let $b$ has weight $w(b)$.

Suppose $e\_{m}$ is the median weighted edge of $G$, and let $e\_{m}$ has weight $w(e\_{m})$. Suppose $G$ gets partitioned into two subgraphs $G\_{1}$ and $G\_{2}$ such that edges in $G\_{1}$ have weight $\leq w(e\_{m})$ and edges in $G\_{2}$ have weight $\> w(e\_{m})$.

If $w(b) \leq w(e\_{m})$, then there must exist an $MBST$ within $G\_{1}$ itself. Since the algorithm is recursing on $G\_{1}$, it will output an $MBST$ if it exists. If the algorithm does not output a valid spanning tree, it means $b \notin G\_{1}$. In other words, $b \in G\_{2}$.

In that case, the algorithm will update $e\_{m}$ to be the median weight edge of $G\_{2}$. The graph $G$ will again get partitioned into two subgraphs $G\_{1}$ and $G\_{2}$. And, the algorithm can repeat this process.
> 1 votes

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


# Question
Title: Why are binary numbers sometimes written with one or more leading zeros that don't change the number (quantity) represented?
Binary numbers like '0110', or '00100101' are seen very often in all contexts. What are the leading (left hand side) zeroes for? Why did the writer not write '110' and '100101', respectively?

# Answer
> 2 votes
Leading zeroes in binary usually indicate the bit length of the data type. For example, the number `110` represented in a 4 bit data type would be `0110`. Even if there is no data type specified, it's sometimes common to pad your binary numbers to the next power of 2. For example, `10111` of size 5 should be padded to 8 $(2^3)$ as `00010111`

# Answer
> 1 votes
Depend on context, so, I bring one small example: if we consider $3$-bit field, then $110$ is negative in $2$'s complement and equal $-2$, while in $4$-bit field $0110$ is positive and equal $6$ in same $2$'s complement.

---
Tags: notation, binary
---


# Question
Title: Recommendation for good book or online course on distributed programming
I am a computer science student in his final year on the university with several years of experience in software engineering. I want to take me to the next level in programming web applications. I am looking for a good book or online course on the subject of distributed programming with in-depth understanding, and how to design and build large and scaled web applications professionally like facebook, amazon, google from scratch.

By the way, I will be happy to hear also about a good book or online course which explain about all the new technologist that web application can connect/interact with like: AI analysis, databases, cloud computing and so on.

Thanks in advance.

# Answer
> 0 votes
This is awesome book: Designing Data-Intensive Applications
https://www.amazon.com/Designing-Data-Intensive-Applications-Reliable-Maintainable/dp/1449373321

You may find the review here:
https://www.goodreads.com/book/show/23463279-designing-data-intensive-applications

---
Tags: distributed-systems
---


title: Minimal unsatisfiable core algorithm

text:
# Question
Title: Minimal unsatisfiable core algorithm
Wikipedia says that

> There are several practical methods of computing minimal unsatisfiable cores.

but I cannot find any. I suppose that “practical methods” means polynomial algorithms. Be careful, a polynomial algorithm, that finds a minimal unsatisfiable core of a given CNF $F$, doesn’t mean that $P=NP$, because the algorithm could output a Boolean formula $G$ such that if $F$ is unsatisfiable, $G$ is a minimal unsatisfiable core of $F$; if $F$ is satisfiable, $G$ is a subset of the clauses of $F$ and it is satisfiable. Therefore, the output of the algorithm is a CNF but we don’t know if it is satisfiable or not.

# Answer
> 2 votes
> Be careful, a polynomial algorithm, that finds a minimal unsatisfiable core of a given CNF , doesn’t mean that =, because the algorithm could output a Boolean formula such that if is unsatisfiable, is a minimal unsatisfiable core of ; if is satisfiable, is a subset of the clauses of and it is satisfiable. Therefore, the output of the algorithm is a CNF but we don’t know if it is satisfiable or not.

The basis of this statement seems to be a slight misunderstanding of the UNSAT to MINIMAL UNSATISFIABILITY reduction given in The complexity of facets resolved. *This reduction is not a way to produce an unsat core even if the original formula is unsatisfiable.* What the reduction does is embed the original formula into a new formula carefully crafted such that satisfiability is unaffected but the new formula's CNF clauses no longer overlap in the assignments that they forbid. Because each clause forbids different assignments and because the formula's clauses cover all possible assignments, removing any one clause is guaranteed to make the result satisfiable, which is the definition of a minimally unsatisfiable formula. But this new formula is not an unsat core of the original formula and tells you nothing about how to find such a core. The original formula and the new formula are equisatisfiable and thus are related, but they aren't related in a way useful in finding an unsat core for the original formula.

As for practicality, by this the Wikipedia article means "easily implemented once you have a certificate of unsatisfiability for a given Boolean formula." If you already have a tool to generate such a certificate, you can produce an unsat core using a polynomial number of calls to that tool. If the tool requires exponential-time relative to the size of the formula, then you're still looking at an exponential process to find an unsat core. But it is just as "practical" as determining whether the formula is unsatisfiable in the first place.

---
Tags: algorithms, search-algorithms, satisfiability, 3-sat
---


# Question
Title: Multiplication of polynomials in value representation as done for Fast Fourier Transform
I am trying to understand the discrete Fast Fourier Transform. I get the idea of switching between coefficient and value representations to and then back but I am stuck in figuring out how the multiplication of 2 polynomials using their value representation works.

The screenshot below is from a Reducible video (at time 6:39) that explains the Fast Fourier transform. I see that we need 5 points to get $C(x)$, which is of degree $4$, but I don't see how multiplying say the first point of $A(x)$ and $B(x)$, that is, $(-2,1) \times (-2,9)$ gives $(-2,9)$

There's a similar answer here but the steps aren't provided just the final answer, which still baffles me.

# Answer
If $P, Q, R \in \mathbb{R}\[X\], R = PQ$, then for any $x \in \mathbb{R}$, $R(x) = P(x)\times Q(x)$.

It means that if the value representation of $P$ is $\[(x\_1, P(x\_1)); (x\_2, P(x\_2)); …, (x\_n, P(x\_n))\]$ and the value representation of $Q$ is $\[(x\_1, Q(x\_1)); (x\_2, Q(x\_2)); …, (x\_n, Q(x\_n))\]$, then the value representation of $R$ is $\[(x\_1, P(x\_1)Q(x\_1)); (x\_2, P(x\_2)Q(x\_2)); …, (x\_n, P(x\_n)Q(x\_n))\]$.

In your example, $(-2, 1)$ represents a couple $(x\_i, P(x\_i))$ and $(-2, 9)$ is $(x\_i, Q(x\_i))$, so it's normal that $(x\_i, R(x\_i))$ is $(-2, 1\times 9) = (-2, 9)$.
> 2 votes

---
Tags: algorithms, divide-and-conquer, polynomials, fast-fourier-transform
---


# Question
Title: How to get the calculate the binary logarithm of a fixed-point number with 18 decimals?
Suppose that:

1. You're using a programming language that doesn't support fixed-point or floating-point numbers.
2. The said programming language rounds down divisions, e.g. `12 / 5 = 2`.
3. You're adding 18 trailing decimals to represent fixed-point numbers in your algorithm. for instance, you'd represent 0.5 as 500000000000000000, equivalent to 5e17 in scientific notation.

Now, say you want to calculate the integer part of the binary logarithm of a number x that adheres to the format above.

If x is greater than or equal to 1e18, then the calculation is easy: you just divide x by 1e18, and calculate the most significant bit of the rounded down result. For example, `4e18 / 1e18` is 4, of which the msb is 2. The integer part is thus 2.

But what if x is between 0 and 1e18 (both exclusive)? For example, 1e17? The binary logarithm of a number between 0 and 1 is negative ..

# Answer
I figured it out, eventually, by making the following observations:

1. $\log\_2{(x)} = -log\_2{(\frac{1}{x})}$
2. To accurately calculate $\frac{1}{x}$, multiply $1e18$ by itself then divide by $x$.

My implementation looks something like this (written in Solidity):

```
pragma solidity ^0.8.0;

function log2(uint256 x) internal pure returns (int256 result) {
    require(x > 0);
    unchecked {
        // This works because log2(x) = -log2(1/x).
        int256 sign;
        if (x >= 1e18) {
            sign = 1;
        } else {
            sign = -1;
            unchecked {
                x = 1e36 / x;
            }
        }

        // Calculate the integer part of the logarithm and add it to the result and finally calculate y = x * 2^(-n).
        uint256 n = mostSignificantBit(uint256(x / 1e18));

        // The integer part of the logarithm as a signed 59.18-decimal fixed-point number. The operation can't overflow
        // beacuse n is maximum 255, SCALE is 1e18 and sign is either 1 or -1.
        result = int256(n) * 1e18;

        // This is y = x * 2^(-n).
        int256 y = int256(x) >> n;

        // If y = 1, the fractional part is zero.
        if (y == 1e18) {
            return result * sign;
        }

        // Calculate the fractional part via the iterative approximation.
        // The "delta >>= 1" part is equivalent to "delta /= 2", but shifting bits is faster.
        for (int256 delta = 5e17; delta > 0; delta >>= 1) {
            y = (y * y) / 1e18;

            // Is y^2 > 2 and so in the range [2,4)?
            if (y >= 2 * 1e18) {
                // Add the 2^(-m) factor to the logarithm.
                result += delta;

                // Corresponds to z/2 on Wikipedia.
                y >>= 1;
            }
        }
        result *= sign;
    }
}

```

Where `mostSignificantBit` is a function that calculates the most significant bit of a number that can go as high as $2^{256} -1 $.
> 0 votes

---
Tags: algorithms, mathematical-programming
---


# Question
Title: Kernelization algorithm for the following problem
We are given an undirected graph $ G $ and a positive parameter $ k \geq 0 $. The problem is to decide if there exists a set $ S \subseteq V(G) $ of size at most $ k $ such that $ G − S $ does not have any path on three vertices.

Is there any deterministic kernel algorithm for this problem with $ \Theta (k^2) $ vertices?

**Kernelization algorithm definition**: Given $ (G,k) $, output an equivalent instance $ (G’,k’) $ of the same problem in polynomial time, such that $ |G’| \leq f(k) $ and $ k’ \leq k $.

# Answer
> 0 votes
Your problem can be stated as $3$-path vertex cover problem. A simple google search gives this paper. The authors design a kernel of size $5k$ for this problem.

---
Tags: algorithms, graphs, parameterized-complexity, vertex-cover
---


# Question
Title: Question regarding notation of a language decidability
$1.\\: A\_{DFA} = \\{\langle B, w \rangle \mid B \text{ is a } DFA \text{ that accepts input string } w \\}$ $2.\\:A\_{DFA} = \\{\langle B \rangle \mid B \text{ is a } DFA \text{ that accepts input string } w \\}$

I know how to proof that **1** is decidable by constructing a machine that always halts and accepts whenever $B$ accepts, otherwise rejects. what's the difference between **1** and **2**. I find that it doesn't make sense to not include $w$ inside the encoding brackets but I have seen this notation in other places. are they both the same?

# Answer
> 2 votes
The languages are not the same.

---

In the first one, $w$ is a part of the input.

In the second one, $w$ is fixed beforehand, and the language has to depend on what you fix it to be.

---
Tags: turing-machines, computability, church-turing-thesis
---


# Question
Title: Why does taking advantage of locality matter in multithreaded systems?
As we all know, when a given thread/process reaches a memory address it does not have cached, the execution will (for the most part) freeze up until said data is fetched from memory. What I don't understand, is why in multithreaded systems, we can't save ourselves the headache of data-oriented design. Why can't the processor/OS simply do work elsewhere on a different thread until the data is received?

I couldn't find a good post on this exact question, and this may just be obvious to others. I only know so much about the pipeline and such so there could be a very obvious reason for this, I simply don't know why.

# Answer
Ask yourself: How long does it take to load data from memory, and how long does it take to stop one thread from running and start another thread? Starting another thread would usually take a lot longer, plus a new thread would have the exact same problem, having to wait for data to be ready.

An exception is hyperthreading cores. A hyperthreading core can officially run two threads simultaneously, but doesn’t actually have twice the processing power of a normal core, so it cannot actually perform twice as many instructions or anywhere near that. Such a core can however process operations of the second thread *immediately* when the first thread cannot proceed for any reason.

Now it’s debatable if hyperthreading is actually a win, especially since it gives hackers ways that operations in one thread can very subtly affect operations in another thread, leading to massive security problems. As a result, many high-performance ARM processors don’t implement hyperthreading at all.
> 1 votes

---
Tags: concurrency, process-scheduling, cpu-pipelines
---


# Question
Title: no of times partion is called in quick sort, assuming array is always halved
In the most even possible split, PARTITION function produces two subarrays, each of size no more than n/2. since one is of size floor(n/2) and one of size ceil(n/2)-1.
The recurrence for the running time will be,

$$ T(n) = 2T(n/2) + \Theta(n) $$

where we tolerate the sloppiness from ignoring the floor and ceiling and from subtracting 1. By case 2 of the master theorem, this recurrence will have the solution $$ T(n) = \Theta(n \log n) $$ My Implementation is as follows:

```
QUICKSORT(A, p, r)
  if p < r
  q = PARTITION(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)

```

```
PARTITION(A, p, r)
  x = A[r]
  i = p - 1
  for j = p to (r - 1)
      if A[j] <= x
          i = i + 1
          exchange A[i] with A[j]
  exchange A[i+1] with A[r]
  return i + 1

```

Assuming that the array is always divided into 2 equal halves, how many times is the partition algorithm will be called?

# Answer
The number of times the partition algorithm is called does not actually depend on where the array is partitioned (asymptotically).

To count the number of partitions you just need to count the number of internal nodes in the recursion tree. Since each internal node has at least two children, the recursion tree is a full binary tree. In a full binary tree, the number of leaves and internal nodes are linearly related (see this link). So the number of internal nodes would be $\Theta(n)$, no matter where the partition happens. You can easily prove this using induction on the number of nodes in the tree.
> 1 votes

# Answer
If you use a partition algorithm that divides a range of numbers into a left and a right half, then you can look at every partition call as inserting one separator between two subranges into the array. And quicksort ends when there is a separator between any two array elements.

Therefore sorting an array of n \>= 1 elements takes exactly n-1 calls to the partition function. This is totally independent of the choice of pivot and the execution time.

You will have fewer calls when the partition algorithm can create a left half, right half, and possibly k equal items in the middle; this would save k partition calls whenever k \>= 1. You will also have fewer calls if small subranges are sorted using bubble sort, insertion sort or whatever is fastest for very small arrays.
> 0 votes

---
Tags: algorithms, quicksort, algorithm-design
---


# Question
Title: Path graph partitioning, minimizing cut while minimizing maximum total node weight in each part
Suppose there is a path (linear) graph $G = (V, E)$ where $V = \\{0, \ldots, n - 1\\}$ and $E=\\{(0, 1), (1, 2), \ldots, (n - 2, n - 1)\\}$, with edge weights $w\_e : E \to \mathbb{N}$ and vertex weights $w\_v : V \to \mathbb{N}$. Let $\lambda$ be a known constant.

We need to find an exact cover $C \subseteq \mathbb{P}(V)$ of $V$ (with $\iota : V \to C$ being the associated injection) such that each $p \in C$ is a contiguous subset (interval) in $\mathbb{N}$ and

$$\lambda \left( \sum\_{\iota(i) \neq \iota(j)} w\_e(i, j) \right) + (1 - \lambda) \left( \max\_{p \in C} \sum\_{v \in p} w\_v(v) \right)$$

is minimized.

In other words, we are trying to minimize a convex combination of the sum of the edge weights of the cut edges and the maximum total node weight for each part.

Is there an efficient algorithm for this problem? An approximation algorithm?

# Answer
> 2 votes
I suggest using dynamic programming. Because your graph forms a path, we can use dynamic programming (considering all prefixes of the path), solving once for each candidate for the maximum total weight of the parts. Details below.

Let $S$ denote the sum of the weights of the cut edges (i.e., the first part of your objective function) and $M$ the maximum total weight of the parts (i.e., the second part of your objective function), so that your goal is to minimize $\lambda S + (1-\lambda) M$. Define $f(m)$ to be the minimum possible value of $S$, for all covers with $M \le m$. I'll show below how to calculate $f(m)$ for any desired $m$. This then is sufficient to compute the minimum possible value of $\lambda S + (1-\lambda) M$, by enumerating all $m$ and checking which gives the lowest value of $\lambda f(m) + (1-\lambda) m$.

So, let's fix $m$ from here on. For any $k$ that ends a consecutive interval in $C$, i.e., where $\iota(k) \ne \iota(k+1)$, define $S\_\*$ by $$S\_\* = \sum\_{i\le k, \iota(i)\ne \iota(i+1)} w\_e(i,i+1).$$ We will let $A\[k\]$ denote the minimum possible value of $S\_\*$, taken over all exact covers that contain an interval that ends at $k$ (i.e., where $\iota(k)\ne \iota(k+1)$) and such that $M\le m$ for this cover. Note that this depends on only how vertices $0,1,2,\dots,k$ are partitioned by $C$, and doesn't depend on what is done with vertices $k+1,\dots,n-1$.

Now we can write a recurrence relation for $A\[k\]$:

$$A\[k\] = \min\_t A\[t\] + w\_e(k,k+1),$$

where $t$ ranges over $0 \le t \< k$ such that $\sum\_{i=t+1}^k w\_v(i) \le m$. Thus, for each $m$, you can fill in the array $A\[\cdot\]$ in $O(n^2)$ time using dynamic programming. It's possible to get this down to $O(n \log n)$ time by pre-computing prefix sums for $w\_v(\cdot)$ and binary search to find the range of allowable $t$'s, and storing $A\[\cdot\]$ in a balanced binary tree augmented with minimums stored in each tree node to quickly find the minimum of $A\[\cdot\]$ over a range of indices. To get the total running time, we must multiply this by the number of values of $m$ we iterate through. A trivial upper bound on $M$ is the sum of all vertex weights.

In this way, we obtain an algorithm whose running time is $O(Tn \log n)$ where $T=\sum\_v w\_v(v)$ is the total of all vertex weights. In practice, often the running time will be less, as we can iterate through $m$ in increasing order, and once we find a solution whose objective function has value $v$, then there is no need to consider values of $m$ larger than $v/(1-\lambda)$. As @j\_random\_hacker points out, we can replace $T$ with $O(n^2)$, if that helps: we only need to consider values of $m$ that are equal to the sum of vertex weights along some interval, and there are only $O(n^2)$ such intervals.

If you want an approximation algorithm, scale all of the vertex weights down by a factor of $c$, and then round to the nearest integer. This will speed up the algorithm by a factor of $c$, and should approximate the optimal solution to within $\pm (1-\lambda)cn$ (probably better than that in practice).

# Answer
> 0 votes
Here's an implementation of D.W.'s algorithm (the $O(n^2)$ version) in C++. There was some subtlety around the base case of the recurrence; `A` needs to be indexed on `std::optional<NodeId>`, where `A[std::nullopt] = 0` is the base case.

---
Tags: graphs, approximation, partitions, dag, minimum-cuts
---


# Question
Title: Is it possible to construct a C^5(U) with V^2=U and no work qubits (Nielsen & Chuang Exercise 4.28)
My question is related to the exercise 4.28 in the book of Nielsen and Chuang (Quantum Computation and Quantum Information). Here is the exercise

For $U=V^2$ with $V$ unitary, construct a $C^5(U)$ gate analogous to that in Figure 4.10, but using no work qubits. You may use controlled-$V$ and controlled-$V^{\dagger}$ gates.

I think the exercise in the current form is not possible to solved. Since any usage of a controlled-$V$ or $V^{\dagger}$ gate gives even 4 cases (with case I mean a combination of qubits) where $V$ or $V^{\dagger}$ is applied. So we can increase the number of applied $V$ gates with any usage of a controlled-$V$ or decrease the number of applied $V^{\dagger}$ gates with any usage of a controlled-$V^{\dagger}$ by 4. But to obtain the controlled-$U$ gate, we may only have $2$ usages of a $V$ gate. Thus any way we apply the controlled-$V$ or $V^{\dagger}$ gates, in the end we will always have more than 2 cases where a $V$ or $V^{\dagger}$ is applied (with applying I mean that it does not contract with another controlled gate, so it will really be applied at the end).

Note that this problem does not occur for controlled-X gate since an addition can be though as an addition modulo 2, therefore we can decrease the numbers of cases where a qubit is switched.

Since I think that this chapter is heavily influenced by the paper https://arxiv.org/abs/quant-ph/9503016.pdf which constructs a $C^3(U)$ with controlled-$V$ gates where $V^4=U$, I think it should be $V^16=U$ in the exercise. However I am not certain if there really does not exist a solution, maybe one using maybe gates creating a superposition like the Hadamard gate. So my question is, if someone has a solution for this exercise or a proof that it is impossible to do.

# Answer
It is not possible. We can consider the simpler case of constructing $C^3(U)$ using only $\tt{CNOT}$, Toffoli, $U$, $V$, $C(U)$, $C^2(U)$ and $C(V)$ where $V^2=1$.

We consider the determinant of the matrix representation of the gates over only the first 3 qubits (so the outcome of the determinant is an operator on the last qubit), and we have:

$$ C^3(U) = \left.\begin{array}{ccc}- & \bullet & - \\ & | & \\\- & \bullet & - \\ & | & \\\- & \bullet & - \\ & | & \\\- & U & -\end{array}\right. = \left(\begin{array}{cccccccc}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & U\end{array}\right) \Rightarrow \det C^3(U) = U $$

$$ C^2(U) = \begin{array}{ccc}- & - & - \\ & & \\\- & \bullet & - \\ & | & \\\- & \bullet & - \\ & | & \\\- & U & -\end{array} = \left(\begin{array}{cccccccc}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & U & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & U\end{array}\right) \Rightarrow \det C^2(U) = U^2 $$

$$ C(U) = \left.\begin{array}{ccc}- & - & - \\ & & \\\- & - & - \\ & & \\\- & \bullet & - \\ & | & \\\- & U & -\end{array}\right. = \left(\begin{array}{cccccccc}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & U & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & U & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & U & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & U\end{array}\right) \Rightarrow \det C(U) = U^4 $$

$$ U = \begin{array}{ccc}- & - & - \\ & & \\\- & - & - \\ & & \\\- & - & - \\ & & \\\- & U & -\end{array} = \left(\begin{array}{cccccccc}U & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\0 & U & 0 & 0 & 0 & 0 & 0 & 0 \\0 & 0 & U & 0 & 0 & 0 & 0 & 0 \\0 & 0 & 0 & U & 0 & 0 & 0 & 0 \\0 & 0 & 0 & 0 & U & 0 & 0 & 0 \\0 & 0 & 0 & 0 & 0 & U & 0 & 0 \\0 & 0 & 0 & 0 & 0 & 0 & U & 0 \\0 & 0 & 0 & 0 & 0 & 0 & 0 & U\end{array}\right) \Rightarrow \det U = U^8 $$

Similarly, we can prove $\det V = V^8 = U^4$ and $\det C(V) = V^4 = U^2$.

The determinant of $\tt{CNOT}$ and Toffoli do not involve factors of $U$ so they will not affect the analysis below.

Now suppose $C^3(U)$ can be constructed by the combinations $C^3(U) = G\_1 G\_2 \cdots$, where each $G\_i$ is among the gates stated above, then we must have: $$ \det C^3(U) = \prod\_i \det G\_i \Rightarrow \prod\_i \det G\_i = U $$

This identity is however impossible to satisfy using the gates above because the determinants of $U$, $V$, $C(U)$, $C^2(U)$ and $C(V)$ all give even powers of $U$.

The only possible way out is to include $C(\sqrt{V})$ because $\det C(\sqrt{V})=\sqrt{V}^4= U$. But $C(\sqrt{V})$ can be used to construct $C^2(V)$. If we can use $C^2(V)$, then the solution to (4.28) is rather obvious and we get the solution given by Bram.

The proof for more qubits is similar.

I am a physicist, not specialized in quantum computing. Question 4.28 was indeed frustrating. Up until that question, the underlying principle of the chapter was the construction of more complicated gates using more elementary gates. Had I known the authors wanted us to use $C^2(V)$ (which would require $C(\sqrt{V})$ gate, which may or may not exist, not previously constructed nor alluded to in the question), I would have solved the question in less than a minute. Perhaps proving once and for all there is no solution (the way most readers would interpret the question) will save others from the frustration.
> 2 votes

# Answer
It can be done in the same way as the $$C^3(U)$$ circuit with 4 controls.

Look in arXiv0708.3274 for details
> 1 votes

---
Tags: quantum-computing, circuits
---


# Question
Title: Are the sets in $\Sigma_{p}$ (or $\Pi_{p}$) totally ordered?
Are the sets in each stage of the arithmetic hierarchy well-ordered, with respect to : $T-$reductions, or $m-$reductions?

It is something which I have been unclear with for a while (from a Computability Theory POV).

# Answer
> 6 votes
No - even within (say) the class of $\Sigma\_1$ (= c.e., r.e., semidecidable, ...) sets, there is **lots** of non-linearity even up to Turing reducibility (of course this is stronger than non-linearity up to many-one reducibility since $m$-reductions imply $T$-reductions).

The study of the c.e. degrees began with Post's problem: is there a c.e. set whose Turing degree is strictly between ${\bf 0}$ (= computable) and ${\bf 0'}$ (= halting problem)? This was answered about a decade later by the Friedberg-Muchnik theorem, which showed that there are Turing-incomparable (so a fortiori many-one-incomparable) c.e. sets. Their argument generalizes immediately to get a *countably infinite sequence* of Turing-incomparable c.e. sets. Later, Sacks proved that whenever we have c.e. sets $A\<\_TB$ we can in fact find a sequence $(C\_i)\_{i\in\mathbb{N}}$ of c.e. sets which are Turing-incomparable to each other and which all lie strictly between $A$ and $B$ in terms of Turing reducibility (this is basically his density theorem + a bit of elaboration). Note that Sacks' theorem also shows that there are *infinite increasing* and *infinite decreasing* sequences of Turing degrees as well as infinite antichains.

So there is extremely rich non-linearity there. In fact, though, that's only the beginning of the story. The structure of $\mathcal{R}$ (= the Turing degrees of c.e. sets, ordered by Turing reducibility) turns out to be **extremely** complicated, and there are still many major open questions about it. Soare's old book Recursively enumerable sets and degrees contains a lot of information on the topic, which really picks up in earnest at chapter $7$ (where priority arguments, the method developed by Friedberg and Muchnik and later elaborated by Sacks and others, are first introduced); Soare also wrote a medium-length survey paper on the topic.

---

EDIT: Even though it's not directly related to the OP let me address a common *related* question: namely, how the c.e. degrees (= Turing degrees of c.e. sets) sit inside the poset of all Turing degrees.

We know that every c.e. set is Turing reducible to the halting problem, so every c.e. degree is $\le\_T{\bf 0'}$. The converse however is **false**: there are degrees below ${\bf 0'}$ which are not c.e. degrees. There *is* a "syntactic" characterization of $\\{{\bf d}: {\bf d}\le\_T{\bf 0'}\\}$ but it's more complicated; see here.

*(Incidentally, the easiest way I know to prove the existence of a non-c.e. degree below ${\bf 0'}$ is to $(i)$ prove Sacks' density theorem and $(ii)$ construct a minimal noncomputable degree below ${\bf 0'}$. This is rather a lot of work, but as far as I know there's no easier way of doing this!)*

There is however a sense in which the degrees below ${\bf 0'}$ are "c.e. in flavor." Specifically, say that a set $X\subseteq\mathbb{N}$ is *$2$-c.e.* if $X=A\setminus B$ for c.e. sets $A,B$. We can similarly define $3$-c.e. and $n$-c.e. sets for all finite $n$, and even continue this into the transfinite in a precise sense. The resulting "hierarchy" *(scarequotes since it's not linear!)* is called the **Ershov hierarchy**, and with help from the limit lemma we can show that every set computable from ${\bf 0'}$ is $\alpha$-c.e. for some ordinal *(or rather, ordinal **notation**)* $\alpha$. The fact that $\le\_T{\bf 0'}$ doesn't imply c.e. is extended by a general, if somewhat technical, non-collapsing result for the Ershov hierarchy; for example, there is a $2$-c.e. set not Turing-equivalent to any c.e. set (which I believe is due to Cooper).

---
Tags: computability, mathematical-foundations
---


# Question
Title: Church-Turing Thesis - the mechanical model - the turing machine- its limits and its equivalence with a modern digital computer
Well in many texts and places I have seen a called statement, which claims it self to the famous "Church Turing Thesis".

I have seen many texts say that based on Church-Turing Thesis :

> "Anything that can be done by a digital computer can also be done by Turing Machine".

Peter Linz text roughly says that the thesis is :

> "any computation that can be done by **"mechanical"** means can also be done by TM".

Linz even adds that **mechanical** term is not well defined. So TM can serve as a definition for mechanical machine.

A look in the Wikipedia says:

> It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.

The Wikipedia indeed defines or considers Turing Machine to be that "mechanical" standard.

Googling about mechanical computation, results in the picture of a device something like this:

*Mechanical Computer*

Even Ullman text has a proof of equivalence of TM and modern computer using the simulation of instruction set... But there the authors make a twist by saying they assume their digital computer says "yes" or "no" for input given.

Sipser says:

> The definition came in the 1936 papers of Alonzo Church and Alan Turing. Church used a notational system called the λ-calculus to define algorithms. Turing did it with his “machines.” These two definitions were shown to be equivalent. This connection between the informal notion of algorithm and the precise definition has come to be called the Church–Turing thesis.

Most of the problems that can be solved by a TM in fact can be solved by applying the algorithm mechanically by an actual human using pen and paper. Like given a graph, one can trace out the TSP tour using pen and paper by drawing it and marking out the path. Or given two integers one can find the sum using pen and paper.

So in that case are our modern computers more powerful than a TM ? What is this mechanical model?

Using modern digital computers we can play Super Mario. Though Mario is after all a program and runs on the processor. The graphics rendering algorithms are algorithms after all. And some texts says that the notion of algorithm comes from the concept of Turing Machine. But a TM cannot possibly produce audio/video.

Then why some people believe that TM is equivalent to modern digital computers ? Or could we somehow use a multi dimensional TM and use each cell as a pixel to produce a picture.... I doubt?

---

I have seen the question here but it does not answer my query.

# Answer
Modern computers are not more powerful than a TM.

The meaning/definition of "mechanical means" is not "a TM"; "mechanical means" refers to any step-by-step process that can be carried out in the real, physical world. For instance, it would include mechnical devices, electronic devices, a human following a procedure "mechnically", and so on.

Wikipedia does not *define* "can be calculated by an effective method" as "can be calculated by a TM". It doesn't define "mechnical" as can be calculated by a TM. Rather, it says that the Church-Turing hypothesis asserts that any computation that can be carried out mechnically, can be carried out by a TM. That's not a definition of what it means to carry out a computation mechnically -- that's a consequence of the Church-Turing hypothesis.

I think you are getting confused about the difference between a definition of computation, vs what the Church-Turing thesis claims/asserts/conjectures to be true about computation. The Church-Turing thesis is not intended as a definition of computation; it's intended as a statement/claim/assertion about computation. The Church-Turing hypothesis doesn't provide a formal definition of "effective computation" or "mechnical means"; it leaves that up to the intuition.
> 3 votes

---
Tags: turing-machines, computation-models, church-turing-thesis
---


# Question
Title: Time-Complexity Verification: Code with two loops with an index halved at each iteration
I have the following code in python and was asked to find the tightest upper-bound in terms of Big-O , I've done two attempts below and I don't know which one is right, can you help me verify as to which one is the right answer/approach?

```
def f1(L):
   n = len(L)
     while n > 0:
        n = n // 2
        for i in range(n):
          if i in L:
             L.append(i)
   return L

```

**My attempts:**
**Approach 1:**
While loop runs $ log(n) $ times. And at the $ith$ iteration the for-loop runs $ \frac{n}{2^i} $ times; inside the for-loop the conditional runs at most $ O(n) $ times ( because "in" has complexity of $ O(n) $ according to https://wiki.python.org/moin/TimeComplexity ). Thus, the time-complexity of the for-loop is $O(n^2) $. So the time-complexity of total code is: $ \sum\_{i=1}^{log(n)} O(\frac{n^2}{2^i}) = O(\sum\_{i=1}^{log(n)} \frac{n^2}{2^i} ) = O( n^2 \cdot \frac{1-(1/2)^{1+log(n)}}{ 1-(1/2)^{log(n)} } ) = O(n^2) $

**Approach 2:**
In the for-loop we have the conditional “if i in L” , the “in” costs $ O(n) $, thus time-complexity of for-loop is $ \sum\_{i=1}^{n} O(n) = O( \sum\_{i=1}^{n} n ) = O(n^2). $ Looking at the while loop we see that “n” is halved at each iteration because of the statement “n=n//2” . Denote $ n\_k = \lfloor \frac{n}{2^k} \rfloor $ as the value of $n$ at the k-th iteration; Disregarding the floor function ( we won't care about $ \pm 1 $ for the value of $ n\_k $ since we care about time-complexity ), we'll seek the smallest $ k $ ( we denote $ k $ as the iteration of the while loop ) where $ n\_k = 1 \leq \frac{n}{2^k} \iff k \leq log(n) $. Hence the total time complexity of code is $ \sum\_{i=1}^{log(n)} O(n^2) = O(log(n)) \cdot O(n^2) = O(n^2 \cdot log(n) ) $

# Answer
> 0 votes
As said above, both approaches are correct but in approach #2 I don't get a tight-bound. Since I want a tight-bound using the second approach I failed to notice what $ n $ actually is once inside the while loop. Let's look at the code above but formatted a bit in the following manner:

```
def f1(L):
   n_0 = len(L)
   n_k = n_0
     while n_k > 0:
        n_k = n_k // 2
        for i in range(n_k):
          if i in L:
             L.append(i)
   return L

```

Analysing the time-complexity of code using "inside-out" approach as I wanted:
The for-loop's complexity is $ \sum\_{i=1}^{n\_k} \cdot O(n\_0) $ ( Complexity of "in" is $ O(n\_0) $ ), i.e. $ O( n\_k \cdot n\_0 ) $. Thus since the while-loop runs $ log(n\_0) $ times by my analysis, the total time-complexity of code is $ \sum\_{k=1}^{log(n\_0)}O(n\_k \cdot n\_0 ) $ , notice that $ n\_k = \frac{n\_0}{2^k} $ ( $ k $ is the k-th iteration of while loop ) hence $ \sum\_{k=1}^{log(n\_0)}O(n\_k \cdot n\_0 ) = O(\sum\_{k=1}^{log(n\_0)}n\_k \cdot n\_0 ) = O(\sum\_{k=1}^{log(n\_0)} \frac{n\_0}{2^k} \cdot n\_0 ) = O(n\_0^2) $. Denote $ n\_0 $ as $ n $ and we have $ O(n^2) $ and we're finished.

---
Tags: time-complexity
---


# Question
Title: A connected acyclic graph has $n-1$ edges
Let $G$ be an undirected graph with $n$ nodes. Prove that any two of the following implies the third:

1. $G$ is connected
2. $G$ is acyclic
3. $G$ has $n-1$ edges

### Proving $1, 2 \implies 3$

A connected, acyclic graph is a tree. Each node(vertex), except the root, in the tree has exactly one edge going upwards(towards the root), hence it has $n-1$ edges.

### The Problem

I'm not able to write a formal proof for the other two. The problem is that here I used the fact that connected, acyclic graph is a tree and then it was easy to prove using properties of a tree, for the other I tried using contradiction but couldn't prove them.

Any hint on how to approach this problem and how to prove $1, 2 \implies 3$ without using the fact that connected acyclic graph is a tree?

### Reference

This problem is from Chapter 3 of `Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley`

# Answer
Proving 2,3 implies 1: We have an acyclic graph $G=(V, E)$ with $n-1$ edges. We want to prove that $G$ is a connected graph. Assume for the sake of contradiction that $G$ is not connected. This means we have $d\>1$ connected components, $G=\\{\bigcup\_{i=1}^{d}G\_i\\}$.

Since $G$ is acyclic, each connected component is a tree by definition. Let $V\_i$ be the set of vertices of graph $G\_i$. Then, the number of edges in $G\_i$ is $\mid E\_i \mid = \mid V\_i \mid - 1$. Thus, the total number of edges in $G$ is $\mid\ E \mid\ =\sum\_{i=1}^{d}\mid E\_i \mid =\sum\_{i=1}^{d} (\mid V\_i \mid-1)=\sum\_{i=1}^{d}(\mid V\_i \mid)- d = n - d \< n -1$.

The last inequality follows because $d \> 1$. This is a contradiction that $\mid\ E \mid\ = n-1$.

Proving that 1,3 implies 2: We have a connected graph $G=(V, E)$ with with $n-1$ edges. We want to prove that $G$ is acyclic. I will not write the proof, but I will hint that (one of many possible proofs) you can use induction on the number of vertices. And let your assumption be that given $G$ with $n-1$ vertices and **at most** $n-2$ edges, then $G$ is acyclic.
> 3 votes

---
Tags: graphs, trees
---


# Question
Title: Difficulty in understanding the proof of "Every context-sensitive language L is recursive" as given in the Peter Linz text
I was going through the automata text by *Peter Linz*. There I came across the proof the theorem below. I could not quite get the portion of the proof in bolds.

---

> **Every context-sensitive language L is recursive.**
>
> Proof: Consider the context-sensitive language $L$ with an associated context- sensitive grammar $G$, and look at a derivation of $w$
>
> $$S \Rightarrow x\_1 \Rightarrow x\_2 ... \Rightarrow x\_n \Rightarrow w$$.
>
> We can assume without any loss of generality that all sentential forms in a single derivation are different; that is, $x\_i \neq x\_j$ for all $i\neq j$ . The crux of our argument is that the number of steps in any derivation is a bounded function of $|w|$. We know that $$|x\_j| \leq|x\_{j + 1}|,$$
>
> because $G$ is noncontracting. **The only thing we need to add is that there exist some $m$, depending only on $G$ and $w$, such that**
>
> **$$|x\_j| \lt|x\_{j + m}|,$$**
>
> **for all $j$, with $m = m(|w|)$ a bounded function of $|V\cup T|$ and $|w|$. This follows because the finiteness of $|V \cup T|$ implies that there are only a finite number of strings of a given length. Therefore, the length of a derivation of $w \in L$ is at most $|w| m (|w|)$.**
>
> This observation gives us immediately a membership algorithm for L. We check all derivations of length up to $|w|m(|w|)$. Since the set of productions of $G$ is finite, there are only a finite number of these. If any of them give $w$, then $w \in L$, otherwise it is not. ■

---

What I could reason on my own is that, since context sensitive grammars are non contracting, we can apply the productions in steps, and if we get more $|w|$ symbols in the right sentential form, it then when we stop. So we shall be ultimately above to check where $w$ is generated by a context sensitive grammar or not.

# Answer
> 2 votes
What he wants to show here is that for any sentence of some given length, there is a (very large but finite) number $m$ which is the maximum number of steps in a derivation of the sentence.

If that is true (which it is), then we can figure out whether or not a sentence is generated by the grammar by enumerating all possible derivations with at most $m$ steps. If we encounter the sentence in one of these derivations, then we have derived it. Otherwise no derivation exists.

There are a finite number of such derivations, so this process will eventually finish. That makes it recursive, since it eventually finishes both on success and on failure). (It won't finish during the lifetime of the universe but mathematicians are allowed to ignore inconvenient aspects of reality).

Type 0 grammars (not context-sensitive) are not non-contracting, so we can't limit the number of possible derivation steps. We can still enumerate all possible derivations in order by derivation length (in steps), but we have no guarantee that the process will ever terminate on failure. (More accurately, there is no point on the enumeration at which we can say that a derivation for the sentence will never appear.) So Type 0 grammars are recursively enumerable, but not recursive.

---
Tags: formal-grammars, proof-techniques, context-sensitive
---


# Question
Title: Why does a polytime hitting set generator derandomize RP?
I am reading Goldreich, Vadhan, Wigderson: *Simplified Derandomization of BPP Using a Hitting Set Generator* and trying to understand the result that polytime hitting set generators (HSGs) would not only imply $\mathsf{RP = P}$ but $\mathsf{BPP = P}$ as well, but I can't even conceptualize why the former holds.

The paper states that

> Having such a generator that runs in polynomial time enables a trivial deterministic simulation of an RP algorithm by using each of the generator’s outputs as the random pad of the given algorithm.

Every paper or lecture notes I've found on the topic of HSGs and $\mathsf{BPP}$ derandomization also mentions that $\mathsf{RP}$ derandomization is trivial using an HSG, simply by trying all elements of the hitting set as random pads.

I am confused as to why this is the case. At least one element of a hitting set must be accepted by circuits that accept over half of their inputs. However, RP circuits don't necessarily accept over half their inputs; rather, if $x \in L$, only *then* will the circuit accept over half the time. I assume that fact is related to why a hitting set must contain a valid $\mathsf{RP}$ random pad, but I do not understand exactly how.

So, my question is: how do the circuits in the definition of an HSG relate exactly to $\mathsf{RP}$ circuits? i.e. how do the elements of the hitting set - which are to be the random pads across all inputs - relate to the randomness of RP algorithms when such algorithms accept over half the time *only* when $x \in L$?

# Answer
> 4 votes
The point is that instead of checking what happens for all possible random strings, you can reduce the search to the output of the generator.

Let $M(x,r)$ be some RP machine for a language $L$, i.e. if $x\in L$ at least two thirds of the $r$'s lead to acceptance, and if $x\notin L$ there is no $r$ for which $M(x,r)$ accepts. Now, Given input $x$, construct a circuit $C\_x(r)=M(x,r)$ and execute the generator $G\left(p(|x|),|C\_x|\right)$, where $p(n)$ is the number of random bits used by $M$ on a length $n$ input. This yields a set $R$ of polynomially many strings, now simply check whether or not $C\_x(r)$ accepts at least one element from $R$. This doesn't straightforwardly generalizes to BPP since in that case it might be the case that $x\notin L$ but $C\_x(r)$ accepts some strings from $R$.

---
Tags: complexity-theory, randomized-algorithms
---


# Question
Title: Finding all pairs of points with no point in between
> Suppose there are $n$ points $p\_1,p\_2,\dots,p\_n$ with color red or blue on a line. We want to find all pairs $(p\_i,p\_j)$ whose color is distinct and such that there are no points between them. If there are $k$ pairs with the described property, design an algorithm with $O(n\log k)$ that uses idea of divide and pruning.

I think if we check all points we can solve this problem, but running time will exceed $O(n\log k)$.

I think for solving this problem we can use projective geometry duality, but I am stuck. Any help would be appreciated.

# Answer
> 1 votes
If you can select $p\_j$ in $O(n)$ time such that it's part of the middlemost group of elements with the same color, the following algorithm works. However I haven't found such a prerequisite.

After finding $p\_j$ we can do an $O(n)$ scan to find $p\_k$, the minimal element $\>p\_j$ with the opposite color. We can do a similar scan for $p\_i$, the maximal element $\<p\_j$ with the opposite color. Finally we can partition our array in $O(n)$ time into three subarrays, left ($\\{\leq p\_i\\})$, middle (rest, all with same color as $p\_j$), and right ($\\{\geq p\_k\\}$).

In an analysis similar to quicksort you can prove that if we recursively apply the above partitioning to the left and right subarrays we end up with a call tree that has height $\log k$ and at each level of the tree we do a combined $O(n)$ operations, thus a total runtime of $O(n \log k)$.

Afterwards (or during) you can simply iterate over each adjacent partition and output the opposite colored pairs (because each partition is uniformly colored).

# Answer
> 0 votes
I believe the following simple algorithm is $O(n\log k)$-time, but I can't prove it because the subproblems are not guaranteed to stop on level $\log k$ of the recursion -- counterexamples, suggestions or direct edits welcome!

## Splitting purple intervals

The basic idea is that we maintain a set of intervals containing both red and blue points (I'll call these *purple* intervals), initially consisting of a single interval containing all the points, and for as long as this set is not empty, we remove some interval from it, split it in half, and add back in whichever of these two halves are still purple (this may be 0, 1 or 2 intervals). Intervals generated along the way that contain only red or only blue points don't need to be subdivided further, and by the time no purple intervals are left, they partition the input into at least $k+1$ blocks of same-coloured points, from which the solution can be read off in $O(n)$ time.

By maintaining for each interval the list of points in that interval, an interval containing $m$ points can be split into two halves each containing at most $\lceil m/2 \rceil$ points in $O(m)$ time using the linear-time "median of medians" algorithm for finding medians. We can also determine in $O(m)$ total time whether each half is red, blue or purple: Loop over the $m$ points, incrementing one of four counters ($\<$ median and blue, $\<$ median and red, $\ge$ median and blue, $\ge$ median and red) for each. The lists of points for the two halves can be created in the same loop.

The splitting process can be represented as a binary tree, with nodes representing intervals and coloured red, blue or purple. The root node consists of the interval containing all points. Purple nodes have 0, 1 or 2 purple children, with the remaining children being red or green leaves that together partition the input points. All intervals on level $i$ have size $n/2^i$ and are disjoint; since a purple node implies at least one red-blue or blue-red colour change, there can be at most $k$ purple nodes on any level. I think this constraint is important for obtaining an $O(n\log k)$ time bound, but haven't figured out how to make use of it.

---
Tags: algorithms, computational-geometry
---


title: Sort a $d$-sorted array

text:
# Question
Title: Sort a $d$-sorted array
An array is *$d$-sorted* if every key in the array is located at a distance at most $d$ from its location in the sorted array.

I need to write an algorithm that get a $d$-sorted array of length $n$ and sort it in the following running times:

1. $\Theta(n)$ if $d$ is constant
2. $\Theta(n\log\log n)$ if $d = \Theta(\log n)$.

My attempt:

I wrote the following pseudo-code:

```
Sort_d_array(A[],d)
 min-heap-size <- d
 for i <- 1 to n
    BUILD-MIN-HEAP(min-heap,heap-size)
      if min-heap not empty
        then EXTRACT-MIN <- A[i]
          if i+d<=n
            then heap-insert-min(min-heap,A[i+d])

```

But in terms of runtime, all I get is $O(n\log\log d)$.

My method: I initialize $i \gets 1$ and then I build a min-heap that contains the first $d$ elements.

As long as the heap is not empty, I use EXTRACT-MIN and put the element at index $i$ in the array. If $i+d \le n$, then I add the element at index $i+d$ to the min-heap.

Any help?

# Answer
Since your heap contains $d$ elements, every operation takes take $O(\log d)$, for a total running time of $O(n\log d)$.

When $d$ is constant, this is $O(n)$, and when $d = O(\log n)$, this is $O(n\log\log n)$.

For a matching $\Omega(n\log d)$ lower bound, see this question.
> 0 votes

---
Tags: data-structures, runtime-analysis, sorting, arrays, pseudocode
---


# Question
Title: Can converting NFA to DFA change the language?
In the context of studying the conversion from an NFA to the equivalent DFA, I came across the following NFA, which accepts all strings over the alphabet $\\{0,1\\}$ which contain $01$:

After I converted the NFA to the equivalent DFA, it became:

The issue is that the NFA accepts the string $101$ but the DFA doesn't.

Is my conversion wrong or is there something I am missing about the NFA to DFA conversion?

# Answer
By definition, two automata are equivalent if they accept the same language.

In your case, the DFA you construct is indeed equivalent to the NFA you start with. Both of them accept all strings starting with $01$. In particular your NFA does *not* accept $101$.
> 0 votes

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


# Question
Title: Strings of length $n$ enumerated by Turing machine
If $E$ is an enumerator and $n$ is a natural number, we define $\langle E,n \rangle$ to be all strings of length $n$ enumerated by $E$. Is $\langle E,n \rangle$ recognizable? Is it decidable?

# Answer
> 0 votes
All finite languages are decidable.

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


# Question
Title: Time complexity of a function with while loop
What is the time complexity of the following procedure?

**for** $x \in \\{1,\ldots,n\\}$:
$\quad$ $i \gets \lfloor n/2 \rfloor$
$\quad$ **while** $i \neq x$:
$\quad\quad$ **if** $i \> x$ **then** $i \gets i -1$, **otherwise** $i \gets i + 1$.

According to me, the time complexity is $O(n^2)$. The inner while loop starts at $n/2$ and moves towards the value of $x$, worst case it runs $n/2$ times, and best case it runs $0$ times.

> What is the exact time complexity of this procedure?

# Answer
Assume $\frac{N}{2}\in\mathbb{N}$, $\frac{N}{2}+(\frac{N}{2}-1)+\cdots+1+0+1+\cdots +(\frac{N}{2}-1)=\frac{N}{2}+2\times\sum\_{k=1}^{N/2-1}k=\frac{N}{2}+\frac{N^2-2N}{4}=\frac{N^2}{4}\in O(N^2)$
> 1 votes

# Answer
The while loop runs for $|x - \lfloor n/2 \rfloor|$ many iterations. Therefore the running time is proportional to $$ \sum\_{x=1}^n |x - \lfloor n/2 \rfloor|. $$ To ease the calculation a bit, let us assume that $n$ is even. We break the sum into two parts: $$ \sum\_{x=1}^{n/2} (n/2 - x) + \sum\_{x=n/2+1}^n (x - n/2) = \sum\_{x=0}^{n/2-1} x + \sum\_{x=1}^{n/2} x = \frac{(n/2-1)(n/2)}{2} + \frac{(n/2)(n/2+1)}{2} = \Theta(n^2). $$
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Proving that the language $\{ w^n\mid w \in \{0,1\}^∗, \, n \ge 2 \}$ is not regular
I'm trying to prove that the following language is not regular:

$$\\{ w^n\mid w \in \\{0,1\\}^∗, \\, n \ge 2 \\}$$

I'm trying to prove this with the pumping lemma, but I'm kind of confused because $w$ is a language, not an expression like $a^n b^n$, and I don't know how can I partition that into three parts.

# Answer
Suppose towards a contradiction that your language $L$ was regular and let $p$ be its pumping length.

Consider the word $w = 0^p 10^p1 \in L$. By the pumping lemma, $w$ can be written as $w=xyz$ with $x=0^{h}$, $y=0^k$, and $z=0^{p-h-k}10^p 1$ (here $h+k \le p$ and $k \ge 1$) such that, for every non-negative integer $i$, $xy^iz \in L$.

Substituting and simplifying, the above means that, for every $i \ge 0$, we have $0^{p-k} 0^{ki} 1 0^p 1 \in L$. In particular, the above must hold for $i=0$, implying that $0^{p-k}1 0^p 1 \in L$. Since $0^{p-k}1 0^p 1 \not\in L$ (recall that $k \ge 1$), this is provides the sought contradiction and concludes the proof.
> 2 votes

# Answer
First to clear up: $w$ is not a language, it is an arbitrary string composed of the symbols $0$, $1$. The "plain English" definition of this language would be "all binary strings that can be expressed as two or more repetitions of any binary string (including the empty string)".

Examples of strings that are members of this language would be $010010$ ($w=010$), $1111$ ($w=1$ or $w=11$) and the empty string $\epsilon$ ($w=\epsilon$).

To prove this language non-regular by pumping lemma, assume there exists a pumping length $p$ for the language. Then let's construct a string belonging in the language with a length of at least $p$ that we can use to demonstrate the impossibility of a legal partition: I suggest $0^p 1^p 0^p 1^p$ which is a member of the language as $w = 0^p 1^p$.

Now it is fairly easy to see any $xyz$ partition using the rules of the pumping lemma is impossible. As $|xy| \leq p$ it must hold that $y$ = $0^n$ for some $n \leq p$. Therefore $xy^2z = 0^{p+n}1^p0^p1^p$. From $|y| \geq 1$ it follows that $n \geq 1$, therefore $xy^2z$ is not a member of the specified language, and there are no legal $xyz$ partitions.

This demonstrates the language doesn't have a finite pumping property, therefore it is not regular.
> 2 votes

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


# Question
Title: Find every edge for which every s,t-path in a DAG goes through that edge
Given a connected sourced/sinked directed acylic graph $G = (V, E \subseteq V^2, s \in V, t \in V)$, we want to enumerate the edges $e \in \mathsf{Bottleneck}(G) \subseteq E$ for which every $s$,$t$-path contains $e$. I don't actually know the real name for this notion; so I'm calling it the "bottleneck set", but when I google that I get unrelated concepts.

An obvious solution is for each edge $e \in E$, run DFS on $G$ to get all $s$,$t$-paths, and check each one for whether it contains $e$. If all of them do, then $e$ is part of $\mathsf{Bottleneck}(G)$. However, this has runtime $O(E(V + E))$. Is there a faster way?

# Answer
For a DAG, a simple linear-time algorithm is all that is needed.

First, prune all vertices not reachable either from $s$ or to $t$. Let $G' = (V', E')$ be the pruned graph. Then, compute any topological ordering $\pi$ of $G'$.

Let $(u, v) \in E'$ be an edge. I assert the edge $(u, v)$ is a bottleneck if and only if $\pi(u) + 1 = \pi(v)$ and there doesn't exist any other edge which interval contains $\[\pi(u), \pi(v)\]$ in the topological ordering. The latter condition can be checked for all edges in linear total-time by maintaining the number of edges containing the current vertex, in the topological order (+1 at the start vertex of each edge, and -1 at the end vertex of each edge).

We have $\mathsf{Bottleneck}(G) = \mathsf{Bottleneck}(G')$. For each $x \in V'$, arbitrary paths from $s$ to $x$ and $x$ to $t$ are denoted by $s\_x$ and $t\_x$, respectively (both exist because of the pruning). I use the symbol ($\circ$) to denote the composition of the paths.

Indeed, if we have $\pi(u) + 1 \< \pi(v)$, then there exists a vertex $w \in V'$ such that $\pi(u) \< \pi(w) \< \pi(v)$, and the path $s\_w \circ t\_w$ cannot use the edge $(u,v)$. Or, if we have another edge $(x,y)$ such that $\pi(x) \le \pi(u) \lt \pi(v) \le \pi(y)$, the path $s\_x \circ (x, y) \circ t\_y$ doesn't use the edge $(u,v)$.

The converse is also true because if the edge is removed we obtain a cut $(\\{x \mid \pi(x) \le \pi(u)\\}, \\{x \mid \pi(v) \le \pi(x)\\})$.
> 2 votes

# Answer
Compute the dominator tree of the flow graph $(G,s)$, i.e., the graph $G$ with source node $s$. Let $s=v\_0,v\_1,\dots,v\_{k-1},v\_k=t$ be the sequence of nodes in the path from $s$ to $t$ in the dominator tree. Check each pair $(v\_i,v\_{i+1})$ of consecutive nodes in this sequence; if it is an edge of $G$, it is visited on every $s,t$-path, so output it. It is possible to see that this enumerates all such edges.

The running time is nearly linear time. It is possible to compute the dominator tree in nearly linear time, and then the rest of the algorithm clearly runs in linear time. In particular, the Lengauer-Tarjan algorithm computes the dominator tree in $O(E \alpha(E,V))$ time, where $\alpha(E,V$) is an inverse Ackerman's function -- thus nearly linear. There is also an $O(V+E)$ time algorithm by Buchsbaum, Kaplan, Rogers, and Westbrook and by Georgiadis and Tarjan, but it is more complex to implement in practice. If you are interested in ease of implementation, you might also be interested in work by Cooper, Harvey, and Kennedy.
> 3 votes

---
Tags: graphs, dag, path
---


# Question
Title: Is the language $\{a^n b^m \mid 2n + 3m \le 1000 \}$ regular?
We have a language $$ L = \\{a^n b^m \mid 2n + 3m \le 1000 \\} $$

Is this language regular?

I'm trying to disprove this using the Pumping Lemma, but it didn't work.

assume I say x = $x=a^{h}$ and $y=a^{t}$ and $z =a^{n-t-h}b^m$

if I say `i = 0` everything is okay because $L =a^{n-t}b^m$ and `2(n-t) + 3m <= 1000`

if I say `i = 2` $L =a^{n+t}b^m$ and `2(n+t) + 3m <= 1000` because I'm not sure about `t` value.

I think it didn't work. Is this language regular? How can I prove that?

# Answer
> 1 votes
The language is finite and, as such, it is regular (all finite languages are regular).

To see that the language is finite, notice that the maximum length of each word in $L$ is upper bounded by $500$. Indeed, if $w \in L$, and $n$ (resp. $m$) is the number of $a$s (resp. $b$s) in $w$:

$$ 2|w| = 2(n + m) \le 2n+ 3m \le 1000. $$

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


title: CPU scheduling Decisions

text:
# Question
Title: CPU scheduling Decisions
Operating System - CPU scheduling Decisions

The question above talks about why CPU scheduling does not take place when ready to running.

But I wonder **why CPU scheduling does not take place when new to ready**. I think it is similar to the process of waiting to ready. They both add processes to ready without changing processes that are running.

# Answer
> 2 votes
When you put a new process in the ready queue, you are just adding the process, not changing anything to running as a result. With a non-preemptive scheduler this is also the case for waiting to ready. But, when you have a preemptive scheduler, tasks that come from waiting to ready get a higher priority than newly running tasks, so that "scheduler decision-making" is determining the priority of this newly ready task in the queue. It looks like they get a higher priority than new tasks because they've already been delayed enough waiting for IO.

---
Tags: operating-systems, scheduling, cpu, process-scheduling
---


# Question
Title: Is the language $\{a^n b^m : 1000|nm \}$ regular?
We have a language $$ L = \\{a^n b^m \mid 1000|nm \\} $$

Is this language regular?

I'm trying to disprove this using the Pumping Lemma, but it didn't work.

assume I say $x=a^{h}$ and $y=a^{t}$ and $z =a^{n-t-h}b^m$ and `1000|nm`

if I say `i = 0` , $L =a^{n-t}b^m$ and `1000|(n-h)*m` and I can't prove (n-h)\*m isn't dividable by 1000.

if I say `i = 2` $L =a^{n+t}b^m$ and `1000|(n+h)*m` I can't prove this too because I'm not sure about `h` value.

I think it didn't work. any idea? I would appreciate it if you helped me with this.

# Answer
> 2 votes
Notice that $1000 = 2^3 5^3$. Then $1000 | nm$ iff for some $0 \le i,j \le 3$, $n$ is multiple of $2^i 5^j$ and $m$ is a multiple of $2^{3-i} 5^{3-j}$ (notice that there are only finitely many choices for $i$ and $j$).

Then $L$ can be obtained as the union of the languages $L\_{i,j} = \\{a^n b^m : 2^i 5^j|n \\;\mbox{ and }\\; 2^{3-i} 5^{3-j}|m\\}$.

Each of these languages $L\_{i,j}$ is the concatenation of $L'\_{i,j} = \\{ a^n : 2^i 5^j|n\\}$ with $L''\_{i,j} = \\{b^m : 2^{3-i}5^{3-j}|m\\}$. It is easy to see that each $L'\_{i,j}$ and each $L''\_{i,j}$ is regular. By the closure properties of regular languages $L$ is regular.

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


# Question
Title: Is the language of DFAs that accept at some string in $\{b, c\}^*$ decidable?
Let the language $K = \\{\langle W \rangle: W \text{ is a DFA on } \\{a, b, c\\} \text{ and } L(W) \text{ contains some string in } \\{b, c\\}^\*\\}$.

Is $K$ decidable?

Is it sufficient to define $M$ as follow :

1. Input $w$;
2. Simulate the computation of $W$ on $w$
3. If the accepting state is final after reading at least one $b$ or one $c$ or both, then halt and accept $w$.
4. Otherwise, halt and reject $w$

I think if $W$ is a DFA, $L(W)$ is a regular language, so it has a pumping length $p$ that is at most the number of states in $W$. Using the pumping lemma to explain why $M$ need only test words in $\\{a,b,c\\}^∗$ whose lengths are less than $p$ in order to ensure that if $L(W)$ contains at least one word with no $a$'s, $M$ will find one. Can I use that? If so, how? I am a bit stuck right now.

# Answer
Assume that the input is a valid description of a DFA $W$ (for any reasonable description this is a decidable problem). You need to show that, given $W$, is is possible to decide whether there exists a word $w \in \\{b,c\\}^\*$ that is accepted by $W$.

Since $W$ is a DFA, $L(W)$ is a regular language. By the closure properties of regular languages, $L' = L(W) \cap \\{ b,c \\}^\*$ is also regular (and you can construct a DFA $W'$ for it by simply deleting all transitions labelled $a$ from $W$).

Then the problem is equivalent to deciding whether $L'$ is empty. This problem is known to be decidable. In fact, you can even solve it in linear time w.r.t. the natural description of the DFA: you just need to decide whether there exists a path from the initial state to a final state in the graph induced by $W'$ (which can be done using, e.g., a breadth first search).

---

Here is an alternative (slower) approach that more closely resembles the one in your question. Design a Turing machine $T$ that, on input $W$, behaves as follows:

* Let $n$ be the number of states of $W$.
* For each $i=0, \dots, n-1$:
    + For each word $w \in \\{b,c\\}^i$:
        - Simulate $W$ on $w$.
        - If $W$ accepted $w$ then accept.
* Reject

It is clear that $T$ always halts and that if $W \not\in K$ then $T$ must reject. Therefore we only need to show that if $W \in K$ then $T$ accepts.

To show the above, it suffices to prove that the existence of some word $w \in \\{b,c\\}^\*$ accepted by $W$ implies the existence of some $w' \in \\{b,c\\}^\*$ with $|w'| \le n−1$ that is also accepted by $W$.

Among all possible words $w \in \\{b,c\\}^\*$ accepted by $W$, let $w'$ be one of those minimizing $|w|$ and suppose towards a contradiction that $|w'| \ge n$. Since the pumping length of $L$ is at most $n$, we can invoke the pumping lemma to write $w'$ as $xyz$ with $|y| \ge 1$. Then, $w''=xz \in L$ belongs to $\\{b,c\\}^∗$, is accepted by $W$, and satisfies $|w''| \< |w'|$. This contradicts the choice of $w'$.
> 3 votes

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