# Question
Title: Why does DFS only yield tree and back edges on undirected, connected graphs?
Prove that if G is an undirected connected graph, then each of its edges is either in the depth-first search tree or is a back edge.

Now, from intuition and in class lectures by Steven Skiena, I know that the above holds true, since it dives all the way down, and then throw a rope back to a previous vertex. I also know that DFS is great in finding cycles.

However, my problem here is that I don't know how to *prove* that the edge is either a tree edge or a back edge.

# Answer
> 14 votes
A depth first search on a directed graph can yield 4 types of edges; tree, forward, back and cross edges. As we are looking at *undirected* graphs, it should be obvious that forward and back edges are the same thing, so the only things left to deal with are cross edges.

A cross edge in a graph is an edge that goes from a vertex $v$ to another vertex $u$ such that $u$ is neither an ancestor nor descendant of $v$. So what you need to argue is that in an *undirected* graph, there's no way you can get a cross edge. It might help to think of why the can occur in directed graphs, and why you can't have this case in undirected graphs.

# Answer
> 8 votes
Let $G=(V,E)$ to be a graph and $u$ and $\nu$ to be its vertices such that $\\{u,v\\}\subseteq V$ and $(u,\nu)\in E$.

Suppose that $u$ is discovered first. Consequently, its color is changed to gray. Then, $\nu$ becomes its descendant (by white path theorem) and the following discovery time relationship holds: $u.d\<\nu.d$.

Now, there are two options of discovering $(u,\nu)$ edge:

$\quad$ 1) if $u$ discovers $\nu$, then $(u,\nu)$ is a tree edge;

$\quad$ 2) if $\nu$ discovers $u$, then $(u,\nu)$ is a back edge since $u$ is still gray at the time the edge is first explored.

# Answer
> 2 votes
The most voting answer says well and I want to claim it more clearly.

Proof:

We know that DFS produces tree edge, forward edge, back edge and cross edge. Let's prove why forward edge and cross edge can't exist for DFS on undirected Graph.

* **For forward edge ***(u, v)*:****

Forward edge is said that v is a descendent of u, or we say v is visited and explored completely when u is being exploring, which is

**(pre\[u\] \< pre\[v\] \< post\[v\] \< pre\[u\])**

this answer is considered as a back edge because (v, u) is an edge as well. But I don't know why to see forward edge as a back one not the inverse insight. Maybe this thought is used for some specific usage?
* **For cross edge *(u, v):***

this is the difficulty of the proof.

We prove that DFS on undirected graph can not yield a cross edge **by contradiction.**

If (u, v) is a cross edge, then v is already explored completely when u is being explored.

**(pre\[v\] \< post\[v\] \< pre\[u\] \< post\[u\])**

This can exist on DAG because when exploring v we don't know u at all! u points to v directedly. However, in undirected graph, when we explore v, u (as a neighbor of v) is being explored and finished. If the cross edge exists, then u can not be a neighbor of v, this contradicts with the undirected graph assumption. In this case, cross edge can not exist.

In fact, this proof gives us another property.

**For an edge (u, v) in an undirected graph, if post(v) \< post(u), then u must be an ancestor of v.**

# Answer
> 0 votes
There's another approach here. Suppose that you have an edge $(u, v) \in E$ and $u, v \in V$. Now, assume that there's a forward edge in the direction from vertex $u$ to $v$. This edge is first explored in the direction of $(v, u)$ while $u$ is gray by scanning the adjacency list of $v$, since $v$ is a descendent of $u$. In the direction from $v$ to $u$, this edge is a back edge.

Then, in a connected undirected graph, there's at least one simple path between any pair of vertices. Therefore, each vertex is either an ancestor or a descendent of the other. Thus, no cross edges are possible.

# Answer
> -2 votes
In the undirected graph we get only tree and back edges . the reason for no forward edges is because in undirected the forward edges get converted into back edges , it is so because in undirected there is no restriction in which direction to visit the vertex, so in case we have any vertex we can visit it from the child itself to the parent which counts as a back edge.

now lets talk of cross edge here also since edges are undirected so, the cross edges get converted to the tree edges as they can be visited as and when we go to any of that edge vertex for more details you can view this MIT vedio https://youtu.be/AfSk24UTFS8?t=36

---
Tags: algorithms, graphs, algorithm-analysis, graph-traversal
---


# Question
Title: A Question in Arora & Barak's Book: $577 \times 423$
I have been reading \[1\] recently. On page xxi, the authors wrote: "For example, multiplying 577 by 423 using repeated addition requires 422 additions, whereas doing it with the grade-school algorithm takes 3 multiplications of a number by a single digit and 3 additions."

The above statement is wrong. There are only 2 additions because 1731+11540+230800=244071 (see page xx) only requires 2 additions. Am I right?

**Reference**

\[1\] S. Arora and B. Barak, *Computational Complexity: A Modern Approach*, Cambridge University Press, 2009.

# Answer
> 2 votes
$$ 2961 + 29610 + 211500 = 244071. $$

There are only 2 additions still. You are right again!

---
Tags: complexity-theory
---


# Question
Title: what is the relation between operating systems and automata theory?
I want to do some research on how machine theory (automata theory) is applied in the operating system. Also thank you for introducing useful links and books.

# Answer
I don't know about direct application of automata theory to operating systems in general or even OS kernel as a whole, but pretty much every kernel subsystem that manages some resource implements a (finite) automaton.

For instance a process (or a thread) has a number of states like "running", "ready" and "blocked", and a process scheduler moves each process between these states. As an example of a transition, a timer interrupt moves a process from "running" to "ready" in a preemptive multitasking system.

Similarly I/O descriptors have states like "open", "closed", "can read", "can write". And TCP/IP sockets famously have somewhat complicated state diagram :)

I couldn't immediately find illuminating references on these topics, but I suspect classic OS books spend some time explaining the connection. On the other hand due to obvious reasons major OS kernels (like Linux or FreeBSD) much more concerned with efficient implementation than clear connection to automata theory. But I would take a look at seL4 — they have *formal proofs* of certain properties, and I bet some of the proofs rely on automata properties. :)
> 2 votes

---
Tags: operating-systems
---


title: Formal definition of algorithm runtime

text:
# Question
Title: Formal definition of algorithm runtime
In the analysis of algorithms textbooks that I've seen, as far as I could tell, the runtime of an algorithm is defined intuitively. Is there a simple formal definition of this concept? I.e. a definition which fully formally, for some particular simple and general programming language defines the runtime of a program in that language?

# Answer
> 1 votes
The runtime of an algorithm is naturally nothing but the sum of the runtimes of the individual operations that are performed. This assumes that execution takes place on a machine for which the individual times are known (and usually constant).

One example of such a machine is the MIX computer defined by Knuth.

---

In a very simple setting, every operation counts for one unit. But there is no universal definition, running time units are ad hoc. The same goes about space complexity: there is no universal definition of the unit of storage.

---

In the complexity analysis, it is rather exceptional that a detailed account of all instruction be made. On the opposite, one usually focuses on a single type of operation (such as comparisons, floating-point additions, data moves...) and just count their number, assuming that the amount of other operation is at most proportional. By a language abuse, these counts can be considered as running time.

---

Needless to say, the modern computers are far from being modelled by constant time operations, due to their complex pipelined operation, as well as sophisticated memory hierarchies. Predicting the running time on a real machine is simply impossible, and even non-deterministic.

# Answer
> 0 votes
You may want to reference here if you are still learning about runtime of an algorithm. 'Intuitively' sounds as if you are making a claim calculating the runtime of an algorithm occurs is a loose sense, where in actually the calculations can be very accurate. Consider calculating parallel vs serial. Serial code runs in O(1) for each line, where the number of parallel instances multiplies this by the number of instances.

Adding in functions with loops or recursive calls could move the runtime for certain lines of code up. This is just an example, though many program's runtime can be calculated very precisely.

---
Tags: algorithm-analysis, definitions
---


# Question
Title: can a computer be totally made up of SRAM?
can a computer be totally made up of SRAM with no DRAM but with secondary memory and run an opreating system properly?

# Answer
Certain early personal computers in fact used SRAM as their main source of memory. The ZX80 for example.
> 1 votes

# Answer
Have a look at the Cray X-MP super computer. It uses SRAM instead of DRAM.
> 0 votes

---
Tags: memory-hardware
---


# Question
Title: Is there an efficient algorithm to find GCD of all cycles' lengths in directed multigraph?
I have weighted connected directed graph with cycles which can have multiple edges and loops (edge from vertex back to itself). Weight of each edge is its length (always positive integer). There always is a path from vertex $v\_0$ to every other vertex (including itself).

I need to find greatest common divisor (GCD) of all cycles' (from $v\_0$ to itself) lengths. It always exists and is a divisor of shortest cycle (from $v\_0$ to itself) length. Note that concatenating any number of such cycles also gives valid cycle.

I know one way to find GCD. We can find generating function of number of cycles of certain length (using Gaussian elimination for example). Such generating function is always a rational function (ratio of polynomials). Then GCD of $x$ powers from denominator is actually GCD of all cycle lengths. However this is really computationally inefficient. Finding generating function always requires near cubic rational function arithmetic operations (cubic for Gaussian elimination but can be less if use sophisticated matrix multiplication, but that is not practical). However those arithmetic operations are exponential in time because coefficients grow exponentially (at least). There is possibility to simplify graph a bit by contracting vertices without loops and merge multiple loops on vertices, but that does not help much.

I am wondering if there is more efficient algorithm to solve this problem. Maybe there are papers on similar subject, however I did not find any.

Here you can see example of such graph. It has GCD=10.

# Answer
I think this actually has really simple solution. I haven't checked it programmatically yet, but it seems right to me. Please comment if you think it does not work.

Main difficulty were loops. But we can efficiently get rid of them. "Eureka" moment was when I realized that position of loops doesn't matter, we can move them anywhere (i.e. to $v\_0$ itself).

Suppose there is path from $v\_0$ to $v\_0$ passing through $v\_1$ which has loop with length $l$, length of path's part before $v\_1$ is equal to $L\_0$ and after $v\_1$ accordingly $L\_1$. Then length of such path is $L\_0+L\_1$. Consider another path which follows exactly same vertices but includes also that loop of $v\_1$. Then length of this path is $L\_0+L\_1+l$. Then GCD of all paths from $v\_0$ to $v\_0$ is equal to

$$GCD(L\_0+L\_1,L\_0+L\_1+l,\ldots)=GCD(L\_0+L\_1,L\_0+L\_1+l-(L\_0+L\_1),\ldots)=GCD(L\_0+L\_1,l,\ldots)$$

by property of GCD. So that is the same result as if loop of length $l$ would be separate path of length $l$, and we can achieve that by moving loop to $v\_0$.

A bit expanding this argument, we can move all loops from all vertices to $v\_0$. By grouping GCD arguments, we can see that we then can replace all loops by one of length which is equal to GCD of lengths of all loops, name it $g$.

Then we recursively contract all other vertices (removing vertex by combining all incoming and outcoming edges), now without loops it is easily done. Usually doing so increases number of edges exponentially. However we can use again property of GCD and reduce edge lengths modulo $g$. This way we keep number of edges bounded. After no vertices are left except $v\_0$, we compute GCD of all loops on $v\_0$ and that is our final answer. If new loop is created during contracting a vertex, then we update $g$ as $g'=GCD(g,l)$, where $l$ is length of new loop, and remove that loop.

We can make other optimizations as well. For example we can remove multiple edges. Suppose we have vertices $v\_1$ and $v\_2$ with 3 edges from $v\_1$ to $v\_2$ with lengths $a$, $b$ and $c$, $L\_1$ being length of path from $v\_0$ to $v\_1$, $L\_2$ being length of path from $v\_1$ to $v\_0$, then GCD of all , then GCD of all paths from $v\_0$ to $v\_0$ is equal to

$$GCD(L\_0+a+L\_1,L\_0+b+L\_1,L\_0+c+L\_1,\ldots)=GCD(L\_0+a+L\_1,b-a,c-a,\ldots)$$

by same property of GCD. So we can choose any one edge to leave and remove other, updating $g$ as $g'=GCD(g,b-a,c-a)$. Here potentially we can cleverly choose which edge is more beneficial to leave.

Also there is possibility to stop algorithm early, if $g$ becomes $1$ (or GDC of all edge lengths).

Here is illustration of the procedure for example graph from question:
> 2 votes

---
Tags: algorithms, graphs, weighted-graphs
---


# Question
Title: Memory capacity of Turing Machine Halting Problem
In Turning Machine Halting Problem, is the memory of the Turing Machine infinite or finite?

Does the Turing Machine have access to infinite tape? Or limited tape?

# Answer
> 1 votes
By definition, *every* Turing machine has access to **unlimited tape**. At every point of execution the machine has inspected a finite portion of the tape, but it always has more available if needed. That is, it will never run out of it.

Mathematically, this is modeled by there being an infinite tape. However, as already stated, at every step of execution only a finite portion of the tape is used.

---
Tags: turing-machines, halting-problem
---


# Question
Title: First-order model checking is not fixed parameter tractable on general graphs
I read that the problem of first-order model checking is believed to be not fixed parameter tractable on general graphs.

Why is this the case? Would be happy about some reference

Thanks in advance!

# Answer
For a fixed $k$, existence of a $k$-clique can be represented as a first order model formula: $\exists u\_1 \dots u\_k, (\bigwedge\_{i \< j} u\_i \neq u\_j ) \land (\bigwedge\_{i \< j} (u\_i,u\_j) \in E)$.

Because $k$-CLIQUE problem is $\mathrm{W}\[1\]$-hard, if the first-order model checking problem is $\mathrm{FPT}$ then $\mathrm{W}\[1\] = \mathrm{FPT}$, contradicting the popular belief that states otherwise.

Of course, such a statement cannot be proved without hypotheses because it implies $\mathrm{P} \neq \mathrm{NP}$.
> 4 votes

---
Tags: complexity-theory, graphs, first-order-logic, model-checking, parameterized-complexity
---


# Question
Title: Reduce instances of a-Turing-machine-does-not-accept-a-string to Turing machines that accept the empty string
I am struggling with a mapping reduction that I think cannot be correct, but I'm not able to say exactly what's the problem.

Let $L\_{u}= \\{\langle M,w\rangle \mid M\text{ accept }w\\}$, $\overline{L\_{u}}= \\{\langle M,w\rangle \mid M\text{ does not accept }w\\}$ and $L\_{\epsilon} = \\{M \mid \epsilon \in L(M) \\}$.

*(Part 1)*

I have started with this:

1. $\langle M,w \rangle \in \overline{L\_{u}}$ iff $f(\langle M,w \rangle) \in L\_{\epsilon}$

My $f$ is a computable function that transforms $\langle M,w \rangle$ in the following TM $M'$:

```
"On input x,
     if x != epsilon, Accept
     otherwise run M with input w,
          if M accepts w, Reject
          otherwise, Accept"

```

Now, assuming $w = \epsilon$, if $M$ accepts $w$ then $\langle M,w \rangle \notin \overline{L\_{u}}$, and $\epsilon \notin L(M')$. If $M$ rejects $w$ then $\langle M,w \rangle \in \overline{L\_{u}}$ and $\epsilon \in L(M')$.

If $w \neq \epsilon$, then we don't need to be dependent of $\overline{L\_{u}}$. So we can accept without any risk.

So, with this in mind, 1. holds and we have a mapping reduction. Since $\overline{L\_{u}}$ is not T-recognisable, so is $L\_{\epsilon}$.

---

*(Part 2)*

Now, the problem. Let's construct a TM $M\_\epsilon$ that recognises $L\_\epsilon$.

```
"On input M (code of a TM),
    run M with input epsilon using the TM for L_u (let's use as a component the Universal Turing Machine - UTM),
       if it accepts, Accept
       if it rejects, Reject"

```

This TM $M\_\epsilon$ should be able to recognise $L\_\epsilon$. That is, given $M$ such that $\epsilon$ is in $L(M)$, $M\_\epsilon$ halts and accepts, otherwise, the machine may or may not halt. But if halts and rejects $\epsilon$, then $M\_\epsilon$ also rejects.

Since $L\_{u}$ ($\\{\langle M,w\rangle \\; | \\; \text{M accepts w}\\}$) is T-recognisable (one may call it recursively enumerable), and we are using the machine that recognises the language $L\_u$, with the modification of always using $w = \epsilon$ to construct $M\_\epsilon$ we know that $M\_\epsilon$ will recognise $L\_\epsilon$.

Now I'm unsure of what definition I have wrong, or what detail I'm overlooking ...

# Answer
I decided to answer my own question since the answers given are not fully correct, maybe because of my confusing question at first. Nonetheless, thanks to @JohnL and @avasuilia for, their answers, making me see my mistake. Also, as said above, in the original question, I should have been more explicit about some terms. That caused the question to have this answer as pointed by @JohnL as the correct solution. However, that solution was not the one that I was expecting, so I am responding to the edited question, that was what I meant at first.

Point 1. from @JohnL is pretty much all that is needed to see the mistake, but I will elaborate further.

First, let’s try to reduce $\overline{L\_{u}}$ to $\overline{L\_{\epsilon}}$. That is:

$\langle M,w \rangle \in \overline{L\_{u}}$ iff $f(\langle M,w \rangle) \in \overline{L\_{\epsilon}}$

Let $f$ be a computable function that transforms $\langle M,w \rangle$ in the following TM $M\_1$:

```
“On input x,
   If x != epsilon, Accept
   Otherwise,
         Run w on M, if M accepts w, Accept
                     if M rejects w, Reject”

```

Let x be different than $\epsilon$. If so, it doesn’t matter the result of $\langle M,w \rangle \in \overline{L\_{u}}$ since it will not affect the *iff*.

If $x = \epsilon$ and $\langle M,w \rangle \notin \overline{L\_{u}}$, meaning $M$ halts and accepts $w$, then $M\_1$ accepts $\epsilon$. This is the expected behaviour.

If $x = \epsilon$ and $\langle M,w \rangle \in \overline{L\_{u}}$, meaning $M$ halts and rejects $w$, then $M\_1$ rejects $\epsilon$. This is the expected behaviour. But it may happen that $M$ doesn’t halt (as far as we know), and in that case $\langle M,w \rangle \in \overline{L\_{u}}$ also holds. In this case, $M\_1$ will be in the same case.

Does this break the *if and only if*? No. The complement of $L\_\epsilon$ is the following: $\\{M \\; | \\; \epsilon \notin L(M) \\}$. This means that $M$, when given $\epsilon$ may or may not halt, but if halts will rejects. $L\_\epsilon$ is $\\{M \\; | \\; \epsilon \in L(M) \\}$, and for this to happen, $M$ must halt to accept.

Let’s sum this up. $M$ not halting on $w$ causes $M\_1$ to also not halt. This means that $\langle M,w \rangle \in \overline{L\_{u}}$ is verified by the definition of $\overline{L\_{u}}$, and $f(\langle M,w \rangle) \in \overline{L\_{\epsilon}}$ is also verified, by the definition of $\overline{L\_{\epsilon}}$.

So we have a mapping reduction from $\overline{L\_{u}}$ to $\overline{L\_{\epsilon}}$.

---

Now the reduction in the question:

$\langle M,w \rangle \in \overline{L\_{u}}$ iff $f(\langle M,w \rangle) \in L\_{\epsilon}$.

We will follow the same principle as $M\_1$. Let $M\_2$ be:

```
“On input x,
   If x != epsilon, Accept
   Otherwise,
         Run w on M, if M accepts w, Reject
                     if M rejects w, Accept”

```

Let x be different than $\epsilon$. If so, it doesn’t matter the result of $\langle M,w \rangle \in \overline{L\_{u}}$ since it will not affect the *iff*.

If $x = \epsilon$ and $\langle M,w \rangle \notin \overline{L\_{u}}$, meaning $M$ halts and accepts $w$, then $M\_2$ rejects $\epsilon$. This is the expected behaviour.

If $x = \epsilon$ and $\langle M,w \rangle \in \overline{L\_{u}}$, meaning $M$ halts and rejects $w$, then $M\_2$ accepts $\epsilon$. This is the expected behaviour. But it may happen that $M$ doesn’t halt (as far as we know), and in that case $\langle M,w \rangle \in \overline{L\_{u}}$ also holds. In this case, $M\_2$ will be in the same case (not halting as far as we know).

Does this break the *if and only if*? Yes. Now we are not talking about the complement, we are talking about $L\_\epsilon$. In this case, $M$ must accept $\epsilon$, and to do this, it must halt.

Let’s sum up this part. $M$ not halting on $w$ causes $M\_2$ to also not halt. This means that $\langle M,w \rangle \in \overline{L\_{u}}$ is verified, but $f(\langle M,w \rangle) \in L\_{\epsilon}$ is not verified.

So, we don’t have a mapping reduction from $\overline{L\_{u}}$ to $L\_{\epsilon}$.

---

So, what we got from this, is that $L\_\epsilon$ is T-recognisable (recursively enumerable), and *part 2* of the question is correct. Also $\overline{L\_{\epsilon}}$ is not T-recognisable.

#### In a nutshell

I has not being careful about the definition of complements of languages, and not being careful about the not halting (as far as we know).

I’m not marking this as solved because I would appreciate some thoughts on my answer.
> 0 votes

# Answer
$L\_\epsilon$ is recursively enumerable whereas $\bar{L\_u}$ is not. If a language $L\_1$ can be reduced to another language $L\_2$ then the following things hold:

1. if $L\_1$ is not T-recognizable then $L\_2$ is not T-recognizable.
2. if $L\_2$ is recursively enumerable then $L\_1$ is recursively enumerable.
3. if $L\_1$ is recursively enumerable then $L\_2$ may or may not be recursively enumerable.
4. if $L\_2$ is not T-recognizable then $L\_1$ may or may not be T-recognizable. This is what's happening in your case.
> 0 votes

---
Tags: turing-machines, computability, reductions, turing-recognizable
---


# Question
Title: Prove $n\log n\neq O(g(n))$ where $g(n)$ alternates between $\log^*n$ and $n!$
I have to prove that $f(n) \neq O(g(n))$, where $f(n) = n\log n$ and $g(n)$ is $\log^\*n$ if $n$ is odd and $n!$ if even.

So my thought is to say that $f(n) = O(g(n))$ and then with the definition prove that this is wrong, but i am struggling. Can someone help me?

# Answer
There is no constant such that $n\log n\<c\log n$ for all odd $n$. (Obviously, there is no constant such that $n\<c$ for all odd $n$).
> 2 votes

# Answer
Let me suggest formal approach to question, because, of course, inequalities are important, but also are important conditions on variables in this inequalities.

To prove directly, that some function is not in some big-$O$, you need negation of definition $f(n)\in O(g(n)),n\to\infty$:

formal defintion is $$\exists c \>0, \exists n\_0\in\mathbb{N}, \forall n\>n\_0, f(n)\leqslant c\cdot g(n) $$ so, negation, $f(n)\notin O(g(n)),n\to\infty$, will be

$$\forall c \>0, \forall n\_0\in\mathbb{N}, \exists n\>n\_0, f(n)\>c\cdot g(n) $$ In definition $n$ is **variable** and $c,n\_0$ are **constants** which we want to find.

In negation $c, n\_0$ are **variables** and we want to determine $n=n(c, n\_0)$ **subsequence** of $\mathbb{N}$.

So, in given case, to prove, that $n \log n \notin O(g(n))$, we need prove, that $n \log \> g(n)$ in conditions done above. Using nice idea from adjacent answer, we can consider two cases:

in case of odd $n$, for $\forall c \>0, \forall n\_0\in\mathbb{N}$ let's consider $n \log n \> c \log n \geqslant c \log^\* n$. To fulfill this inequality is enough to take $n=\max (n\_0, \lfloor c \rfloor +1)$.

even case can be done in similar way.
> 0 votes

---
Tags: asymptotics, big-o-notation
---


# Question
Title: What role is the set, S playing in Dijkstra's algorithm given in the book CLRS?
I'm looking at Dijkstra's algorithm for single source shortest paths in a graph $G$ from a vertex $s$ from *Introduction to Algorithms* by Cormen et al. The $w$ parameter is the weight function such that $w(u,v)$ gives you the weight of the edge from $u$ to $v$.

```
DIJKSTRA(G, w, s)
  INITIALIZE-SINGLE-SOURCE(G,s)
  S = {}
  # Put all vertices of G in a priority queue, Q.
  Q = G.V
  while Q != {}
    u = EXTRACT-MIN(Q)
    S = S U {u}
    for each vertex v in G.Adj[u]:
       RELAX(u,v,w)

```

Here, the INITIALIZE-SINGLE-SOURCE method simply sets the shortest distance values for $s$ to $0$ and all other vertices to $\infty$. The RELAX method:

```
RELAX(u,v,w)
  if v.d > u.d + w(u,v)
    v.d = u.d + w(u,v)
    v.pi = u

```

Note that all vertices have the $v.d$ property which is the length of the shortest path from $s$ to $v$ and the $v.pi$ property which is the parent of $v$ in the shortest path.

Staring at the algorithm, I'm wondering what role the set $S$ is playing exactly. What if I removed $S$ completely - doesn't seem like it'll affect the algorithm at all. What am I missing?

# Answer
> 9 votes
No, you are not missing anything if you remove $S$ completely. You could implement and run Dijkstra's algorithm correctly still.

Set $S$ is used later in the book to help explain the algorithm and prove its correctness.

* $S$ is the set of "**s**ettled vertices", the vertices to which the shortest distances from the source have been computed. The partition of all vertices into "settled vertices" and "unsettled vertices" together with the continual settlement of the nearest unsettled vertex summarizes Dijkstra's algorithm.
* The correctness of the algorithm is proved by showing the loop invariant that all vertices in $S$ are settled at the start of each iteration of the while loop.

In most implementations of Dijkstra's algorithm, $S$ does not appear explicitly as a variable or an indicator variable, as you might have suspected. However, it appears implicitly since it consists of all vertices that have been extracted from the priority queue $Q$,

There is a common implementation of the algorithm where $S$ is maintained explicitly, which I have used many times. Since it may not be easy to update the priority of an element in a priority queue efficiently, vertices with shorter distance found are added to the priority queue even if they are in the priority queue. After extracted from priority queue, a vertex will be used to relax the distance of its neighbors only if it is not in $S$, after which it will be added to $S$. Here is the pseudocode.

```
DIJKSTRA(G, w, s)
   INITIALIZE-SINGLE-SOURCE(G,s)
   S = {}
   # Initialize priority queue Q with the source
   Q = {s}
   while Q != {}
       u = EXTRACT-MIN(Q)
       if u is not in S
           for each vertex v in G.Adj[u]
               RELAX(u, v, w)
               Add v to Q if v.d becomes less
           S = S U {u}

```

---
Tags: graphs, shortest-path, graph-traversal, dijkstras-algorithm
---


# Question
Title: Why computer didn't use cesium atom to define 1 second?
As far I know computer using crystal oscilator to define 1 second and it's not real 1 second, i mean it's not stable.

While real clock using cesium and we know cesium is stable, why doesn't computer contain cesium in its component to define 1 second.

So thats mean 1 second in clock atom and 1 second in computer are not syncreon, even 1 second at between two computers are not syncreon each other.

What I mean with computer is not only advanced computer device like personal computer, this applied to microcontroller.

Instead of using atom cesium, they are using Internet Protocol especially `Network Time Protocol (NTP)`

I'm wonder is there fatal effect from asyncreon of computer time like maybe airport schedule or what if they didn't use NTP.

# Answer
First of all, the reason personal computers dont't use atomic clocks based on caesium is price. One CSAC (chip scale atomic clock) costs 5000 USD nowadays. The added precision is not worth the price for the normal consumer. However there are cases where the time synchronization via NTP combined with a crystal oscillator are not precise enough. For example missiles that rely on GPS to determine their location / find their target use CSACs to get much higher GPS precision.
Other applications are for example radar, or scientific measurements.
> 5 votes

---
Tags: clocks, real-time
---


# Question
Title: How does + symbol works in regular expression?
What's the difference between $a^\*+b^\*$ and $(a+b)^\*$?

I was going through this question. So according to the question-:

(a+b)\* generates $\in$, a,b,ab,ba,aa,ba,...

whereas a\*+b\* generates $\in$, a,aa,aaa,b,bb,bbb etc.

Why can't a\*+b\* generate ab? What's stopping it from generating it? I feel like I am missing something fundamental. (Even if I take english meaning of word "OR", (a+b)\* should generate same as a,aa,b,bb etc.)

I don't understand what's going on here. Please help me.

# Answer
> 2 votes
If $E$ and $F$ are regular expressions then $E+F$ is also a regular expression that matches all words that are matched by at least one of $E$ and $F$.

In you case $E=a^\*$, $F=b^\*$, and $E+F=a^\*+b^\*$. The word $ab$ is not matched by $a^\*+b^\*$ since it is not matched by $a^\*$ nor by $b^\*$.

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


# Question
Title: Prove that a quadratically-constrained linear program (QCLP) is NP-Complete
> Show that if we strengthen linear programming by also allowing constraints of the form $$ \sum\_{i,j = 1}^n a\_{ij} x\_i x\_j = b, $$ for integers $b$ and $a\_{ij}$, then the problem becomes NP-complete.

---

This is a practice problem that I am trying to solve. I really do not know how to approach, or reason about it. I understand that if $i =j$ for instance, then there would be non-linear polynomial constraints. So then, this will not be a linear program anymore. Particularly, $x^2 = b \implies$ two areas of solutions, so I suppose this affects the linear program somehow.

I have tried reducing SAT to this problem ,but with no success and it also seems like a wrong approach.Now I am thinking Vertex Cover, but I am not sure where to begin. Can anyone give some insights on this problem ?

# Answer
Given a graph $G$ and a parameter $k$, consider the linear program with a variable $x\_v$ for each vertex $v$, and the following constraints:

* $x\_v \leq 1$ for all vertices $v$
* $\sum\_v x\_v \ge k$
* $x\_u x\_v = 0$ whenever $(u,v)$ is an edge

This program is feasible iff $G$ contains an independent set of size $k$.
> 5 votes

# Answer
You can force a variable $x\_i$ to be binary introducing a new variable $y\_i$ and adding the quadratic constraint $y\_i^2 = 1$ (forcing $y\_i$ to be either $1$ or $-1$) and the linear constraint $2 x\_i = y\_i + 1$. It turns out that this is the only type of quadratic constraint needed.

Given two binary variables $x\_i$, $x\_j$, you can force another binary variable $x\_k$ to be equal to their logical "and" by writing the linear constraints $x\_k \le x\_i$, $x\_k \le x\_j$, $x\_k \ge x\_i + x\_j -1$. Also, given a binary variable $x\_k$ you can force another binary variable to $x\_h$ to be equal to the logical "not" of $x\_h$ by writing the linear constraint $x\_h = 1-x\_k$. We have then ensured that $x\_h = x\_i \text{ NAND } x\_j$. Since the NAND gate is a universal gate, you can take any instance of circuit SAT, convert it into a circuit consisting only of NAND gates, and then convert it into a linear program with quadratic constraints by:

* Creating a binary variable for each circuit input.
* Writing the above set of constraints for each NAND gate in the circuit.
* Setting the objective function to $\max x^\*$, where $x^\*$ is the variable corresponding to the circuit's output.

Then, deciding whether the circuit SAT instance is a "yes" instance corresponds to checking whether the objective function of an optimal solution of the linear program is $1$.

Notice that both the transformation into a circuit having only NAND gates, and the above reduction can be performed in linear time.
> 4 votes

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


# Question
Title: Is there a reason Depth-First Search and Breadth-First search commonly called "Search" instead of "Traversal?"
From my understanding, two separate and distinct operations can be performed on binary search trees: Search and Traversal.

**Search**: Given a key, search will run an algorithm to find the node containing that key in the tree, then return this node.

**Traversal**: Using a Breadth-First or Depth-First search algorithm, visit every node in the tree.

The above two operations are distinct and have separate algorithms with little in common.

Considering Breadth-First Search and Depth-First Search perform a *traversal* operation and not a *search* operation, why are they commonly called such instead of Depth-First Traversal and Breadth-First Traversal?

I'm curious if there's something I've misunderstood here, or there's a specific reason for this.

# Answer
> 3 votes
> Considering Breadth-First Search and Depth-First Search perform a traversal operation and not a search operation

I would not say that as a blanket statement. While it does make sense in certain context it can be very misleading.

As one who programs in Prolog daily, traversal and search are very distinct.

When I see the word traversal used explaining code I expect the code to visit every node of a structure (think tree, graph, list, etc.). Traversals are typically hidden inside map functions and thus visit every node.

When I see the word search I also think of guards that modify the search and search indexes that make the search more efficient. Also a search may visit all of the nodes, some of the nodes or only one node, a search does not always need to visit every node and often does not.

However there are other types of methods/functions/predicates that use callbacks and will traverse a structure but use the call back to access guards and search indexes making the traversal more efficient.

---

You noted binary tree but it makes more sense if one uses a binary search tree instead meaning the values are ordered such that for a node all values greater are in the left branch and all lesser values are in the right branch.

A traverse of a binary search tree will visit every node of the tree.

A depth-first search of binary search tree will use the value at the node to decide to search the left or right branch. This obviously does not traverse the entire tree.

A breadth-first search of a binary search tree seems senseless. (confused emoji goes here) It is ignoring the fact that a binary search tree is constructed to quickly find a value by comparing the current value and picking the left or right branch.

# Answer
> 4 votes
It seems that you are only focusing on a very limited use of BFS and DFS.

Consider this wikipedia entry for BFS, where it was stated that BFS was invented to **find** a connected component and was later rediscovered as an algorithm for **finding** shortest path out of a maze. This entry on DFS, states that it was use to solve mazes which basically means **finding** a path.

What I simply mean from above is that both algorithms are really meant for searching, although different from how you *search* using a BST. Based on the articles, BFS (1945/1959) and DFS (19th Century) predates the invention of BST (1960). Using BFS and DFS as traversal strategy is just an application of these algorithms.

# Answer
> 0 votes
Traversal means visiting every element exactly once but in case of DFS , elements are visited more than once , that's why it is known as searching rather than traversal .

---
Tags: binary-trees
---


# Question
Title: Why windows 11 does not support old cpu?
I know CPUs execute machine language code. Also I know operating systems such as Windows and Linux are a piece of code. But I cannot understand why Windows 11 does not run on a somewhat old CPU.

Can anyone explain it please?

# Answer
It´s an artifical barrier set by Microsoft that requires a **TPM 2.0**, intended to enhance system security.

A TPM is a so-called **Trusted Platform Module**, a piece of security hardware on a chip (in this case the CPU) that can be trusted for several security relevant things like storing keys etc. It also has a unique own key as shipped that can be used to verify it as a platform.

Many not-so-old CPUs have a TPM on them, but don´t support the rather new TPM 2.0 version.

Microsoft claims to enhance Windows 11 security by requiring it: *"Today, we are announcing Windows 11 to raise security baselines with new hardware security requirements built-in that will give our customers the confidence that they are even more protected from the chip to the cloud on certified devices."*

Yes, it is something controversial. My own desktop with its 5 year old CPU doesn´t support TPM 2.0. Microsoft alienated a lot of customers with that.
> 2 votes

---
Tags: operating-systems, cpu
---


# Question
Title: Consequence of having a randomised algorithm for graph colouring, which shows Yes and No with probability $1$ and $p(n) \sim_{n} 1$
Suppose we have a randomized algorithm that takes a graph G and color k as inputs and provides yes if the graph is k-colorable and no with probability $p(n)$ if it's not k-colorable, where $n$ is the number of vertices. What is the consequence if someone comes with a proof that $\displaystyle \lim\_{n \rightarrow \infty} p(n) = 1$.

Does it imply that graph coloring in BPP or ZPP?

N.B. I am familiar with randomized algorithms, NP, NP-completeness, and polynomial reductions as they were covered in Algorithms, Automata, and Languages. However, I didn't go too deep into complexity theory. In my understanding answer to the question is "if its true then graph coloring is in BPP."

# Answer
The complexity class RP consists of problems which have a randomized algorithm, running in polynomial time, with the following properties:

* If the answer is No, the algorithm always answers No.
* If the answer is Yes, the algorithm answers Yes with probability at least $1/2$ (or at least $1/\mathit{poly}(n)$, or at least $1-1/\exp(\mathit{poly}(n))$ — the resulting class is the same).

You have a similar promise with Yes and No reversed, so the complexity class is coRP.
> 2 votes

---
Tags: algorithms, complexity-theory, graphs
---


# Question
Title: How to prove non-planar graph can't reduce to single line
Define two operations:

B-operation: When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices.

C-operation: When one edge connects vertices $u$ and $v$, another edge connects $v$ and $w$ (where $u \ne w$), and there is no other edge incident to $v$, remove the vertex $v$, and replace the two edges with a new edge connecting $u$ and $w$.

How to prove a non-planar graph can't become a graph with only two vertices and a single edge by repeating B and C?

Two examples:

* $K\_3$, let the vertices be called $A\_1,A\_2,A\_3$. Use C on $A\_2$ to remove $A\_2$, then B on $A\_1$ and $A\_3$ to remove the redundant edge.
* $K\_4$, since all vertex degrees are 3, no C is possible, and since there are no multi-edges, no B is possible.

# Answer
Show that if $G$ reduces to $H$ via one of your operations and $H$ is planar, then $G$ is also planar.
> 2 votes

---
Tags: graphs
---


# Question
Title: Hash / Compression algorithm to shorten text?
I desperately need a hash / compression function that is suited to **shorten text**.

The context is this: I want to bring order and sort my box with hundreds of charging adapters (duh). After I determined for each one to what ever it belongs to, I want to label it accordingly.

Why don´t I just enumerate them? I have tried this in the past and it didn´t work out well for me. I forgot where the file is that mapped numbers, and also the 'order' didn´t make any sense.

What I want to do: have a function f that would do something like e.g. "Nikon CoolPix S3300" -\> a9cd81d2, so **a function that shortens a string that can contain alphanumeric letters and outputs a shorter (hexanumerical) string** that could also decoded / reversed later to find out what was the original input.

If I wanted to simply encode the string, the output would always be longer. In ASCII or UTF-8, a single character would then by 1 byte each at least, meaning two hexadecimal numbers per letter. The result is that the output is not shorter but much longer.

I also considered hash functions. However, I´m unsure about this because of these factors:

1. Most hash functions have a quite long output that wouldn´t fit onto my labels, e.g. 128 bits, which is 32 hex digits.
2. Cryptographic hash functions aren´t intended to be reversed. I am aware that some of the old hash functions like e.g. md5 can be cracked, but I want something that could be decoded back in a matter of seconds, even on a CPU.

So in the end, I am looking for something with **these properties**:

* Is fast to compute in both directions (hashing/reversing or encoding decoding)
* Has outputs of equal sizes, like hash functions
* The outputs are short, e.g. 4 bytes
* Despite short outputs, the collision probability of natural language strings is generally small
* Restoring / decoding the original string is accurate. If collisions exist, it is likely to get the original input string

Does a hash / encoding algorithm exist that can fulfill these needs?

# Answer
> 2 votes
If you insist that it be reservible, what you want is data compression. Unfortunately in practice it is unlikely that the result will be short enough to be useful. At that point I recommend you buy a label-maker and label it with "Nikon CoolPix S3300" and give up on trying to encode that in some fancy way.

---
Tags: strings, hash, encoding-scheme
---


# Question
Title: Differences between DFS based cycle detection algorithms
I have seen several variants of DFS algorithms used to check existence of cycles in graphs.

They all have the same structure : do a DFS in the graph. There is a cycle in the graph if and only if there exists a node which, while being treated, has a neighbour which has property P.

The variants are based on different properties used for P :

1. P = already visited but not the current node's parent
2. P = "grey" (a node already discovered but not all its children are already visited) but not the current node's parent
3. P = a node currently in the stack. By stack, here I mean the basic stack that is used to implement the DFS, nothing more.

I've seen 1. and 2. a lot of times here and in the literature. For 3., I wrote it myself, I have a proof of the equivalence with the existence of a cycle, that I am quite confident in (but I could be wrong !)

**My question is** : are these three equivalent (to the existence of a cycle, in other words are those correct) ? Under some specific assumptions for some of them ?

What I already think I know :

* I know that the variant 1. does not work for directed graphs (because the already visited neighbour might not be reachable in this direction). In undirected graphs it seems that all the three variants are equivalent (to the existence of a cycle).
* If 2. and 3. are correct they are of course equivalent since both are equivalent to the existence of a cycle. But is there a simple way to see their equivalence directly ? Clearly 3 implies 2 since a node in the stack is gray. But how is it true that if there is a node with a gray neighbour, then there is a node with a neighbour in the stack ?
* It seems to me that the difference between grey nodes as in 2. and stack nodes is that grey nodes are "recursive stack" nodes (i.e. nodes in the stack of the recursive calls if DFS is implemented recursively)

# Answer
I think I've found my answer here. So basically the differences between 2 and 3 is just the order in which children are inserted in the stack. So in the end, grey nodes and stack nodes as I've described above are actually the same thing up to re-ordering of nodes.

https://stackoverflow.com/questions/9201166/iterative-dfs-vs-recursive-dfs-and-different-elements-order
> 1 votes

---
Tags: algorithms, graphs
---


title: Divide and conquer recurrence relation

text:
# Question
Title: Divide and conquer recurrence relation
I have divide and conquer problem and below is the recurrence relation for it $$\begin{align}t (n) &= a\cdot t (n/4) + O (n^2/\log(n)) + O(n^2)\\ t(n) &= a\cdot t (n/4) + O(n^2) \end{align}$$ I solved this recurrence for different values of $a$. These are the solutions below
$$ =\begin{cases}O(n^2),&\text{ for }a = 8\\ O(n^2 \log(n)),&\text{ for }a = 16\\ O(n^5/2),&\text{ for }a=32 \end{cases}$$

Do these solution always apply if $n$ is not power of $4$ and how can I justify it?

# Answer
You need to define first where the recursion ends. And what t(n/4) means if n is not a multiple of 4.

The likely outcome will be that t(n) for 4^k \< n \< 4^(k+1) is between t(4^k) and t(4^(k+1)).
> 0 votes

# Answer
We can use **Master Theorem** to solve this :

If a **Recurrence Relation** is of the Form

## $$T(n)=aT\bigg(\frac{n}{b}\bigg)+{n^k}({\log(n)})^p$$

Then, as per **Master Theorem**, we have **Six Conditions** depending on value of $a,b,k$ and $p$

* If $\log\_ba\>k$
Answer is $\theta(n^{\log\_ba})$
* If $\log\_ba=k$ and $p\>-1$
Answer is $\theta({n^k}({\log n})^{p+1})$
* If $\log\_ba=k$ and $p=-1$
Answer is $\theta({n^k}\log\log n)$
* If $\log\_ba=k$ and $p\<-1$
Answer is $\theta(n^k)$
* If $\log\_ba\<k$ and $p\geqslant0$
Answer is $\theta({n^k}({\log n})^p)$
* If $\log\_ba\<k$ and $p\<0$
Answer is $\theta({n^k})$

In any problem, our main motive is to find $a,b,k$ and $p$.

**In Given Problem**
$b=4$
$k=2$
$p=0$

1. If $a=8$, $\log\_48 = 1.5$ which is less than $k$, and $p\geq0$

Therefore, Answer is $\theta({n^k}({\log n})^p)$. Putting Values **$$\theta(n^2)$$**
2. If $a=16$, $\log\_416 = 2$ which is equal to $k$, and $p\>-1$

Therefore, Answer is $\theta({n^k}({\log n})^{p+1})$. Putting Values **$$\theta({n^2}{\log n})$$**
3. If $a=32$, $\log\_432 = 2.5$ which is greater than $k$

Therefore, Answer is $\theta(n^{\log\_ba})$. Putting Values **$$\theta({n^{5/2}})$$**

**Thus, obtained solutions are Correct!**

* Since, we are finding *"Time Complexity"*, and not *"Solution of Recurrence Relation"*, the asymptotic analysis of the Recurrence Relation is correct whatever may be the value of $n$.
* Moreover, this entire result can be justified by Master Theorem. The Theorem *\[means, it has been mathematically proved\]* provides a crisp method for finding Time Complexity with help of Recurrence Relation.
> -1 votes

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: How Janus (Reversible Programming Language) `if`, `while`, and Update Work
In Reversible Computing, all program statements are reversible. I understand for example that the following:

\begin{align} x\ {+}&{=}\ 4\\ y\ {\*}&{=}\ x\\ x\ {-}&{=}\ 10 \end{align}

Has the inverse:

\begin{align} x\ {+}&{=}\ 10\\ y\ {/}&{=}\ x\\ x\ {-}&{=}\ 4 \end{align}

However, I am not following the following `if` statement, `while` loop, and reversible update:

$$\texttt{if}\\;e\_1\\;\texttt{then}\\;s\_1\\;\texttt{else}\\;s\_2\\;\texttt{fi}\\;e\_2$$

$$\texttt{from}\\;e\_1\\;\texttt{do}\\;s\_1\\;\texttt{loop}\\;s\_2\\;\texttt{until}\\;e\_2$$

$$x \odot f(y)$$

I understand that for a statement to be reversible, the function has to be *injective*. So you can't have $f(x, y) \mapsto x$ because information is lost.

I don't understand how those if/loop/update functions can be reversible without storing some sort of information/state in the program's evaluation. For example:

```
x += 4

```

While that does have the inverse `x -= 4`, that is not inherent in the statement `x += 4`. For it to be reversible, it is almost like it would have to store state about it's previous value:

```
statement1 x = 1
statement2 x.values.push(x)
statement3 x.value = x.value + 4

```

Then you can do `undo x` and it would do something like:

```
x.value = x.values.pop()
x // 1

```

which is equivalent to:

```
x -= 4

```

So basically I'm wondering, how these "reversible" statements work. If they are saving state in some hidden way, or if it is reversible in some sort of tricky way. Maybe an example of stepping forward and backward through the program as it evaluates any of these expressions.

# Answer
> While that does have the inverse `x -= 4`, that is not inherent in the statement `x += 4`.

Invertibility means that every program `A` has an inverse `B` such that, if `A` terminates, `A ; B` terminates and does nothing. `A = (x += 4)` and `B = (x -= 4)` satisfy this criterion.

---

In pseudocode, `if p then A else B fi q` is equivalent to

```
if p
then
    A
    assert q
else
    B
    assert not q

```

(If an assertion fails, the whole program halts with an error.) Thus **`q` is true after the loop if and only if `p` is true before the loop**. This fact allows us to recover which branch was taken originally, when we enter the conditional backwards:

```
inverse (if p then A else B fi q) = if q then (inverse A) else (inverse B) fi p

```

The assertion becomes the test, and the test becomes the assertion.

---

Similarly, `from p do A loop B until q` is equivalent to

```
assert p
loop
    A
    if q
    then
        break
    B
    assert not p

```

When entering the loop backwards (through the `break` statement, which is the only place we could have exited the loop), we first invert `A`. Now `p` holds if and only if we entered the loop at this point (due to the assert before the loop and the assert at the end of the loop body). Thus if `p` holds, we exit. Otherwise, we invert `B` and repeat the process. Therefore, the inverse is

```
inverse (from p do A loop B until q) = from q do (inverse A) loop (inverse B) until p

```

---

References:

1. *Janus: a reversible programming language* (1986)
2. *A reversible programming language and its invertible self-interpreter* (2007)
3. *Reversible flowchart languages and the structured reversible program theorem* (2008)
4. *Partial evaluation of the reversible language janus* (2011)
> 2 votes

---
Tags: loops, reversible-computing
---


# Question
Title: Trying to understand the basic about recurrence trees
I have little background on recurrence trees, and I am working on the following exercise:

**Exercise.** Take $T(n) = 2T(n/2) + 3\log(n)$. Draw the recurrence trees for $n=2$ and $n=4$. What can we conclude complexity-wise?

**My attempt.** For $n=2$ we have the following recurrence tree:

```
Recursive Call        Recurrence Tree        Sum

     T(2)                3log(2)           3log(2)
                         /   \
     T(1)            3log(1)  3log(1)      6log(1) = 0

```

Since we arrived at $T(1)$, we should stop (**IS THIS TRUE?**) with our tree and the total sum is given by $3\log(2) + 0 = 3\log(2) = \Theta(1)$ which means that, complexity-wise, for $T(2)$, we're dealing with constant-time complexity.

For $n=4$, and using the same method, we could should that the sum would be $3\log(4) + 6\log(2) = \log(4^3\*2^6) = \Theta(1)$.

Let's upgrade the exercise and draw the recurrence tree for any $n$. Here follows my attempt:

```
 Recursive Call        Recurrence Tree        Sum

     T(n)                3log(n)             3log(n)
                         /   \
     T(n/2)          3log(n/2) 3log(n/2)      6log(n/2)
                       / \
                      /   \
    T(n/2^2)   3log(n/4)  3log(n/4) (...)     12log(n/4)

     (...)

     T(n/2^i)        (...)                   3*2^i log(n/2^i)

```

And we stop when $\frac n {2^i} = 1 \Leftrightarrow \lg n = i$, where $\lg n = \log\_2 (n)$. With this being said, our total sum is $\sum\_{i=0}^{\lg n} \left(3\*2^i \log(\frac n {2^i} ) \right) $. And I don't know how to proceed from here.

Is my attempt wrong at any point?

# Answer
> 1 votes
#### "Since we arrived at $T(1)$, we should stop."

Yes, the recurrence relation should not be applied any more once the initial conditions are reached.

It should not be a problem to assume the value of $T(1)$ and no others are given as the initial conditions for the recurrence relation, although it does not violate any rules if all values of $T(1), T(2), T(3), T(4)$ are given independently along with the recurrence relation $T(n) = 2T(n/2) + 3\log(n)$, making the task of drawing the recurrence trees for $n=2$ and $n=4$ vacuous.

Assume that $T(1)=t\_1\ge0$. Assume the $\log$ in the question is the logarithm with base $2$. A difference base will not affect the result of asymptotic analysis as long as it is a constant greater than 1.

$T(2)=2T(1) + 3\log\_2(2) = 2t\_1 + 3.$ **Note $t\_1$ should appear.**
$T(4)=2T(2) + 3\log\_2(4) = 4t\_1 + 12.$

So it takes up to some constant time to compute $T(2)$ and $T(4)$, both of which are constants, too.

"$3\log(2) + 0 = 3\log(2) = \Theta(1)$" might not be outright wrong. However, "$=\Theta(1)$" makes sense only when the left-hand side is viewed as a function of a variable that could go to infinity.

#### Obtain an asymptotic approximation for $T(n)$

The recursion trees for $n=2$, $n=4$ and general $n$ in the question are pretty good.

Suppose $n=2^k$ for some integer $k\>0$. Do not forget $t\_1$.

$$T(n)=2^kt\_1 + \sum\_{i=0}^{\log\_2(2^k)} 3\cdot2^i \log\_2(\frac{2^k}{2^i}) = 2^kt\_1 + \sum\_{i=0}^{k} 3\cdot2^i (k-i)= 2^kt\_1 + 3\sum\_{i=0}^{k-1}2^i (k-i)$$

Intuitively, the sum $\sum\_{i=0}^{k-1}2^i (k-i)$ is not much different from $2^{k-1}$, the last term where $i=k-1$.

* "Intuitively" is meant to alert you to learn this kind of approximate reasoning/understanding.
* "not much different" means "different by at most a constant factor". This factor might be as large as $999999999$ or even much larger. As long as it is independent of $n$, it does not matter how large it is.
* Look at all the summands, $\cdots,\ 2^{k-4}4,\ 2^{k-3}3,\ 2^{k-2}2,\ 2^{k-1}1$, from the back to the front. Each summand is a product of a power of $2$ and another number. The power of $2$ shrinks to one half each time and the other number increases by $1$ each time. The shrinkage of the power of $2$ is so much more significant than the addition of $1$, the product shrinks very fast as well. It shrinks so fast that sum of all them is not much different from the first term (from the back).

Let us realize the intuition above by accurate computations.

Let $X=\sum\_{i=0}^{k-1}2^i (k-i)$. $$\begin{aligned} X&=-X+2X\\ &=-(k + 2(k-1) + 2^2(k-2) + 2^3(k-3) + \cdots + 2^{k-2}2 + 2^{k-1})\\ &\quad\quad\quad +(2k\quad\quad\ + 2^2(k-1) + 2^3(k-2) + \cdots + 2^{k-2}3 + 2^{k-1}2 + 2^{k}) \\ &\quad\text{(combine terms with the same power of 2)}\\ &=(2^k-k)+\sum\_{i=1}^{k-1}2^i \\ &=2^{k}-k+(2^k-2) \quad\quad(\text{which is not much different from }2^{k-1}) \end{aligned}$$ So, $T(n)=2^kt\_1+3X =2^k(t\_1+6)-3k-6=n(t\_1+6)-3\log\_2(n)-6=\Theta(n)$.

---
Tags: asymptotics, recurrence-relation, recursion, landau-notation
---


# Question
Title: Minimal DFA produced by equivalent theorem vs Myhill nerode theorem are different. What is happening?
The problem is-:

Site 1 solves this in this way-: https://onlinesmarttrainer.blogspot.com/2020/08/minimization-of-dfa-solved-example.html

Site 2 solves this in different way-:

https://aswaddev.github.io/dfa-minimizer/

Book solves (using table filling method) and gets this-:

Here is the youtube video, which uses Myhill Nerode method and tallies with my answer as well-:

https://www.youtube.com/watch?v=JORJffsG4B0

My answer tallies with the blogspot one.

Why are all answers different to each other? If you know the method which is correct, can you tell in brief about that method or link some study material for that method?

# Answer
The second online tool seeminly contains a code bug. It makes $F$ and $A$ states equivalent, but $0$-transition from $F$ is to the final state, while $0$-transition from $A$ is to the non-final state $B$. The same bug is with the state $D$.

The table from the book is equivalent to the first solution up to the node renaming.
> 1 votes

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


# Question
Title: an O(m+n) algorithm to decide whether a graph can be reduced to a single edge with two vertices
Given B and C operations.

* B-operation: When two multi-edges connect a pair of vertices, replace the multi-edges with a single edge connecting the pair of vertices.
* C-operation: When one edge connects vertices $u$ and $v$, another edge connects $v$ and $w$ (where $u \ne w$), and there is no other edge incident to $v$, remove the vertex $v$, and replace the two edges with a new edge connecting $u$ and $w$.

Input a graph with n vertices and m edges, and check whether it can be reduced to a single edge with two vertices. How to make the algorithm be $O(m+n)$ time complexity?

My thought is to record the deg of vertices. But can't figure out what to do next.

# Answer
#### The Simple Idea

Keep the graph without multi-edges by B-operations. Apply C-operation whenever we can, keeping track of possible new opportunities of C-operations in a set of vertices.

#### A Simple Algorithm

Assume there is no loops in the graph.

1. Replace all edges between the same pair of vertices by one edge.
There will be at most $m$ edges left. The graph is a simple graph now.
2. Put all vertices in a set $S$.
3. Repeat the following routine until $S$ is empty.
    1. Poll $S$ to get a vertex $v$.
    2. If the degree of $v$ is 2,
        1. apply the C-operation that removes $v$ together with two edges incident to $v$ and adds an edge between vertex $u$ and $w$. If there has been another edge between $u$ and $w$, merge these two edges by a B-operation, so that the graph remains a simple graph.
        2. add $u$ and $w$ to $S$.
4. Return "Yes" if the graph is a single edge with two vertices. Otherwise, return "No".

#### Time-Complexity Analysis

Each execution of step 3.2.1 will reduce the number of edges in the graph at least by 1. Hence step 3.2.1 can be executed at most $m$ times. That means step 3.2.2 can be executed at most $m$ times, too.

Hence, the number of times a vertex is added to $S$ by step 3.2.2 is at most $2m$. Since $S$ contains $n$ vertices initially, the total number of times that a vertex is added to $S$ is $n+2m$. So the total number of times the removal of a vertex from $S$ can be done by step 3.1 is at most $n+2m$. That is, step 3.1 can be executed at most $n+2m$ times.

Hence the running time of step 3 is $O(n+m)$. The running time of step 1 and step 2 is $O(n+m)$. So, the time-complexity of the algorithm is $O(n+m)$.
> 1 votes

---
Tags: algorithms, graphs, time-complexity
---


# Question
Title: Regular Expression for $L = \{w \mid w\in \{a,b\}^*\text{ and }n_a(w) \equiv 1 \bmod 3\}$
Here, $Σ=\\{a,b\\}$ The number of $a$ can be $1, 4, 7, 10.....$, also $a$ can be placed anywhere.

Find Regular Expression for $L = \\{w \mid w\in \\{a,b\\}^\*\text{ and }n\_a(w) \equiv 1 \bmod 3\\}$

How can I proceed in this problem?

# Answer
> 2 votes
You haven't indicated your alphabet, so let me assume that it is $\\{a,b\\}$, though this makes little difference.

In order to create a regular expression for your language, you can use the following two steps:

1. Write a regular expression for the language of all words $w$ *over the alphabet $\\{a\\}$* such that $n\_a(w) \equiv 1 \pmod{3}$.
2. Add back the $b$s to the regular expression. One way to do it is to replace each $a$ by $ab^\*$, and to add an additional $b^\*$ as a prefix.

---
Tags: regular-languages, regular-expressions
---


title: Comparing two functions rate of growth

text:
# Question
Title: Comparing two functions rate of growth
This is pretty simple and I **THINK** I know the answer to the question, but I don't know how to prove it formally. Below follows the question.

**Question.** Compare the functions $f(n) = \frac{n^2}{\log(n)}$ and $g(n) = 3^{\log(n)}$ in terms of rate growth.

**My attempt.** I have tried to compute the limit $\lim\_{n \rightarrow +\infty} \frac{f(n)}{g(n)}$ but this doesn't seem easy by hand. Using *symbolab*, it says it can't compute the limit. Obviously my intuition points towards $f(n) \<\< g(n)$ just because $g(n)$ is an exponential function, and normally it grows faster than the polynomial ones, but I don't know how to prove this for the functions above.

Besides what I've shown above, I also tried taking $\log$ in both the functions, which would origin $2\log(n) - \log(\log(n))$ for $f(n)$ and $\log(n)\log(3)$ for $g(n)$ and the limit between these two is a constant which leads me to believe I cant really use this to comparate both the functions (Since my intuition tells me $f(n) \<\< g(n)$, the limit I stated would be a contradiction).

So here come my **two** questions:

1. Can I use the $\log$ property above to compare two functions? I.e., does $f(n) \<\< g(n) \Leftrightarrow \log(f(n)) \<\< \log(g(n))$ ? More generally, is the comparation (of rates of growth) between $f(n)$ and $g(n)$ equivallent to comparing the rates of growth of $\log(f(n))$ and $\log(g(n))$ ?
2. How would one compare the functions from the **question** formally?

Thanks for any help in advance.

# Answer
$$\lim\_{n\to\infty}\frac{n^2}{\log(n)\ 3^{\log(n)}}=\lim\_{n\to\infty}\frac{n^{2-\log(3)}}{\log(n)}=\infty$$ because any positive power of $n$ grows faster than a logarithm.

---

To convince yourself, you can set $m=\log(n)(2-\log(3))$ and the limit is proportional to that of$\dfrac{e^m}m$. An exponential grows faster than any polynomial.
> 3 votes

---
Tags: complexity-theory, time-complexity, asymptotics, big-o-notation
---


# Question
Title: Efficient data structure to maintain a set of postal codes and mailbox numbers
A 'person' is represented by a combination of postal code and mailbox number(both are natural numbers)

No two postal codes are alike, yet a postal code can contain many different mailboxes.

At any given postal code, all mailboxes have different numbers.

Display a data structure that supports the following methods in best complexity:

$Insert(z,p)$: insert a new person into the structure, who's postal code is $z$ and mailbox number is $p$.

$Delete(z,p)$: delete a person with postal code $z$ and mailbox number $p$ .

$Median(z)$: at postal code $z$, who has a mailbox that is the median? (half of people at postal code $z$ have mailbox with lower number)

$Max(z\_1,z\_2)$: out of the people living in the range $z\_1 \rightarrow z\_2$, who has the maximal mailbox number?

$HowMany(x)$: how many postal codes have exactly $x$ mailboxes?

The DS I've come up with was an AVL tree, where each key is a postal code and each node has a pointer to another AVL tree which represents the mailboxes in that postal code. That solves $insert/delete$ in

$O(max\\{log$(amount of postal codes)$, log$(amount of mailboxes in postal code z)$\\})$

which seems pretty efficient.

From this point forward I'm not sure how to continue, Median seems like $O(log$(amount of postal codes)$)$ to me since the mailboxes are in an AVL tree, so we can keep track of how many mailboxes we got, if number of mailboxes is uneven, the median is at the root, else we can find the heavier subtree and claim the median is the mean of the root and the root of said subtree, yet I'm not sure that works.

About $max$ and $howmany$, I still can't think of a solution that yields anything better than $O(n)$ where $n=$number of postal codes so far.

What would be some efficient data structure for my situation?

# Answer
> 2 votes
Your idea of using a tree of tree representation seems good. Let $n$ be the current number of postal codes and $m$ be the current maximum number of mailboxes in any postal code. Then the `insert` and `delete` implementation takes $O(\log n + \log m) = O(\log nm)$.

To implement `median`, you can make the mailbox tree of each postal code to be an order statistic tree. This will give you a bound of $O(\log nm)$ running-time.

To implement `max`, first augment each postal code node $z$, so it will store the current maximum mailbox number of its mailbox tree as $z.max$. Also, let $z.maxT$ be a pointer to the node that has the largest $max$ value in $z$'s subtree. Note that it's possible for $z.maxT$ be equal to $z$. The $maxT$ of each nodes must be updated accordingly after every `insert` and `delete`. Now, find $z\_1$. As you do the search, check the $max$ attribute of all nodes $z$ in the search path such that $z\_1 \le z \le z\_2$ and remember the node $z\_1'$ with the maximum $max$ attribute. Next, find $z\_2$ similarly to also find $z'\_2$. Finally, compare the $max$ attributes of $z\_1'$, $z\_1.right.maxT$, $z\_2'$, and $z\_2.left.maxT$ to find the overall maximum in the range $\[z\_1, z\_2\]$. The $left$ and $right$ attributes are pointers to the left and right child of a node. Since this procedure performs 2 searches in you postal code tree, it takes $O(\log n)$.

As for `howmany`, the only idea I have to prevent checking all postal codes is to create another AVL tree such that the key of each node is a number $m'$ representing the number of mailboxes and the value of the node is the number of postal codes with $m'$ mailboxes. Think of this as a reverse look-up map, such that given a number of mailboxes, it returns the number of postal codes that have such mailboxes. In the worst-case, each postal code will have different number mailboxes, so the size of this tree is $n$. Performing a `howmany` operation is just a search in the tree, which takes $O(\log n)$ time. However, an `insert` or `delete` operation will requires adding/deleting/updating of this tree, which also incurs an additional $O(\log n)$ time to `insert` and `delete`. But since its just an additive increase, it does not affect the overall asymptotic running-time of the two operations.

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


# Question
Title: How to calculate the dimension of a convex polyhedron?
A convex polyhedron can be represented by a set of linear inequalities. If the inequalities involve $n$ variables, then the polyhedron can be $n$-dimensional, but it can also be of a smaller dimension - in case some of the inequalities in fact define equalities. As a simple example, the following inequalities:

$$x\_1 \geq 0, x\_2\geq 0, x\_3 \geq 0\\ x\_1 \leq 1, x\_2\leq 1, x\_3 \leq 1 $$

define a 3-dimensional polyhedron (a cube). But if the last inequality is changed to $x\_3 \leq 0$ then the polyhedron becomes 2-dimensional (a square).

What is an algorithm for determining the dimension of a polyhedron given by a set of linear inequalities?

EDIT: By "convex polyhedron" I meant any object that can be represented by the intersection of a finite number of half-spaces (i.e., conjunction of finitely many linear inequalities).

# Answer
While there are probably much more efficient approaches, the following method can be used to compute the dimension in polynomial time, and is not too complicated.

## Implicit inequalities

The dimension of a polyhedron $P$ is defined as the dimension of its affine hull, i.e. $\dim P := \dim \mathrm{aff}(P)$.

Let $a^i x \leq b\_i$ for $i\in M$ be the linear inequalities that compose the system $A x\leq b$ defining $P$. An inequality $a^i x \leq b\_i$ is called an *implicit inequality* of this system if $a^i x = b\_i$ for all $x$ such that $A x\leq b$. Let $A^= x\leq b^=$ denote the subsystem of $Ax\leq b$ that consists only of the implicit inequalities in $Ax\leq b$. Now, we have the folllowing theorem:

> Let $P = \\{x\in \mathbb{R}^n \mid Ax\leq b\\}$ be a nonempty1 polyhedron. Then, $\mathrm{aff}(P) = \\{x \mid A^= x= b^=\\} = \\{x \mid A^= x\leq b^=\\}$. Additionally, $\dim P = n - \mathrm{rank}\ A^=$.

(see Theorem 3.17 from *Integer Programming* by Conforti, Cornuéjols, and Zambelli. Chapter 3.8 contains additional examples for computing the dimension by hand)

So, to compute the dimension of $P$, we first find all implicit inequalities to obtain $A^=$, and then compute the rank of $A^=$. The latter is easy to do, but the first can be rather complicated to do in general (although it is often doable 'by hand' for well structured cases).

## Finding implicit inequalities via linear programming

Note that an inequality $a^i x \leq b\_i$ is implicit if and only if the hyperplane $a^i x = b\_i$ (i.e. the 'border' of the halfspace defined by the inequality) contains $P$. We can determine whether this is the case by solving a pair of linear programs (thanks to @plop for pointing this out). The inequality $a^i x \leq b\_i$ is implicit if and only if

$$\max \\{a^i x \mid Ax\leq b\\} = \min \\{a^i x \mid Ax\leq b\\} = b\_i,$$

or in other words when optimizing within $P$ in the directions of $a^i$ and $-a^i$ both yields the value $b\_i$.

To see why this is true, first note that if either of the results of these programs give a value other than $b\_i$, we have found some $x\in P$ with $a^i x \neq b^i$, so the inequality is not implicit2.

For the other implication, any point $x'\in P$ that lies outside the hyperplane $a^i x =b\_i$ lies inside the hyperplane $a^i x = b'\_i$ for some $b'\_i\neq b\_i$. If $b'\_i \< b\_i$, then $\min \\{a^i x \mid Ax\leq b\\} \leq a^i x' = b'\_i \ b\_i$, then $\max \\{a^i x \mid Ax\leq b\\} \> b\_i$. So at least one of the linear programs gives a value unequal to $b\_i$ if $a^i x \leq b$ is not implicit.

## The algorithm

So, a possible algorithm for finding the dimension of $P$ in $\mathbb{R}^n$ when given by a system of $m$ inequalities is

1. Solve $2m$ linear programs to find the implicit inequalities and $A^=$.
2. Compute the rank $r$ of $A^=$, and return $n-r$.

Linear programs can be solved in polynomial time via e.g. the interior point method (although the simplex method is much faster in practice), and the rank of a matrix can be computed in polynomial time via Gaussian elimination. So, the dimension of a polyhedron can be computed in polynomial time.

As I mentioned earlier, there are probably much better approaches than what I suggest here. The suggestions offered by @plop in the comments look promising and I recommend anyone looking for something better than what I'm suggesting here to follow them through, but I will end my answer here, it is already long enough.

---

(The first part of this answer is taken from these slides by Rudi Pendavingh , page 8)

---

1: If $P$ is empty, then its dimension is $0$. Additionally, we can test whether $P$ is empty via linear programming. So, we can and I will assume that $P$ is non-empty for the remainder of this answer.
2: It may happen that the minimization and maximization program give the same value, but a different one than $b\_i$. (Try to think of an example!) In this case, the inequality must be *redundant*: it can be removed from the system without changing $P$.
> 5 votes

# Answer
I'd point to Section 8.3 of Fukuda's lecture notes for this topic. (Long story short, the dimension of a polyhedron that lives in $d$ dimensions can be computed via $d$ linear programs.)
> 2 votes

---
Tags: computational-geometry, linear-programming
---


title: prove an inequality on binary tree

text:
# Question
Title: prove an inequality on binary tree
Let $\mathcal{T}\_n$ be the set of ordered binary trees that have n leaves.

$d\_T(v)$ means the node $v$'s depth in the tree T.

Prove: for any $T\in \mathcal{T}\_n$ , for any $\\{c\_1,c\_2,...c\_n\\}$ , $c\_i \>0$ , $S=\sum\_i c\_i$

$$ -\sum\_{i=1}^n(c\_i\cdot\log\_2(c\_i/S)) \le \sum\_{i=1}^{n} (c\_i\cdot d\_T(v\_i)) $$

$v\_i$ means the i-th leaf in tree T.

---

My primary thought:

Since it has log2, so maybe 2^x can be a direction. Then 2 leaves have the same parent, their depth are the same. $2^{-depth1} + 2^{-depth} = 2^{-parent's depth}$

# Answer
> 2 votes
Gibbs'inequality implies that $$-\sum \_{i=1}^{n}p\_{i}\log p\_{i}\leq -\sum \_{i=1}^{n}p\_{i}\log q\_{i}$$ if $p\_i\ge0$, $q\_i\ge0$, $\sum \_{i=1}^{n}p\_{i}=1$ and $\sum \_{i=1}^{n}q\_{i}\le1$.

---

Let $T$ be a binary tree with $n$ leaves $v\_1, \cdots, v\_n$ and $q\_i=2^{-d\_T(v\_i)}$. Let $p\_i=c\_i/S$. It is obvious that

1. $p\_i\ge0$ and $\sum \_{i=1}^{n}p\_{i}=1$,
2. $q\_i\ge0$ and $\sum \_{i=1}^{n}q\_{i}\le1$,

except that last inequality.

**Claim**: $\sum\_{i=1}^{n} 2^{-d\_T(v\_i)}\le 1$.
**Proof**: This is immediate from the recursive nature of a binary tree, as indicated by the thought at the end of the question.

Now we can obtain the inequality at the start of this answer. It is none other than the wanted inequality in the question.

---
Tags: trees, binary-trees
---


# Question
Title: Find the largest MinHeap subtree in a given Tree
We are given a rooted tree $T$ of distinct Natural numbers. The goal is to find the largest subtree of $T$ that has MinHeap property. In fact, we want to calculate the largest subset $S$ of nodes, in a way that all nodes in $S$ have a common ancestor in $S$, and any ancestor of $n \in S$ that appeared in $S$ has a smaller value than $n$.

I can solve this problem by DP in $O(n^2)$ time, but I want to know if there is an algorithm to solve it in $O(n \log n)$ time?

For the $O(n^2)$ solution we can use the $DP$ technique. First of all, we maintain a sorted array of nodes, named $nums\[n\]$, then we define the array $DP\[n\]\[n\]$.

$DP\[i\]\[j\]$ maintains the solution for the subtree rooted by $i$, such that the biggest number in the solution is less than or equal to $nums\[j\]$. In this manner, we can dynamically full the DP by traversing the tree from bottom to top.

# Answer
> 2 votes
I think this can be done quite easily in linear time: a heap is an almost complete tree that satisfies the heap property.

An almost complete tree is one of the following:

* a leaf (a single node);
* a node with a left child that is a single node and no right child;
* a node with a left child $\ell$ of height $h\_{\ell}$ and a right child $r$ of height $h\_r$ such that one of the following is true:
    + $\ell$ and $r$ are both perfect trees and $h\_{\ell} -1 \leqslant h\_r \leqslant h\_{\ell}$;
    + $\ell$ is a perfect tree and $r$ is an almost complete tree and $h\_r = h\_{\ell}$;
    + $r$ is a perfect tree and $\ell$ is an almost complete tree and $h\_r = h\_{\ell} -1$.

Now you can compute recursively, for each node of the tree:

* its size;
* its height;
* whether it is perfect or not;
* whether it is almost complete or not;
* whether it verifies the heap property or not.

For a given node, if you know those informations for its children, you can compute those informations for the node in constant time. You can also keep track of the biggest subtree that is a min-heap. All this is done in linear time.

# Answer
> 1 votes
Perform a level order traversal of $T$, and store the visited nodes in an array $A$.

Let $S$ be an array such that $S\[i\]$ is the size of the min-heap rooted at node $A\[i\]$. Initially the values of all indices is 1. This implies that initially, there are $n$ individual min-heap ordered subtree. These subtrees will be merged later when possible to obtain larger subtrees. This in effect increases the value stored in the corresponding indices of $S$.

Let $s\_{max}$ be the index of $S$ that contains the largest value. Initially $s\_{max} = -1$.

Iterate over the contents of $A$ in reverse. This guarantees that nodes are accessed from the bottom to top. For each node $A\[i\]$, check each of its children. If child $A\[j\] \gt A\[i\]$, then it is possible to merge the subtree rooted at node $A\[j\]$ as child of node $A\[i\]$. This means that the size of subtree rooted at $A\[j\]$ must be added to the size of the subtree rooted at $A\[i\]$, so add $S\[j\]$ to $S\[i\]$. Update $s\_{max}$ when necessary.

Once the iteration is done, use the contents of the arrays and $s\_{max}$ to construct the largest min-heap ordered subtree of $T$.

The running-time will be $O(n)$ for the traversal. As noted in the comment, the iteration basically checks the children of all nodes, which amounts to checking all the child links in the tree. Since there are $n-1$ child links in a tree with $n$ nodes and checking a child takes $O(1)$ time, the entire iteration takes $O(n)$ time. Construction of the subtree is at most the cost of the iteration. The entire procedure therefore, takes $O(n)$ time.

---
Tags: algorithms, dynamic-programming, trees, heaps
---


# Question
Title: Which algorithm would be most suitable for finding a minimum subgraph that connects all vertices in a graph and has the smallest weight?
Which algorithm would be most suitable Kruskal, Prims or Steiner tree algorithm ?

# Answer
If you are talking about edge weights, that is the minimum spanning tree problem. You can use either Prim or Kruskal. Practically, Prim is probably easier to implement and faster.
> 0 votes

---
Tags: algorithms, graphs, artificial-intelligence
---


# Question
Title: How is the lookahead set computed for the Earley algorithm?
I read the dissertation \[1\] and the paper \[2\], but I'm not sure how to compute $H\_{k}$.

$H\_{k}$ is defined as:

$$H\_{k}(\gamma) = \\{ \alpha | \alpha \text{ is terminal,} |\alpha| = k \text{ and } \exists{\beta} \text{ such that } \gamma \overset{\*}{\Rightarrow} \alpha\beta \\}$$

The operation $\overset{\*}{\Rightarrow}$ seems to be roughly defined as a recursive application of $\Rightarrow$:

Is really the goal here to generate every possible string of length $k$ reachable from the production rule?

Note: Although there are some other sources \[3\] stating the lookahead may not be necessary, I'm still curious to understand how it was initially intended to be computed.

1. An efficient context-free parsing algorithm by Jay Earley (1968)
2. An efficient context-free parsing algorithm by Jay Earley (CACM 1970)
3. Practical Earley Parsing by John Ayock and R. Nigel Horspool (The Computer Journal vol45 no6 2002)

# Answer
The intention is to generate every reachable $k$-length terminal prefix reachable from $\gamma$, which is a much less daunting task than generating every possible derivation. You can do it with a simple least fixed-point algorithm.

As indicated, in practice this computation is unnecessary. It reduces the number of alternatives that have to be explored, but they will soon get dropped anyway and the speed-up is not considered sufficient to justify the cost of computing the lookahead sets.
> 1 votes

---
Tags: parsers
---


# Question
Title: On the language of Turing machines that accepts 1 but does not accept 0
I need to find the find the minimal class $\mathcal{L}$ belongs to where

$$\mathcal{L} = \\{\langle M \rangle: M \text{ is a TM that accepts 1 but does not accept 0}\\}.$$

I think I can prove that $\mathcal{L}\in \overline{\mathsf{RE}\cup\mathsf{co{-}RE}}$ using 2 mapping reductions from $\text{ACC}$ ($M$ is TM that accept $w$) and $\overline{\text{ACC}}$ respectively. But I also know that

$$\hat{L}=\\{ \langle M\_1,w\_1,M\_2,w\_2\rangle : w\_1 \in L(M\_1) \wedge w\_2 \notin L(M\_2)\\}\in \overline{\mathsf{RE}\cup\mathsf{co{-}RE}}$$

My question is whether it is possible to apply somehow reduction from $\hat{L}$ to $\mathcal{L}$ ? or am I missing something...

# Answer
Yes, we can reduce $\hat L$ to $\mathcal L$ as you suspected. Imagine we replace $1$ by $w\_1$ and $0$ by $w\_2$.

---

Let $s=\langle M\_1,w\_1,M\_2,w\_2\rangle$, where $M\_1, M\_2$ are Turing machines and $w\_1, w\_2$ are strings. Construct Turing machine $T\_s$ such that given input $w$, $T\_s$ will check whether $w$ is $0$ or $1$.

* if $w=0$, $T\_s$ will simulate $M\_2$ with input $w\_2$ exactly.
* if $w=1$, $T\_s$ will simulate $M\_1$ with input $w\_1$ exactly.
* if $w$ is not $0$ nor $1$, $T\_s$ will accept immediately.

If $s\in\hat L$, it is clear that $T\_s\in\mathcal L$. If $s\not\in\hat L$, it is clear that $T\_s\not\in\mathcal L$.

The map $t$ that maps a string $s$

* to $\langle T\_s\rangle$ if $s$ is the encoding of some $M\_1, w\_1, M\_2, w\_2$ and
* to $\langle\text{acc}\rangle$ otherwise, where $\text{acc}$ is the Turing machine that just accepts upon every input (hence, $\langle\text{acc}\rangle\not\in\mathcal L\\,$).

is a Turing reduction from $\hat L$ to $\mathcal L$.
> 1 votes

---
Tags: turing-machines, reductions, halting-problem, recursively-enumerable
---


# Question
Title: Use NFA to express the left quotient of the language of a DFA with respect to the language of another DFA
Let $\Sigma = \\{a,b\\}$, $L\_1,L\_2\subseteq \Sigma^\*.$

$L\_1 \triangleleft L\_2 = \\{w\in \Sigma^\* \mid \exists v\in L\_1, vw \in L\_2\\}$

For clarity, here is python code that shows $L\_3 \triangleleft L\_4$:

```
answer = set()
L3 = {"aa", "b", "bb"}
L4 = {"a", "b", "ab", "bb", "aaa", "bbab"}
for c in L3:
    for c1 in L4:
        if c1.startswith(c):
            answer.add(c1.removeprefix(c))
print(answer)
# output: {'', 'a', 'ab', 'b', 'bab'}

```

$\mathcal{L(A\_1)}$ means the language accepted by DFA $\mathcal{A\_1}$.

Let $\mathcal{A\_1} = \\{Q\_1, \Sigma, \delta\_1,q\_{1,0},F\_1\\}$, $\mathcal{A\_2}= \\{Q\_2, \Sigma, \delta\_2,q\_{2,0},F\_2\\}$ be 2 DFAs, how to write an NFA to accept $\mathcal{L(A\_1)}\triangleleft\mathcal{L(A\_2)}$?

# Answer
#### An NFA with $\epsilon$-moves

Here is an NFA with $\epsilon$-moves $\mathcal M=((Q\_1\times Q\_2)\sqcup Q\_2, \Sigma, \delta, (q\_{1,0},q\_{2,0}), F\_2)$, where $\delta$ is defined as below.
$\quad\delta((r,s), \epsilon)=\\{(\delta\_1(r, \sigma), \delta\_2(s, \sigma))\mid \sigma\in\Sigma\\}\quad\forall r\in Q\_1\setminus F\_1,\\, \forall s\in Q\_2$,
$\quad\delta((r,s), \epsilon)=\\{(\delta\_1(r, \sigma), \delta\_2(s, \sigma))\mid \sigma\in\Sigma\\}\sqcup\\{s\\}\quad\forall r\in F\_1,\\, \forall s\in Q\_2$,
$\quad\delta(s,\sigma)=\\{\delta\_2(s,\sigma)\\}\quad\forall s\in Q\_2,\ \forall\sigma\in\Sigma.$

In plain words, upon an input word $w$, $\mathcal M$ will simulate $\mathcal A\_1$ and $\mathcal A\_2$ in parallel, as if both DFAs are given the same arbitrary input. When the simulation of $\mathcal A\_1$ goes into one of its final states, $\mathcal M$ will optionally switch to continue the simulation of $\mathcal A\_2$ only and with input $w$. $\mathcal M$ accepts when the lonely simulation of $\mathcal A\_2$ ends up at one of its final states.

We can prove that $\mathcal M$ accepts $\mathcal{L(A\_1)}◃\mathcal{L(A\_2)}$ routinely.

#### Also as an NFA

Because of the equivalence of NFA with $\epsilon$-moves to NFA, the construction above can be transformed methodically to build an equivalent NFA, which is what is wanted in the question.

#### What if $\mathcal L(\mathcal A\_1)$ is replaced by any language?

In fact, we can build an NFA with $\epsilon$-moves for $$\mathcal D\triangleleft \mathcal L(\mathcal A\_2) = \\{w\in \Sigma^\* \mid \exists v\in {\mathcal D},\ vw \in\mathcal L(\mathcal A\_2)\\}$$ where $\mathcal D$ is *any* language, i.e., it can be non-regular or even non-computable.

Assume $\mathcal D$ is nonempty. Let $Q\_{\mathcal D}=\\{\delta(q\_{2,0}, v)\in Q\_2\mid v\in {\mathcal D}\\}$.
Define $\mathcal N=(Q\sqcup\\{q\_{\text{new}}\\}, \Sigma, \mu, q\_{\text{new}}, F\_2)$, where $\mu$ is defined below.
$\quad\mu(q\_{\text{new}}, \epsilon)=Q\_{\mathcal D}$
$\quad\mu(q, \sigma)=\\{\delta(q, \sigma)\\}\quad\forall q\in Q, \forall\sigma\in\Sigma$

Thanks to $Q\_{\mathcal D}$, $\mathcal N$ looks even simpler than $\mathcal M$.

We have $\mathcal L(\mathcal N)={\mathcal D}\triangleleft {\mathcal L}(\mathcal A\_2)$. In particular, the right-hand side is a regular language.
> 3 votes

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


# Question
Title: Build an automaton from a given automaton to prove regularity of more complex strings
let $L$ be a regular language, and let $A=\\{\Sigma, Q, q\_0, F, \delta\\}$ be a DFA such that $L = L(A)$.

I need to prove that $$L\_p=\\{xy\in\Sigma^\*\mid\delta(q\_0, y)=p\text{ and } \delta(p, x)\in F\\}$$ is regular for every $p\in Q$ by defining an automaton $A\_p$.

I tried to define it like so $$A\_p=\\{\Sigma, Q\times Q, (p, q\_0), F\times \\{p\\}, \delta\_p\\}$$ where $\delta\_p$ is defined like so $$ \delta\_p((q\_1, q\_2), \sigma) = (\delta(q\_1, \sigma), q\_2)\text{ if }q\_1 \not\in F, \\ \delta\_p((q\_1, q\_2), \sigma) = (q\_1, \delta(q\_2, \sigma))\text{ if }q\_1 \in F. $$ But then I have a problem where $x=uv$, $\delta(p, u)\in F$ and $\delta(p, x)\in F$.

I thought maybe I define $A\_p$ as a non-deterministic automaton and then $$\delta\_p((q\_1, q\_2), \sigma) = \\{(\delta(q\_1, \sigma), q\_2), (q\_1, \delta(q\_2, \sigma))\\}.$$ However, word $z=uwv$ where $$\delta\_p((p, q\_0), u) = (p\_1, q\_0) \Longrightarrow \delta\_p((p\_1, q\_0), w) = (p\_1, p) \\ \Longrightarrow \delta\_p((p\_1, p), v) = (p\_2, p), p\_2\in F\times \\{p\\}$$ is accepted while it shouldn't be part of $L\_p$

# Answer
> 1 votes
Since how a word $w$ is recognized as a member of $L\_p$ depends on a successful choice of partition of $w$ into a prefix ($x$) and a suffix ($y$) among many possible partitions, a DFA with $\epsilon$-moves that accepts $L\_p$ should be easier to build than a DFA.

To distinguish whether a symbol is used as in $x$ or in $y$, we can employ two copies of $A$, one copy for reading $x$ and one copy for reading $y$. When the state after reading some $x$ is one of the final states of the first copy, switch to the initial state $q\_0$ of the second copy optionally, continuing reading the remaining $y$. At the end of reading all input, accept if the second copy is at state $p$.

Two copies of $A$ can be built on the cartesian product $Q\times \\{1,2\\}$, where the copy index $1$ and $2$ indicates which copy of $A$.

Here is a DFA with $\epsilon$-moves that accepts $L\_p$.
$D\_p=\\{\Sigma, Q\times\\{1,2\\}, (p, 1), \\{(p,2)\\}, \mu\\}$, where $\mu$ is defined below. $\quad\mu((q,1), \sigma) = (\delta(q, \sigma), 1)\quad\forall q \in Q,\ \sigma\in\Sigma,$
$\quad\mu((q,2), \sigma) = (\delta(q, \sigma), 2)\quad\forall q \in Q,\ \sigma\in\Sigma,$
$\quad\mu((f,1), \epsilon) = (q\_0, 2)\quad\forall f \in F.$
Note that when the copy index is fixed, $D\_p$ behaves exactly as $A$.

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


# Question
Title: Context free grammar for a language that is a complement of another
> Create a context free grammar for L. $$ L=\\{a^nb^mc^k | n+m \neq k\\} $$

First I tried to create a CNF for a language that accepts strings in which $n+m = k$. I got this:

$$ S \rightarrow aAc $$ $$ A \rightarrow aAc \mid B $$ $$ B \rightarrow bBc \mid \epsilon $$ to create a CNF for $L$, I wanted to add a new start state that basically adds another symbol to the strings accepted by the CNF above. I can add as and cs with no problem but don't know how to add bs since b is in the middle.

# Answer
I would like to add that the language $L\_0=\\{a^n b^m c^k\\;|\\;n+m=k\\}$ is the deterministic context-free language, and a DPDA can be constructed recognizing $L\_0$ by the final state. Then we can use the closure property of DCFLs under the complement and obtain a DPDA for $L$ swapping the final and non-final states in the initial DPDA (with a little mess with the trap state).

The main construction is rather straightforward, but it is refined in the two following aspects:

1. The new stack symbol $A$ is introduced, marking the very first occurrence of either $a$ or (if $a$ block is empty) $b$. If we use the single stack symbol $B$, then we would also have a DPDA (having an $\epsilon$-transition to the state $Q\_4$ by the stack symbol $Z\_0$), but that DPDA is not so convenient to construct a complement, since it contains $\varepsilon$-transitions between the final and the non-final state. The DPDA below has no such transitions, distinguishing the last pop operation.
2. We omitted most transitions to the trap state $T$, because these transitions correspond to the words not belonging to the language $a^\* b^\* c^\*$ (and the initial language $L$ is a subset of this regular language, thus these transitions kick from $L$ as well).

Now simply swap the final and non-final states and get the DPDA for the required language.  If you like to construct PDAs, this technique works rather well for recognizing complements of the deterministic languages, but since you ask not for a PDA, but for a CFG, you still have to make the PDA$\rightarrow$CFG transition. In the case considered, it is again quite straightforward (and gives almost the same result as the direct CFG construction): all what you need is to consider the stored $A$ and $B$ stack symbols as the nonterminals which derive a single letter $c$ if popped and $\varepsilon$ otherwise.

Btw, the PDAs above allow $n$, $m$, and $k$ to be zeros.
> 6 votes

# Answer
There's no procedure for creating a context-free grammar for the complement of a context-free language, because the complement of a context-free language might not be context-free, and the question of whether a language is context-free is not decidable.

Of course, particular context-free languages (and some languages which are not context-free) do have context-free complements, and this is an example of such a language. Indeed, as @Tonita observes in her excellent answer, $L^C$ is a deterministic context-free grammar, which are closed under complement. So that's not entirely a dead end.

But on the whole, it's rarely helpful to try to start with a grammar for $L$ and transform that into a grammar for $L^C$, since the latter might not even exist, and even if it dies, mechanically generating it could be a lot of work.

Here's another approach which often works for problems like this. When trying to deal with languages whose descriptions involve inequalities, it's often useful to remember that $i\ne j$ is the union of the two predicates $i\<j$ and $i\>j$, and furthermore that $i\>j$ is the same as $\exists k\>0 \mid i = j + k$. Finally, $a^{j+k} = a^ja^k$. That should be enough to quickly find the solution.
> 4 votes

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


# Question
Title: prove or give counterexample about regular language
Let $\Sigma = \\{a,b\\}$, $L\_1,L\_2\subseteq \Sigma^\*$

$L\_1 ◃ L\_2 = \\{w∈ \Sigma^\* | \exists v\in L\_1, vw \in L\_2\\}$

For any context-free language $L$, regular language $R$, whether $L \triangleleft R$ is regular language or not? How to prove or give a counterexample?

# Answer
> 1 votes
After some google && watching some videos\[1\], I think I understand this:

consider there is a $R$ as regular language. We can get its DFA=$\\{Q,\Sigma, \delta, q\_0, F\\}$, then we find all the status $q\_i$ which $q\_0$ to $q\_i$ is in $L$, take these $q\_i$ as begin. So we get a new (NFA), DFA. Which is to say, we get a regular language.

\[1\] https://www.youtube.com/watch?v=PgUB\_07N0eA

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


# Question
Title: Depth-first search (DFS) time complexity for a Red-Black Tree
If we indicate *n* as the number of nodes of a Red-Black Tree, which is the time complexity of a DFS algorithm that analyzes only the internal nodes of the Tree?

I think that the complexity is O(n), but I'm not sure because of the leaf nodes that the algorithm doesn't need to analyze.

# Answer
The number of internal nodes in a binary tree is at most $n/2$, which is still $O(n)$, therefore the time it takes to perform a DFS is still $O(n)$.

In the usual implementation of red-black trees, leaves are null nodes. Therefore, only the internal nodes have keys/elements. In this case the number of internal nodes is $n$.
> 1 votes

---
Tags: binary-search-trees, red-black-trees
---


# Question
Title: Minimum number of query to find Largest sum of a contiguous subarray
Consider this post, the problem is given an array $A\[1..n\]$. We don't have direct access to $A$, but we can query what is the sum of $A\[i..j\]$ for every interval $i..j$. We would like to find the maximum of $A\[i..j\]$ over all intervals $i..j$.

**That answer describe an algorithm that solve the problem with at most $O(n)$ query, but the question is, what is the lower bound of number queries we need to find largest continuous sub array? Can we claim that $\Omega(n)$ queries is necessary?**

# Answer
> 2 votes
At least $n$ queries are needed in the worst case.$^\*$ Consider an algorithm which receives the answer $0$ on any query. After $n-1$ queries, it learns that $\langle v^{(1)},A \rangle = \cdots = \langle v^{(n-1)},A \rangle = 0$, where $v^{(i)}$ is the vector corresponding to the $i$'th query. We can find a non-zero vector $u$ which is orthogonal to all of $v\_1,\ldots,v\_{n-1}$. Thus we could have $A = u$ or $A = -u$. We claim that an answer which is valid for $A = u$ is not valid for $A = -u$. Since the algorithm cannot tell these two cases apart, it cannot guarantee outputting a valid solution.

To prove the claim, suppose without loss of generality that $u$ contains a positive entry. Therefore any optimal solution $I$ for $u$ satisfies $\sum\_{i \in I} u\_i \> 0$. In contrast, $\sum\_{i \in I} (-u)\_i \< 0$. We now distinguish between two cases:

* Case 1: Some entry of $u$ is non-positive. In this case, the optimal solution $J$ for $-u$ satisfies $\sum\_{j \in J} (-u)\_j \geq 0$, and so we are done.
* Case 2: All entries of $u$ are positive. **If $n \> 1$,** this means that the unique optimal solution for $u$ is $\\{1,\ldots,n\\}$, whereas all optimal solutions of $u$ are either singletons or the empty interval, if we allow it. **If $n = 1$,** then this argument breaks unless we allow the empty interval as a solution. Indeed, if $n = 1$ and we don't allow the empty interval, then no queries are needed. This is the reason for the asterisk above.

---

A similar approach shows that $n$ queries are needed *always*. Suppose that after $n-1$ queries, the algorithm learns that $\langle v^{(i)}, A \rangle = c\_i$ for $i = 1,\ldots,n-1$. The space of solutions to these equations includes a line $\alpha u + w$ (here $\alpha$ is the parameter), where $u \neq 0$. For large positive $\alpha$, any optimal solution for $\alpha u + w$ is also an optimal solution for $u$. This is since if $\sum\_{i \in I} u\_i \> \sum\_{j \in J} u\_j$ then $$ \sum\_{i \in I} (\alpha u\_i + w\_i) - \sum\_{j \in J} (\alpha u\_j + w\_j) = \alpha \left(\sum\_{i \in I} u\_i - \sum\_{j \in J} u\_j\right) + \left(\sum\_{i \in I} w\_i - \sum\_{j \in J} w\_j\right), $$ which is positive for large enough $\alpha$, say $\alpha \> \alpha\_{I,J}$. The claim follows since there are only finitely many pairs $I,J$. Similarly, for large negative $\alpha$, any optimal solution for $\alpha u + w$ is also an optimal solution for $-u$. Above we have shown that an optimal solution for $u$ cannot be an optimal solution for $-u$ (unless $n = 1$ and we do not allow the empty interval).

# Answer
> 2 votes
Assume that you perform less than $n$ queries, so obtain less than $n$ sums. The corresponding system of equations so obtained is indeterminate, leaving room for degrees of freedom to move the maximum at different places.

E.g. for $n=3$, assume we query $a+b=5$ and $b+c=4$. Then $a=5-b$, $c=4-b$ and $a+b+c=9-b$, with $b$ free. So with large positive $b$, the optimal sequence would be $b$ alone, and with large negative $b$, it would be $a+b+c$.

# Answer
> 1 votes
For every 1 ≤ j \< n: We must make a query ending in $A\_j$ otherwise we cannot determine the largest sum.

Reason: Assume we determined all subarray sums for all subarrays not ending in $A\_j$. If we increase $A\_j$ by a huge amount and decrease $A\_{j+1}$ by the same amount, then the largest subarray sum is for a subarray ending in $A\_j$. But if we decrease $A\_j$ by a huge amount and increases $A\_{j+1}$ by the same amount, the largest subarray sum is NOT for a subarray ending in $A\_j$. Both actions leave all the subarray sums that we queried unchanged, so we cannot determine the largest subarray sum without an interval ending at $A\_j$.

We also need an interval containing $A\_n$, because $A\_n$_ could be very large or very small so it cannot be ignored. So n intervals are needed. And the intervals A\[1..1\], A\[1..2\], ..., A\[1..n\] are sufficient because we can calculate all subarray sums from these. Or we could take A\[1..1\], A\[2..2\], ..., A\[n..n\].

---
Tags: algorithms
---


title: Serializing Chess Games

text:
# Question
Title: Serializing Chess Games
This is an open question I have been thinking about lately. Let's say we are black player and we play two "harmless" moves A and B. We assume it won't change anything if we play A - B or B - A. So all chess games having the exact same position and with an option A - B or B - A could end up the same. So the question is: Can chess moves be serialized like transactions in databases?

So could we compress the chess games based on similarities and classify them? For example using a bottom-up approach where we start with the most simple positions. We figure out the similarities when there is only two kings and one black rook, then we reuse those simple games in the more complex ones having the exact position …

Using that new technique, could we theoretically reduce the number of possible chess games to a "lower" upper bound?

# Answer
> 1 votes
Most chess engines already use a technique like this: they use transposition tables to remember positions that have already been evaluated. Since A-B and B-A both lead to the same position, during search that position will only be evaluated once and then its evaluation will be remembered, rather than evaluating the same position twice.

The sheer number of possible positions is still ridiculously large, so there is no way to enumerate them all in any reasonable amount of time. Instead, chess engines use heuristics and search techniques to identify which positions are promising and worth examining in detail, and prune the search space so they don't have to examine all possible positions. Transposition tables don't solve this problem.

---

Related: Model checking uses partial order reduction, which addresses a somewhat similar problem, though there are also important differences.

---
Tags: complexity-theory
---