# Question
Title: Minimum vertices to remove from a graph so that no path exists between two given vertices anymore
Given an undirected graph $G=\\{V, E\\}$ with its vertices numbered from $1$ to $V$, given two vertices $s$ and $t$ $(1 \leq s \lt t \leq V)$, what is the minimum number of vertices (except $s$ and/or $t$) that we need to remove (we also remove the edges associated with those vertices) so that there doesn't exist any path between $s$ and $t$ anymore?

If it's difficult to solve under general constraints, can it then at least be solved efficiently in case the maximum possible degree of any vertex in the graph is $4$?

My current progress: Maybe it can be solved by using the BFS/DFS numbers obtained from starting BFS/DFS from $s$?

# Answer
> 2 votes
Your problem is known as *minimum vertex cut* or *minimum vertex separator*. There is a simple reduction from this problem to the directed minimum edge cut, adopted from notes by Locke.

The new graph contains vertices $(s,0),(t,1)$, and $(u,0),(u,1)$ for any $u \neq s,t$, as well as the following edges:

* For every $\\{s,u\\} \in E$: the edge $(s,0) \to (u,1)$.
* For every $\\{u,v\\} \in E$ (where $u,v \neq s,t$): the edges $(u,0) \to (v,1)$ and $(v,0) \to (u,1)$.
* For every $\\{t,u\\} \in E$: the edge $(u,0) \to (t,1)$.
* For every $u \neq s,t$: the edge $(u,1) \to (u,0)$.

A path $s \to x \to y \to z \to t$ in $G$ lifts to the following directed path in the new graph from $(s,0)$ to $(t,1)$: $$ (s,0) \to (x,1) \to (x,0) \to (y,1) \to (y,0) \to (z,1) \to (z,0) \to (t,1). $$ As can be seen, in order to realize an $s$-$t$ path, we need to use the edges $(u,1) \to (u,0)$ for all vertices $u$ appearing internally in the path.

We now give unit weight to the edges $(u,1) \to (u,0)$ and infinite (or large enough) weight to all other edges, and look for a minimum edge cut between $(s,1)$ to $(t,0)$; this can be solved by computing a maximum flow. A minimum edge cut in the new graph is the same as a minimum vertex cut in $G$.

---
Tags: graphs, planar-graphs, connected-components
---


# Question
Title: What is the time complexity of a Turing Machine that iterates through each prime number from 2 to K (assume oracle generates the next prime)?
Let `NextPrimeNumber` be an oracle that accepts a prime number `n` and returns the smallest prime number `m` such that `m > n`. It can be called by a Turing machine and returns the answer in constant time.

Let `F` be the Turing Machine that receives `K` a positive integer as a number. Suppose its code is the following:

```
current_prime = 2
while (current_prime <= K):
  current_prime = NextPrimeNumber(current_prime)

```

**What is the time complexity of `F`?**

If we printed out all numbers from `2` to `K` then it would take exponential time in terms of the bit length `k` of `K`. However we only iterate only over the primes, not all numbers from `2` to `K`. I believe primes represent `1/ln(K)` of primes less than or equal to `K`. Therefore the time complexity would be: `(2^k)/ln(K)` \- which would still be exponential or at least super-polynomial?

# Answer
> 1 votes
The running time is $O(K/\ln K)$. This is an exponential running time: the input takes $\lg K$ bits (assuming $K$ is specified in binary), so the running time is exponential in the length of the input. If you set $k=\lg K$, then the running time is $O(2^k/k)$, which is an exponential function of $k$.

---
Tags: time-complexity
---


title: Decoding CFG for odd length string-:

text:
# Question
Title: Decoding CFG for odd length string-:
```
S → aX | bX
X→ aS | bS | ε

```

This is required cfg, I want to learn how we arrived at this cfg? What steps did we follow to arrive here? Do we memorize some standard cfgs? I can derive strings using this but that is not useful when I don't know the cfg already.

I have solved a cfg on my own and came up with this, if you can tell me logic like this. So I thought strings would be ,b,aab,aba,abb,aaa, baa,bab,bba,bbb.

SO cfg will be-:

```
S->aP|aQ|aR|aS|bP|bQ|bR|bS

p->aPa
Q->aQb
R->bRa
S->bSb

```

This is wrong I know but this is the type of logic I love to solve problems with. i.e take "a" or "b" then combine that with even length strings, that gives me odd length string

# Answer
> 0 votes
Your grammar is *regular*. This means that it describes an NFA, which is in this case deterministic. Here is the DFA which was used to construct your grammar:

Each transition in this automaton corresponds to a rule:

* The transition from $S$ to $X$ labeled $a$ corresponds to $S \to aX$.
* The transition from $S$ to $X$ labeled $b$ corresponds to $S \to bX$.
* The transition from $X$ to $S$ labeled $a$ corresponds to $X \to aS$.
* The transition from $X$ to $S$ labeled $b$ corresponds to $X \to bS$.

Every final state also corresponds to a rule:

* $X$ being a final state corresponds to $X \to \epsilon$.

Finally, the starting symbol is the same as the starting state, in this case $S$.

Whenever your language is regular, you can similarly construct a DFA (or in fact, an NFA), and convert it to a regular grammar in this fashion.

---
Tags: context-free
---


# Question
Title: What do we conclude from diagonalization principle?
I understand $R\_{fa}$ etc. I understand why the diagonals are higlighted. I understand D={a,d,f}. But I don't understand what is the conclusion we derive from this?

# Answer
It's rather unfortunate that D is presented in the table, because the point is that D cannot possibly be in the table!

You construct a function (in this case D) that is different from all the rows in the table. The way you do that is by first taking the opposite of the first function's first element, the opposite of the second function's second element, and so on.

Then you have a function that differs from all the functions in the table. Why? Suppose that this new function D was actually in the table, in row i. But D was constructed in such a way that it differs from the ith function in the ith place.

We conclude that D is not in the table.

What does this give us? Well, if the set of functions like this was countable, then we could list them one by one in a table. But since D is a function and not in the table, it cannot be possible to list all the functions one by one. Hence the set of such functions cannot be countable.
> 1 votes

---
Tags: proof-techniques
---


# Question
Title: What is the contradiction of statement "if $n^2$ is odd then n is odd"
In my opinion the contradiction should be-: If $n^2$ is even then n is even. But it is written in my discrete mathematics book that, "n is even then $n^2$ is odd". How do we find contradiction statement?

This is what is written in my textbook.

# Answer
> 1 votes
The textbook shows an example of using a proof technique called "proof by contradiction".

Basically, if you want to prove $A\rightarrow B$, then this technique says: "assume that $B$ **doesnt** hold, but $A$ **does**. From here, we want to derive a contradiction (i.e, we want to derive some statement that is clearly nonsense)".

In this case, $A$ would represent the statement that $n^2$ is odd, and $B$ the statement that $n$ is odd.

---
Tags: proof-techniques
---


title: finish time of vertex in DFS

text:
# Question
Title: finish time of vertex in DFS
Will u.f and u.d of a vertex in DFS traversal change if we change order of vertices in adjacency list ? I know that u.d won't change but what about u.f? u is a vertex of the graph. u.f, u.d are finish and discovery times of the vertex u respectively in Depth traversal search algorithm.

# Answer
> 1 votes
Both the start time and the finish time of a vertex can change when edges are examined in a different order.

Here is an example of a DFS visit starting from vertex $a$. In the figure on the left the edge $(a,b)$ is examined before the edge $(a,c)$. In the figure on the right the order is reversed. Start times are in blue, while finish times are in red.

# Answer
> 0 votes
I can show the order's visit of vertices, using the algorithm **Depth first search**.

```
#include <iostream>
#include <vector>
using namespace std;
const int maximumSize=5;
vector<int> visited(maximumSize, 0);
vector<int> graph[maximumSize];
int vertices, edges, order;
void showContentVector(vector<int> input)
{
    for(int i=0; i<input.size(); ++i)
    {
        cout<<input[i]<<", ";
    }
    return;
}
void createGraph()
{
    cin>>vertices>>edges;
    int vertex0, vertex1;
    for(int i=1; i<=edges; ++i)
    {
        cin>>vertex0>>vertex1;
        graph[vertex0].push_back(vertex1);
        graph[vertex1].push_back(vertex0);
    }
    return;
}
void depthFirstSearch(int current, int previous, vector<int>& orderToDepth, vector<int>& orderFromDepth)
{
    if(visited[current]==1)
    {
        return;
    }
    visited[current]=1;
    ++order;
    orderToDepth[order]=current;
    for(int next : graph[current])
    {
        if(next==previous)
        {
            continue;
        }
        depthFirstSearch(next, current, orderToDepth, orderFromDepth);
    }
    orderFromDepth[order]=current;
    return;
}
int main()
{
    createGraph();
    vector<int> orderOfVisitTo(maximumSize, 0),
    vector<int> orderOfVisitFrom(maximumSize, 0);
    depthFirstSearch(1, 0, orderOfVisitTo, orderOfVisitFrom);
    cout<<"orderOfVisitTo <- ";
    showContentVector(orderOfVisitTo);
    cout<<endl<<"orderOfVisitFrom <- ";
    showContentVector(orderOfVisitFrom);
    return 0;
}

```

If we have the graph:

```
  1
 / \
2   3

orderOfVisitTo <- 0, 1, 2, 3, 0,
orderOfVisitFrom <- 0, 0, 2, 1, 0,

```

If we have the graph:

```
  1
 / \
3   2

orderOfVisitTo <- 0, 1, 3, 2, 0,
orderOfVisitFrom <- 0, 0, 3, 1, 0,

```

---
Tags: graph-traversal
---


# Question
Title: Problem reduction: Can YES-Instances also be mapped to NO-Instances if there is perfect correspondence?
> **Definition**: Problem A is reducible to problem B if an algorithm for solving problem B efficiently (if it existed) could also be used as a subroutine to solve problem A efficiently. When this is true, solving A cannot be harder than solving B. In these reductions, a YES instance of A maps to a YES instances of B and NO instances of A maps to a NO instances of B.

I want to focus on the part that a YES-Instance of A must be mapped to a YES-instance of B (and the same for NO-Instances).

For some problem I currently study I found a reduction which I am not sure of if it is allowed and follows the rules of reductions.

What I did was that I mapped the YES-instances of A to the NO-instances of B, (and the NO-instances of A to the YES-instances of B).

Is this allowed? I assume that i could just change the definition of Problem B to exactly exchange YES-Instances and NO-Instances, but I am somewhat unsure how to do it.

# Answer
> 1 votes
It depends on the exact definition of reduction that you are using. What you describe is not a many-one reduction, but (assuming that your reduction is computable) it is a Turing reduction.

Whether that's useful of not depends on what you're trying to prove. For example polynomial-time Turing reductions (called Cook reductions) are still useful to provide evidence that a problem can be solved easily / might be hard to solve but are less refined than polynomial time many-one reductions. i.e., Karp reductions (e.g., if you have a Cook reduction from a NP-Hard problem A to a problem B, then you cannot conclude that B is NP-hard).

# Answer
> 0 votes
> What I did was that I mapped the YES-instances of A to the NO-instances of B, (and the NO-instances of A to the YES-instances of B).

I was actually looking into this recently! This is a common type of reduction, but to my knowledge, there isn't a standard separate name for it. Instead, complexity theorists usually describe this as either:

* A **many-one reduction from $A$ to $B^C$**, or
* A **Turing reduction from $A$ to $B$.**

It's really much more restricted than a Turing reduction; a general Turing reduction uses an oracle for B as a subroutine to solve A, and may use several queries to B (and negate or process their answers). So a Turing reduction could potentially do a lot more than simply making one query to B and negating the result, which is what you are doing here.

So I would favor the "many-one reduction from $A$ to $B^C$" terminology, as that is more specific and clearly describes what you mean.

---
Tags: reductions, decision-problem, polynomial-time-reductions
---


# Question
Title: Inverse of Ackermann function and $\log^* n$
Consider inverse of Ackermann function, can we conclude that the growth rate of it as the same as growth rate $\log^\*n$?

# Answer
> 4 votes
No, since the Ackermann function grows faster than any primitive recursive function.

The iterated logarithm is one of the two inverse functions of tetration. As a primitive recursive function, Tetration with base 2 is "roughly" equivalent to $A(4,n)$, where $A(m,n)$ is the Ackermann function of two variables . $A(n,n)$ is assumed to be the Ackermann function in the question.

**Exercise.** Show that the inverse of Ackermann function grows slower than $\log^\*(\log^∗n)$.

---
Tags: algorithms, asymptotics
---


# Question
Title: Let Σ = {a} be a one-element alphabet and L ⊆ Σ^* be an arbitrary language over Σ = {a}. Show that L^* is regular
I have a computer science question: Let Σ = {a} be a one-element alphabet and L ⊆ Σ^\* be an arbitrary language over Σ = {a}. Show that L^\* is regular

These are all the facts I have been able to gather thus far: an alphabet Σ,

any set L such that

L ⊆ Σ ∗ is called a language over Σ

Fact 1 For any alphabet Σ,

any language over Σ is countable

Languages over Σ Fact 2 For any alphabet Σ , ∅,

there are uncountably many languages over Σ More precisely,

there are exactly C = |R| of languages over any non - empty alphabet Σ Languages over Σ Fact 1 For any alphabet Σ, any language over Σ is countable

Proof By definition, a set is countable if and only if is finite or countably infinite

1. Let Σ = ∅, hence Σ ∗ = {e} and we have two languages ∅, {e} over Σ, both finite, so countable
2. Let Σ , ∅, then Σ ∗ is countably infinite, so obviously any L ⊆ Σ ∗ is finite or countably infinite, hence countable Languages over Σ

Fact 2 For any alphabet Σ , ∅, there are exactly C = |R| of languages over any non - empty alphabet Σ Proof We proved that |Σ ∗ | = ℵ0 By definition L ⊆ Σ ∗ , so there is as many languages over Σ as all subsets of a set of cardinality ℵ0— that is as many as 2 ℵ0 = C

am i on the right track or do i need to rethink? can you please proffer tips on how to slve this if you can

# Answer
**Hint:** Let $w\in L$ be the smallest non-empty word. What can you say about the relation between $L^\*$ and $w$? How can you construct one from another?
> 0 votes

# Answer
If $|L|$ is finite, the result is trivial (since $L$ is regular). Therefore, suppose $L$ is infinite. There may be a simpler proof, but I didn't find it.

Consider $S = \\{|u|\mid u\in L\\}$, and $d = \text{gcd}(S)$. There exists a finite subset $S'=\\{x\_1, x\_2, …, x\_n\\}$ of $S$ such that $d=\text{gcd}(S')$. Without loss of generality, suppose $0\<x\_1\<x\_2\<…\<x\_n$ (if $0$ is in $S'$, we can just remove it). Note that for all $i\in\\{1, …, n\\}$, $a^{x\_i}\in L$.

Using Bézout's identity, there exist $a\_1, a\_2, …, a\_n\in\mathbb{Z}$ such that $\sum\limits\_{i=1}^na\_ix\_i = d$.

For convenience, I will suppose that $d = 1$ for the remainder of the proof, but it is similar to the general case.

Let $i\_0\in \\{1, …, n\\}$ such that $a\_{i\_0} = \min\\{a\_i\mid i\in \\{1, …, n\\}\\}$, and let $x = x\_1|a\_{i\_0}|\times \sum\limits\_{i=1}^n x\_i$.

Then $x$, $x + \sum\limits\_{i=1}^na\_ix\_i$, $x + 2\sum\limits\_{i=1}^na\_ix\_i$, …, $x + x\_1\sum\limits\_{i=1}^na\_ix\_i$ are consecutive numbers (since $\sum\limits\_{i=1}^na\_ix\_i = 1$), expressed as linear combination with non-negative coefficients of the $\\{x\_i\\}$. That means that $a^x$, $a^{x+1}$, $a^{x+2}$, …, $a^{x+x\_1}$ are words of $L^\*$. Since $a^{x\_1}\in L$, that also means that $\\{a^{kx\_1}\mid k\in \mathbb{N}\\}\subseteq L^\*$. We finally conclude that $\\{a^y\mid y \geqslant x\\}\subseteq L^\*$. That means that $L^\*\cup\\{a^y\mid y\<x\\} = \Sigma^\*$. Since $\\{a^y\mid y \< x\\}$ is finite, we conclude that $L^\*$ is regular.

In the general case, you can also find an integer $x$ such that $L^\*\cup \\{a^y\mid y\< x\\} = (\Sigma^d)^\*$. I will let you write the proof by yourself.
> 0 votes

---
Tags: complexity-theory, regular-languages
---


# Question
Title: Restore planar graph from vertex degrees
Suppose you are given a list of vertices (with known positions) and their respective degrees, find any set of non-intersecting edges that satisfies the vertex degrees. Or, in other words, connect the dots in a way that each one has the specified number of connections. It's not necessary to find all solutions, the first one is enough. Equivalently: given a degree sequence, find a planar graph that has that degree sequence.

I'm not sure how to even approach this task, seems like I need to find all possible graph connections (it gets even harder because the connection order matters). I feel like there should be some greedy approach (like trying to connect each vertex the specified number of times), but I'm not sure how to make it check all possible ways eventually.

# Answer
> 1 votes
## Mathematical Approach

Ideally, there would be an algorithm that directly and efficiently listed, from the degree sequence, only those graphs that are planar. However, that currently seems to be an open problem.

However your problem should be solvable using a combination of existing algorithms. There seem be at least two possibilities.

## Filtering the output of HH with planarity checking

This way would combine Havel-Hakimi (HH), and planarity testing. The idea would be to use HH to check if any graph exists for the degree sequence. Then, use a planarity check on that graph to see if it is planar.

The only difficulty is that HH gives you the first possible graph for a sequence and not all of them. There is a more general algorithm here :

http://web.cse.msu.edu/~cse835/Papers/On%20realizing%20all%20simple%20graphs%20with%20a%20given.pdf

for realizing (listing) all graphs for a degree sequence. To list them efficiently, this paper gives a method with polynomial delay:

http://www.cs.elte.hu/egres/tr/egres-11-11.pdf

note that the total size of the output may be exponential.

## Filtering Planar graphs by Degree Sequence

An alternative would to do the opposite : list all planar graphs on the number of vertices, and filter out (any) that match the degree sequence.

Although this sequence (https://oeis.org/A003094) grows very quickly, the approach outlined for plantri (https://users.cecs.anu.edu.au/~bdm/papers/plantri-full.pdf ) can be adapted to avoid generating examples with degrees above a specified maximum.

For some code that implements this approach, see https://github.com/mishun/plantri/blob/master/allowed\_deg.c which is based on this paper : G. Brinkmann, B. D. McKay and U. von Nathusius, Backtrack search and look-ahead for the construction of planar cubic graphs with restricted face sizes, MATCH, 48 (2003) 163-177.

## Weird hybrid approach

One final approach occurs to me, although it might have flaws that I cannot see:

1. 'Reduce' the degree sequence in all possible ways to tree-realizable ones
2. From the set of reduced sequences, generate trees
3. Connect these trees up to full graphs, planar checking as you go

To do step 2, I found \[this thesis\]\[1\] by Samuel Stern that gives what looks like an efficient algorithm, but the complexity given is not clear to me - $O(c\_n(n^9))$ where $c\_n$ is the number of non-isomorphic trees on n vertices.

The advantage of this approach would be that you should be able to check for planarity with each edge added to the trees, thus 'weeding out' any that cannot be planar. \[1\]: https://digitalcollections.wesleyan.edu/object/ir-672

---
Tags: algorithms, graphs, planar-graphs
---


# Question
Title: Difference between forward/backward slicing and reaching definition - def/use - use/def chains
I'm a little bit confused about the difference between forward/backward slicing and the use/def-def/use as part of the reaching definitions technique. Isn't the use-def chain supposed to be equivalent to the backward slicing?

Let's assume we have a line that uses some variables. Like: `x = y + z`.

If we try to find all the code locations that influenced the given code line (backward slicing), shouldn't it be the same as all the entries of the use-def chain of the variable `x`?

# Answer
Backward slicing includes both data and control dependencies while ud-chains consider only data depedencies.
> 1 votes

---
Tags: data-flow-analysis
---


# Question
Title: Why is this equality about the relative translation in the iterative closest point (ICP) algorithm obvious, and how can I derive it?
I'm a computer science bachelor student tasked with understanding **On the ICP Algorithm** by Esther Ezra, Micha Sharir, and Alon Efrat, and I'm having a lot of difficulty with even supposedly obvious claims. The setup is as follows, wherein we only look at translation, not rotation:

Let $A = \\{a\_1, ..., a\_m\\}$ and $B = \\{b\_1, ..., b\_n\\}$ be two point sets in $d$-space, for $d\ge1$, and suppose that the ICP algorithm aligns $A$ to $B$; that is, $B$ is fixed and $A$ is translated to best fit $B$.

At every iteration $i$ the ICP algorithm tries to find a relative translation vector $\Delta t\_i$ that minimises its cost function, in this case the *root mean square* $$\mathrm{RMS}(\Delta t\_i) := \frac{1}{m} \sum\_{a\in A} || (a + t\_{i-1} + \Delta t\_i) - N\_B(a + t\_{i-1}) ||^2,$$ where $||\cdot||$ denotes the Euclidean norm, $N\_B(a)$ denotes the nearest neighbour of $a$ in $B$, and $m = |A|$.

The paper states:

> #### Lemma 2.3
>
> At each iteration $i \ge 2$ of the algorithm, the relative translation vector $\Delta t\_i$ satisifies $$\Delta t\_i = \frac{1}{m} \sum\_{a \in A} \left(N\_B(a + t\_{i-1}) - N\_B(a + t\_{i-2})\right),$$ where $t\_j = \sum\_{k=1}^j \Delta t\_k$.
>
> #### Proof
>
> Follows using easy algebraic manipulations, based on the obvious equality that follows by construction $$\Delta t\_i = \frac{1}{m}\sum\_{a \in A} \left(N\_B(a+t\_{i-1}) - (a + t\_{i-1})\right).$$

Unfortunately this ***obvious equality*** is not obvious to me, or at least not how I would derive/construct it.

Informally it seems plausible and intuitive to me that $\Delta t\_i$ is equal to the average difference between the current and previous nearest neighbour of each $a$, but I'm not sure how I methodically arrive at this equality.

# Answer
Indeed, that "obvious equality" is not that "obvious", except for people who have solved one or more similar problems.

Here is a transformation formula, where $b=(a + t\_{i-1}) - N\_B(a + t\_{i-1})$ and $c$ is some term that does not involve $\Delta t\_i$.

$$\mathrm{RMS}(\Delta t\_i) =\frac{1}{m} \sum\_{a\in A} ||\Delta t\_i +b||^2 =||\Delta t\_i + \frac{1}{m}\sum\_{a\in A}b||^2 + c$$

So, $\mathrm{RMS}(\Delta t\_i)$ achieves its minimum value when $$\Delta t\_i = -\frac{1}{m}\sum\_{a\in A}b=\frac{1}{m}\sum\_{a \in A} \left(N\_B(a+t\_{i-1}) - (a + t\_{i-1})\right).$$

Once that transformation formula is known, that equality should become obvious to you, since it is also your intuition that $\Delta t\_i$ be "equal to the average difference between the current and previous nearest neighbour of each $a$".

---

Let see how we can prove that transformation formula. Recall that $m$ is the cardinality of $A$.

$$\begin{aligned} \frac{1}{m} \sum\_{a\in A} ||\Delta t\_i +b||^2 &=\frac{1}{m} \sum\_{a\in A} (\Delta t\_i+b)\cdot(\Delta t\_i+b)\\ &=\frac{1}{m} \sum\_{a\in A} (\Delta t\_i\cdot\Delta t\_i + 2b\cdot\Delta t\_i + b\cdot b) \\ &=\Delta t\_i\cdot\Delta t\_i + \frac{2}{m}(\sum\_{a\in A}b)\cdot\Delta t\_i + \sum\_{a\in A} b\cdot b \\ &=(\Delta t\_i + (\frac{1}{m}\sum\_{a\in A}b))\cdot (\Delta t\_i + (\frac{1}{m}\sum\_{a\in A}b)) + c \\ &=||\Delta t\_i + (\frac{1}{m}\sum\_{a\in A}b)||^2 + c, \\ \end{aligned}$$

where $$c=\sum\_{a\in A} b\cdot b - (\frac{1}{m}\sum\_{a\in A}b)^2.\quad\quad \checkmark$$
> 1 votes

---
Tags: algorithms, algorithm-analysis, optimization, derivation
---


# Question
Title: CISC and RISC - synchronous and asynchronous
I have two opposing ideas. I think that all the instructions in a RISC take the same time what makes me believe RISC is associated with synchronous.

At the same time i think that CISC should be synchronous and RISC should be asynchronous.

Can you tell me if RISC is associated with asynchronous and CISC is associated with synchronous? Why?

# Answer
> I think that all the instructions in a RISC take the same time what makes me believe RISC is associated with synchronous.

It's not true that all instructions in a RISC CPU take the same time. Even in the classic RISC pipeline, the pipeline will stall in some circumstances. Pipeline interlocks and control hazards are the ones that Hennessy and Patterson go into some detail about, but they also mentioned data cache misses.

Even if you ignore those complications, it's unrealistic to design a general-purpose CPU where every instruction takes the same time these days. Programmers want floating point, and SIMD operations, and so on.

> Can you tell me if RISC is associated with asynchronous and CISC is associated with synchronous?

On, that's easy: They're not.

Truly asynchronous CPUs are rare, for a few reasons. One of them is that you can't (currently) prototype asynchronous logic on an FPGA, and it's much harder to express in Verilog or VHDL than synchronous logic.

Having said that, it is easier to implement a RISC pipeline in asynchronous logic than a CISC pipeline (e.g. Sproull's Counterflow Pipeline). However, even this is a bit misleading because the boundary between RISC and CISC is quite fuzzy these days. Most modern CISC CPUs use RISC cores internally, and dynamically translate the CISC instruction stream into RISC code. The main reason for this is that the same features which make RISC attractive (e.g. fixed-size instructions which can be buffered) are also the ones which make superscalar execution work.

So to the extent that asynchronous logic works, modern CISC CPUs can benefit almost as much as RISC CPUs can.
> 4 votes

# Answer
Actually, instructions don't all take the same time in RISC. They are forced to all take a fixed number of cycles, but the latencies will vary, and even within the same instruction. For instance, adding 1 to 0x01111111 is harder than adding 1 to any even number.

And you can do RISC or CISC regardless of the strategy used to obtain such an architecture. It isn't the number of instructions needed to produce a result that is the concern here, but more the variability of the lowest-level instructions.

Consider the clock rate, that is just the time it takes for the worst-case instruction (RISC) or instruction part (CISC) to consistently run reliably. It is the lowest common denominator and is applied to all instructions, even those with significantly lower latency. However, if you can run each instruction the precise amount it needs at a given time, you could improve performance.

So the above considerations affect your build philosophy. For a clocked system, you'd be racking your mind trying to figure out how to eliminate certain bottlenecks that are holding back your clock rate. For a clockless implementation, you'd be more concerned with improving the performance of nominal/average values and operations.

**Clocked Approach**

If you are designing a 6502-similar CPU using the synchronous approach, you'd be trying to figure out how to do BCD math faster to not slow the critical path for the rest. So maybe you'd use a carry-skip adder arrangement or break down your BCD instructions internally to require 2 or more cycles. You would figure that it isn't fair to hold back the other instructions because BCD is slower than binary math, and that making the BCD instructions require more cycles to complete by breaking them into smaller micro-ops would be worth it for a faster clock rate overall.

**Asynchronous Approach**

Designing the same type of CPU above, you wouldn't be as concerned with edge cases that take longer as they will be allowed to take what time they need when necessary. While you could do a carry-skip or CLA adder arrangement, you won't feel as compelled since the edge cases won't cut into the critical path in every instance.

Interestingly, this approach could even help slower operations. Consider an instruction that takes 1.6 times the usually-allowed latency. On a clocked system, you'd need to break that up into 2 instructions or micro-ops. On a clockless system, you can give it the exact extra time that it needs.

**Back to the RISC part of the question.**

It is easier to think of RISC in terms of fixed cycles, but it is more about the size of the building blocks you use. It is more about using instructions that just do one task (though that can be a group of things that happen coincidentally or in parallel) as opposed to using larger instructions that require a number of sub-tasks performed in series. This distinction can be blurry at times. For instance, the Gigatron TTL computer is a RISC machine on the native Harvard side, but there are a few instructions that do up to 3 things at the same time (OR/AND during a memory read and route that to the port while incrementing the index register). Now, instructions such as that are used to make the vCPU interpreter that allows user code to run, and that is like microcode in that it builds more complex instructions.

So once you take the clock off the table, then you'd still have a RISC machine. It would be harder to quantify as such, but that won't change. What will change are the latencies per instruction (and even within the same instruction ran at different times such as math operations). Clocks are just arbitrary time units designed to take the worst cases into account. But you could otherwise use a RISC model. The clock thing is about a different type of granularity than what is commonly thought of in RISC v. CISC.
> 2 votes

# Answer
A purely asynchronous CPU would not need a clock, so based on that point alone, it is clear that RISC and CISC are both synchronous as both have their operations granulated into clock bins. However, both RISC and CISC processors can have asynchronous logic blocks nestled between clocked components to achieve particular logic functions.
> 1 votes

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


# Question
Title: Why the multiplier and quotients can not store in the ACC?
When I study the Arithmetic Unit, there is the below information:

there I have some questions:

1. Why the multiplier must store in the `MQ` and the product must divide into the high part and low part?
2. Why the quotients must store in the MQ? why the multiplier and quotients can not store in the ACC?

# Answer
> 1 votes
The issue here is that the product is often twice as big as the accumulator. So only half can fit into the accumulator. So the rest must go into another register. Even the 286 does it this way. You can only store the low part in the AX register. The rest will be returned in the DX register. Except in this case, Acc is the high part of the result and the low part stores in MQ. Acc is not wide enough to hold the entire result. I don't know why they put the low part of the answer in MQ rather than Acc.

On divisions, this works similarly. On older x86 machines, when you divide, the quotient is placed in AX and the modulus is returned in DX.

---
Tags: arithmetic, cpu
---


# Question
Title: Is the language $L=\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \}$ regular or not regular?
I'm trying to understand how to prove a language is regular or not regular, for example this language: $$L=\\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \\}$$ Is this language regular or not?

**My solution**
Using the pumping lemma, I can choose a string with a pumping length $p$ like: $w=a^{5+p}b^p$, then $x = a^j, y=a^l$ and $z=a^kb^p$ such that $j+l+k=5+p$, I will pump with $i=0$, so the string will be $xz=a^{j+k}b^p$, this is not regular because $j+k\<p$.

Am I correct about this? Thanks for your help !

# Answer
> 1 votes
If $L$ is regular, then so is $L\\{b\\}^5$. You can conclude by studying $L\\{b\\}^5$ (which is a very classic language).

Also in your proof, you cannot guarantee that $j+k \< p$, but $j+k \< 5 + p$ is enough.

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


title: Regularity condition for cases 1 & 2

text:
# Question
Title: Regularity condition for cases 1 & 2
My question concerns the version of the Master Theorem described in CLRS and in this handout.

I already understand the following:

* If the regularity condition in case 3 does *not* hold, then we can't apply case 3.
* If the regularity condition in case 3 *holds* then $f(n)=\Omega(n^{\log\_ba\ +\ \epsilon})$ is definitely true.

I have two questions:

* Can there be a situation where $f(n)=\Omega(n^{\log\_ba\ +\ \epsilon})$ is true but the regularity condition does not hold?
* Why isn't there a regularity condition for cases 1 and 2? Is there a proof that a similar condition is unnecessary (or at least what is the intuition for it being unnecessary in cases 1 and 2)?

# Answer
> Can there be a situation where $f(n)=\Omega(n^{\log\_b a + \varepsilon})$ is true but the regularity condition does not hold?

Yes. Let $f(n)$ be equal to $n$ if $n$ is between an even power of two and the next (odd) power of two, and $2n$ otherwise. Formally:

$ f(n)= \begin{cases} n &\mbox{if } \exists k \in \mathbb{N} : 2^{2k} \le n \< 2^{2k+1}; \\ 2n &\mbox{otherwise}. \end{cases} $

Consider the recurrence $T(n)=T(n/2)+ f(n)$. In this case $a=1, b=2$, and $n^{\log\_b a + \varepsilon} = n^\varepsilon$. You can see that, for $\varepsilon\<1$, $f(n) \ge n = \Omega(n^\varepsilon)$.

Nevertheless the regularity condition is not satisfied. Indeed, for any choice of $c\<1$ and $n\_0 \ge 0$, you can pick $n= 2^{2k}$ for some sufficiently large integer value of $k \ge 1$ that satisfies $2^{2k} \ge n\_0$.

Then $f(n)=n$ while $n/b = n^{2k-1}$ is an odd power of $2$, hence $a f(n/b)=2 \cdot (n/2) = n$. This shows that $a f(n/b) = n = f(n)$ and therefore we cannot have $a f(n/b) \< c f(n)$.

> Why isn't there a regularity condition for cases 1 and 2? Is there a proof that a similar condition is unnecessary...

Yes. The proof you are looking for is exactly the standard proof of cases 1 and 2 in the master Theorem (which does not require the regularity condition).
> 1 votes

# Answer
First, let's discuss the meaning of the regularity condition. It states that $af(n/b)\<=cf(n)$ for a constant $c \< 1$ and $n \> n\_0$. Now consider the recurrence equation $T(n) = aT(n/b) + f(n)$. The corresponding recursion tre has $f(n)$ as its root node, and $a$ children each one doing $f(n/b)$ work. In case three of the master theorem the cost of the tree is dominated by the cost of its root node, and this corresponds to a geometric series with decreasing terms. In case one the cost of the tree is dominated by the cost of its leaves and this corresponds to a geometric series, with increasing terms. Finally, in case 2 the cost of the tree is evenly distributed among the levels of the tree.

Therefore, in case one the work done in the root node is less than the work done by its children, and in case two it is equal.

Now note that the conditions associated to cases one and two are already enough to assure that the work done in the root node is less than the work done by its children ($f(n)=O\left(n^{\log \_{b} a-\epsilon}\right)$ for $\epsilon \> 0$), and in case two it is equal ($f(n)=\Theta\left(n^{\log \_{b} a}\right)$). No additional conditions are required: indeed, no additional assumptions are in the master theorem for cases one and two.

What about case three? The associated condition ($f(n)=\Omega\left(n^{\log \_{b} a+\epsilon}\right)$ for $\epsilon \> 0$) is not enough to guarantee that the work done in the root node is greater than the work done by its children, and this is why we also need the regularity condition. Here is an example, answering your question, in which the condition holds, but the regularity condition does not:$T(n) = T(n/2) + n (\sin(n - \pi/2) + 2)$. Indeed, for $f(n) = n (\sin(n - \pi/2) + 2)$ there is at least a value $x$ such that $f(x/2) \> f(x)$ (actually many such $x$ exist), but $f(n) \geq n \ \forall n$.
> 1 votes

---
Tags: time-complexity, asymptotics, runtime-analysis, recurrence-relation, master-theorem
---


# Question
Title: Algorithmn for SIMD matrix multiplication
I've been trying to implement a program for matrix multiplication of multiple of 4 (ex: 4x4, 8x8, 16x16, etc.) and while I my program works for 4x4 matrix, it only fills the first 4 row of every other matrix (which are filled with the proper value).

My guess it's because I don't have the proper algorithm implemented, so I made some search and I came upon that link:

http://www.mathcs.emory.edu/~cheung/Courses/561/Syllabus/90-parallel/SIMD.html

While I understand the first step of the algorithm, I would appreciate if someone could explain to me why the final row of 12 18 18 in the example becomes 13 19 19? I know these are the good values for the result matrix, but I seem to be missing a step and I guess if I could understand it I could come up with a proper algorithm to solve my problem.

I can provide the code I have so far by personal inbox if anyone is interested, but basically it's an adaptation of this algorithm: https://codereview.stackexchange.com/questions/101144/simd-matrix-multiplication

# Answer
The diagram seems to have a number of mistakes. Firstly, the top right entry is a 5 in Step 3 but a 1 everywhere else, without explanation. Secondly, pairs of numbers are multiplied that are not part of the straightforward definition of matrix multiplication. Unless there is something amazingly clever going on here that is being glossed over, I think it's just plain wrong, and what they're trying to show is this:

In step 1, the blue 2 is multiplied by the top row of the second matrix, and the result added to the top row of the result, i.e. 2 * \[3, 6, 2\] = \[6, 12, 4\]. In the second step, the blue circle should move right one column to the 3, which is multiplied by the new red row and again added to the first step, i.e. 3 * \[2, 2, 4\] = \[6, 6, 12\], making the top row of the result \[12, 18, 16\]. Finally in step 3, the blue circle moves right again, giving 1 * \[1, 1, 3\] = \[1, 1, 3\], which is added to give \[13, 19, 19\]. Then the blue circle drops to the second row and it repeats.

In other words, to summarize the algorithm in pseudocode, it's something like:

```
For i = 0...height_of_first_matrix-1:

     For j = 0...width_of_first_matrix-1:

            multiply left_matrix[i,j] by j-th row of right matrix and add to i-th row of result

```

Hope that makes sense!
> 1 votes

---
Tags: c++
---


# Question
Title: The amount of ROM needed to implement a 4-bit multiplier?
For a 4-bit multiplier there are $2^4 \cdot 2^4 = 2^8$ combinations.

The output of 4-bit multiplication is 8 bits, so the amount of ROM needed is $2^8 \cdot 8 = 2048$ bits.

Why is that? Why does the ROM need all the combinations embedded into it?

What will be the case with RAM?

# Answer
As shown in the figure bellow (general architecture of ROM):

to address 8-bit numbers correctly your ROM size should be: $2^8 \times 8$ bits.
> 8 votes

# Answer
If you are storing all the value of the function (in this case, multiplication) in a big table, then the size of this table is $2^{\text{# input bits}}\cdot \text{# output bits}$. This becomes impractical rather quickly, so CPUs implement arithmetic operations differently.
> 6 votes

# Answer
To address your last point (albeit late): whether the lookup table is stored in RAM or ROM makes no difference to the size needed (although it would almost never make sense to store a multiplication table like this in RAM).

If it *were* stored in RAM you would either have to load it from ROM or populate it manually, neither of which make much sense in the typical situations where you might use a lookup-table.

Copying a ROM table to RAM would typically only be used if the contents were to be updated over time, and the ROM copy is just the starting point (not the case with multiplication). The only other likely use-case that comes to mind would be where you use a ROM to "bootstrap" the system -- copying programs and data to RAM -- and then switch the ROM out of normal address-space and run everything from RAM.

As for populating manually: using a look-up table for multiplication would tend to imply that you're on fairly low-level hardware, where you either don't have a full-blown CPU (in which case there would be nothing to populate the table) or it's a fairly basic CPU (in which multiplication is slow). In the latter case, it *could* make sense to populate a RAM table at start-up (essentially creating a cache), but since you would have to evaluate all combinations, this would lead to a lengthy delay before you could do "real work".
> 4 votes

# Answer
If you want to implement a multiplier in a lookup table in memory of any sort, then for 4x4, you'd need address space that covers the width of both source operands. In this case, you'd 8 bits. That is 256 addresses, and room for every combination. When you multiply, you double the bits needed of each operand in the result.

The type of memory you use doesn't really matter. While you can use a ROM, you could build the chart in RAM. It would be harder if you have not ROM to copy to it since you'd have to first build the chart there. And you wouldn't need a RAM-based chart unless the CPU didn't provide that functionality. So you'd have to use many addition loops (or shifting in some cases if you have that, or a different type of specialized instruction such as LEA) to build the chart. That would be a lot of overhead, so you'd want to make sure if you create a LUT multiplier in software, that the software uses multiplication extensively.

But since the RAM-based LUT is not on a discreet chip and likely shares with other things. Then you'd have to first compute the addresses and then offset your way into the table. In a higher-level language, you'd likely use a matrix (and array of arrays) for this. While the programming to use the table would be easier for the coder, matrices tend to pull in lengthy library functions which have their own overhead. So if you are trying to replace a slow multiplication function in the CPU with a faster one, you may end up disappointed.

Just so I am not misunderstood, just having a ROM to do multiplication is not what would improve speed over using RAM. ROM itself is slower than RAM. But what would be faster is if you had a CPU with a ROM like this inside or you made a homebrew CPU using discrete logic and you had an opcode to put the multiplicand and multiplier on the address bus of the ROM (or an SRAM shadowing the ROM) and put the product on the data bus of the RAM. No calculation of addresses would be needed as that is directly assembled from the numbers supplied. So what I said earlier about issues addressing the RAM have to do with sharing the RAM with other things and needing to compute the addresses. As a minimum, doing it in software would require knowing where it is in memory and adding the numbers to multiply to it in a concatenated form (like high nibble is A and low nibble is B). So it would be a matter of setting the page register to the correct page and adding the assembled address to the offset and reading the memory there.

Now, if you have more than 8 address bits into your ROM, you could use that for other things. If you use a ROM (or RAM copied from a ROM) for an entire ALU, then the remaining upper bits would be used to select the operation other than multiplication.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Online binary tree creation via $a\to ax$ and $ab\to a(bx)$
I wish to construct a sequence of unlabeled binary trees $T\_n$ satisfying the following properties:

* $T\_n$ has $n$ leaves
* $T\_n$ is well balanced (height $\lg n+O(1)$)
* $T\_n$ is obtained from $T\_{n-1}$ by one of the two operations $t\to (t,\ast)$ or $(t,t')\to (t,(t',\ast))$

In other words, we are limited to right insertion and rotation at the root. Ideally, the sequence $T\_n$ should also have a simple recursive form for any $n$. Is it possible?

Originally, I attempted to use the sequence $T\_1=\ast$, $T\_n=(T\_k,T\_{n-k})$ where $k$ is the largest power of 2 less than $n$, but I believe that it is not possible, since $T\_8$ cannot be obtained from $T\_7$ by the two operations, and one would need an infinite number of deeper operations like $(a,(b,(c,d)))\to(a,(b,(c,(d,\ast))))$ to get the whole sequence. Furthermore, an exhaustive enumeration shows that $T\_8$ in this sequence (the perfect binary tree on 8 leaves) is not obtainable, although there are some trees with height 4 in the sequence, so perhaps $\lg n+O(1)$ is not impossible.

# Answer
We can characterize the trees that are constructible as follows. If $T\_n=(a,b)$, then both $a$ and $b$ must be subtrees of every following $T\_k$, $k\>n$, because neither of the two operations can split them. So let $A\_n$, $B\_n$ be sequences defined as $T\_n=(A\_n,B\_n)$ (for $n\>1$). In the base case we have $A\_2=B\_2=\ast$, and at each following step we either have $A\_{n+1}=(A\_n,B\_n)$ and $B\_{n+1}=\ast$ or $A\_{n+1}=A\_n$ and $B\_{n+1}=(B\_n,\ast)$.

In particular, $B\_n$ can only ever be $\ast$ or $(B\_{n-1},\ast)$, so $B\_n$ must be a left leaning path like $(((\ast,\ast),\dots,\ast),\ast)$. Similarly, $A\_n$ consists of a left leaning path with $B\_i$'s hanging off it as in $(((\ast,B\_{i\_k}),\dots,B\_{i\_2}),B\_{i\_1})$, so it has a restricted structure.

Let a $B$ tree mean a tree which has only leaves coming off the left spine, and an $A$ tree is a tree with $B$ trees coming off the left spine. Note that $T\_n$ is also an $A$ tree.

Unfortunately, $A$ trees are not even balanced up to a constant factor: they are at best height $\Omega(\sqrt n)$. A $B$ tree with $n$ leaves has height exactly $n-1$, so the heaviest $A$ tree of height $k$ has the form $(((\ast,B\_1),B\_2),\dots,B\_k)$ (where the subscript is now being used to indicate the number of elements in the $B$ tree), and this has $1+1+2+\dots+k=\frac{k(k+1)}{2}+1=O(k^2)$ leaves, so any $A$ tree with $n$ leaves has height at least $\Omega(\sqrt n)$.

This generalizes to the case of deeper rules like $(a,(b,c))\to(a,(b,(c,\ast)))$. In this case, we find that $T$ has the form $(A,(B,C))$ where $C$ has $\*$ off the left spine, $B$ has $C$ off the left spine, and $A$ has $B$ off the left spine (so $C$ is a $B$ tree and $B$ is an $A$ tree in our previous terminology). By a similar argument, we find that $T$ can have at most $O(k^3)$ leaves for height $k$, so it has height at least $\Omega(\sqrt\[3\]{n})$, and in general, with $m$ such rules you get height at least $\Omega(\sqrt\[m\]{n})$, so optimal balance is not possible.
> 0 votes

---
Tags: algorithms, asymptotics, combinatorics, binary-trees
---


# Question
Title: A different way of reducing subset sum to partition
For brevity, let $s(D) = \sum\_{d\in D} d$ denote the sum of the elements in $D$.

Given a set $A = \\{a\_1, \dots, a\_n\\}$ of positive integers, and a target value $K$, the **subset sum** problem is to determine if there exists a subset $A' \subseteq A$ such that $s(A') = K$.

Given a set $B = \\{b\_1, \dots, b\_m\\}$ of positive integers, the **partition problem** is to determine if there exists a subset $B' \subseteq B$ such that $s(B') = s(B \setminus B')$.

**Theorem.** Subset sum $\propto$ partition.

The proof found in most references, and the one given in the relevant CS SE question, performs the reduction from subset to partition by letting $S = s(A)$ and taking $B = A \cup \\{S + K, 2S - K\\}$ in the reduction.

I came up with the following alternative approach.

---

**Proof.** Given an instance of subset sum, take $S = s(A)$ and construct an instance of the partition problem with $B = A \cup \\{S, 2K\\}$.

Suppose that $B$ admits a partition $B' \subseteq B$. Because $2K + S \> s(A)$, we must have either $2K \in B'$ and $S \in B \setminus B'$ or vice-versa. Assume (without loss of generality) that the former is the case.

Now, let $A' = A \cap (B \setminus B')$ denote the elements of $A$ that are not in $B'$. We know that $$\begin{align} &&s(B') &= s(B \setminus B') \\ \iff\quad&& 2K + s(A\setminus A') &= S + s(A') \\ \iff\quad&& 2K + s(A\setminus A') + s(A') &= S + s(A') + s(A') \\ \iff\quad&& 2K + S &= S + 2s(A') \\ \iff\quad&& K &= s(A') \\ \end{align}$$

Conversely, if $A$ admits a subset having $s(A') = K$, then it is easy to see that $B' = \\{2K\\}\cup (A\setminus A')$ is a valid partition for $B$.

---

Is this proof correct?

# Answer
Yes, but perhaps more cumbersome than necessary, and less readable than it could be. Here's an alternative approach:

Let $S = \\{e\_1, ..., e\_n\\} , W \in \mathbb{N}$ be the instance for subset sum and let $$U = S \cup \left\\{ \sum S , 2W \right\\}$$ be the instance for partition.

Since, as you noted, $\sum S + 2W \> \sum S$, we can assume that if $A$ and $B$ partitions $U$ in equal sums, $\sum S \in A$ and $2W \notin A$.

Now, $$ \sum A = \sum B = \sum U /2 = \frac{\sum S + \sum S + 2W}{2} = \sum S + W.$$

But since $\sum S \in A$, it follows that $\sum A - \sum S = W$, which is precisely the set we are looking for in subset sum.

You also need to prove that a yes instance for subset sum translates to a yes instance for partition, but that is straightforward.
> 1 votes

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


# Question
Title: Which type can cause problems with encapsulation in Java?
Out of the following, which type can cause problems with encapsulation?

A. Int

B. Int\[\]

C. String

D. non of the above

I chose D and was incorrect. I am kind of confused what this questions is asking about... I just began to learn about the encapsulation and it seems it's just to keep the fields private and not changeable from outside of the class. Why would any type cause problems?

# Answer
> 1 votes
I think it should be **(B)** because when using implement `get method` to get the array will be able to change the array even if it's private through the getter because the "get" method will return a reference to the array, not the array itself.

Check this link

---
Tags: programming-languages, java, object-oriented
---


# Question
Title: How can it be proved that two different kinds of dfs unequivocally define a unique tree?
How can it be proved that two different kinds of dfs ( for example let call them `inorder` and `postorder`) unequivocally define a unique tree? Let's say we have two dfs arrays:

```
A0(inorder) = {a01, a02, a03, ... a0n};
A1(postorder) = {a11, a12, a13, ... a1n};

```

So can we say that the pair {A0 and A1} defines a unique tree, if so how can we prove it?

# Answer
> 2 votes
Since your are talking about in-ordering, I will suppose that the tree is a binary tree (otherwise I don't know how the in-order is defined).

This result of unicity can be proven by induction of the length of arrays, but only if nodes are distincts (which I will assume for the rest of the proof). Suppose $T$ to be a tree with an in-order given by $A = (a\_1, a\_2, …, a\_n)$ and a post-order given by $B = (b\_1, …, b\_n)$.

* If $n = 0$, then the tree is the empty tree and is unique.
* Suppose the result is true for all lengths of array $\leqslant n$, $n$ being a fixed non-negative integer. Let $T$ be a tree with an in-order given by $A = (a\_1, a\_2, …, a\_{n+1})$ and a post-order given by $B = (b\_1, …, b\_{n+1})$.

+ Since $B$ is a post-order, that means there exists $k\in \\{0,…, n\\}$ such that $T = Node(b\_{n+1}, T\_l, T\_r)$, and $T\_l$ has a post-order $B\_l=(b\_1, …, b\_k)$ and $T\_r$ has a post-order $B\_r = (b\_{k+1}, …, b\_{n})$.
    + Since $A$ is an in-order, that means that $T\_l$ has an in-order $A\_r=(a\_1, a\_2, …, a\_k)$, $b\_{n+1} = a\_{k+1}$ and $T\_r$ has an in-order $A\_l=(a\_{k+2}, …, a\_{n+1})$. Since nodes are distincts, the equality $b\_{n+1} = a\_{k+1}$ guarantees a unique value of $k$.
    + Now, $T\_l$ has in-order $A\_l$ and post-order $B\_l$, and since $|A\_l| = |B\_l| = k \leqslant n$, there exists (by induction hypothesis) a unique corresponding tree. The same way, there exists a unique possible $T\_l$

We conclude that there exists a unique tree $T = Node(b\_{n+1}, T\_l, T\_r)$ with in-order $A$ and post-order $B$.

---
Tags: graphs, trees, discrete-mathematics, graph-traversal
---


# Question
Title: Efficient solution for a particular form of quadratic Diophantine equation
***Preface:*** I know there are a lot of posts already here and elsewhere about algorithms for solving quadratic Diophantine equations in general. I am posting this in the hope that my very particular case might allow an approach much simpler (both in time complexity and the need for me to relearn combinatorics) than those for the general case.

---

I have a program in which I must solve equations of the following form.

$$ x(A-x)=y(B+y) \\\~\\ \mbox{or, equivalently,} \\\~\\ x^2 - Ax + By + y^2 = 0 $$

Subject to the following nontrivial (I think) constraints.

* $A, B \in \mathbb{N} \quad \mbox{and} \quad A, B \quad \mbox{are even}$
* $A \gt B$
* $x(A-x)=y(B+y)\<\frac{A^2-B^2}{8}$
* $1 \le x \lt \frac{A-B}{2}$
* $1 \le y \lt \frac{A-B}{2} - 1$

The even, natural numbers $A$ and $B$ are the only parameters.

These constraints are sufficient to reduce the number of possible values of $x,y$ to a few hundred or thousand (342 in the example below). Therefore, rote trial and error can usually find a solution in well under a second. But I'm convinced there must be a smarter way to do this, rather than just checking all possible answers. Therefore, I appeal to you who are smarter than me.

---

##### Example

$$ \mbox{Let } A = 50 \\ \mbox{Let } B = 10 \\\~\\ x(50-x)=y(10+y) \< \frac{50^2-10^2}{8} = 300 \\ 1 \le x \lt \frac{50-10}{2} = 20 \\ 1 \le y \lt \frac{50-10}{2} - 1 = 19 $$

This equation has two solutions.

$$ \begin{align} x&=2,\quad y=6 \\ x&=6,\quad y=12 \end{align} $$

The potential solutions $x=8,y=14$ and $x=14,y=18$ are disqualified because $x(A-x)=y(B+y) \ge 300$ in both cases.

# Answer
> 3 votes
If you apply this transformation:

$$\begin{eqnarray\*}-4x & = & X - 2A \\ -4y & = & Y + 2B\end{eqnarray\*}$$

You get a quadratic Diophantine equation without the linear terms:

$$X^2 + Y^2 = 4A^2 + 4B^2$$

Can you take it from there?

**ADDENDUM**

Just for completeness, suppose you have a general six-term quadratic Diophantine equation:

$$ax^2 + bxy + cy^2 + dx + ey + f = 0$$

Compute the discriminant of the homogeneous quadratic part:

$$D = b^2 - 4ac$$

Then this substitution eliminates the linear terms, keeping the homogeneous part untouched:

$$\begin{eqnarray\*}Dx & = & X + 2cd - be \\ Dy & = & Y + 2ae-bd\end{eqnarray\*}$$

This is due to Legendre, but I don't know precisely where.

---
Tags: algorithms, optimization, diophantine-equation
---


title: Equivalence relation between two CFG's

text:
# Question
Title: Equivalence relation between two CFG's
In our course: Automata and Computation there is a definition about Context-Free Grammars which states:

"Two CFG's $CFG\_{1}$ and $CFG\_{2}$ are equivalent if $L\_{CFG\_{1}} = L\_{CFG\_{2}}$ where $L\_{CFG\_{i}}$ is the language that is derived by $CFG\_{i}$".

Below the definition, it is stated that this defines an equivalence relation of the CFG's, but I don't see how I could prove this. I know that I should prove the 3 properties of an equivalence relation being:

-Reflexive -Symmetric -Transitive

But how can I do this for the particular problem?

# Answer
Let $\mathcal{G}$ be the set of all context-free grammars and let $\rho \subseteq \mathcal{G}^2$ denote the binary relation "being equivalent to".

Let $G$ be a CFG grammar. Clearly it holds that $G \rho G$ since $L\_G=L\_G$. Therefore $\rho$ is reflexive.

Let $G$ and $G'$ be CFG grammars such that $G \rho G'$. By definition of $\rho$ we have $L\_{G} = L\_{G'}$ and since set-equality is symmetric we also have $L\_{G'} = L\_{G}$. This shows that $G' \rho G$ and hence $\rho$ is symmetric.

Let $G$, $G'$ and $G''$ be CFG grammars such that $G \rho G'$ and $G' \rho G''$. By definition of $\rho$, we have $L\_G = L\_{G'}$ and $L\_{G'} = L\_{G''}$ and by transitivity of set-equality we have $L\_G = L\_{G''}$ showing that $G \rho G''$ and that $\rho$ is transitive.
> 1 votes

# Answer
$G\_1$ and $G\_2$ are equivalent if and only if $L\_{G\_1} = L\_{G\_2}$.

Since the relation $=$ is an equivalence relation over languages, so is the equivalence between grammars.
> 5 votes

---
Tags: automata, context-free, equality
---


title: Maximum flow on a n ×n grid

text:
# Question
Title: Maximum flow on a n ×n grid
I am currently dealing with a network flow problem and I am trying to find some similar solved problems to help me formulate my solution.

The text is:

You are the owner of a large chain of franchise shops, and you would like to expand to a new city. The blocks in your city make an $n ×n$ grid. However, although your products are awesome and in high demand, the city will not allow you to open a shop in each block. Instead, for every row of blocks i, you are are given a number $r\_i$ that limits the maximum number of shops opened there - and for every column j, there also is a maximum number $c\_j$ .

a) Find the maximum number of franchise shops you can legally open in the city. To do so, model the problem as a flow network. Then, describe how to get the right answer using Ford-Fulkerson, and prove the correctness of your construction.

How can I construct the digraph from the $n ×n$ grid ? I think the blocks can be represented in this way grid Should I assume an initial orientation on the grid?

> Image taken by https://www.chegg.com/homework-help/questions-and-answers/n-x-n-grid-graphs-defined-drawing-nx-n-grid-vertices-connecting-adjacent-vertices-drawn-g3-q30726135

# Answer
> 2 votes
Assume an $n\times n$ grid. I'd build a network as follows. A source on the left with $n$ arcs going to $n$ nodes each representing a row of the grid. Call these $n$ nodes $R\_1, R\_2...R\_n$. The flow capacity on the $i^{th}$ arc (from source to $R\_i$) is $r\_i$. Do something similar at the sink. Have arcs arriving there from nodes $C\_1,C\_2..C\_n$ with capacity $c\_i$. Then connect each $R\_i$ to $C\_j$ with an arc of capacity 1. Maximize the flow. The arcs $R\_i-C\_j$ chosen to have a flow in an optimal solution will tell you to place a franchise at grid point $i,j$.

---
Tags: graphs, square-grid
---


# Question
Title: References to deterministic time complexity of language classes
It's fairly well known that $REG \in TIME(n)$. I would like to know similar inclusions for the language classes $DCFL$ and $CFL$.

I have found a variety of claims for these classes on the internet. For instance,

I was taught that $CFL \in TIME(n^3)$ due to the fact that the CYK algorithm parses in time $O(n^3)$. Does anyone have references to the original time complexity results for these language classes?

# Answer
Did you read the slides in the Stanford course? A key point is that it is discussing time complexity *for a Turing Machine (TM)*. Turing Machines are only polynomially equivalent in time complexity to general computers. The precise relationship is found in the slide (in bold for convenience): What it says is:

> ### TIME($n^{18}$)
>
> * All CFLs are in TIME($n^{18}$)
>     + Given a grammar $G$, there exists **an algorithm on a standard computer** that can decide whether $G$ generates $w$ in **time TIME(${n^3}$)**.
>     + **Since an $f(n)$-time computer program can be simulated in time $O(f(n)^6)$ on a TM**, this means all CFLs are in TIME($n^{18}$)).

Of course, that's a loose bound, since it's based on a general model for converting a computer program into a TM. The graphic presents a tighter bound, but also for DTIME, which is: (again, emphasis added)

> the computational resource of computation time for a **deterministic Turing machine**.

In short, there is no contradiction here. You need to read the complexities in the context of the computational model being used. And remember that they are just upper bounds on the complexity.
> 1 votes

---
Tags: time-complexity, context-free, formal-grammars
---


title: Merging balls interview problem

text:
# Question
Title: Merging balls interview problem
Here is an interview problem about balls rolling towards buckets from Sprinklr Interview Experience at GeekforGeeks.

> You are given $n$ balls on the table and all the balls are rolling towards the one end of the table with velocities $V\_1, V\_2, \dots, V\_n$ and there is a bucket placed at that end. The distance of the ball with velocity $V\_i$ from the end of the table where the bucket is placed is $D\_i$. It is given that when two balls collide, both balls merge into each other and move with the velocity of the ball nearer to the bucket. So, at last, you have two tell the number of the balls which will fall into the bucket.

Here is what I am doing. First, I insert one extra ball in the array with zero velocity and distance zero. That is, I am inserting the bucket as a ball. We will find how many balls are getting merged with last ball.

Find a pair of adjacent balls which have the smallest value of $T = \frac{D\_i - D\_{i+1}}{V\_i - V\_{i+1}}$ and $V\_i \> V\_{i+1}$ and remove ball with velocity $V\_i$, that is, the first ball in the pair. Now for each remaining ball, reduce its distance by its velocity times $T$, and continue doing this process.

The number of time we will choose the bucket as the second ballwill be the final answer.

Can anyone suggest a better approach? My approach has time complexity of $O(n^2)$.

# Answer
Keep all the values $\frac{D\_i - D\_{i+1}}{V\_i - V\_{i+1}}$ in a min-heap. At each step, remove the minimum value, say $T = \frac{D\_i - D\_{i+1}}{V\_i - V\_{i+1}}$. We would first like to update all unaffected pairs, using $D'\_j = D\_j - TV\_j$. The affect this has on the ratios is $$ \frac{D'\_j - D'\_{j+1}}{V\_j - V\_{j+1}} = \frac{D\_j - TV\_j - D\_{j+1} + TV\_{j+1}}{V\_j - V\_{j+1}} = \frac{D\_j - D\_{j+1}}{V\_j - V\_{j+1}} - T. $$ In other words, their relative order does not change. However, the removed ball $i$ does affect one of the other ratios: instead of $\frac{D\_{i-1}-D\_i}{V\_{i-1}-V\_i}$ we now have $\frac{D\_{i-1}-D\_{i+1}}{V\_{i-1}-V\_{i+1}}$. So we remove the former and insert the latter instead.

Constructing the min-heap in the beginning takes time $O(n\log n)$. Afterwards, we perform $O(n)$ operations on the min-heap, each of which runs in $O(\log n)$, and so the total running time is $O(n\log n)$.
> 4 votes

# Answer
Calculate a time value for each ball ($D\_i/V\_i$). Assume bucket is on the right. Find the ball with largest time value, say ball $i$. Then all balls to the left of ball $i$ will merge into ball $i$ before they fall into the bucket. Remove those balls, and repeat the step until no more balls. I don't think it is linear time.
> 1 votes

# Answer
Not sure if I understand this right. My understanding is this: If the ball furthest away would move at incredibly high speed so it can catch up with all the other balls, then it will collide with all of them and only one ball would fall into the bucket.

If this is right, then the problem is easy: Calculate the time when each ball would drop into the net if there were no other balls. Find the ball that would drop earliest and remove all balls that started out ahead of it, that is one drop. Then as long as there are other balls, find again the ball that would drop earliest and remove all balls that started ahead of it.

I think this can be done in linear time if the balls are sorted by distance: For each ball, calculate the drop time. Go through the balls one by one. For each ball, as long as it arrives earlier at the net than the ball starting before it, remove the ball before it, and you will be left with k balls that arrive in ascending order.
> 0 votes

---
Tags: algorithms, dynamic-programming, greedy-algorithms, priority-queues
---


# Question
Title: What are you allowed to move into the big O notation for it to be still correct?
Can someone tell me what the rules are for moving log or exponents into the $O(n)$ notation so it is still correct?

For example: Is this $\log(O(n))= O(\log(n))$ correct? Or is this correct $O(n)^2=O(n^2)$? Or am I not allowed to do this?

# Answer
> 15 votes
To prove or disprove this kind of equality with $\mathcal{O}$, you need to go back to the definition of $\mathcal{O}$ with inequalities.

For example, let's study the question $\log(\mathcal{O}(n)) = \mathcal{O}(\log n)$:

$f\in \log(\mathcal{O}(n))$ means that there exists a function $g\in\mathcal{O}(n)$ so that $f = \log g$. That means there exists a constant $A\>0$ such that:

$$f(n) = \log g(n) \leqslant \log (An) = \log A + \log n\leqslant 2\log n$$

The first inequality holds true because $\log$ is an increasing function. The second inequality holds true for $n$ big enough. We proved that $f \in \mathcal{O}(\log n)$.

Reciprocally, $f\in \mathcal{O}(\log n)$ means that there exists $B\>0$ such that $f(n) \leqslant B\log n$. That means: $$2^{f(n)}\leqslant 2^{B\log n} = n^B$$ Therefore, we cannot conclude that $2^f\in \mathcal{O}(n)$, or equivalently that $f\in \log(\mathcal{O}(n))$.

For example, consider $f(n) = 2\log n$. Then clearly, $f\in \mathcal{O}(\log n)$, but $2^{f(n)} = n^2 \notin \mathcal{O}(n)$.

In the general case, we have:

* $\log(\mathcal{O}(n))\subsetneq \mathcal{O}(\log n)$;
* $(\mathcal{O}(n))^k = \mathcal{O}(n^k)$;
* $\mathcal{O}(2^n) \subsetneq 2^{\mathcal{O}(n)}$.

# Answer
> 8 votes
In order for $f(O(n)) \in O(f(n))$ to hold you essentially want $f$ to satisfy $f(cn) \le df(n)$ where $n$ is sufficiently large. Here the inequality must hold for all sufficiently large constants $c$, while $d$ is a constant that can be chosen as a function of $c$ (but not as a function of $n$).

For example $\log cn \le \log c + \log n \le (1+ \log c) \log n$ for $n \ge 2$ and $c \ge 1$, so you can pick $d=(1+ \log c)$.

Also: $(cn)^2 = c^2 n^2$ for any $c \ge 0$ so you can pick $d=c^2$.

Notice that you can't just move any function into the Big-Oh notation. For example $2^{O(n)} \not\in O(2^n)$. Indeed, when $c \> 1$, you can always satisfy $2^{cn} \> d 2^n$ for any $d$ chosen independently of $n$, by simply considering values of $n$ that are large enough.

# Answer
> 2 votes
Although $\mathcal O(f(n))$ will often be given as a function, e.g. $\mathcal n^2+n=\mathcal O(n^2)$, strictly speaking $\mathcal O(f(n))$ is a set of functions, so the precise statement is $n^2+n \in \mathcal O(n^2)$. The expressions $\mathcal \log(O(f(n))$ and $\mathcal O(f(n))^2$ don't really make sense. You can't do math on $\mathcal O(f(n))$, other than set operations.

---
Tags: big-o-notation
---


# Question
Title: Any PRC class is closed under a construction involving a function f such that f(x+1) < x+1
So I'm trying to solve this problem(problem 8 from section 3.4) of the book *Computability, Complexity and languages* by Martin Davis:

> Let k be some fixed number, let `f` be a function such that `f(x + 1) < x + 1` for all x, and let
>
> ```
> h(O) = k
> h(t + 1) = g(h(f(t + 1)))
>
> ```
>
> Show that if `f` and `g` belong to some PRC class **C**, then so does `h`.

I can't seem to find the way although there is a hint given in the book. Any tips or solves would be much appreciated!

# Answer
> 1 votes
This is an interesting exercise.

---

All variables are non-negative integers.

Since $f(x+1)\lt x+1$ for all $x$, for any fixed $x$, the sequence $x, f(x), f(f(x)), \cdots$ will reach $0$ at some term. Let the index of first $0$ in that sequence be $f'(x)$, i.e., $$f'(x)=\min\_{t\le x}\left({(f^t)(x)=0}\right).$$ In particular, $f'(0)=0$ since $f^0(x)=x$.

Here is the simple critical observation, $$h(t)=\underbrace{g(\cdots g(k)\cdots)}\_{f'(t)\text{ copies of } g},$$ i.e., $h(t)$ is the result of applying $g$ repeatedly $f'(t)$ times, starting at $k$.

The problem we have now is to prove the following two general facts.

* Assuming $f(x+1)\<x+1$, if $f$ is in primitive recursive class $\mathcal C$, so is $f'$.
* For any functions $f\_1$ and $f\_2$ in $\mathcal C$, the function that maps $t$ to the result of apply $f\_1$ repeated $f\_2(t)$ times, starting at a fixed $k$ is also a function in $\mathcal C$.

---
Tags: computability, primitive-recursion
---


title: Histogram representation of a database

text:
# Question
Title: Histogram representation of a database
I'm reading though *The Algorithmic Foundations of Differential Privacy* and the authors define a database in a mathematically convenient way. Unfortunately I'm a little confused about what the definition actually means in practice.

From page 17 of the pdf:

> We will think of databases $x$ as being collections of records from a universe $\mathcal{X}$. It will often be convenient to represent databases by their histograms: $x \in \mathbb{N}^{\lvert\mathcal{X}\rvert}$, in which each entry $x\_i$ represents the number of elements in the database $x$ of *type* $i \in \mathcal{X}$ (we abuse notation slightly, letting the symbol $\mathbb{N}$ denote the set of all non-negative integers, including zero).

Suppose we have a sample database that looks like this:

| Row | Name | Age |
| --- | --- | --- |
| 1 | Tom | 19 |
| 2 | Ray | 22 |
| 3 | Sue | 42 |
| 4 | Bob | 42 |

I'm pretty sure each $x$ is just some combination of all rows of the database (say rows 1,3, and 4 or only row 1). I'm not at all clear what "*type* $i$" means. Is each *type* a row so that a database of rows 1, 3, and 4 would be $x = \\{1, 0, 1, 1\\}$? Or is *type* a level in the database; e.g. *type* $1$ is "Age 19", *type* $2$ is "Age 22", *type* $3$ is "Age 42", *type* 4 is "Tom", *type* 5 is "Ray", *type* 6 is "Sue", *type* 7 is "Bob". Thus the histogram representation is $x = \\{1, 0, 2, 1, 0, 1, 1\\}$?

To summarize my questions: What would the histogram representation $x$ be for a database with rows 1, 3, and 4? What are the possible values of $i$ in this $\mathcal{X}$?

# Answer
> 2 votes
No, you went wrong right from the start. $x$ is the database. In this case, if the database is shown in that table, $x$ is the set of all rows shown in the table above. If $x$ is a database with just rows 1, 3, and 4, then $x$ would be those set of three rows.

Now they recommend representing a set as a histogram. To do that, we need to have a "universe" $\mathcal{X}$ of all possible rows that could ever occur (including both rows that do occur in the database as well as rows that don't occur in the database but could have). Then, $x$ is a vector that records a count of how many times each of those possible rows actually occurs in the database. If the possible row doesn't occur in the database, its count is 0; if it occurs once, its count is 1; and so on. You then put those counts into a vector.

The possible values of $i$ are all possible rows in the universe $\mathcal{X}$.

---
Tags: database-theory, differential-privacy
---


# Question
Title: A turing machine L takes a machine <M> which has to halt at for least n Inputs
I've been wondering about this problem for a while:

Say we have L = { \<**M**\>, *n* | **M** has to halt for at least *n* Inputs} and multitapes are simulating various inputs bla bla

How do I count how many Simulations came to a halt?

My guess was to have another tape that has e.g. n zeros as Input and whenever a Simulation comes to a halt the counting tape pointer is incremented by 1 until it reaches blanks.

Is that even possible?? I hope I got the point across... I didnt really know how to put my thoughts into words so if you have trouble understanding just hmu :)

have a good day (^^)/

# Answer
Yes, you can simulate several TMs on separate tapes and mark a separate tape with a 1 whenever one of your simulations halts. For TMs that are well behaved (like deciders), this approach will work and your approach will answer Yes correctly.

The immediate problem is that some TMs don't behave nicely—they will run forever without halting. No matter how many separate tapes you have, or how cleverly you divide up the simulation work, you will eventually encounter a TM that loops forever and uses up all of your tape resources. This means that your machine will not be able to say "No" because it is stuck waiting to find out.

The deeper problem is that the question "Does machine $M$ halt on at least $n$ different inputs?" is undecidable. If you had a subroutine that could decide it, you could solve the halting problem. (Proof below.) It's not just that your counting approach is flawed—no algorithm exists that decides this problem.

---

***Proof that the problem is undecidable***: Suppose you had a machine $f(M,n)$ which decides whether $M$ halts on at least $n$ different inputs. Here's an algorithm for solving the halting problem:

Given a machine $M$ and a word $w$, design a new machine $M^\prime$. The machine $M^\prime$ is a modified version of $M$. If you give $M^\prime$ the input $w$, it simulates $M(w)$ as usual and halts if $M$ halts. On any other input, $M^\prime$ loops forever.

You can now solve the halting problem by computing $f(M^\prime, 1)$, which will return YES if $M$ halts on input $w$, or NO if $M$ doesn't halt on input $w$. This is a contradiction, so the algorithm $f$ can't exist.
> 1 votes

---
Tags: formal-languages, turing-machines, simulation
---


# Question
Title: Can a non-recognisable language have a recognisable subset?
If $L\notin$ **RE**, can there be a language $L'\subseteq L$ such that $L'\in$ **RE**? Or is it necessarily true that $L'\notin$ **RE** for all $L'\subseteq L$.

# Answer
> 2 votes
Take any language $L\notin RE$. Now, $\emptyset \subseteq L$, and clearly $\emptyset\in RE$.

---

FYI, the converse is also not necessarily true: $L\subseteq \Sigma^\*$, and $\Sigma^\*\in RE$.

# Answer
> 0 votes
Yes; as others have said, the empty language $\varnothing$ is recognizable, and it's a subset of every language.

For a less trivial example, let $L$ be an unrecognizable language. Pick any finite subset of strings $D$ from $L$. That subset $D$ is a recognizable language—in fact, it's a regular language! The algorithm that recognizes it is a lookup table that checks whether the input matches any one of the hard-coded strings from $D$.

---
Tags: formal-languages, turing-machines, semi-decidability
---


# Question
Title: Prove that "If $L$ is a context-free language, is $\overline{L}$ also context-free?" is undecidable
Lately I need to find the decidability of the following decision problem:

> If $L$ is a context-free language, is $\overline{L}$ also context-free?

I know that context-free language is not closed under complementation. Had it been otherwise, this decision problem would have been trivially decidable, since a Turing machine that always answer "YES" can decide the problem.

Few of my peers say that the problem is undecidable since CFLs are not closed under complementation. This logic/reasoning seems utter nonsense to me.

Yet few other peers try arguing about the decidability of the problem using Rice Theorem as follows:

> Let $L$ be set of all CFLs. For this language whether any member's complement is CFL or not is a nontrivial property, since CFL are not closed under complementation. So According to Rice theorem it is undecidable.

Is the argument above correct in the first place? The Rice Theorem states that :

> Any nontrivial property of Recursively Enumerable Languages is undecidable.

And my peers probably justifies this argument about Rice Theorem saying that all CFLs are also RE languages. But as I understand, the "property" in Rice Theorem is a predicate where the universe of discourse is the set of RE languages. If they reduce/chop this universe of discourse to contain only CFLs, would things remain the same? I do not think so, \[I might be wrong however.\] in the sense that we are dealing with just a small fraction of the entire set. For instance, the set $\mathbb{N}$ is closed under addition, but the set $\\{1,2,...,10\\}$ is not.

To apply Rice Theorem, I would define the language of the property as:

$$L\_p=\\{\langle M \rangle \mid L(M)\text{ is a context-free language and }\overline{L(M)}\text{ is a context-free language}\\}$$

The language $L\_p$ is undecidable, because the property that "a RE language is context-free and its complement is context-free", is non-trivial. But this non-triviality arises primarily due to the check of a RE language being context-free. Is the actual decision problem correctly addressed by the $L\_p$ above?

Moreover for decidability question I usually try to design a TM machine, but I have no clue to this decision problem. Given a CFL (using a finite description of course), how do I design the TM to find the complement of this finite description? Once this complementation is done, we should check whether the language produced is a CFL. But how? I cannot proceed further.

Or is this decision problem much more notorious than it seems? How can we approach the problem beyond what I have written?

---

PS: The beautiful answer to a similar question answers the decidability question, but it remains mysterious to me whether the approach of my peers using Rice-Theorem is at all correct, and what could have been a raw TM machine approach? This is how my question slightly differs from this question.

# Answer
> 2 votes
## Rice's theorem can't help.

You are right that Rice's theorem isn't applicable, and you're right about the reason.

You've been given a decision problem about **(context-free) languages**. Meaning, you're trying to design a Turing machine that takes in a *context-free language as input* (for example, your machine might accept only valid context-free grammars as input). And it is supposed to output YES or NO based on whether the complement of that language is also context-free.

Rice's theorem applies exclusively to decision problems about **turing machines**. Meaning, a situation where you're trying to design a Turing machine that takes in a *Turing machine as input* and answers YES or NO based on whether the input machine's language has a particular property.

It is true that, according to Rice's theorem, the property: "M is a turing machine whose language is context free and where the complementary language is also context-free" is undecidable. But this fact is, unfortunately, useless because it tells you that a property of *machines* is undecidable. You want to know whether a property of *context-free languages* is undecidable. Rice's theorem can't help you.

## How do you design a decider?

If the language "\<G\> : G is a context-free language whose complement is also context free" is decidable, then there's some algorithm for deciding it, even if it takes some thought. But, if the language is *undecidable*, then there's no algorithm for deciding it. So you have two approaches:

1. If you think the problem is decidable, you can try to develop an algorithm—design a TM, for example. Or:
2. If you think the problem is undecidable, try to think of the different proof strategies you have for showing that a problem is undecidable.

You can switch back and forth between these approaches, of course. If the language is undecidable, then you won't be able to come up with an algorithm (!). If the language is decidable, then you won't be able to come up with an undecidability proof (!).

## Proof of undecidability

The usual tool for proving undecidability is a reduction from another hard problem. You show that if you did have an algorithm for deciding *your* problem, you could use it as a subroutine to solve another problem you already know is undecidable. This is a proof by contradiction.

The proof you reference is a good example.

---
Tags: turing-machines, context-free, undecidability, rice-theorem
---


# Question
Title: If both could be implemented with the other, what are the differences between priority queues and binary heaps?
I've red that a binary heap can be implemented using a priority queue. I've also red the opposite, that a priority queue can be implemented using a binary heap.

This seems strange to me as conceptually they are different: a priority queue is a linear data structure with a priority assigned to each element, whereas a binary heap is a binary tree whose nodes are arranged in a certain way.

Is one more fundamental than the other in the sense that it would be better to build one from the other and not the other way around? When thinking about it or coding, what are the benefits and drawbacks of one over the other?

Is it better (in terms of space used or runtime of operations) to not implement one using the other, and that it's often done because most programing languages have one built in but not the other?

# Answer
Based on standard usage of the terms, a heap is a specific data structure, with a specific representation in memory. A priority queue is an abstract data type: it identifies some operations that must be supported by the data structure, but does not itself describe any particular data structure. You can use a heap to implement the priority queue operations. There are also other ways to implement a priority queue.

You link to a Stack Overflow post that talks about implementing a min heap using `priority_queue`, but I recommend that you disregard it, as it is only likely to cause confusion. They appear to be using the term "min heap" in an imprecise sense that fails to make a careful distinction between a data structure and an abstract data type. I can see why you were confused after reading it.
> 6 votes

# Answer
A priority queue implemented with a binary heap has worst case behaviour if you add random elements and repeatedly remove the largest element: Say you start with 1,000 random items, then one million times you add a random element and remove the largest one. You will end up with lots of small elements, making adding a random element the worst case.

You get around this by implementing it with *two* binary heaps: When you find out that adding items is expensive, you create binary heap #2 and add all items that are larger than the largest item of binary heap #1 to heap #2. In an extreme case you could end up with a linked list of binary heaps, with significantly better runtime than a single binary heap.
> 0 votes

---
Tags: data-structures, binary-trees, heaps, priority-queues
---


# Question
Title: Algorithm to find shortest distance from source to all other vertices of graph in O(m)?
My question is for (c), as I struggle to find an algorithm that can do this in O(m) time.

# Answer
> 0 votes
Start at the bottom (at $s$). Traverse the bottom row back and forth in one loop, updating your Dijkstra label on each node. Then process each of the arcs that lead up to the next level, one at a time updating the labels of each node in that 2nd level. Then move up to the 2nd level and traverse that row back and forth as before, updating the label at each node. Continue. You traverse each arc at most once I think, so $O(m)$. This relies on the positive length of each arc obviously.

More formally, let $d(i)$=distance from $s$ to node $i$, for each node $i$. Let $c\_{ij}$ be the cost of using arc $i$--\>$j$. Start with $d(s)=0$ and $d(i)=+\infty$ for all other nodes. Starting in the bottom row, traverse each arc to the right starting at $s$. When you reach node $j$ from node $k$, do your update step: $d(j) = \min(d(j),d(k)+c\_{kj})$. When you reach the right end, turn back and go back to $s$ (though you won't update anything on your way back in the bottom row this way). Now with the bottom row all updated, "process" the up arcs from the bottom row. So do the update step for each of the up arcs one by one (in any order). Then again traverse this row starting on the left, following each arc right until the end then back (applying the update step for each arc). Here you might update a label on your way back because there might be a really cheap arc that moves you from the bottom row to the 2nd row. Anyway, continue this until you traverse the top row.

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


# Question
Title: Is the language containing Turing machine $(M_1, M_2)$ such that $L(M_1) \cup L(M_2) = \Sigma^*$ decidable?
We are given two Turing machines $M\_1$ and $M\_2$ and we wish to decide whether the union of the language $L(M\_1)$ accepted by $M\_1$ with the language $L(M\_2)$ accepted by $M\_2$ coincides with $\Sigma^\*$.

Is this problem undecidable? In other words, is the language $\\{ (M\_1, M\_2) \mid L(M\_1) \cup L(M\_2) = \Sigma^\*\\} $ undecidable?

I'm thinking about doing a proof by contradiction and somehow reducing to $E\_{TM}$, but not sure where to start.

# Answer
Yes, the language $L = \\{ (M\_1, M\_2) \mid L(M\_1) \cup L(M\_2) = \Sigma^\* \\}$, where $M\_1$ and $M\_2$ are Turing machines, is undecidable.

If $L$ were decidable then you would be able to decide if the language accepted by a Turing machine $T$ is $\Sigma^\*$ by simply checking whether $(T,T) \in L$.

To see that the problem of deciding whether a given Turing machine $T$ satisfies $L(T) = \Sigma^\*$ is undecidable you can reduce from the well-known undecidable problem of deciding whether a given Turing machine $M$ halts on empty input. To do so, it suffices to construct $T$ from $M$ by replacing each transition that halts the machine and rejects with a transition that halts the machine and accepts. Then $M$ halts if and only if $L(T)=\Sigma^\*$.
> 4 votes

---
Tags: turing-machines
---


title: Reduce subset sum to simple path

text:
# Question
Title: Reduce subset sum to simple path
I have a similar question as this post:Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost

My question: Given a weighted and directed graph $G$, it might contain negative cycles, is there a simple path(no repeated vertices) from $s$ to $t$ with total weight at most $T$?

We want to prove this question is NP-Complete, as I mentioned this is very similar to the post one, the only differences are my question mentioned negative cycles and the total weight is at most $T$ instead of exactly $T$. As the post suggested, we can reduce subset sum to our problem, but does it equivalent to asking the subset sum question sum to at most $T$ instead of sum to exactly T? Additionally, the reduction seems ignoring the property of negative cycles, but it still works somehow. Anyways, I'm really new to this field, like doing reduction and proving problems are NP-Complete. Any suggestion would be really helpful.

# Answer
Consider all weights are -1. Now asking if there is a simple path with weight at most $-(n-1)$ is equivalent to asking if there is a Hamiltonian path. So your problem is NP-hard.
> 1 votes

---
Tags: algorithms, np-complete
---


# Question
Title: Undecidability of language involving two TMs
I am currently browsing the lecture notes on computability/decidability and I have encountered the following exercise I am unable to solve.

> Given $M\_1$, $M\_2$ Turing machines, is it true that for every $x \in \Sigma^\*$ $M\_1$ performs at least as many steps while working on input $x$ as $M\_2$ does with input $x$?

There is also an answer to the excercise and a hint, though it didn't help me that much:

* Let $M\_1$ be a TM which enters an infinite cycle for any input → halting problem (and thus undecidable).
* Complement of the language is partially decidable, because non-deterministic TM can provide a counter-example.

In particular, I would like to know how can I express these statements formally:

* How to formally describe the language describing the problem?
* How to reduce the language to halting problem?
* How to show that the complement is partially decidable?

The only thing I can decide with a confidence is that the language itself is not even partially decidable, since complement is partially decidable, but the language itself is not decidable, and thus the language is not even partially decidable (Post theorem).

# Answer
> 1 votes
1. The language is the set of all strings $M\_1\\#M\_2$ where $M\_1$ and $M\_2$ are descriptions of Turing machines, and those machines have the property that $M\_1(x)$ runs for more steps than $M\_2(x)$ on every input $x$.
2. Given a string $M\_1\\#M\_2$, it is undecidable whether the string is in the language; that is, whether $M\_1$ and $M\_2$ are machines such that $M\_1(x)$ runs for more steps than $M\_2(x)$ for all inputs $x$.

To show that it's undecidable, assume you have a decider $f(M\_1, M\_2)$ which accurately reports YES if $M\_1$ runs for more steps than $M\_2$ on every input, or NO otherwise. Then you can use this decider as a subroutine to solve the halting problem (which is impossible, so $f$ can't exist).

3. Here's the algorithm for solving the halting problem: Given a machine $M$ and a word $w$, you want to know whether $M$ halts on input $w$. Let $L$ be a special machine that loops forever on every input. Let $M\_w$ be a machine that just simulates $M$ on $w$ no matter what its actual input is. Compute $f(L, M\_w)$. If $M$ halts on input $w$, then this function will return YES. If $M$ loops forever on input $w$, then this function will return NO—because both $L$ and $M\_w$ just loop forever no matter what input they're given. So this subroutine $f$ solves the halting problem—which we know is impossible.
4. A language $\mathscr{L}$ is partially decidable if there's a machine $M(x)$ that always halts and answers YES when $x\in \mathscr{L}$, but which is allowed to halt and answer NO or even just loop forever when $x\notin \mathscr{L}$.

The complement of the language described in (1) is the language $M\_1\\# M\_2$ where $M\_1$ and $M\_2$ describe Turing machines, where $M\_1(x)$ runs for **fewer** steps than $M\_2(x)$ on **some** input $x$.

I figured this out by interpreting the language in (1) formally: $$\\{M\_1\\#M\_2: \forall x\in \Sigma^\*, \mathsf{steps}(M\_1(x)) \geq \mathsf{steps}(M\_2(x))\\}$$

so its complement (by deMorgan's law) is $$\\{M\_1\\#M\_2: \exists x\in \Sigma^\*, \mathsf{steps}(M\_1(x)) \< \mathsf{steps}(M\_2(x))\\}.$$

This language is semi-decidable. It is semi-decidable because whenever the answer is YES (whenever $M\_1$ and $M\_2$ are machines such that $M\_1(x)$ runs in fewer steps than $M\_2(x)$ on at least one string), you can use a Turing machine to prove it.

The algorithm is: Given two machines $M\_1$ and $M\_2$, nondeterministically pick a random string $x\in\Sigma^\*$. Simulate the computation of $M\_1(x)$ and $M\_2(x)$. If $M\_1(x)$ halts before $M\_2(x)$, return YES. If the machines really belong to the language, then one of the nondeterministic guesses will halt and say YES. (If the machines *don't* belong to the language, then the simulations might loop forever, which is allowable for semi-decidable.)

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


# Question
Title: Finishing Time in DFS, is that necessary?
According to DFS algorithm for graph traversing:

```
DFS(G)
  for each v ∈ V (G)
      v.mark = false
  time = 0
  for each v ∈ G.V
      if not v.mark
         DFS-Visit(v)

```

```
DFS-Visit(v)
   v.mark = true
   time = time + 1
   v.d = time
   for each (v, w) ∈ E(G)
      if w.mark == false
              w.parent = v
              DFS-Visit(w)
   time = time + 1
   v.f = time

```

Where v.d and v.f are start and final meet time of vertex "v".
**Question:**
Why should we use v.d and v.f? I cannot see the impact of the time in the pseudo code.Its just been incrementing and intializing to something but haven't been used by any **if** or **for** condition.

# Answer
> 1 votes
Those markings give a pre-ordering and a post-ordering respectively. They are indeed not used by the DFS algorithm per se.

There are several applications, one of them being that the reverse post-order is a topological sort. It can help finding strongly connected components efficiently.

See here for some details.

---
Tags: algorithms, algorithm-analysis
---


title: Stuck on a possible greedy problem

text:
# Question
Title: Stuck on a possible greedy problem
I am currently dealing with a problem that I believe to be a Greedy releated problem and I'm trying to find some similar problems in order to solve it. I would like to have some hints or resources to study because I'm stuck on it. The text is:

You are tasked with creating a competitive programming squad, selecting students from schools around France. There are $n$ schools in total and every school $i$ has $g\_i ≥ 0$ girls and $b\_i ≥ 0$ boys. You need to select exactly $k$ students from each school, but be careful: the total number of girls and boys need to be as close as possible. In particular, you need to select $b^\*\_i$ boys and $g^\*\_i$ girls from each school $i$, respecting that 0 ≤ $g^\*\_i$$g\_i$ , 0 ≤ $b^\*\_i$$b\_i$ and $g^\*\_i$ \+ $b^\*\_i$ = $k$, in order to minimize:

$ | \sum\_{i=1}^{n} g^\*\_i - \sum\_{i=1}^{n} b^\*\_i|$

You are guaranteed that for every school $i$, we have $b\_i$ \+ $g\_i$$k$

Provide an algorithm that computes the $g^\*\_i$ and $b^\*\_i$ in polynomial time. Prove its correctness and analyze its run time.

Thank you for your time.

# Answer
> 0 votes
I think there is a dynamic programming solution in linear time.

For $i$ a school, denote $r\_i$ to be the range that the value $g^\*\_i - b^\*\_i$ can take. For example, if $k = 4$, $g\_i = 7$ and $b\_i = 2$, then the choices can be $(g^\*\_i, b^\*\_i) \in \\{(4, 0), (3, 1), (2, 2)\\}$. Therefore, $r\_i = \[0, 4\]$. (For convenience, you could consider the range of $\left\lfloor \frac{g^\*\_i-b^\*\_i}{2}\right\rfloor$ to get consecutives values.)

Then, define $R\_i$ to be the range that the value $\sum\limits\_{j=1}^i(g^\*\_j-b^\*\_j)$ can take. Knowing $R\_{i-1}$ and $r\_i$, the range $R\_i$ can easily be computed.

Given $(g\_i)$ and $(b\_i)$ for $i\in\\{1, …, n\\}$, we want to know the value $x\in R\_n$ that minimize $|x|$ (either $0$ or $1$ if it is in $R\_n$, depending on the parity of $nk$, or one of the two bounds of $R\_n$ otherwise). You can compute the exacts values of $g^\*\_i$ and $b^\*\_i$ starting from $i = n$ and going backward.

---
Tags: algorithms
---