# Question
Title: What is meant by a single-threaded kernel?
I was looking at this course but I cannot seem to understand what is meant by the term *"single-threaded kernel"*.

Does it mean that:

1. only a single kernel thread is made available by the OS?
2. only a single kernel thread can be executed at one time?

or is there some other interpretation?

# Answer
> 2 votes
I will be adding to nir shahar's answer.

A single-threaded kernel is essentially a kernel that processes only one thread at a time. We can have multiple kernel threads, but only one can get executed at any given point in time. This can be achieved by some scheduling procedure on the kernel threads.

But is this the same thing as having only one kernel thread (and using the *many-to-one* model) as even multiple threads have to be executed sequentially?

**NO!** A blocking call made on a *many-to-one* model blocks all other processes mapped to that kernel thread. Having a *one-to-one* model will allow for other processes to run even if one process executes a blocking call.

This does come at a cost. The overheads of creating and managing multiple kernel threads are somewhat expensive, but it all depends on your usage.

# Answer
> 1 votes
It literally means that the kernel runs only on one core.

Different threads can be run on multiple cpu cores, and thus a single-threaded kernel is a kernel that runs only in one core

---
Tags: operating-systems, os-kernel
---


title: Manipulating stack pointer in assembly

text:
# Question
Title: Manipulating stack pointer in assembly
I have written an assembly program to store digits in a stack. And to print the digits I have used

```
loop2:
mov ah,2
int 21h
sub cl,1
jnz loop2

```

But this would only print them in reverse order as the SP is pointing to the last element, Now, I have a very simple yet very interesting question, I was very curious to know If I were to print it in the same way it was entered, how would I do that? I could use another stack but it would be quite complicated.

# Answer
A stack is a *last-in-first-out* structure. This causes the reverse order you experience. What you need is a *first-in-first-out* structure, i.e., a queue.

This way or another, the stack in x86 is just a region in the memory you can access directly. Instead of **popping** each digit, initialize BP to point at the bottom of your stack (the first digit), then print it, and then advance BP to the next digit (i.e., decrease BP since the stack grows towards lower addresses). At the end of the print loop, just clean the stack by popping everything out, or by changing SP directly.

```
MOV BP, SP    ; init BP to the first digit

... <push digits> , <init CX> ...

PrintLoop:
   MOV DX, [BP]
   MOV AH, 2
   INT 21h            ; print

   SUB BP, 2          ; assuming each digit is a word
   LOOP PrintLoop     ; Loop according to CX

MOV SP, <...>         ; restore stack / "pop" everything

```
> 1 votes

---
Tags: computer-architecture, assembly
---


# Question
Title: Dividing EX stage of a pipeline into EX1 and EX2 stages
There is this problem about pipelining that does not have an answer, and I'm wondering what the answer could be:

> In the five stage pipeline with forwarding support to EX, the first operand of ALU comes from 3-to-1 input multiplexer. As the memory latency increases, MEM stage now takes 2 cycles (from 1 cycle) To adjust the pipeline for the latency increase, the MEM stage becomes MEM1 and MEM2.
>
> * How should the input mux for the ALU be changed, if forwarding to EX needs to be fully supported?
> * Even with the full forwarding to EX, show an example where the number of stall cycles increase in the new pipeline compared to the old one.

I don't get what it means to divide MEM stage with MEM1 and MEM2. Why would any additional input be necessary?

# Answer
This is multi-cycle processor, where each stage takes a single clock cycle. The text suggest that the new MEM stage should take 2 clock cycles. Then, it can be seen as splitting this 2-cycle stage into 2 separate 1-cycle stages which we can call MEM1 and MEM2 respectively.

There is no new input. You only need to make sure that the "right" input travels along the pipeline and reaches the right stage at every time.
> 0 votes

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


# Question
Title: Is there any guarantee in asynchronous systems?
We know that in an asynchronous system, no assumptions about process execution speeds or message delivery times are made. My question is: can we present any guarantee in asynchronous systems?

Some examples of the guarantees that I'm looking for are:

1. Consider two processes $p$ and $q$. $p$ sends a message an infinite number of times to $q$. $q$ delivers the message finally if two processes are correct (a process that never crashes is said to be correct).
2. If 1. is correct, then: no edge-cut in the network persists forever between the correct processes.

# Answer
> 1 votes
Your question is somewhat unclear. In asynchronous systems we normally assume that any message will eventually be delivered after some finite time. It if perfectly feasible to write an algorithm that sends infinitly many messages:

```
While(true):
   Send a message to p;
   If received message form p do <...>

```

This is valid and will indeed cause infinite number of message exchange. But the timings of these messages are unknown.

I am not sure what you mean at your second point. If there are no link-failures, all edge-cuts remain alive. As long as the processors are correct, the link will be utilized infinitely often.

---
Tags: distributed-systems, computer-networks
---


title: Synchronization in Distributed Systems

text:
# Question
Title: Synchronization in Distributed Systems
If there is no global clock in Distributed systems , then what is the solution for synchronization in DS ? Also , no global clock in DS is a direct consequence of the fact that the only communication is by sending messages through a network. Can someone please explain how the communication via message passing has resulted in no global clock ?

# Answer
It is the other way around. We first *model* the system in a certain way, for instance we *assume* that there is a (or is no) global clock, or we *assume* that messages arrive or may fail, etc. Once we fix our assumptions, we can ask questions about the system we have characterized: does it allow computations of certain types or not?

For instance, if we *assume* all the nodes are identical and ask whether we can break symmetry, then the answer is **no** (in certain cases). If we assume there is no global clock, and ask whether the parties can synchronize, then probably the answer is no (it depends on what you mean by "synchronize"). However, can the system solve tasks without a global clock? Sure! there are plenty asynchronous algorithms that perform a large variety of tasks, like broadcasting, finding a leader, or computing a spanning tree.

So, communication via message-passing does not imply no global clock. These two are independent assumptions that characterize the system. Under these assumptions certain tasks are possible/fast and other might be impossible/slow.
> 3 votes

---
Tags: distributed-systems, synchronization
---


# Question
Title: Is Vertex Cover of size $k >100$ polynomial time solvable?
I know that when we want to find out if Vertex Cover of size $k$ when $k \leq C$, belongs to P or not (when $C$ is some constant), we actually can find algorithm with polynomial time complexity (in the algorithm we iterate over subsets $V'$ such that $|V'|=C$). But what about $k \geq C$?

I personally think it's not in P because $k$ can be as most in size $|V|$, and therefore the time complexity is exponential, but I'm not sure if I'm right (maybe it's unknown?)

# Answer
We don't actually iterate over subsets $V'$ of size $C$, because that would be running in time $\Theta (n^k)$. While that is polynomial for fixed $k$, there is an algorithm that runs in time $O(2^k \cdot n)$, which is much better.

The problem you have stated is not really very well defined, so let's try to clear it up.

The *Vertex Cover* problem is given a graph $G$ and a number $k$ and asks whether there exists a vertex cover in $G$ of **size at most $k$**. This problem is NP-complete (as long as $k$ is not a constant).

However, if you ask to find *any* vertex cover in $G$, then you can reply with $V(G)$, which has size $n$. This version is of course polynomial time solvable and uninteresting.

The answer is therefore: Vertex Cover is NP-complete. If you *fix* the bounds, however, you can solve the problem in time "polynomial" time (exponential in the bounds).
> 1 votes

---
Tags: time-complexity, vertex-cover
---


# Question
Title: Can PTAS $\epsilon$ parameter be dependent on the algorithm input?
Let A be a PTAS algorithm with time complexity $O\left(\frac{1}{\epsilon}\right)$. Let $n$ be the input of the algorithm A.

From Wikipedia:

> The running time of a PTAS is required to be polynomial in $n$ for every fixed $\epsilon$, but can be different for different $\epsilon$.

Can we define $\epsilon$ to be equal to $\frac{1}{n}$? Thus, the time complexity of A would be $O(n)$, which is polynomial in $n$, but, can $\epsilon$ be dependent on $n$?

# Answer
> 1 votes
If $A$ is an algorithm whose running time is $O(1/\epsilon)$, then if you substitute $\epsilon = 1/n$, its running time will be $O(n)$. This is a property of the particular algorithm $A$ rather than of polynomial time approximation schemes. We have absolutely no guarantee on the running time of a PTAS when $\epsilon$ is subconstant (i.e., when $\epsilon = o(1)$).

The running time of algorithms tends to depend on the input length (though it's not always the case), so I'm not convinced that $A$ really has running time $O(1/\epsilon)$.

---
Tags: algorithms, complexity-theory, time-complexity, approximation, polynomial-time
---


# Question
Title: Unrecognizability of $L(M_1) \cap L(M_2) = \emptyset$
Let's define a language $$C = \\{ \\{M\_1, M\_2\\} \mid M\_1, M\_2 \text{ are TMs s.t. } L(M\_1) \cap L(M\_2) = \emptyset \\}$$

We have to show that $C$ is unrecognizable.

I am having trouble going on about with this proof. I am trying to do this by reduction, showing that this language is unrecognizable, but I am unsure on how to reduce this problem into a simpler problem.

# Answer
Let $T$ be a Turing machine. Construct a Turing machine $T'$ that simulates $T$ on the empty input word and, when (if) the simulation ends, it accepts (regardless of the input to $T'$). Notice that $T'$ can be computed from $T$.

Pick $M\_2$ as the Turing machine that immediately halts and accepts.

Then $\\{T', M\_2\\} \in C$ iff $L(T') = \emptyset$, which happens iff $T$ does not halt on the empty input word. Therefore if $C$ were recognizable, the halting problem would be decidable (since the language of all Turing machines that halt on the empty input word is recognizable). This shows that $C$ is not recognizable.
> 3 votes

# Answer
Reduce from the acceptance problem using the following trick:

Let $M\_w$ be the turing machine that accepts if and only if its input is $w$. Then $L(M\_w)=\\{w\\}$.

Therefore, for any TM $M$ and word $w$,

\begin{matrix} \langle M,w\rangle \in ACCEPT\_{TM} &\iff\\ w\in L(M)&\iff\\ L(M)\cap \\{w\\}\neq \emptyset &\iff\\ L(M)\cap L(M\_w)\neq \emptyset &\iff\\ \langle M,M\_w\rangle \notin C &\iff\\ \langle M, M\_w\rangle \in \overline C\end{matrix}

Which means that the reduction defined by $f(\langle M,w\rangle) = \langle M, M\_w \rangle$ is a reduction from the acceptence problem to $\overline C$, and thus $C$ is undecidable (since the acceptence is not in co-RE).
> 1 votes

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


# Question
Title: Both $\overline{A_{TM}}$ and $\Sigma^*\backslash A_{TM}$ are not turing-recognizable?
if we define $A\_{TM}$ and $\overline{ A\_{TM}}$ as follows: $$ \begin{align} A\_{TM}&= \\{ \langle M,w \rangle |M \text{ is a turing machine and $M$ accepts $w$} \\}\\ \overline {A\_{TM}}&= \\{ \langle M,w \rangle |M \text{ is a turing machine and $M$ do not accepts $w$} \\}\end{align} $$ $\overline{A\_{TM}}$ and $\Sigma^\*\backslash A\_{TM}$ both are not turing-recognizeable. right?(a bit confused by the way $\overline{ A\_{TM}}$ is defined. noramly $\overline A = \Sigma^\*\backslash A$).

My reasons :

1.$\overline{A\_{TM}}$ is not reconizable because: if it was then we could run two recognizer for $\overline{A\_{TM}}$ and $A\_{TM}$ in parallel and decides $A\_{TM}$.
2. $\Sigma^\*\backslash A\_{TM}$ is not recongnizeable by fallowing lemma :
**lemma**: $L$ and $\overline L$ recognizeable **iff** $L$ is decideable.

in fact both reasones are quite the same but in second one we are considring inputs ($\langle M,w \rangle$) which are not properly formated.

# Answer
> 2 votes
Usually the second language is denoted by $A\_{\overline{TM}}$, exactly to avoid the confusion with the complement.

This is actually a common question, and it has to do with the encoding of TMs and words. When we write $\langle M,w\rangle$, we mean that we give some agreed-upon encoding of a Turing machine and a word over its alphabet. We usually don't go to much into it, but it is agreed that the encoding is simple enough so that another Turing machine can easily parse it (where easily usually means either in logarithmic space, or polynomial time, or something of the sort).

Now, intuitively, in an agreed encoding, some words represent $M,w$ such that $M$ accepts $w$, some represent $M,w$ such that $M$ does not accept $w$, and some are meaningless gibberish. When the encoding is easy to parse, we can kind of ignore this gibberish. However, it does pose a small problem when we start complementing languages.

Indeed, $\Sigma^\*\setminus A\_{TM}$ should, formally, also contain all strings that are not legal encodings. However, since determining whether an encoding is legal is easy, then it doesn't effect the recognizability or decidability of the language. You can always start by checking the legality of the encoding, and accept if the encoding is illegal.

There is another way around it, which I like: you can define the encoding such that *every* string is a legal encoding. You do that by using some encoding of your liking, and adding to it the statement that any string that is not a legal encoding is now interpreted as some fixed TM $T$ and the empty word. Then, you actually get that $A\_{\overline{TM}}=\overline{A\_{TM}}$, and the problem goes away.

# Answer
> 0 votes
$A\_{TM}\in RE$ (aka, turing recognizable), but $\overline{A\_{TM}}\notin RE$.

The proof is quite simple, assuming you know that $A\_{TM}$ is not decidable:

Look at the turing machine $M$ that given $\langle M', w\rangle$ simulates $M'$ on $w$, and accepts if and only if $M'$ accepted. for any $\langle M', w\rangle\in A\_{TM}$, $M'$ accepts $w$ and thus $M$ accepts $\langle M', w\rangle$. Therefore, $M$ recognizes $A\_{TM}$ (notice that anything which is not in $A\_{TM}$ will never get accepted in $M$), and thus $A\_{TM}\in RE$.

Since $L\in R \iff L\in RE\cup co-RE$, and we know that $A\_{TM}\notin R$ but $A\_{TM}\in RE$, then $A\_{TM}\notin co-RE$ and thus $\overline{A\_{TM}}\notin RE$.

---
Tags: turing-machines
---


# Question
Title: How to use Parallel Semaphores for Dining Philosophers Problem
I am in an intro to OS class and we are learning about mutual exclusion and semaphores. One classical problem we learned about was the dining philosophers problem. My professor touched on the different cases using simple semaphores (i.e asking the last philosopher to grab the right fork before the left while the others grab right first) however, these still violates the concurrency requirement.

He explained that these types of problems begin to show the importance of advanced synchronization and how we need more but he didn't go into details because that subject belongs to the actual Operating Systems course.

I am curious as to how you could implement AND semaphores to solve the dining philosophers problem. I did some research and could not find any great resources showing implementations using AND or monitors.

Could someone go into some detail or point me to an article/textbook that does?

# Answer
Assume we have 4 processes p\[0\], p\[1\],...,p\[3\] and 4 mutexes m\[0\],m\[1\],...m\[3\]. Now in order to solve the dining philosophers problem, we only need to make one of the philosopher (one of the processes) to take the folk (one of the mutexes) in reverse direction than the other philosophers. Note that by doing this, we are trying to avoid deadlock.

---

So in practice, we need to make all processes to follow certain implementation, except one.

All processes (philosophers) should follow this implementation:

```
while(1)
{
   down(m[(i+1) % 4]);
   down(m[i]);

   'critical section'

   up(m[i]);
   up(m[(i+1)%4]);
}

```

except one process should follow this:

```
while(1)
{
   down(m[i]);
   down(m[(i+1) % 4]);

   'critical section'

   up(m[i]);
   up(m[(i+1)%4]);
}

```

---

Note by down we mean taking the folks and by up we mean releasing the folks, and note how both implementations differ. **For example, we made one of the philosopher to take the fort (down) in reverse order than the others.**

I hope this could help.
> -1 votes

---
Tags: operating-systems, parallel-computing, concurrency, process-scheduling, synchronization
---


# Question
Title: Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$
> Consider the language $L= \\{a^n \mid n\geq 0\\} \cup \\{a^nb^n\mid n\geq 0\\}$ and the following statements.
>
> $\quad\quad\text{I. }L$ is deterministic context-free.
> $\quad\quad\text{II. }L$ is context-free but not deterministic context-free.
> $\quad\quad\text{III. }L$ is not $LL(k)$ for any $k$.
>
> Which of the above statements is/are TRUE?
>
> $\quad\quad\quad$ A. $\text{I}$ only
> $\quad\quad\quad$ B. $\text{II}$ only
> $\quad\quad\quad$ C. $\text{I}$ and $\text{III}$ only
> $\quad\quad\quad$ D. $\text{III }$ only
>
> (GATE-CS-2020)

My doubt is only regarding a part of the above question, i.e. arguing about statement $\text{III}$.

Most of my mates are arguing as :

> "Since $a^n$ for any arbitrary $n$, on just seeing $a^n$ on the input we cannot decide whether it is a part of $a^m$ or $a^mb^m$ for $m\>n$ so the language is not $LL(k)$ for any $k$ since we cannot have an arbitrary or finite $k$ ".

But while reading the automata text by *Peter Linz* I came across an example as:

> **Example 7.11** The grammar $$S \rightarrow SS |aSb| ab$$ not an $LL (k)$ grammar for any $k$.

The above grammar in the Linz text is the grammar generating the positive closure of $\\{a^nb^n|n\geq 1\\}$ or simply it generates the set of strings having well formed parenthesis structure.

Now here the thing to be noted is that : Linz talks about the "grammar" not about the language as a whole. Talking about the language seems a bit difficult to me.

The author says that the "grammar" is not $LL(k)$ for any $k$ with the following argument:

> To see why this is so, look at the derivation of strings of length greater than two. To start, we have available two possible productions $S \rightarrow SS$ and $S \rightarrow aSb$. The scanned symbol does not tell us which is the right one. Suppose we now use a look-ahead and consider the first two symbols, finding that they are $aa$. Does this allow us to make the right decision? The answer is still no, since what we have seen could be a prefix of $a$ number of strings, including both $aabb$ or $aabbab$. In the first case, we must start with $S \rightarrow aSb$, while in the second it is necessary to use $S \rightarrow SS$. The grammar is therefore not an $LL (2)$ grammar. In a similar fashion, we can see that no matter how many look-ahead symbols we have, there are always some situations that cannot be resolved.

The above explanation which my mates gives, quite matches with that of Linz, but the difference is that my mates are talking about the language and Linz talks about the grammar.

I came up with a grammar for the language in $\text{GATE-CS-2020}$ paper.

> $$S\rightarrow S\_1 | S\_2$$
>
> $$S\_1 \rightarrow aS\_1 b | \epsilon$$
>
> $$S\_2\rightarrow aS\_2| \epsilon$$

which is not $LL(k)$ for any $k$ using similar logic as in Linz text. But proving that a grammar is not $LL(k)$ for any $k$ does not say anything about the language, as Linz says:

> This observation about the grammar does not imply that the language is not deterministic or that no LL grammar for it exists.

then Linz removes the problem with the grammar and comes up with a "more not obvious form" (but does not explain how) which is $LL$ and equivalent to the original grammar in **example 7.11**

> $$S\_0 \rightarrow aSbS $$ $$S \rightarrow aSbS| \epsilon$$

---

So given such a question about the "language" as in the $\text{GATE-CS-2020}$ paper, how should one proceed? Or what should be the thinking approach?

# Answer
Rosenkrantz and Stearns prove in their paper Properties of deterministic top-down grammars that the language $$ \\{ a^n b^n : n \ge 0 \\} \cup \\{ a^n c^n : n \ge 0 \\} $$ is not $\mathrm{LL}(k)$ for any $k$ (see page 246). Presumably a similar proof will show that your language is not $\mathrm{LL}(k)$ for any $k$.

---

You mention a confusion between grammars and languages. *By definition*, a language is $\mathrm{LL}(k)$ if it has an $\mathrm{LL}(k)$ grammar. To show that a language is not $\mathrm{LL}(k)$, you have to show that it has no $\mathrm{LL}(k)$ grammar.
> 2 votes

# Answer
I would approach this question in this way, **(k)** in $\mathrm{LL}(k)$ means the number of **lookaheads**. The grammar of $\mathrm{L}$ here possess non-determinism. For example, if you can only see **aaaa** then by just looking at the first k symbols, you can't make the decision whether it is **aaaa** or **aaaabbbb**.

No matter how large the value of k is, there will always be some string which has the number of a's larger than the lookahead, for which we couldn't decide what string it is.

In short, here $\mathrm{LL}(k)$ cannot conclusively distinguish that whether the string is from $ a^n$ or from $ a^n b^n $.

Another reason that you can give is that the language here is a union of two languages which have common prefix. Hence the $\mathrm{LL}(k)$ cannot parse it using any value of lookahead **k**.

---

I agree that a language is $\mathrm{LL}(k)$ if there is an $\mathrm{LL}(k)$ grammar which recognizes the language.

**But** the language can also be $\mathrm{LL}(k)$ and has non-$\mathrm{LL}(k)$ grammars which recognize the language. Hence, If a language is $\mathrm{LL}(k)$, it **does not mean that** it has $\mathrm{LL}(k)$ grammar.

To understand more clearly why the language here is not LL(k),you can have a read of this LL(k) languages are closed under union with finite languages.
> 3 votes

---
Tags: formal-languages, formal-grammars, pushdown-automata, ll-k, gate-cs
---


# Question
Title: Context-free grammar for $ \{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, l \geq \min(n,m)\}$
I know that $L = \\{a^lb^n c^m |l, n, m ∈ \mathcal{N}^+, (l ≥ n) ∨ (l ≥ m)\\}$ is a context-free language, because I know the context-free grammar, i.e.

$$ S \rightarrow AbZ \mid XBc \\ A \rightarrow aAb \mid X \\ B \rightarrow aBc \mid Y \\ X \rightarrow aX \mid a \\ Y \rightarrow bY \mid b \\ Z \rightarrow cZ \mid c $$

I have a bit of difficulties understanding this construction. Can you explain step-by-step how it has been created? The rules?

# Answer
> 1 votes
Let us start by noticing that $X \to a^+$, $Y \to b^+$, $Z \to c^+$. Furthermore, $A \to a^n X b^n$ and $B \to a^m Y c^m$. Therefore $S$ generates words of the following two forms: $$ a^na^+b^nbc^+ \\ a^+a^mb^+c^mc $$ You take it from here.

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


# Question
Title: Intersection of Decision Tree Boundaries in Higher Dimensions
I have trained two binary decision tree classifiers with splits in $\mathbb{R}^4$. Same data, but from two different patches. Now, I want to find the exact intervals where the two trees disagree.

The splits are along the lines of: \begin{align\*} & (x\_1 \> 0.35592521727085114) \wedge (x\_3 \leq-0.13628841191530228) \implies 0, \\ & \vdots \\ & (x\_3 \leq -0.013720870949327946) \wedge (x\_1 \> 0.35592521727085114) \wedge (x\_3 \> -0.13628841191530228) \implies1. \\ \end{align\*} ($x\_2$ and $x\_4$ are allowed to live anywhere between their absolute bounds.)

Any advice on how to approach this? I've read some material on interval trees, and theoretically at least I can see how they might be expanded to higher dimensions, but I'm wondering if someone out there has experience with a particular tree variant, or other data-structure that would be appropriate in this case.

Help very much appreciated.

# Answer
> 0 votes
Yuval Filmus has articulated an elegant solution, which I'll expand on.

Given a leaf of a decision tree, it is easy to characterize the set of values of $x$ that reach that leaf. Namely, you take the conjunction of all the conditions along the path from the root to the leaf. For trees of the form you list, this will have the form $\[\ell\_1,u\_1\] \times \cdots \times \[\ell\_4,u\_4\]$, i.e., the set of all $x$ such that $\ell\_1 \le x\_1 \le u\_1 \land \cdots \land \ell\_4 \le x\_4 \le u\_4$, where you can explicitly compute $\ell\_1,\dots,\ell\_4,u\_1,\dots,u\_4$.

Now apply the following algorithm:

* For each pair of leaves, with one leaf in the first tree and the other leaf in the second tree, such that the two leaves lead to different classifications:

+ Compute the set of values $x$ that reach the first leaf, the set of values $x$ that reach the second leaf, and compute their intersection. Output the intersection (this is one set of points where the decision trees differ).

The union (i.e., disjunction) of all of those outputs will be the complete set of points where the two trees give a different decision.

---

It is possible to come up with algorithms that might be faster; however, I'm not sure whether they will lead to a significant improvement in higher dimensions.

One approach is to construct a new tree via a "product construction". Thus, each node in the new tree is a pair $(u,v)$, where $u$ is a node in your first tree and $v$ is a node in your second tree. The root of the tree is $(r\_1,r\_2)$, where $r\_1$ is the root of your first tree and $r\_2$ is the root of your second tree. You can build the new tree top-down, starting from $(r\_1,r\_2)$, then splitting using the condition at one of these two nodes ($r\_1$ or $r\_2$). As you build the tree, keep track of the set of values that can reach each new node $(u,v)$. If this set is empty, you can prune it and don't need to explore any of its children. This might reduce the number of nodes you need to expand. In the worst case, there is no speedup, but in practice, it might help a little.

---

It gets more interesting if each classifier is an ensemble/forest of trees; then the best solution would probably be to use a SMT solver.

---
Tags: intervals, decision-tree
---


title: Bellman-Ford algorithm intuition

text:
# Question
Title: Bellman-Ford algorithm intuition
We recently learned Bellman-Ford algorithm for shortest path in class, but I didn't understand it. Can you give me intuition for why the algorithm works? And can you please explain why it is correct? Why are we sure to find negative circles?

Also, we learned the following two lemmas:

> **Lemma (upper bound property)**: At all times we have that for all $v$, $v.d \ge \delta(s,v)$.

> **Lemma (Path-relaxation property)**: Let $p = \langle s=v\_1, v\_2, \ldots, v\_n \rangle$. Following any sequence of relaxations in which the edges $(v\_1,v\_2),(v\_2,v\_3),\ldots,(v\_{k-1},v\_k)$ are relaxed in order, we have that $v\_k.d \le w(p)$.

Here:

* $v.d$ is the distance of $v$ from the initial vertex $s$. (We constantly update this value using the relax function in the Bellman–Ford algorithm.)
* $\delta(s,v)$ is the minimum weight path between $s$ and $v$.
* $w(p)$ is the total weight of path $p$.

Can you give me an intuition for the lemmas and what they mean?

# Answer
I can give you the intuition behind Bellman-Ford. It is beautiful! I'm going to do it in an indirect way. I want to share a warm-up puzzle that might seem unrelated, but stay with me.

> Suppose we have a digital door lock with a four-digit code (each digit is 0..9), with a funny property: you can enter in extra stuff between the digits of the code and the lock will still open up. For instance, if the code was 2749, then you could enter in 32675049, and the lock would open up, because 32675049 contains 2749 as a subsequence.
>
> Challenge: what is the shortest sequence you can come up with, that will guarantee to open the lock? You could of course enter in each of the $10^4$ possible codes one by one, but that would require you to enter 40,000 digits; can you find a faster way?

Go ahead, see if you can solve it on your own.

Hint:

> Whatever the secret code is, we need it to appear as a subsequence of your chosen sequence. If we start with 0123456789, we are guaranteed to get at last one digit into the code. Can you take it from there?

Hint:

> You should be able to find a sequence of length 40 that suffices.

Really, I want you to solve it yourself! It'll be rewarding and help you understand Bellman-Ford.

---

Now back to Bellman-Ford. Let's consider a graph with no negative cycles, but where edge distances can be positive or negative. The relax operation has an interesting property:

* Suppose the shortest path from $s=v\_1$ to $v\_n$ is via the path $v\_1 \to v\_2 \to \cdots \to v\_{n-1} \to v\_n$. If we do some sequence of relax operations, that includes Relax($v\_1,v\_2$), Relax($v\_2,v\_3$), ..., Relax($v\_{n-1},v\_n$) as a subsequence, then $d\[v\_n\]$ will hold the correct distance from $s$ to $v\_n$.

In other words, this refers to a sequence of relax operations where we do some relaxes, then Relax($v\_1,v\_2$), then relax on some other edges, then Relax($v\_2,v\_3$), then relax on some more edges, and so on. The property holds *no matter what other relax operations you do in the middle* -- you can add as many extra relax operations in the middle anywhere you want and they won't do any harm.

Moreover, once $d\[v\_n\]$ gets set to the correct value, it stays correct forever.

So if our goal is to come up with the correct distance in $d\[v\_n\]$, we can think of that as a digital door lock like the one above: there is some secret code (the code is a sequence of edges, namely, $(v\_1,v\_2),\dots,(v\_{n-1},v\_n)$) that is not known to us, but if we do a sequence of relax operations on some sequence of edges, and if the secret code appears as a subsequence in there, then the lock will open (i.e.,, $d\[v\_n\]$ will get set to the correct distance), and will stay open forever after (i.e., $d\[v\_n\]$ will hold the correct value from there on).

So this is just like the digital door lock puzzle above! The challenge is to construct a sequence of edges, so that if we relax edges in that sequence, it'll surely include the code (the shortest path) as a subsequence. Now you can verify that the sequence of edge relaxations done by Bellman-Ford exactly matches the solution to the digital door lock puzzle above.

I'll let you prove the property I mentioned above. It follows from the two lemmas you quoted.
> 3 votes

# Answer
The first lemma states that $v.d$ is always an upper bound on the distance from $s$ to $v$.

The second lemma states that $v.d$ becomes equal to the distance form $s$ to $v$ if we relax edges $e\_1,\ldots,e\_\ell$ which together form a path of minimal weight from $s$ to $v$.

Put together, the lemmas imply that the Bellman–Ford algorithm computes shortest paths correctly:

* The first lemma guarantees that $v.d$ is always *at least* $\delta(s,v)$.
* The second lemma guarantees that $v.d = \delta(s,v)$ after $\ell$ rounds, where $\ell$ is the length of a minimum weight path from $s$ to $v$.
> 0 votes

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


# Question
Title: How was $T(N)$ derived for this function?
I’m struggling to understand how $T(N)=C\_1 \times N + C\_2$ was derived

Assuming $C\_1$ refers to `l <- 0`, and $C\_2$ refers to `return l`

Shouldn’t it total $T(N)= C\_1 + (N + 1) + N + C\_2$, which simplifies to $T(N)= C\_1 + 2N + 1 + C\_2$ ?

# Answer
> 1 votes
Here, $C\_1$ and $C\_2$ are constants that concern several instructions:

* $C\_2$ corresponds to instructions executed only **once** `l <- 0`, the last executed test of `while(A[l]!=NULL)` and `return l`
* $C\_1$ corresponds to instructions executed several times: each test of `while(A[l]!=NULL)` but the last, and `l<-l+1`. Those are executed a total of $N$ times.

We indeed get $T(N) = C\_1\times N + C\_2$.

---
Tags: asymptotics
---


# Question
Title: $L^{\prime}=\{x \# y \mid x y \in L, y x \notin L\}$ where $L$ is regular
Hey I'm trying to prove that the following Language is regular so far couldn't find a way, hope someone can help me $L^{\prime}=\\{x \\# y \mid x y \in L, y x \notin L\\}$ where $L$ is regular.

# Answer
You can write this language as the intersection of two languages: $$ \\{ x \\# y \mid xy \in L \\} \cap \\{ y \\# x \mid xy \notin L \\} $$ I assume you know how to handle the first one. As for the second one, construct an NFA that acts as follows:

* Start with a DFA for $L$.
* Guess which state the DFA will be on after reading $x$.
* Based on this guess, verify that after reading $xy$, the DFA reaches a rejecting state.
* Now read $x$ and verify your guess.

You take it from here.
> 3 votes

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


# Question
Title: A task-scheduling problem as a matroid (CLRS book)
I don't understand very well section 16.5 of the 3rd edition of the famous `Introduction to Algorithms` book, known as CLRS. It defines the problem of **scheduling unit-time tasks with deadlines and penalties for a single processor** with the following inputs:

* a set $S = {a\_{1}, a\_{2}, ..., a\_{n}}$ of $n$ unit-time tasks
* a set of $n$ integer deadlines ${d\_{1}, d\_{2}, ..., d\_{n}}$ such that each $d\_{i}$ satisfies $1 \leq d\_{i} \leq n$ and task $a\_i$ is supposed to finish by time $d\_i$
* a set of of $n$ nonnegative weights or **penalties** ${w\_{1}, w\_{2}, ..., w\_{n}}$, such that we incur a penalty of $w\_i$ if task $a\_i$ is not finished by time $d\_i$, and we incur no penalty if a task finished by its deadline.

And the following goal:

> We wish to find a schedule for S that minimizes the total penalty incurred for missed deadlines.

**NOTE:** I'm aware that there are other posts here about similar problems (scheduling unit-time tasks with profit etc.), but I'm trying to understand *this particular explanation*, on the CLRS book.

So, I'll get now to the point. On the same page (444), where it explains the core idea, the book talks about the **early-first form** and the **canonical form**, without mentioning the penalties anymore: it talks **exclusively** about the deadlines (I'm not going to copy the whole text, I'm assuming that who answers the question owns the book).

**My first question:** because the whole reasoning does **not** mention penalties, it looks like to me it will work only if all the penalties are equal, which would be a different problem. I'm probably missing something here. But what? No matter how you order the tasks based on deadlines, you **cannot** possibly minimize the penalties without taking them into account. In other words, even if you hit 99/100 deadlines and missed the deadline for that one single task, its penalty might be bigger than the penalties of all the other tasks combined. I don't understand CRLS's logic, in this particular case.

**My second question:** on the next page (445), CLRS mentions the penalties in one place:

> The problem of minimizing the sum of the **penalties** of the late tasks is the same as the problem of maximizing the sum of the **penalties** of the early tasks. The following theorem thus ensures that we can use the greedy algorithm to find an independent set A of tasks with the **maximum total penalty**.

And after that it mentions theorem 16.13 claiming substantially that $(S, I)$ is a matroid.

I believe I understand that, it makes sense. But, how can we determine in the first place the subset of the **early tasks** without taking into account the actual values of each $w\_i$ penalty? In my understanding, that's not possible. I wouldn't dare claiming there's a mistake in the CLRS book, but that's my only theory at the moment. **Very likely I'm wrong**, but I cannot figure out why. On page 444, it mentions twice "monotonically increasing deadlines" but **never** anything like "monotonically decreasing penalties".

On the other side, I've done some research and I've read about **variations of this problem with profits** instead of penalties. I've understood that the tasks need to be ordered by **monotonically decreasing profit**. After doing that, we put each task as close to its deadline as possible, and move left only (= early) when the slot is already taken. That makes completely sense, because the profit is taken into account. If we consider penalties as negative profits, shouldn't the same logic apply? But, even with a different logic, how can we ignore the $w\_i$ values?

# Answer
> 2 votes
I believe you are completely correct but mixed up two things from the book, namely the order in which the tasks are selected and the order in which the tasks are scheduled.

The greedy algorithm here indeed orders the task by their weights $w\_i$ (as for every max-weight greedy algorithm on matroids). Given a set $A$ of tasks that are independent, i.e. they **can somehow** be scheduled so that no task is late, one way to schedule those tasks, such that none of them is late is by ordering those tasks (and only those, you omit the the tasks that are not in $A$) in increasing order of their due dates $d\_j$.

Regarding your example with 99/100 tasks early: The one with the biggest weight (or penalty) is definitely one of the 99 tasks, as it is the first one to be selected by the greedy algorithm (unless its due date is non-positive). However, this task does not need to be the one that appears in the schedule first.

In essence, the order in which the greedy algorithm selects the tasks is not related to the order in which the tasks are scheduled.

Towards your second question: Whether a task is early only depends on its due date. The corresponding independence check for the matroid would work as follows:

1. The empty set is independent (no task is late).
2. Given set $A$ and task $a \notin A$, order all tasks in $A+a = \[a\_1, \ldots, a\_m\]$ by $d\_j$ (such that $d\_1 \leq \ldots \leq d\_m$) and check for all $a\_j \in A+a$ whether $j \leq d\_j$ (as you have unit processing times).

The reason why this works, is subject of Lemma 16.12 (in the 3rd edition at least. the equivalence of three statements).

---
Tags: scheduling, matroids
---


# Question
Title: Intersection of Deterministic Context-Free Languages
If deterministic context-free languages (DCFLs) are not closed under intersection, does this mean that the intersection of two DCFLs will always be context free but may not be deterministic? Or does it mean their intersection may not be context-free?

# Answer
> 2 votes
The statement itself doesn't imply that. It just means that the intersection of two DCFLs might or might not be a DCFL; and thus presumably could be a DCFL; could be a CFL but not a DCFL; or could be not context-free.

However, we know more actually.

* The intersection of two DCFLs could be, of course, a DCFL. For example, you can let both of them be the same DCFL. For another example, just take any two regular languages. Every regular language is a DCFL and the intersection of two regular language is still regular.
* Here is an example of two DCFLs the intersection of which is not a CFL. The intersection of $\\{a^{n}b^{n}c^m \mid n\ge0, m\ge 0\\}$ and $\\{a^{n}b^{m}c^m \mid n\ge0, m\ge 0\\}$ is the most classical non-CFL, $\\{a^{n}b^{n}c^n \mid n\ge0\\}$.

*Exercise*. Find two different non-regular DCFL the intersection of which is a DCFL.

*Deeper fact*. Given any natural number $n$, there is a language that is the intersection of some $n+1$ DCFLs, but it is not the intersection of any $n$ DCFLs.

---
Tags: context-free
---


# Question
Title: Why do researchers only count the number of multiplications when analyse the time complexity of Matrix Multiplication?
In this article about the recent breakthough in Matrix Multiplication, it quotes Chris Umans's words:

> Multiplications are everything. The exponent on the eventual running time is fully dependent only on the number of multiplications. The additions sort of disappear.

I was wondering how I should understand this. Why the number of additions doesn't matter?

# Answer
> 2 votes
It looks like the article was written by someone who does not understand matrix multiplication.

> the number of additions is equal to the number of entries in the matrix, so four for the two-by-two matrices and 16 for the four-by-four matrices.

With the classic matrix multiplication algorithm (which is the one explained in the example) between two $4\times 4$ matrices, each coefficient of the product requires $3$ additions, so a total of $3\times 16 = 48$ additions, not $16$.

Usually, when it is said that only multiplications matter and not additions, it means of **matrices**, not **coefficients**.

For example, a "naive" divide-and-conquer strategy compute $A\times B$ where $A,B$ are matrices of size $n\times n$ by doing $8$ products of matrices of size $\frac{n}{2}\times\frac{n}{2}$ (and some additions of matrices, but those are done in complexity $O(n^2)$, which is negligible in front of the complexity of matrix multiplication). That way, the complexity verifies $C(n) = 8C\left(\frac{n}{2}\right) + O(n^2)$ and it is easily proven that $C(n) = O(n^3)$, so this strategy is not an improvement.

The Strassen algorithm use a divide-and-conquer strategy to improve complexity: it does $7$ products of matrices of size $\frac{n}{2}\times\frac{n}{2}$ and some additions, so the complexity verifies $C(n) = 7C\left(\frac{n}{2}\right) + O(n^2)$ and we get $C(n)\simeq O(n^{2.8})$.

In the two examples above, the number of matrices multiplications matter much more than the number of matrices additions. But in both, the number of multiplications/additions on coefficients is not compared.

It is confirmed in the article:

> Volker Strassen reportedly set out to prove that there was no way to multiply two-by-two matrices using fewer than eight multiplications. Apparently he couldn’t find the proof, and after a while he realized why: There’s actually a way to do it with seven!

---
Tags: time-complexity, algorithm-analysis, matrix-multiplication
---


# Question
Title: Linear programming formulation for the single-source shortest path problem
In this course lecture; section 5.1, single-source shortest path (SSSP) is formulated as the following linear program (LP):

\begin{align} \max &\sum d\_u \\ \text{subject to} & \\ d\_v &\le d\_u + l\_{uv} \quad \forall (u,v) \in E \\ d\_s &= 0 \end{align}

The comment on the objective function is as follows (emphasis added):

> The variables $d\_u$ represent the distances from $s$ to each vertex $u$. ***Maximizing the sum of the $d\_u$ is done by maximizing each one individually, since increasing any single $d\_u$ never forces us to decrease some other $d\_v$***.

I can get its basic idea. However, how to argue that $(\max d\_u \\;\forall u \in V)$ is equivalent to $(\max \sum d\_u)$ more rigorously? Specifically, why is that "increasing any single $d\_u$ never forces us to decrease some other $d\_v$"?

# Answer
> 2 votes
Any optimal solution to the problem must satisfy $$ d\_v = \min\_{u\colon (u,v) \in E} (d\_u + \ell\_{uv}), $$ as well as $d\_s = 0$, of course. Assuming the graph is connected, you can prove by induction on the length (number of edges) of a shortest path from $s$ to $v$ that $d\_v$ is at most the distance from $s$ to $v$, which we denote by $d^\*\_v$. In particular, the optimal value is at most $\sum\_v d^\*\_v$.

On the other hand, it is not hard to check that $d\_v = d^\*\_v$ (for all $v$) itself is a feasible solution, showing that the optimal value is exactly $\sum\_v d^\*\_v$, and it is achieved only when $d\_v = d^\*\_v$ for all $v$.

# Answer
> 1 votes
The claim that "increasing any single $d\_u$ never forces us to decrease some other $d\_v$" can be seen from the constraint $d\_v \leq d\_u + l\_{uv}$. Here, increasing $d\_u$ will not cause a violation in this particular constraint, while increasing $d\_v$ would require $d\_u$ to increase (not decrease) in order to keep the constraint true.

Now for the "maximizing each one individually" part, recall that the single source single destination shortest paths problem is solved by having the above linear program maximizing a single $d\_u$ instead of the sum. From the claim in the paragraph above, we see that maximizing the sum results in a solution for which it is impossible to improve any individual $d\_u$ (if it were, then since we need not decrease anything, it would be guaranteed to contradict our initial assumption of having already maximized the sum).

Hence maximizing the sum gives a solution for which each individual $d\_u$ has the same value as if it were individually maximized in the single-pair case, and thus maximizing the sum optimally solves the single-source all destination problem.

---
Tags: shortest-path, linear-programming, modelling
---


title: Is reduction symmetric?

text:
# Question
Title: Is reduction symmetric?
I was watch this lecture https://youtu.be/moPtwq\_cVH8?t=2895, and at this point he says a lot about reductions, take a problem and reduce to another problem. From what I could understand this is a symmetric relation, if I can reduce A to B, then I can reduce B to A. This seems pretty intuitive to me but I don't have a formal proof, is there any (for beginners would be better) material on this proof?

Still on this lecture, from what I could understand we have problems that are known to be NP-hard, if I have a problem that I don't know what is but I can reduce to NP-hard problem then it must be NP-hard.

Another question, supposing that reduction is symmetric if any NP problem can be reduced to P problem that would prove that P = NP. Or in reverse, if I have a known NP problem and I prove it can't be reduced to a P problem then this would prove that P ≠ NP.

Is my reasoning right? I'm not trying to prove anything just want to make sure that I understand the reduction implications because this seem powerful tool for day reasoning on solving problems in general.

# Answer
> 4 votes
Reduction is not symmetric. Intuitively, if $A$ reduces to $B$, then $B$ is at least as hard as $A$. Just as the usual comparison is not symmetric — for example $3 \> 2$ but $2 \not\> 3$ — reduction, which is a (partial) order of hardness, isn't symmetric.

For example, SAT reduces to the halting problem, but the halting problem doesn't reduce to SAT.

---
Tags: p-vs-np
---


title: Capacity of Binary Erasure Channel

text:
# Question
Title: Capacity of Binary Erasure Channel
Consider the the binary erasure channel, with input and output alphabet $\\{0,?,1\\}$ and channel matrix \begin{bmatrix} 1-\lambda-\mu & \mu & \lambda\\ 0 & 1 & 0\\ \lambda & \mu & 1-\lambda-\mu \end{bmatrix} I want to determine its capacity, i.e. maximize $I(X;Y)$ over the probabilities distribution of the input.

I have tried writing and rewriting $I(X;Y)$ in different ways but the expression gets too complicated and I can't find a way to assign values to $p(x)$ so that $I(X;Y)$ is maximized. Any suggestions? Thank you in advance.

# Answer
By symmetry, we can assume that $\Pr\[X=0\] = \Pr\[X=1\] = p$, and so $\Pr\[X=?\] = 1-2p$. We can then express $I(X;Y)$ as a function of $p,\lambda,\mu$. The capacity of the channel is the maximum of $I(X;Y)$ over all $p \in \[0,1/2\]$. You can find this maximum using calculus.

In more detail, let us first note that $\Pr\[Y = 0\] = \Pr\[Y = 1\] = (1-\mu)p$ and $\Pr\[Y=?\] = 1-2(1-\mu)p$. Furthermore, $H(Y|X=?) = 0$ and $H(Y|X=0) = H(Y|X=1) = H(1-\lambda-\mu,\lambda,\mu)$. Therefore $$ I(X;Y) = H((1-\mu)p,(1-\mu)p,1-2(1-\mu)p) - 2pH(1-\lambda-\mu,\lambda,\mu). $$ The derivative of this with respect to $p$ is $$ -2(1-\mu)\log((1-\mu)p)+2(1-\mu)\log(1-2(1-\mu)p) - 2H(1-\lambda-\mu,\lambda,\mu) = \\ 2(1-\mu) \log \frac{1-2(1-\mu)p}{(1-\mu)p} - 2H(1-\lambda-\mu,\lambda,\mu). $$ Equating this to zero, we get $$ \log \frac{1-2(1-\mu)p}{(1-\mu)p} = \frac{H(1-\lambda-\mu,\lambda,\mu)}{1-\mu} $$ and so $$ \frac{1-2(1-\mu)p}{(1-\mu)p} = e^{H(1-\lambda-\mu,\lambda,\mu)/(1-\mu)}. $$ Massaging this, we finally get $$ p = \frac{1}{(1-\mu)(2 + e^{H(1-\lambda-\mu,\lambda,\mu)/(1-\mu)})}. $$
> 1 votes

---
Tags: information-theory, entropy
---


# Question
Title: Produce all unordered unique combinations of N-sized subsets of an m·N-sized set
Say there is a set of *m*·*N* named elements. How to produce all the (unordered) combinations of *N*-sized subsets?

For example, *m*=2 and *N*=2, the elements are called A, B, C and D. There will be 3 combinations: AB+CD, AC+BD and AD+BC.

For *m*=2 and *N*=3 there will be 10 combinations. In general, it will be:

$$\frac{(mN)!}{(N!)^m\cdot m!}$$

(thanks to Ross Millikan)

How to approach creating an algorithm that produces / iterates over the whole set of combinations?

# Answer
Here is **a program in Java** that prints all unordered unique `m`-combinations of `N`-sized subsets of numbers from 0 inclusive to `m * N` exclusive. Click the run button to see some result.

---

The algorithm used in the program is adapted from the usual algorithm that produces all unique $k$-combinations out of $U$ objects. Here is some explanation of the recursive method, `static void printCombinations(int m, final int N, int startNumber, boolean[] used, int[][] subsetsHolder, int curSubset, int toFill)`.

That method prints all print all unordered partition of numbers starting from 0 inclusive to `m * N` exclusive into `m` subsets of size `N`, where

* the first `curSubset` subsets have been specified by `subsetsHolder[0:curSubset]` and
* the first `N - toFill` numbers in the current subset, `subsetsHolder[curSubset]` have been specified in `subsetsHolder[curSubset][0:N - toFill]` and
* if `toFill` is not `N`, all unspecified numbers in `subsetsHolder[curSubset]` must be at least `startNumber`. If it is `N`, the first number in `subsetsHolder[curSubset]` must be the first unused number.

The parameter `used` records those specified numbers. Namely, `used[i]` is true iff `i` has been specified somewhere. It is a convenience argument to ease the coding.

---

The body of that method is, in fact, quite simple, thanks to the power of recursion.

It first checks if all `N` numbers of the current subset is waiting to be selected.

* If yes, there are two cases.
    + If `curSubset` is `m`, we have arrive at a full combination. Print and return.
    + Else we will find the smallest unused number. It becomes the `0`-th element of the current subset, i.e., `subsetsHolder[curSubset][0]`. Recurse to fill the next number in the current subset.
* Otherwise,
    + If there is no more to fill the current subset, recurse to fill the next subset.
    + Else let the next smallest number in the current subset to iterate through all numbers starting at `startNumber`. Recurse to fill the next number in the current subset.

---

It is not hard to prove that the algorithm/program prints all wanted combinations once in the natural lexicographic order.
> 1 votes

# Answer
Knuth wrote a chapter on this, as part of the new volume 4 of his Art of Computer Programming.

The simplest algorithm uses the following recursion to generate all combinations of length $m$ of a set $x\_1,\ldots,x\_n$:

* If $m = 0$ then output the empty set.
* Otherwise, for each $m \leq i \leq n$, generate all combinations of length $m-1$ of $x\_1,\ldots,x\_{i-1}$, and add $x\_i$ to all of them.
> 2 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: How to prove the correctness of the binary tree inversion algorithm?
Define the inversion of a binary tree as the tree whose left sub-tree is a mirror reflection of the original tree's right sub-tree around the center and right sub-tree a mirror reflection of the original tree's left sub-tree.

```
Examples:

   Inversion 1           Inversion 2

   C    |    C           C    |    C
  / \   |   / \           \   |   /
 A   B  |  B   A           B  |  B
                          /   |   \
                         A    |    A

```

Consider the following binary tree inversion algorithm (source: LeetCode):

```
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(tmp);
    return root;
}

```

I sought to prove it inductively on the depth of tree but am stuck at the inductive step. How can I show that the mirror reflection of the left subtree (or right) around the center of the root tree is a combination of moving the subtree from `root.right` to `root.left` and inverting the subtree around the center of the subtree itself?

# Answer
> 1 votes
It might be surprising to you, but "the mirror reflection of the right subtree around the center of the root tree is a combination of moving the subtree from root.right to root.left and inverting the subtree around the center of the subtree itself" could be, in fact, part of the definition of "a mirror reflection of the right subtree around the center of the root tree"!

Note that the following definition of "the inversion of a binary tree", as given in the question, does not define what is the "mirror reflection of the original tree's right subtree". Although that mirroring is pretty intuitive for a human to understand accurately, given the accompanying illustrations, it is, in fact, not defined/specified clear enough to enable you to prove the correctness of the algorithm formally.

> Define the inversion of a binary tree as the tree whose left subtree is a mirror reflection of the original tree's right subtree around the center and right subtree a mirror reflection of the original tree's left subtree.

So, here is the real question.

### How do we define mirror reflection formally?

Here is **a recursive definition**. (This can be seen as taking the given algorithm as the definition basically.)

Given a binary tree $T$ or an empty graph, its mirror reflection $T'$ is another graph such that

* $T'$ is empty if $T$ is empty.
* $T'$ is a single node that is the same as $T$'s single node if $T$ is a single node.
* Otherwise, $T'$ is also a binary tree such that
    + the root of $T'$ is the same as the root of $T$ and
    + the left subtree of $T'$ is a mirror reflection of the right subtree of $T$ and
    + the right subtree of $T'$ is a mirror reflection of the left subtree of $T$.

When $T'$ is a mirror reflection of $T$, we also say $T'$ is a mirror reflection of $T$ along/around the center of $T$, or any imaginary line that goes from root to a leaf.

---

Here is **a non-recursive definition**, that is equivalent to the above.

Given a binary tree $T$ or an empty graph, its mirror reflection is any graph that is isomorphic to the graph $T'$ defined below.

* If $T$ is empty, so is $T'$.
* Otherwise, let $V$ be the nodes of $T$. Let $V'$ be a copy of $V$; that is, for each $v\in V$, there is unique node in $V'$ that corresponds to $v$. Call that unique node $v'$.
    + For any two nodes $p, c\in V$ such that $c$ is the left child of $p$, we let $c'$ be the right child of $p'$.
    + For any two nodes $p, c\in V$ such that $c$ is the right child of $p$, we let $c'$ be the left child of $p'$.

---

The OP also proposes the following geometric/graphical definition of "inversion of a tree".

> Let $(a,b)$ be the coordinate of the node at depth $a$ that is the $b$-th node from the imaginary center line. If $b$ is negative then the node is to the left of the line. Then the inversion can be defined as the resulting tree if we map $(a,b)$ to $(a,-b)$ and keep the edges accordingly.

The definition above, although graphically clear to a human, might not be very friendly for rigorous reasoning. For example, "the b-th node from the imaginary center line" requires further non-trivial clarification.

---

With either of my definitions above, it will be rather easy to prove the correctness of the algorithm.

You might have noticed by now that inversion of a binary tree means exactly the same as its mirror reflection!

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


# Question
Title: k disjoint triangles with graph splitting to two distinct groups
Please note that this question is different than this question.

The $k$-disjoint triangles problem is as follows:

> Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$
>
> Output: Are there $k$ vertex-disjoint triangles in $G$?

An FPT algorithm is presented here (starting from slide 60). The algorithm uses color-coding and relies on dynamic programming to determine if a solution is highlighted (each vertex in the solution group is colored with a distinct color). The running time of the algorithm is $O^{\*}((2e)^{3k})$.

Now, Let's assume that we get a group $X \subseteq V$ of vertices, and the problem changes: Are there $k$ vertex-disjoint triangles in $G$ where one vertex is from $X$ and the other two are from $V \setminus X$?

I need to find an algorithm whose running time is $O^{\*}((2e)^{2k})$. I tried coloring all vertices from $X$ in a single color, but I couldn't find a way to avoid the duplicate choices of vertices from $X$. I also try to color each vertex from $X$ in a distinct color that is different from the colors of $V\setminus X$ but the running time is higher.

Can you propose a coloring method that will highlight a possible solution within the required complexity? Should I try something else?

# Answer
Color the vertices in $V \setminus X$ with $2k$ colors at random. With probability $e^{-2k}$, the $V \setminus X$ vertices of your $k$ disjoint triangles will be highlighted.

Suppose without loss of generality that $X = \[m\]$. Using dynamic programming, determine for each subset $S \subseteq \[2k\]$ and $i \in \[m\]$ whether there exist $|S|/2$ disjoint triangles using the colors in $S$ and vertices $1,\ldots,i$ of $X$. This takes time $O^\*(2^{2k})$.
> 2 votes

---
Tags: complexity-theory, np-hard, randomized-algorithms, colorings, parameterized-complexity
---


# Question
Title: How to prove that existence of one-way functions implies P≠NP?
Wikipedia:

> The existence of such one-way functions... would prove that the complexity classes P and NP are not equal.

How is this proved?

# Answer
Suppose that P=NP, and that $f\colon \\{0,1\\}^\* \to \\{0,1\\}^\*$ is an arbitrary function computable in polynomial time. Suppose that $|x| = n$, and we are given $y = f(x)$. We will show how to find $z \in \\{0,1\\}^n$ such that $y = f(z)$ in polynomial time (in $n$).

Using an NP oracle, we determine whether there exists $z$ such that $z\_1 = 1$ and $y = f(z)$. If so, we set $w\_1 = 1$, and otherwise, we set $w\_1 = 0$. Using an NP oracle, we determine whether there exists $z$ such that $z\_1 = w\_1$, $z\_2 = 1$, and $y = f(z)$. We set $w\_2$ accordingly. Continuing in this way, we eventually found $z$ such that $y = f(z)$. Since we assumed that P=NP, this algorithm runs in polynomial time.
> 5 votes

---
Tags: complexity-theory, complexity-classes, cryptography, p-vs-np, one-way-functions
---


# Question
Title: Is best case complexity big Omega of worst case complexity?
I need to prove or disprove the following claim:

> Given that the best case complexity of the algorithm A is $O(f(n))$ and the worst case complexity of A is $Ω(g(n))$, it follows that $f(n) ∈ Ω(g(n))$.

I know that obviously $A\_b \leq A\_w$. I can also conclude obviously that for constants $c\_1 , c\_2$ and for all $n\_0 \leq n$ for some $n\_0$ the following happens: $A\_b \leq c\_1f(n)$ and $A\_w \leq c\_2g(n)$. I can see that it doesn't mean that $f(n) \geq cg(n)$ for some constant $c$ but I am having trouble disproving it. Any help will be welcomed.

# Answer
Consider the following algorithm $A$:

* If the input consists entirely of zeroes, return.
* Otherwise, count from $1$ to $n^2$, where $n$ is the length of the input.

The best case complexity of this algorithm is $O(n)$, and the worst-case complexity of this algorithm is $\Omega(n^2)$. Does $n = \Omega(n^2)$ hold?
> 1 votes

---
Tags: time-complexity, asymptotics
---


# Question
Title: Can intersection of non-context-free languages be context-free?
For two languages over the same alphabet that are not context-free, can their intersection be context-free, Or does at least one of them have to be context-free?

# Answer
Let $L$ be an arbitrary language. Then $$ \\{ 0x : x \in L \\} \cap \\{ 1x : x \in L \\} = \emptyset. $$
> 2 votes

# Answer
The intersection of two CFL may or may not be a CFL. We can show that both possibilities exist. For example if both $L\_1$ and $L\_2$ are regular then $L\_1∩ L\_2$ is regular and therefore CF.

For intersection of non-context-free languages be context-free, you can assume that the intersection could be empty.
> 2 votes

---
Tags: context-free
---


title: Analyzing parallel performance question

text:
# Question
Title: Analyzing parallel performance question
I was reviewing for my CS class and came across this question and answer combo that didn't have any explanation why it was correct. I'm confused on how they got the answer:

> We have a system to which we can instantaneously add and remove cores -- adding more cores never leads to slowdown from things like false sharing, thread overhead, context switching, etc
>
> When the program foo() is executed to completion with a single core in the system, it completes in 20 minutes. When foo() is run with a total of three cores in the system, it completes in 10 minutes.
>
> If 100% of foo() is parallelizable, with 3 cores it would take 20/3=6.66 minutes. Since it instead takes 10 minutes, what fraction of foo() is parallelizable?

ANSWER GIVEN: 0.75

> How many minutes would it take to execute foo on this magical system as the number of cores approaches infinity?

ANSWER GIVEN: 5

Could someone explain how the staff got these answers?

# Answer
> 0 votes
Suppose that the fraction of `foo()` that is parallelizable is $\alpha$. Then the total execution time with $n$ cores is:

* the non-parallelizable execution, done by only one core: $(1- \alpha)\times 20$
* the parallelizable execution: $\alpha \times 20 \times \frac{1}{n}$

Then, for the first question, we have to consider that the number of cores is $3$, and the total time is $10$. The equation becomes:

$(1-\alpha)\times 20 + \alpha\times \frac{20}{3} = 10\Leftrightarrow \alpha = 0.75$.

For the second question, we suppose known the answer to the first question: $\alpha = 0.75$, and we suppose then that $n = \infty$. The total execution time becomes:

$0.25 \times 20 + 0.75\times \frac{20}{\infty} = 0.25 \times 20 = 5$.

---
Tags: time-complexity, parallel-computing, performance, threads
---


# Question
Title: Why does universe level restriction behave differently between inductive family and parameterized inductive type without axiom K in agda
An observation when defining `List` in agda with `--without-K` enabled:

The following parameterized inductive definition is accepted:

```
data List (A : Set) : Set where
    [] : List A
    _::_ : A → List A → List A

```

but not the equivalent inductive family definition:

```
data List' : Set → Set where
    []'  : {A : Set} → List' A
    _::'_ : {A : Set} → A → List' A → List' A

```

The error message is `Set₁ is not less or equal than Set`, so I have to change the type from `List' : Set → Set` to `List' : Set → Set₁` in order for it to type-check. If I disable `--without-K`, then agda also correctly type-checks.

I tried to look up why this is the case, e.g., on the page https://agda.readthedocs.io/en/latest/language/without-k.html it says "When `--without-K` is enabled, some indexed datatypes must be defined in a higher universe level. In particular, the types of all indices should fit in the sort of the datatype." But it doesn't say the reason for such difference between inductive family (indexed datatypes) definition and the parameterized inductive definition. I guess it has something to do with the homotopy model interpretation of the underlying type theory. However I want to know what sort of "bad" thing will happen if the inductive family lives in a smaller universe (syntax and semantics). And how would parameterized inductive definition avoids such issue?

# Answer
Normally, Agda does an analysis to determine that your indexed type is equivalent to a parameterized type. Essentially, since `A` occurs in the result type, knowing that `l : List A` tells you what type `A` is 'stored' in the value `l`. The value is known, which means that tricks that involve embedding a universe into a small type within said universe to cause a paradox will not work.

However, the above reasoning basically presumes K for the universe. Really all we can say is that knowing the type `List A` lets us know that the stored type is equal to `A`, but without K, we don't know that there are no non-trivial equalities between types. I'm not sure if there is an example of how this extra degree of freedom would allow a paradox to be written, but even if no example is known, it is safer to require the larger size than to assume that the small size is consistent.
> 1 votes

---
Tags: programming-languages, type-theory, dependent-types, homotopy-type-theory, agda
---


# Question
Title: Find the k length path that maximize a node associate metric
Let's say I have :

1. a Graph **g**
2. **v** vertices. Each vertex is associated to a cost **c**.
3. A special vertex called the starter vertex or **vs**.

I want to find the **path *p* of length 10** (for example), that start from **vs** and that **maximize the sum of the 10 seens nodes costs**. I need to tell you that my graph represent a road network which means it has a big diamater, and the degree of each node is never above 6 or 7. Here is an example of the kind of a graph that I have. Obviously, I got way more nodes.

# Answer
A brute-force approach is to do a backtracking search starting from $s$. Something like:

Search($s$, $n$, $S$):

1. If $n=1$, yield $S \cup \\{s\\}$ and return. Otherwise:
2. For each vertex $v$ that is adjacent to $s$, do:

a. Call Search($v$, $n-1$, $S \cup \\{s\\}$).

If you invoke Search($vs$, $10$, $\emptyset$), this will generate all possible sets of vertices that can arise from a path of length 10; now calculate the cost of each such subset, and keep the largest one.

$6^{10}$ is about 60 million, so this might complete within a few seconds on most graphs.
> 1 votes

---
Tags: graphs, optimization, path
---


title: Is clause learning in SAT parsimonius?

text:
# Question
Title: Is clause learning in SAT parsimonius?
I have a model counting program bob. On some graph coloring formulas, bob got the right answer only after removing clause learning. That is to say, with clause learning, bob sometimes counts duplicate solutions, while satisfiability remains stable. This would be big news if true.

# Answer
> 4 votes
I don't know precisely how Bob works, but let's talk about clause learning.

Suppose you have a set of variable assignments, $A$, say $x\_1 = 0$, $x\_2 = 1$, $x\_3 = 0$. This is a single clause in disjunctive normal form:

$$A = \neg x\_1 \wedge x\_2 \wedge \neg x\_3$$

The *negation* of this set of assignments is a single clause in conjunctive normal form:

$$\neg A = x\_1 \vee \neg x\_2 \vee x\_3$$

So if you have a set of variable assignments that you know you never want to see in any solution, you can add its negation to a SAT problem in CNF and it remains a SAT problem in CNF.

With conflict-directed clause learning, you add clauses which correspond to "dead ends" in the search. Suppose you try some assignments and find that this is not a valid SAT solution. This means that you have identified a CNF clause which is unsatisfiable (i.e. a "conflict"). So if you can find an appropriate subset of assignments that inevitably leads to the dead end, and add its negation as a new clause, this has the effect of directing the search so that it will not get stuck in that dead end any more, while also not changing the solution set.

For model counting, you find a solution to the SAT problem, add its negation as a new clause, and then go try to find a solution to the augmented problem.

It would be big news indeed if adding the negation of a known solution to a SAT problem meant that the solution that you explicitly negated is still a solution. I suspect Bob has a bug.

---
Tags: complexity-theory, np-complete, satisfiability, correctness-proof
---


# Question
Title: Lower bound on positive coefficients of the optimum of 0,1-linear programming problem
I have an instance linear programming such that the coefficients and the constant terms are 0 or 1. Formally, the set of variables is denoted as $V$ and $|V| = n$. There are $m$ constraints, formed as $$ \mathbf{a}\_{1}^{\top} \mathbf{v} \leq 1 $$ or $$ \mathbf{a}\_{2}^{\top} \mathbf{v} \geq 1 $$ where $\mathbf{a}\_{1}, \mathbf{a}\_{2} \in \\{0,1\\}^{n}$ and $\mathbf{v} = \[v\_{1}, v\_{2}, \ldots, v\_{n}\]^{\top}$. (Assume that $0 \leq v\_{i} \leq 1$).

The objective function is $$\min \sum\_{i}v\_{i} = \[1,1, \ldots, 1\] \cdot\mathbf{v}$$ I am hoping to find a constant $c \geq 0$ (depending only on $n$) such that there always exist an optimum $\mathbf{v}^{\*} \in \[0,1\]^{n}$ satisfying $v^{\*}\_{i} = 0$ or $v^{\*}\_{i} \geq c$.

Does it hold for $c = 1/n$? Is there any positive lower bound on $c$?

For example, consider the LP relaxation of the vertex cover problem. The constraints are formed as $v\_{i} + v\_{j} \geq 1$, for each edge $v\_{i}v\_{j} \in E(G)$. We know that there exists a half-integral optimum, i.e., $v\_{i} \in \\{0,1/2,1\\}$.

# Answer
> 4 votes
$\frac 1n$ is not a lower bound. For example, let $n=10$. Consider 3 set of equations (you can get equalities by considering both $a^\top v \le 1$ and $a^\top v \ge 1$):

1. \begin{align} v\_1 + v\_2 + v\_3 \qquad = 1\\ \qquad v\_2 + v\_3 + v\_4 = 1\\ v\_1 \qquad + v\_3 + v\_4 = 1\\ v\_1 + v\_2 \qquad + v\_4 = 1\\ \end{align} It's easy to check that $v\_1=v\_2=v\_3=v\_4=\frac 13$ is the unique solution.
2. Consider $v\_5 + v\_6 + v\_7 + v\_8 + 0 \cdot v\_9 = 1$ and, similarly to the above case, all cyclic shifts of $(v\_5, \ldots, v\_9)$. Again, the unique solution is $v\_5 = v\_6 = v\_7 = v\_8 = v\_9 = \frac 14$.
3. The last equation is $$v\_1 + v\_2 \qquad + v\_5 \qquad + v\_{10} = 1$$ Then $v\_{10} = 1 - 2 \cdot \frac 13 - \frac 14 = \frac 1 {12}$.

Generalizing it, you can always obtain coefficient $\frac 1{k (k+1)}$ using $2k + 4$ variables.

I think that by properly selecting numbers $p\_1, \ldots, p\_k$, you should be able to get a coefficient as small as $O\left(\frac 1 {\prod\_i p\_i}\right)$ with $O\left(\sum\_i p\_i\right)$ variables.

---
Tags: linear-programming
---


# Question
Title: Can a language be context free and not have a BNF grammar?
Leslie Lamport claims that TLA+ is too complex to be described in BNF.

Does that mean TLA+ is not a context free language?

What is the relationship between the set of context free languages and the set of languages that can be described by BNF grammars?

# Answer
No. If a language is context-free, it has a BNF grammar, by definition. A context-free language is a language with a context-free grammar, and a context-free grammar is a grammar written in BNF with only one symbol on the left-hand side of each production. That's what "context-free" means.

It might not be convenient to write the grammar. For example, consider the language of words containing characters from some alphabet where no word contains two of the same character. The language is context-free, but the size of the shortest BNF grammar which describes it is exponential in the size of the alphabet. If you chose the set of 95 printable ASCII characters, the grammar would have so many productions that you would need a computer the size of the galaxy to store them.

Even if the language is not so pathological, you might feel that writing down its grammar in BNF is too time-consuming and mundane to make it a worthy use of your superior intellect.

But if the language is context-free, the grammar exists, at least in the mathematical sense of the word "exists".
> 18 votes

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


# Question
Title: How do real numbers like Pi, golden ratio, etc fit into type theory
In type theory, all computable functions must terminate, however, numbers like Pi are non-terminating real numbers, hence a non-terminating function is required to compute this number, even though one would never compute the full sequence.

How does type theory view/deal with such non-terminating numbers/object?

# Answer
If by "non-terminating real number" you mean to say that the digit expansion of the number is an infinite sequence, then that is not saying much, because *every* real number is "non-terminating" in this sense, even the real number 42, for its digit expansion is

$$41.999999999999999999999999999999....$$

In any case, nobody suggests that the digits must somehow be computed all at once, although that is a common misconception that arises in the study of computability of reals. We just need *a method* which computes any digit we desire – but we *never* desire all the digits at once.

A sequence of digits is a function $f : \mathbb{N} \to \mathbb{N}$, and such functions can be perfectly managed by type theory. In fact, the *correct* way to represent a real number by a sequence is to use positive and *negative* digits, or else you can't compute certain operations (such as $+$). So in reality, in type theory or in any other setting a real number may be represented by a sequence of digits $f : \mathbb{N} \to \\{-9, -8, \ldots, 8, 9\\}$. Even better but equivalent is the representation by which a real number is represented by a map $g : \mathbb{N} \to \mathbb{Q}$ satisfying the condition $\forall m, n \in \mathbb{N} \\,.\\, |g(m) - g(n)| \< 2^{-\min(m,n)-1}$. Such a map represents the number $\lim\_n g(n)$.

All of the above can be stated in type theory: $$ \Sigma (g : \mathbb{N} \to \mathbb{Q}) \\, \Pi (m, n : \mathbb{N}) \\; \mathrm{Id}\_\mathbb{Q}(1, \max(|g(m) - g(n)| \cdot 2^{1 + \min(m, n)}, 1)) $$ The inner $\mathrm{Id}$-type says $$\max(|g(m) - g(n)| \cdot 2^{1 + \min(m, n)}, 1) = 1$$ which is just a fancy way of stating $$|g(m) - g(n)| \cdot 2^{1 + \min(m, n)} \leq 1.$$
> 4 votes

---
Tags: type-theory
---


# Question
Title: Why is my run time calculation of selection sort different?
This is the pseudocode I used:

Their calculation seems to be different from mine. Can someone explain how they derived it? Here is mine in comparison:

* Line 1: $c\_1 \cdot (n-1)$
* Line 2: $c\_2 \cdot (n-1)$
* Line 3: $c\_3 \cdot n $
* Lines 5-6: $c\_4 \cdot \frac{n(n-1)}{2}$ (the if statement executes with an arithmetic progression)
* Line 9: $c\_5 \cdot n$

Altogether,

$$T(n) = c\_1(n-1) + c\_2(n-1) + c\_3n + c\_4 \frac{n(n-1)}{2} + c\_5n,$$

which simplifies to

$$ T(n) = \frac{c\_4}{2} n^2 + c\_1n + c\_2n + c\_3n - \frac{c\_4}{2} n + c\_5n - c\_1 - c\_2. $$

# Answer
Both of you get the same result, $\Theta(n^2)$.

Your calculation is more detailed, and takes into account all parts of the code. In contrast, the calculation in the textbook only considers the most significant part of the code (time-wise), and counts the number of iterations rather than the running time.

If I were writing the textbook, I would rephrase this sentence along the following lines:

> The running time of selection sort is dominated by the inner loop (5–7), which runs $\frac{n(n-1)}{2}$ times. The total running time is proportional to that, and so it is $\Theta(n^2)$.

There is no need to carry the various constants as you do. The correct way to simplify your original formula is to state that $T(n) = \Theta(n^2)$, since you can't say anything more about the constants $c\_1,\ldots,c\_5$ anyway.
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Closure of regular languages under permutation
Given a regular language $L$ over the alphabet $\Sigma = \\{a,b,c,d\\}$, is the language $\mathrm{Perm}(L)$ consisting of all permutations of words in $L$ also regular?

My intuition says it is, since each word in $L$ only has finitely many permutations, but I don't know how to prove it.

Any help would be great.

# Answer
You can consider the regular language $(ab)^\*$. We have $$ \mathrm{Perm}((ab)^\*) \cap a^\*b^\* = \\{ a^n b^n : n \geq 0 \\}, $$ which isn't regular. If you take instead $(abc)^\*$ and intersect with $a^\*b^\*c^\*$, you get the language $\\{ a^nb^nc^n : n \geq 0 \\}$, which isn't even context-free.

In contrast, the class of context-sensitive languages is closed under permutation. To see this, it suffices to observe that you can nondeterministically permute the input without any additional space (for example, by applying an arbitrary number of transpositions).
> 6 votes

# Answer
It is not regular.

Counter example:

Take $L= L((ab)^\*)$. Now look at $Perm(L)$. It is the language of all words $w$ such that $|w|\_a =|w|\_b$.

Now, show that the pumping lemma doesn't apply.

**Hint:**

Take the word $a^Nb^N$ for $N$ the pumping length.
> 3 votes

---
Tags: regular-languages
---


title: Check if two graphs are edge-disjoint

text:
# Question
Title: Check if two graphs are edge-disjoint
> Two undirected graphs $G$ and $H$ on the vertices $1,2,\ldots,n$ are disjoint if the intersection of their edge sets is empty. Assume both $G$ and $H$ are represented by adjacency matrices.
>
> Describe an efficient algorithm that decides if $G$ and $H$ are disjoint. What is the complexity of your algorithm? Justify the correctness of your algorithm and your complexity claim.

What I am thinking is just picking an arbitrary vertex on either graph like $G$ and checking if we can reach a vertex from the other graph $H$ by running some simple traversal like DFS. Is there a better way? I am thinking what if we go through the adjacency matrix of one graph and check if any edge connects a vertex from one graph to the other.

# Answer
The adjacency matrix $A\_G$ of an undirected graph $G=(V,E)$ is defined as follows: $A\_G$ is a $V \times V$ matrix, $A\_G(v,v) = 0$ for all $v \in V$, and $A\_G(u,v) = 1$ if $\\{u,v\\} \in E$ and $A\_G(u,v) = 0$ if $\\{u,v\\} \notin E$.

Two graphs $G,H$ are edge-disjoint if there doesn't exist an edge $\\{u,v\\}$ which belongs to both of them. That is, $G,H$ are edges-disjoint if there do no exist $u,v$ such that $A\_G(u,v) = A\_H(u,v) = 1$.

You take it from here.
> 1 votes

---
Tags: graphs, depth-first-search, disjoint-sets
---


title: Time complexity of computing $AA^T$

text:
# Question
Title: Time complexity of computing $AA^T$
What is the time complexity of computing $AA^T$? The context is building a co-citation weighted adjacency matrix.

# Answer
If $A$ is an $n \times m$ dense matrix then $AA^T$ is an $n\times n$ matrices given by $$ (AA^T)\_{ij} = \sum\_{k=1}^m A\_{ik} A\_{jk}. $$ This gives a $\Theta(n^2m)$ algorithm for computing $AA^T$.

If $n \geq m$ then faster algorithms exist, but they are not used in practice (at least in most situations).

If $A$ is sparse, that is, stored as a list of non-zero entries, then $AA^T$ can be calculated using different algorithms which exploit the sparsity of $A$. For example, we can sort the non-zero entries in $A$ according to the second coordinate, and then compute $AA^T$ by going over all $k$ and adding $A\_{ik} A\_{jk}$ to $(AA^T)\_{ij}$ for any $i,j$ in the list of $k$. If $s$ is the sparsity of $A$ and $s\_k$ is the number of non-zero entries with second coordinate equal to $k$, then this runs in time $$ \sum\_{k=1}^m \binom{s\_k+1}{2} \propto \sum\_{k=1}^m s\_k^2 \in \[s^2/m,s^2\]. $$ Therefore the worst-case running time is $\Theta(s^2)$, and the best-case running time is $\Theta(s^2/m)$.
> 1 votes

---
Tags: algorithms, machine-learning, matrices
---


# Question
Title: How to remove null production from context free grammar?
How to remove null production and simply the grammar?

$$ S \to a \mid Ab \mid aBa \\ A \to b \mid \epsilon \\ B \to b \mid A $$

Can the simplification result in this CFG?

$$ S \to a \mid aBa \\ A \to b \\ B \to b $$

# Answer
The given grammar is: $$ S \to a \mid Ab \mid aBa \\ A \to b \mid \epsilon \\ B \to b \mid A $$

Now the algorithm for the removal of null productions is as follows:

1. We need to find all the nullable symbols from the grammar. A nullable symbol is one that generates the null string in one or more steps.

Since $A \rightarrow \epsilon$ so the symbol $A$ is nullable.

Due to $B\rightarrow A$ we shall have $B\Rightarrow ^\* \epsilon$. So $B$ as well is nullable.

These are the only two nullable symbols in the grammar.
2. Remove all null productions in the grammar, and use substitution for the nullable symbols to incorporate the effect which could have been obtained due to their nullable nature as follows:

For each nullable symbol on the RHS of a production, rewrite the production, by once including it, and another time by not including it. Only with the exception that if due to this rewriting of rules, a null production is introduced, then just ignore that production.

So for the given grammar, we have:

For $S$ productions:

$S \to a \mid Ab \mid b \mid aBa\mid aa$

For the $A$ productions we have:

$A\to b$

For the $B$ productions we have:

$B\to b$

Since $A$ and $B$ are unit productions, they can be removed by substituting their RHS in the productions for $S$.

So the final grammar:

$S \to a \mid bb \mid b \mid aba\mid aa$
> 2 votes

# Answer
Your simplification is wrong. The language of the first grammar includes $b$, but the one of the second grammar does not.

If you replace the definition of $A$ in the productions of $B$ you obtain $B \to b \mid \epsilon$. Then if you replace $A$ and $B$ with their definition in $S$ you have.

$$ S \to a \mid bb \mid b \mid aba \mid aa $$
> 0 votes

# Answer
To remove A-\>eps, you go through all right hand sides, and add right hand sides with any combinations of A’s removed. You have a rule S-\>Ab, so you add S-\>b. And you have B-\>A, so you add B-\>eps, and that all done you remove A-\>eps.

Now you got a new null production B-\>eps, so you remove that in the same way. There’s only the rule S-\>aBa, so you add S-\>aa and remove B-\>eps.

S-\>eps cannot be removed, you need that to have an empty string in the language.
> 0 votes

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


# Question
Title: Why does Insertion sort take linear time in this case?
**Remove any 5 elements from a sorted array of n items and replace them with 5 new elements.**

Why does running **Insertion sort again on this array take linear O(n) time**, I tried counting the number of swaps when running Insertion sort again, and noticed every element is shifted by at most 5 places(not sure why), I cannot get the intuition behind why this takes linear time?

Wouldn't the new elements affect the position of the unchanged items in the array as well?

Appreciate any explanation on this!

# Answer
> 2 votes
Count the number of times each of the 5 new element is moved in the array:

The areay is of length $n$, and thus each of the 5 elements move at most $n$ times. The place of all other elements is correct, and thus there is at most $5n$ swaps required to "correct" the array, hence $O(n)$ swaps.

---
Tags: algorithms, complexity-theory, sorting, arrays
---


# Question
Title: Refine quickselect with Median of Medians to deal with duplicates
In slide 17 of this lecture note of a course at UC Berkeley, it is said concerning quickselect with median of medians:

> If there are repeated elements
>
> We can reduce to the case of no repetitions by considering the median of the array $a\_0'$, $a\_1'$, $\cdots$, $a\_n'$ where $a\_i' = (n + 1)a\_i + i$.
>
> The order is preserved and there are no repetitions.
>
> Alternatively, one has to refine the algorithm and the analysis (see CLR).

But in my copy of CLRS (2011), the authors assumed that the elements are distinct.

How would one refine the algorithm and the analysis? I'm aware that you can make elements distinct in $O(n)$, but I'm interested in the alternative.

# Answer
A common refinement to quicksort could also be used with quickselect to deal with duplicates. Instead of partitioning into two buckets, do so into three. This new partition is called the "**fat partition**". It holds items that are equal to the current pivot. When there are no duplicates, this adds 2% overhead to the sort, according to the following paper.

See https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engineering.pdf

The paper discusses several memory layouts for partition, like whether to put the fat partition in the middle or the end of the invariant array or even split it and put part at the head and part at the tail, all to reduce the number of memory swaps.

The paper quantifies the huge benefits for some extreme edge cases, like when the data is a random set of ones and zeroes. In that case, their algorithm went from being four times slower than a benchmark Unix qsort to being twice as fast, an 8x speedup by the addition of a fat partition.
> 2 votes

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


# Question
Title: Could the empty language be NP-Complete?
I think the empty language is NP but I'm not sure if it is NP-Complete

# Answer
You are correct that $\emptyset\in NP$, since we already know that $\emptyset$ can be decided in constant time (a TM that immediately rejects), and $DTIME(O(1))\subseteq P\subseteq NP$.

But $\emptyset$ is **not** NP-complete, regardless of whether $P=NP$. Indeed, by definition, a NP-complete language $A$ is such that every language $B \in NP$ admits a Karp reduction to $A$, i.e., a function $f$ that is computable in polynomial time and such that $x \in B \iff f(x) \in A$.

If $A= \emptyset$ and $B \neq \emptyset$ then no such function exists, since there is no way to satisfy $x \in B \implies f(x) \in A$.
> 3 votes

---
Tags: complexity-theory, computability, np-complete
---


# Question
Title: Prove the following claim on Hamilton Path?
I am trying to prove the following claim:

> Given DAG graph, there is Hamilton path iff the following algorithm returns true:

1. Do topologic sorting.
2. Move on the graph's vertices one by one (from low to high). In case there is no edge connecting 2 vertices with adjacent values from the topologic sorting then return false. if no false was returned after we check all vertices, return true.

---

I am stuck of proving one side which is: if there is Hamilton path then the algorithm returns true.

I tried using **induction on number of vertices in the graph** n:

* Base case is simple for n==0.
* Assuming claim is correct for n I want to prove for n+1

So I said, let's exclude the last vertex in the given Hamilton path (let's call it a), and assume by contradiction that the algorithm returned false.

This means one of the 2:

1. Two vertices with adjacent values had no edge connecting them and both aren't a. this contradictc the assumtion that the claim hold for graph with n vertices.
2. One of the two vertices is a and the other isn't a.

I am stuck on proving that case (2) will give us a contradiction, How may I continue?

# Answer
Try to prove instead (without induction) that if the algorithm returned false, there is no hamilton path.

Hint: there must be two parallel nodes. Can we reach one from the other?
> 0 votes

---
Tags: algorithms, graphs, induction, hamiltonian-path, topological-ordering
---


# Question
Title: Is the best known algorithm for the shortest path problem for an undirected and unweighted graph $O(E)$ or $O(E+V)$?
I'm a bit confused by Wikipedia's tables of algorithms for the shortest path problem.

For an unweighted graph with $E$ edges and $V$ vertices, it gives the best algorithm as breadth-first search, with a time complexity of $O(V+E)$. But above that, for an undirected graph with natural-number weights, it gives the best algorithm as an $O(E)$ algorithm due to Thorup (1999). This seems faster than the $O(V+E)$ for breadth-first search despite applying to a more general problem.

Am I correct in understanding that the $O(V+E)$ breadth-first search algorithm applies to a *directed* unweighted graph, and for an undirected and unweighted graph, Thorup's 1999 $O(E)$ algorithm is faster even though it's capable of handling arbitrary natural number edge weights? This seems surprising to me.

# Answer
To the extent of my knowledge, applying BFS on a graph (directed or undirected), starting from the "source" node and visiting only nodes that we can reach using the BFS (that is, we don't run BFS from every node if we didn't see that node already. Only one instance starting from the source node is enough), would require $O(E)$ time.

It follows since the graph BFS traverses is guaranteed to be connected, hence $\forall v:deg(v)\ge 1$. Thus $|E\_{traverse}| \ge \frac{|V\_{traverse}|}{2}$ where $E\_{traverse}$ and $V\_{traverse}$ are the sets of edges and vertices the BFS "saw" while running.

Clearly, the BFS works in $O(|E\_{traverse}|+|V\_{traverse}|)$ but since $|V\_{traverse}|=O(|E\_{traverse}|)=O(|E|)$, we can conclude that the BFS instance runs in $O(E)$.

**Note:** This is only true if the BFS is ran **only from one source**, unlike the usual BFS algorithm description that starts the traversal from a node we didn't mark yet if we finished the last traversal instance.

---

Honestly, I don't know about Thorup's algorithm, so I can't answer this part of the question about it. However, I know that BFS works for both directed and undirected graphs, but doesn't work with natural weights.
> 1 votes

# Answer
I have looked up a little bit about Thorup's algorithm (see here), but it turns out that:

> For simplicity, we assume \[…\] that the input and output size is $O(m)$

Here, $m$ is the number of edges $|E|$. This assumption in fact proves that a hypothesis for the proof is $|V| = O(|E|)$ (since $V$ is part of the input).

That means that even Thorup's algorithm runs in time $O(|V| + |E|)$.
> 0 votes

---
Tags: time-complexity, shortest-path, graph-traversal, breadth-first-search
---


# Question
Title: A state machine that is either DFA or NFA: is it possible?
I am studying Crafting Interpreters, and although I understand the responsibility of the Scanner (or Lexer), I still cannot understand if it is a deterministic finite automaton or non-deterministic finite automaton. The code responsible for scanning the input text in the book is:

```
    private void scanToken() {
        char c = advance();
        switch (c) {
            case '(': addToken(LEFT_PAREN); break;
            case ')': addToken(RIGHT_PAREN); break;
            case '{': addToken(LEFT_BRACE); break;
            case '}': addToken(RIGHT_BRACE); break;
            case ',': addToken(COMMA); break;
            case '.': addToken(DOT); break;
            case '-': addToken(MINUS); break;
            case '+': addToken(PLUS); break;
            case ';': addToken(SEMICOLON); break;
            case '*': addToken(STAR); break;
            case '!':
                addToken(match('=') ? BANG_EQUAL : BANG);
                break;
            case '=':
                addToken(match('=') ? EQUAL_EQUAL : EQUAL);
                break;
            case '<':
                addToken(match('=') ? LESS_EQUAL : LESS);
                break;
            case '>':
                addToken(match('=') ? GREATER_EQUAL : GREATER);
                break;
            case '/':
                if (match('/')) {
                    while (!isAtEnd() && peek() != '\n') {
                        advance();
                    }
                } else if (match('*')) {
                    do {
                        if (peek() == '*' && peekNext() == '/') {
                            advance();
                            advance();
                        } else {
                            advance();
                        }
                    } while (!isAtEnd());
                } else {
                    addToken(SLASH);
                }
                break;
            case ' ':
            case '\r':
            case '\t':
                // Ignore whitespace.
                break;
            case '\n':
                line++;
                break;
            case '"': string(); break;
            default:
                if (isDigit(c)) {
                    number();
                } else if (isAlpha(c)) {
                    identifier();
                } else {
                    Lox.error(line, "Unexpected character.");
                }
                break;
        }
    }

```

According to several sites out there, the FA definition is:

> Finite Automata(FA) is the simplest machine to recognize patterns.The finite automata or finite state machine is an abstract machine which have five elements or tuple. It has a set of states and rules for moving from one state to another but it depends upon the applied input symbol. Basically it is an abstract model of digital computer. Following figure shows some essential features of a general automation.

A DFS consists of the following:

```
Q : Finite set of states.
Σ : set of Input Symbols.
q : Initial state.
F : set of Final States.
δ : Transition Function.

```

and for NFA:

```
Q : set of all states.
Σ : set of input symbols. ( Symbols which machine takes as input )
q : Initial state. ( Starting state of a machine )
F : set of final state.
δ : Transition Function, defined as δ : Q X Σ --> Q.

```

My lexer can start in any state, does that mean it is either DFA or NFA? How can I conclude if it is one or the other?

# Answer
> 1 votes
Any piece of code can never be non-deterministic (a non-deterministic process can "multiply itself" by a constant factor every step, and obviously computers can't just multiply by their own free will).

Hence it is a DFA.

---

Also, your lexer will start always at the initial state $s\_0$, and from it, depending on what it reads - it moves to different states.

# Answer
> 1 votes
The difference between NFAs and DFAs is not so huge, because you can trivially convert an NFA into a DFA simply by using the elements of the power set of the states of the NFA as the states of a DFA.

Usually, not all the elements of the power set turn out to be accessible, so the DFA is not as huge as this transformation makes it sound. But there are some NFAs whose transformation into a DFA involves exponential blow-up.

It's possible to emulate an NFA reasonably efficiently by implicitly using the power-set transformation without actually computing the entire transformation matrix, and this is done by many regular expression libraries. If you represent the powerset as a binary vector, it's easy to use it as a hash table key; the hash table is used to cache particular values of the transition function. The cache is capped at a certain size in order to avoid memory exhaustion; if the traverse of the NFA requires more powerset elements than can fit in the cache, some of them will be dropped from the cache and recomputed when necessary. (The recomputation doesn't take much time; although it is theoretically $O(|Q|^2)$ where $|Q|$ is the number of states in the NFA, in practice storing state sets as bit vectors means that the set union operation can be done with a single bitwise boolean operation, or a few such operations if there are really a lot of states in the NFA.)

Lexical scanner generators often precompute the entire DFA, on the assumption that the scanner descriptions they will be handling don't involve exponential blow-up. If that assumption is wrong, the scanner generator will either take an enormous amount of time to process the scanner description, or will fail because of memory exhaustion, or both. With a little work, you can create a fairly short scanner description that flex cannot handle. But practical programming languages rarely include these kinds of lexical constructs.

The key difference between a regular expression library and a scanner generator is that the regular expression library is doing its work at runtime, and possibly using a user-supplied regular expression. So the regular expression library needs to avoid algorithms which could take exponential time, in order to prevent denial-of-service (DoS) attacks. (Or at least, the library should avoid such vulnerabilities. Not all of them do.)

The scanner generator, on the other hand, is executed once when the scanner is compiled using a lexical definition supplied by the programmer. If that definition involves exponential blow-up, the programmer will have to fix it or live with very slow compile times, just as with any other compilation issue. No runtime vulnerability is involved. (At least, that's the usual use case. There are a few applications which might call a scanner generator at runtime using a user-supplied input; putting an application like that into production would require some kind of protection against denial-of-service attacks. But that's not the context in which flex is generally used.)

The particular code you present in your question was not generated either by a scanner generator nor a regular expression library. It's mostly a very simple DFA, where the first character of the token defines the only state transition. (Identifiers and numbers involve functions which may well be implemented with slightly more complex state machines, or which might use standard library functions or some other idiosyncratic technique. But either way they have probably been precompiled into the equivalent of a DFA by a programmer.)

There is one place in the code which is visibly not emulating a finite-state automaton at all: the code to recognise comments includes a two-character lookahead and fallback, which is not how a comment would be recognised by a finite automaton (NFA or DFA). In that sense, I would agree with the commenter (to a previous version of this question, now deleted) who said that the program is neither an NFA nor a DFA; rather, it's a computer program. But it's interesting how little state is used by the program; there is only one local variable, which is the character being processed.

---
Tags: finite-automata, compilers, parsers
---