title: Regularity of CFG and DCFL

text:
# Question
Title: Regularity of CFG and DCFL
I read that it is undecidable whether, given a CFG $G$, $L(G)$ is regular. And there exists no algorithm that, given a CFG $G$ such that $L(G)$ is regular, outputs a DFA that accepts $L(G)$.

My question is, why is regularity decidable for DCFLs and undecidable for CFLs?

# Answer
> 2 votes
Your question unfortunately doesn't have a simple answer. The best I can do is go over the proofs and point out where they fail when trying to apply them to the other class.

**Regularity of the language generated by a CFG**

The proof that regularity of the language generated by a CFG is undecidable is very similar to the proof that *universality* of the language generated by a CFG is undecidable, so we'll start with the latter. The proof proceeds by reduction from the halting problem. Given a Turing machine $M$, we construct a context-free grammar $G$ with the following property:

* If $M$ doesn't halt on the empty input, then $G$ is universal, that is, $L(G) = \Sigma^\*$.
* If $M$ does halt on the empty input, then $L(G) = \Sigma^\* \setminus \\{t\\}$, where $t$ is a transcript of the execution of $M$ on the empty input.

We encode transcripts as sequences of configurations: $c\_1 \\# c\_2 \\# \cdots \\# c\_n$. Here each $c\_i$ is a configuration (the contents of the tape together with the location of the head and the current state), and $c\_{i+1}$ is the configuration following $c\_i$. The grammar $G$ describes all strings which are *not* transcripts of halting executions. A string fails to be such a transcript if one of the following cases holds:

* It is not of the form $c\_1\\#c\_2\\#\cdots\\#c\_n$, where $c\_1,\ldots,c\_n$ are valid configurations.
* The transcript is of the form $c\_1\\#c\_2\cdots\\#c\_n$, where $c\_1$ is not a valid initial configuration.
* The transcript is of the form $c\_1\\#c\_2\cdots\\#c\_n$, where $c\_n$ is not a valid halting configuration.
* The transcript is of the form $c\_1\\#c\_2\cdots\\#c\_n$, and for some $i$, the configuration $c\_{i+1}$ doesn't follow from the configuration $c\_i$.

The first three cases represent regular constraints, and see are easy to handle (and could be handled by a DPDA). The problematic case is the final one: while it is easy to describe bad stretches of the form $\\#c\_i\\#c\_{i+1}\\#$, the grammar has to "guess" the value of $i$. Indeed, consider the special case $n=3$, and take the point of view of a PDA. The PDA has to guess whether it should be comparing $c\_1$ to $c\_2$, or whether it should skip $c\_1$ and instead compare $c\_2$ to $c\_3$. This is something that a DPDA cannot do.

*From universality to regularity.* In the construction outlined above, the language $L(G)$ is regular in both cases. However, given $G$, we can construct another grammar $G'$ that accepts the language $$ \\{a^n b^m \\# w : n,m \ge 0, w \in L(G)\\} \cup \\{a^n b^n \\# w : n \ge 0, w \in \Sigma^\*\\} $$ By construction,

* If $M$ doesn't halt on the empty input then $L(G') = a^\*b^\*\\#\Sigma^\*$, which is regular.
* If $M$ does halt on the empty input then $L(G') = \Sigma^\* \setminus \\{a^nb^m\\#t : n \neq m\\}$, which isn't regular.

**Regularity of the language accepted by a DPDA**

There are several proofs that the regularity of the language accepted by a DPDA is decidable. Here I will outline the original proofs of Stearns and Valiant, but a newer and more efficient algorithm of Shankar and Adiga, A graph-based regularity test for deterministic context-free languages, should also be mentioned.

Given a DPDA, we would like to show that if the language it accepts is regular, then it is accepted by a DFA with at most $N$ many states, where $N$ is a quantity that depends in some explicit computable way on the number of states, number of state symbols, and maximum number of symbols pushed at a single step of the DPDA.

Suppose we somehow showed that. How do we proceed? We go over all DFAs having at most $N$ many states, and for each one, check whether it accepts the same language as the DPDA. Denote the DPDA by $P$ and the candidate DFA by $D$. We first check whether $L(P) \cap \overline{L(D)} = \emptyset$, that is, whether $L(D) \subseteq L(P)$. We can do this by combining three constructions:

1. Given a DFA, we can construct a DFA for the complement language.
2. Given a PDA and a DFA, we can construct a PDA for the intersection language.
3. Given a PDA, we can solve the emptiness problem, that is, determine whether the language is empty.

We then check whether $\overline{L(P)} \cap L(D) = \emptyset$ using a similar approach, crucially using the fact that given a DPDA, we can construct a DPDA for the complement language. If both tests pass, then $L(P) = L(D)$.

In contrast, CFLs are not closed under complementation, and in particular, given a PDA, we cannot in general construct a PDA for the complement language. Moreover, as shown above, we cannot decide if a PDA generates the same language as a given DFA; indeed, even the special case of universality is undecidable.

Now let us go back to the first part of the proof, in which we give a bound on the number of states in an equivalent DFA. Unfortunately this part of the proof is somewhat complicated. Roughly speaking, we show that if at some point of the execution the stack is very deep, then the first few symbols on the stack are too deep to make a difference; otherwise, we can "pump" the input in some way that guarantees that the language accepted by the DPDA is not regular. This implies that in order to simulate the DPDA, it suffices to keep track of a constant number of symbols on the stack, which a DFA can do.

The undecidability proof for CFGs shows that a similar statement is wrong for PDAs. More accurately, while there is still a bound on the number of states in an equivalent DFA, it cannot be computed from the complexity parameters of the PDA since it grows too fast. Indeed, for the grammar $G$ we construct in the undecidability proof, in the case where the machine $M$ halts, the size of the equivalent DFA is essentially the same as the size of the transcript $t$, and so it grows faster than the number of steps it takes $M$ to halt. The maximal number of steps in an equivalent minimal DFA is thus some sort of busy beaver function, which grows too fast to be computable.

# Answer
> 2 votes
Structurally the classes CFL and DCFL have very different closure properties. CFL are closed under union, but not under complement. DCFL are not closed under union, but closed under complement.

The undecidability of regularity for CFL is usually obtained from two properties of the context-free languages: (1) they are closed under union, and (2) universality, i.e., equality to $\Sigma^\*$, is undecidable.

To the contrary, DCFL (1) are not closed under union, (2) have decidable universality. The latter for instance, because DCFL are closed under complement, and emptiness is decidable (in fact for all CFL).

---
Tags: regular-languages, finite-automata, context-free, undecidability, decidability
---


title: simulate PDA using LBA

text:
# Question
Title: simulate PDA using LBA
0. urestricted -\> turing machine
1. context-sensitive -\> linear bounded automaton (LBA)
2. context-free -\> pushdown automaton (PDA)
3. regular -\> finite state machine

Hi, I am kind of confused about relation between LBA and PDA.

Is the stack in pushdown automaton bounded (not using infinite space)?

If not, how can a LBA accept a language that PDA accepts? (How can one simulate a PDA with unbounded stack using a linear **bounded** automaton?)

# Answer
> 1 votes
The stack in a pushdown automaton is *not* bounded in general. For example, consider the machine which accepts $\\{a^nb^n : n \geq 0\\}$ by pushing and then popping $A$s. Indeed, if the stack is guaranteed to be bounded, then we might as well store it as part of the state, converting the PDA into an NFA.

However, by tweaking the PDA, we can ensure that the depth of the stack is *linear* in the number of symbols read so far, and in particular, linear in the input size. This allows us to simulate the PDA on an LBA, by using a "parallel track".

---
Tags: chomsky-hierarchy
---


# Question
Title: On the relation between several graph parameters
Recently, I came across several parameters of graphs. So I know in general graphs, it might be hard to compare between them, but I'd like to try and see which upper/lower bounds can be made.

Some parameters are: arboricity $a(G)$, maximal degree $\Delta(G)$, degeneracy $d(G)$, minimal degree $\delta(G)$, chromatic number $\chi(G)$.

So ofcourse $\delta(G) \leq \Delta(G)$. Also by definition: $d(G)\leq \Delta(G)$. And also $\chi(G) \leq d(G)$.

If we direct each edge to its parents, then $d(G) \leq a(G)$. I read that $a(G) \leq 2\cdot d(G)-1$, because the amount of edges is at most $(|V|-1)\cdot a(G)$. I understand why this is an upper bound to the amount of edges. But why does this imply $a(G) \leq 2\cdot d(G)-1$?

And apart from being smaller than the arboricity, can we bound the pseudoarboricity?

Also, if there are any more inequalities or bounds that can be made using these parameters, I'd be interested to know.

And if there are bounds which require the use of additional parameters, this is also interesting to me.

# Answer
> 1 votes
Your post asks several questions. I will only answer the first one, why $d(G) \leq 2a(G) - 1$, following the exposition in notes of Steven Butler.

As you mention, a graph of arboricity $a(G)$ contains at most $(|V|-1) a(G)$ many edges, and so the average degree is at most $\frac{2(|V|-1) a(G)}{|V|} \< 2a(G)$. Consequently, there is a vertex whose degree is $2a(G) - 1$. Since the arboricity of a subgraph of $G$ is always at most $a(G)$, every subgraph of $G$ has a vertex of degree at most $2a(G) - 1$.

---
Tags: graphs, colorings
---


# Question
Title: Regular expression for all a* except aa?
I'm stumped on how you would describe a language which is a\* except for aa, so the following is acceptable:

```
a
aaa
aaaa
aaaaa
...

```

It's for part of the below DFA

# Answer
Hint: A word consisting of $n \neq 2$ many $a$s either consists of zero $a$s, or of a single $a$, or of at least three many $a$s.
> 2 votes

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


# Question
Title: How many RAM chips of size 256k x 1 bit are required to build 1M Byte memory
$$1MBytes =1024\*1024\*8$$ $$256k\*1bit=256\*1024$$ $$1MBytes = \frac{1024\*1024\*8}{256\*1024}=32$$

Now my question is that for converting 1MByte to bit level we need 1024\*1024\*8 but 256K is not converted the same way why (256\*1024\*8)bit? why we don't multiply with 8 at last since it is kilobyte than byte than bit.

# Answer
> 1 votes
Because you're trying to make a one mega**byte** RAM from a collection of 256 kilo**bit** chips.

# Answer
> 1 votes
No. of RAM chips=1MB/256K=1024x1024x8/256x1024 =32.

---
Tags: computer-architecture
---


title: Interactive sort for only top elements

text:
# Question
Title: Interactive sort for only top elements
I have a set of objects and a set of comparison results for some of them.

I want an algorithm that returns the next comparison I should make to two objects towards having a way to know the full order of all objects. If the order of all objects can be already known I should get the objects ordered.

Requirements: ask for the minimal number of comparisons between objects as they are the most expensive operation.

For example: I know elements A,B,C,D and relations A-\>B , A-\>C , B-\>D , C-\>D the algorithm should return next pair to compare B and C

# Answer
> 1 votes
A similar question has been considered in the literature: given a poset $P$ and a list of elements whose order is consistent with $P$, how many comparisons are needed in order to order the list? If there are $e(P)$ many extensions of $P$ to a linear order, then clearly at least $\log\_2 e(P)$ many comparisons are needed. Conversely, Kislytsin and Fredman showed (separately) that $\log\_2 e(P) + 2n$ comparisons suffice, but their algorithms cannot be implemented efficiently. Kahn and Kim gave in their classic paper Entropy and Sorting an efficient algorithm which uses $O(\log e(P))$ comparisons.

While these results might have been improved along the years (you can check this by going over papers citing Kahn–Kim), it might be too much to ask for an *optimal* algorithm which can be implemented efficiently.

---
Tags: algorithms, ordering
---


# Question
Title: Why REC languages is undecidable under emptiness and finiteness?
Membership problem of Recursive languages are decidable.

**My approach:**

Let $L$ be a recursive language and $M$ be the Turing Machine that accepts it. For string $w,$ if $w ∈ L,$ then $M$ halts in final state. If $w ∉ L,$ then $M$ halts in non-final state. (halts always!). That's why Recursive languages are decidable for Membership problem

My question is in same logic, why finiteness, emptiness is undecidable? Don't want any concrete proof. I just want brief concepts like my approach.

# Answer
> 4 votes
To decide whether a language is empty you'd have to run $M$ on **all** possible input strings and verify that $M$ always rejects. How are you going to do that in a way that ensures that your algorithm always terminates?

Similarly, to decide whether $L$ is finite you'd have to check that $M$ rejects almost always, i.e., always except for at most a finite number of inputs.

Formally, you can reduce the halting problem to problem of deciding whether a language $L$, encoded as a decider machine for $L$, is empty/finite.

For example, given Turing machine $T$ you can define a Turing machine $T'$ that takes a string $x$ as input and simulates $T$ on empty input for $|x|$ steps. If the simulation ends, $T'$ accepts. Otherwise $T'$ rejects. Then, you can decide if $T$ halts on empty input by checking if the language recognized by $T'$ is not empty.

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


title: Convert regex pattern to LL1 parser

text:
# Question
Title: Convert regex pattern to LL1 parser
Background: I'm trying to solve this leetcode problem: regular-expression-matching. My approach is to implement a LL(1) parser generator, might be overkilling for this problem but it's just a brain exercise.

I only have entry level knowledge of parser theory, so excuse me if this is a silly question that I ask.

So, there's this testcase that I fail. Requirement is regex pattern should match the whole string

```
Regex: a*a
Input: aaa

```

I cannot wrap my mind about how to convert this pattern into a LL(1) parser.

The way I see it, `a*a` pattern can be converted into production rules:

```
S -> Aa      # a*a
A -> aA | ε  # a*

```

Parse table:

|  | a | $ |
| --- | --- | --- |
| S | S -\> Aa |  |
| A | A -\> aA | A -\> ε |

Here's the steps to parse:

```
0: S$    aaa$  # use [S,a]
1: Aa$   aaa$  # use [A,a]
2: aAa$  aaa$  # eat 'a'
3: Aa$   aa$   # use [A,a]
4: aAa$  aa$   # eat 'a'
5: Aa$   a$    # use [A,a]
6: aAa$  a$    # eat 'a'
7: Aa$   $     # use [A,$]
8: a$    $     # Error!

```

The correct matching should be:

```
a* -> aa
a -> a

```

But what I get instead is:

```
a* -> aaa
a -> Error!

```

I don't know which part I'm missing . Is this problem even solvable using LL(1)?

# Answer
> 1 votes
No, it's not possible in general. There's no guarantee that a regular expression be LL(1), not even the simplified form of regular expressions required by that exercise, and the example you provide is a perfect illustration.

To be LL(1), it must be possible to work out which production to match based only on the parse up to that point and the first symbol in the input. ("First symbol" because it's LL(**1**).) But that's not possible for your grammar; in general, it's not possible to decide between $A\to\epsilon$ and $A\to a A$, because the fact that the next symbol is an $a$ doesn't give you enough information to decide between them.

In slightly more technical terms, that happens because $A$ is *nullable* (matches the empty string) and $FIRST(A) \cap FOLLOW(A) \ne \emptyset$.

In fact, grammars derived from regular expressions (in the way you show) are not guaranteed to be unambiguous, and an ambiguous grammar cannot be deterministically parsed (by definition). Your grammar is unambiguous, but that wouldn't be the case for $.^\*a^\*$ (strings ending with one or more $a$s).

---
Tags: regular-expressions, parsers
---


# Question
Title: Prove 2 cups contain the same number of marbles without revealing quantity
I have seen proofs of this particular problem in a few articles/papers (which lead to a ZKP 2 nuclear warheads are similar), but I find a problem in the proof with the marbles - surely the proof doesn't work because the experiment cannot be repeated.

Proof outline:

1. The prover claims a pair of cups each contain $n$ marbles and for some $N$, $1 \leq n \leq N$.
2. The prover prepares a pair of buckets and claims each contain $N-n$ marbles.
3. The prover pours each cup of marbles into a different bucket, but the verifier chooses which cup goes into which bucket.
4. The verifier confirms each bucket now contains $N$ marbles.
5. This can be repeated an arbritrary number of times until the verifier is satisfied.

Is there a way this proof can be rectified? (I'm assuming the marbles aren't necessarily identical so weighing won't work)

http://cvt.engin.umich.edu/wp-content/uploads/sites/173/2014/10/Glaser-Nature-Article.pdf https://www.latimes.com/science/sciencenow/la-sci-sn-verification-nuclear-disarmament-20140625-story.html

# Answer
Add $m - 2$ more pairs of cups. The prover claims that the first $m$ cups (including the two original ones) contain $n$ marbles, and the second $m$ cups contain $N-n$ marbles. You choose a matching between the two $m$-tuples, the prover pours the cups, and you check that they all contain $N$ marbles.

If the two original cups contained the same amount of marbles, then the prover will always win. Otherwise, suppose that the first $m$ cups contain $k$ different amounts of marbles, with $c\_1,\ldots,c\_k$ copies each (so $c\_1 + \cdots + c\_k = m$). For the prover to have any chance of winning, we need the second $m$ cups to be partitioned similarly. Out of the $m!$ many partitions that the verifier chooses, the number of ones for which the proof goes through is $c\_1! \cdots c\_k!$, hence the success probability is $$ \frac{c\_1! \cdots c\_k!}{m!}. $$ Let us now notice that if $a \geq b \geq 2$ then $$ (a+1)! (b-1)! = \frac{a+1}{b} a! b! \> a! b!. $$ Therefore the quantity $c\_1! \cdot c\_k!$ is maximized, subject to $c\_1,\ldots,c\_k \geq 1$ and $c\_1 + \cdots + c\_k = m$, when $c\_1 = m-k+1$ and $c\_2 = \cdots = c\_k = 1$, that is, $$ \frac{c\_1! \cdots c\_k!}{m!} \leq \frac{(m-k+1)!}{m!} \leq \frac{(m-1)!}{m!} = \frac{1}{m}, $$ since $k \geq 2$ (recall the prover is trying to cheat now!).

While this is less efficient than standard zero-knowledge proofs (in which the error probability decreases exponentially in the amount of work), this does show that you can get the error as small as you want.
> 1 votes

---
Tags: zero-knowledge-proofs
---


# Question
Title: Can you help me provide some examples of 3-co-SAT?
Recently I'm studying 3SAT problem, which is a NP-complete problem. I feel that it's easy to find a boolean formula which is satisfiable,but how about boolean formulas which are unsatisfiable， namely 3-co-SAT problem. Can you help me provide some examples of 3-co-SAT?

The definition of 3SAT problem is supplemented here, which is quoted from the book Computational Theory.

> 3SAT = {$\<\phi\>|\phi$ is a satisfiable 3cnf-formula}

Then the definition of 3-co-SAT is

> 3-co-SAT = {$\<\phi\>|\phi$ is an unsatisfiable 3cnf-formula}

Is there any problem about the definition of the above sat, 3-co-sat problem?

Can you help me provide some examples of 3-co-SAT?

# Answer
> 1 votes
The formula $$(x\vee y \vee z) \wedge (\overline{x}\vee y \vee z) \wedge(x\vee \overline{y} \vee z) \wedge(x\vee y \vee \overline{z}) \wedge(\overline{x}\vee \overline{y} \vee z) \wedge(\overline{x}\vee y \vee \overline{z}) \wedge(x\vee \overline{y} \vee \overline{z}) \wedge(\overline{x}\vee \overline{y} \vee \overline{z})$$ is in $3$-co-SAT.

# Answer
> 1 votes
1. Pick any unsatisfiable CNF SAT instance.
2. Transform the CNF to 3-SAT.
3. The new instance is an element of 3-co-SAT.

Any unsatisfiable satisfiability instance undergoing the same 3-SAT CNF transformation is an example of 3-co-SAT.

---
Tags: algorithms, complexity-theory, turing-machines, np, co-np
---


# Question
Title: Is this divide-and-conquer algorithm O(n)?
Yesterday I came up with a divide-and-conquer algorithm about all subarrays of length k of an array of length n. Outline:

```
function solve(array, k):
   if array shorter than k:
      return default value
   left = solve(left half of array, k)
   right = solve(right half of array, k)
   middle_crossing = combine(left half of array, right half of array, k)
   return max(left, right, middle_crossing)

```

Make the array a "view" or a begin/end index pair, so passing an array half is O(1). And the `combine` operation takes O(k).

At first sight its structure looks like for example mergesort, so might take O(n log n). But it's faster for two reasons:

* The recursion doesn't go all the way down to length 1. Only to length k.
* The `combine` operation doesn't take O(n), only O(k).

So we have this runtime:

```
T(n) = { 2 * T(n/2) + O(k)    if n >= k
       { O(1)                 otherwise

```

I believe the total runtime is T(n) = O(n). One way to I think prove it:

We recurse only down to length k. So instead of finding the runtime `T(n)` as number of element-operations given n elements, consider the array of n elements as an array of n/k *blocks* of k elements each, and find the runtime `B(n)` as number of *block*-operations. Since each block-operation takes O(k) time, we have:

```
T(n) = B(n/k) * O(k)
B(m) = 2 * B(m/2) + O(1)

```

Master theorem (or just thinking) gives `B(m) = O(m)` and thus we have:

```
T(n) = B(n/k) * O(k) = O(n/k) * O(k) = O(n)

```

Is that right? Is it O(n), and is my proof correct? And does this *"consider blocks"* technique have a name (I haven't seen it before)? Or is there a better way to prove it?

# Answer
You can easily compute the height $h$ and the total number of nodes in the recurrence tree. After $h-1$ levels, the size of the subproblem is at least $k$ and at most $2k$. Therefore, $n/2^{h-1} \geq k$ after $h-1$ levels. Thus, we get the height of the tree at most $\log (n/k)+1$. Furthermore, the total nodes in the recurrence tree is at most $O(2^{\log n/k+1}) = O(n/k)$.

At every node of the tree, the algorithm is doing $O(k)$ operations. Therefore, the overall running time is $O(n)$
> 1 votes

---
Tags: algorithms, complexity-theory, time-complexity, divide-and-conquer
---


# Question
Title: Assigning balls to bins with constraints
Let $S= \\{ b\_{11}, b\_{12}, b\_{21}, b\_{22}, b\_{31}, b\_{32},\dots, b\_{n1}, b\_{n2} \\}$ be a set of $2n$ balls grouped in $n$ pairs, and $T = \\{ B\_1, B\_2, \dots, B\_m\\}$ be a set of $m$ bins with capacities $\overline B\_{1}, \overline B\_{2}, \dots, \overline B\_{m}$, respectively. Considering that each ball is stored in exactly one bin, the problem is to find the maximum number of balls that can be stored in those $m$ bins under the following two constraints. First, for each ball $b\_{ij}$ there is a set of bins $\hat B\_{ij}$ such that $b\_{ij}$ can only be stored in a bin in $\hat B\_{ij}$. Second, balls forming a pair (e.g., $b\_{21}$ and $b\_{22}$) cannot be stored in the same bin.

My attempt consists of modelling this problem as a max-flow problem and then running the Ford–Fulkerson algorithm. I've built a graph $G$ with starting node $s$ and ending point $t$. The first layer of nodes are the $2n$ balls, and my second layer of nodes are the $m$ bins. The first layer and second layer are connected to match the first constraint and the capacity of those edges are all equal to one. All the nodes of the second layer are connected to the ending node $t$, and their capacities are $\overline B\_{1}, \overline B\_{2}, \dots, \overline B\_{m}$. I don't know how to connect the starting node $s$ to the first layer of nodes and what the capacity of those edges should. It seems that it doesn't matter, but I'm not sure. Also, I don't know how to handle the second constraint.

# Answer
You are on the right track.

Connect the starting node $s$ to each node in the first layer with an edge of capacity one.

Since the balls $b\_{i1}$ and $b\_{i2}$ cannot stored in the same bin, for each bin $X$ in $\hat B\_{i1}\cap\hat B\_{i2}$, instead of connecting $b\_{i1}$ and $b\_{i2}$ directly to the node $X$ in the second layer,

* construct a node $c\_{i,X}$ that connects to $X$ with capacity 1.
* connect $b\_{i1}$ to $c\_{i,X}$ with an edge of capacity one.
* connect $b\_{i2}$ to $c\_{i,X}$ with an edge of capacity one.
> 1 votes

---
Tags: algorithms, graphs, optimization, discrete-mathematics, network-flow
---


# Question
Title: Integer-only computation rounds down fractions in division require extra work?
In integer-only computation, a fraction like 5/2 is rounded down to 2. Is this any extra work at the ALU level, or, is the way it does division, at the level of logical gates, automatically outputting the rounded down result as standard?

# Answer
Division is hard and slow.

The typical process to divide x by a non-zero y on a fast modern processor goes like this:

Step 1: Multiply y by 2^k, k even, such that y \<= x \< 4. Initialise the result to 0.

Step 2: Find the largest integer m such m*y \<= x \< (m+1) y; replace result with (result \<\< 2) + m, x with x - m*y, y with y \>\> 2. If k ≠ 0 then k = k-2 and back to Step 2.

The hardware to determine m will be limited so it can pick an m that is a little bit too low, for example it might pick m = 2 if x ≈ 3.001m, so the m in the next round could be 4, and after the last round the remainder might be x ≥ y. So we add

Step 3: If x \>= y then increase result by 1, subtract y from x.

As you see, there isn't actually any way to produce a fraction.

Some additional steps are needed to handle y = 0, and to handle negative numbers, including the notorious case that say for 32 bit numbers, (-2^31) / (-1) = 2^31 is too large to fit into a signed 32 bit integer.

Note that the hardware automatically produces x modulo y at the same time.
> 2 votes

---
Tags: integers
---


# Question
Title: Is Brainfuck, but you can only move the tape into one direction or rewind it to the beginning, Turing complete?
If you take Brainfuck and modify '\<' to move the tape head to the beginning of the tape, would this modified Brainfuck still be Turing complete?

It feels like it should be, but I can't wrap my head around how you'd emulate a Turing machine using (or proper Brainfuck for that matter). It feels like you'd need to come up with a scheme to partition the tape in a way that allows you to address certain points in the memory.

# Answer
> 0 votes
It is Turing complete. The details depend a bit on whether the tape and/or the numbers in the cells are unbounded. (If neither are, then even regular Brainfuck is not Turing complete.)

If the cells can hold unbounded integers, then we can easily use $k$ cells to simulate a $k$-counter machine. Those are Turing complete already for $k = 2$.

If the tape is infinite, we can simulate regular Brainfuck as follows. Partition the tape into pairs of cells, each of which simulates a single regular BF cell. The idea is that cell $2n$ contains a $1$ if the simulated pointer is at that pair and $0$ if not, and cell $2n+1$ holds the contents of the simulated cell. When we start to execute a simulated instruction, the pointer is on top of the $1$ at cell $2n$.

If we want to read or modify the current cell's value, just step right, perform the operation, return to the origin, and step 2 cells to the right until we see a $1$. If we want to take a step right, we decrement, move right twice, and increment.

The difficult part is moving the simulated pointer to the left. To do this, we return to the origin and increment. Now we have two simulated cells with a $1$ on the even part. Then we repeatedly move the leftmost $1$ one cell to the right (as if simulating a step to the right) until the next simulated cell also contains a $1$. In that case we break out of the loop, remove said $1$, return to the origin and walk to the remaining $1$ two steps at a time.

---
Tags: turing-machines
---


title: Compilation speed dependent on CPU?

text:
# Question
Title: Compilation speed dependent on CPU?
Is the speed of compiling software very dependent on the CPU? I know this question is a bit broad, but I'm to find an answer to the case described below.

If I download a software project that makes use of Node.js, TypeScript, and JavaScript and compile it running `yarn` it takes a certain duration on `machine A` and another duration on `machine B`. In my test case `machine A` is equipped with an `Intel i5-4570` and `machine B` is equipped with an `AMD Ryzen 5 1600x`. Both have 16 GB RAM and both also have similar SSD drives in use.

Now, if I run the software compilation on both machines, `machine A` takes about 1:30min and `machine B` takes about 1:20min. Hence, `machine B` is not significantly faster, even though the CPUs are quite different in capability and get different scores according to CpuBenchmark:

The single core rating of both CPUs is quite similar at around 2000 Points, but when I run compilation all cores move up to 100% according to system power statistics.

I also checked the network usage, but doesn't move over 10kB/s and is therefore negligible. The RAM use fluctuates within about 1GB in both systems between 9GB and 10GB.

Now, as the expected results differ quite intensly to the reality, I obviously am missing a point. So, an experienced input of some of you guys would very much help.

Is there anything else I could measure? Is there anything I missed or maybe don't know and therefore should further test? I basically want to find out, why the Ryzen is not significantly faster than the Intel mentioned above.

# Answer
Things you are missing is

* RAM performance: Intel CPUs has lower memory latency, and compilation speed significantly depends on memory latencies
* Amount of cores/threads: each Ryzen core is slightly slower than Intel core, but it has 1.5x more cores, and each core can run 2 threads. This makes it 1.5x faster for ideal multi-threaded tasks (like benchmarks), but real programs may be not ideally scale from 4 to 12 threads
* SSD speed, in particular 4K IOPS (i.e. speed of reading many small files)

F.e. first test on this page compares C++ compile times on various Intel/AMD CPUs:

* 8700K: Intel 6-core
* 7820X: Intel 8-core with slower memory controller
* 2700X: AMD 8-core
* 2600X: AMD 6-core

As you can see, Intel 6 cores outperformed AMD 8 cores and even Intel's own 8 cores coupled with slower memory controller.

And this page discusses a lot memory/cache latencies.
> 2 votes

# Answer
The amount of cores is important only for very large projects when compilation takes at least 15+ minutes. Try building OpenCV from scratch, for example.

Your project build time is very moderate thus single-core performance (+ RAM, disk performance) is what makes the difference.

According to the links you've posted both processors have similar single-core benchmark scores:

```
AMD Ryzen 5 1600X: Single Thread Rating: 2187
Intel Core i5-4570 @ 3.20GHz: Single Thread Rating: 2028

```

They are almost the same, as you said, system A makes it in 1:30, the system B in 1:20. Looking at the single-core score you can tell that AMD Ryzen 5 1600X's score is `159` more. This is the 10 seconds difference you get.

If you want even fast build time, look for a processor that has even better single-core performance. You'll definitely get what you've paid for.
> 1 votes

# Answer
A major factor is how many threads the build system can use. Some code that I fortunately don't have to build too often uses a single threaded build system - so you could have a machine with sixteen cores of which 15 are doing nothing.

One effect I had once was using a machine with not enough RAM. Eight threads tried to compile simultaneously, running out of RAM and thrashing virtual memory. Restricting the compiler to four threads ran faster.

What makes much more difference than the CPU is making sure you use the compiler at its best. I have seen using pre-compiled header files reduce compile time to a quarter.
> 0 votes

---
Tags: compilers, cpu
---


# Question
Title: Is the clique problem polynomial-time solvable still in unit disk graphs allowing different sized disks?
Clark *et al.* proved that the clique problem is polynomial-time solvable in unit disk graphs. Does anyone know if this result holds still if the disks are allowed to be different sizes? Or do such "non-unit disk graphs" in fact constitute all graphs, and thus the clique problem is NP-hard again? (I've been able to draw some of the impossible unit disk graphs found here with different sized disks.)

EDIT: as stated in the comments, disk graphs are a strict subset of graphs. In this paper the authors give an example: $K\_{3,3}$ is not a disk graph.

# Answer
> 2 votes
## This is an open problem

In a paper from 2020, *Maximum Clique in Disk-Like Intersection Graphs* by Édouard Bonnet, Nicolas Grelier, and Tillmann Miltzow, the authors note in the abstract that

> (...) The main open question (...) is the complexity of Maximum Clique in disk graphs. It is not known whether this problem is NP-hard.

and proceed to present their results, which can be seen as progress towards proving the problem one way or another.

---
Tags: graphs, np-hard, polynomial-time, clique
---


# Question
Title: Difference between Counter-machine and stack machine
I read from this question that counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol).

My question is counter machine means counter coexist with stack? I mean "DFA $+ 1$ counter" is same thing with "DFA $+1$ stack" . For example to generate this language $\\{a^n b^n \mid n\geq 0\\}$ we need counter + stack.

I also from that question **Languages recognized by one counter automata form a proper subset of the context free languages.** What does it mean? Could you give one example.

# Answer
> 1 votes
You can recognize $\\{a^nb^n\\}$ with just a counter (which is incremented by an $a$ and decremented by a $b$). No additional stack is needed. (If you used a stack, it would only contain $a$s; in general a counter is functionally equivalent to a stack whose alphabet consists of only one symbol.)

The answer to the question you link to provides an example of a deterministic context free language which cannot be recognised by a one-counter automaton: $\\{a^nb^ma^mb^n\\}$.

---
Tags: formal-languages, computability, automata, context-free, pushdown-automata
---


# Question
Title: Prove language is not Turing-recognizable using contradiction
Show that the language L = {\<M\>| M is a TM and does not accept \<M\>} is not Turing-recognizable.

Note: Prove by contradiction. No need for reduction.

This is the problem I am trying to solve. I'm confused on how to do this without using reduction.

# Answer
Let's suppose that the language $L$ is decidable, so then exists a Turing Machine $M'$ such that $M'$ stops for all inputs (doesn't loop infinitely) and that $L(M') = L $.

If $\omega$ is the codification for $M'$, What happens with $M'$ with input $\omega$?

$M$' accepts $\omega$, if and only if, (as $\omega$ encodes $M'$), $M'$ does not accept $M'$, a contradiction.

This is the same idea to prove undecidability of the Halting problem and numerous other results, the idea of diagonalization
> 0 votes

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


# Question
Title: Does Turing machine move left on particular input?
We know that RE language is the collection of unrestricted grammar which is known as type-0 grammar that's why emptiness, finiteness of every RE languages is undecidable. My question is how I check decidability "the Turing machine makes move left or not" on particular input string. I have found some internet contents but very difficult to understand. I want to understand just intuition which is brief, not the concrete proof.

# Answer
> 1 votes
What would happen if we never move left? Either we halt at some time, or we always see the input $\sqcup$ (blank symbol) and choose to move right. But there is a finite number of states, and by the pigeonhole principle after a long time we will get stuck in a loop in those states.

Checking if we get stuck in a loop in the states, is not hard when the input is always $\sqcup$ \- since we have to consider **only** the states.

---

In summary, the idea is to use the fact we will always see the same input after a while to our advantage - the states of a TM are finite, and hence it must act very simple (even simpler than a finite deterministic automaton!)

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


# Question
Title: Variant of Chomsky Normal Form for Languages with Strings of Length $\ge 2$
> Given a context-free grammar $G$ for a language $L$, where $L$ contains strings of length greater than 2, show that there exists some context-free grammar $G'$ which generates $L$ such that every rule of $G'$ has the form $$A\to x\_1 x\_2$$
>
> where $x\_i$ is either a terminal or non-terminal and $A$ is a terminal.

I know that this CFG $G'$ has to be similar to the CNF of $G$.

However, I am unsure how to remove transitions of the form $A\to a$. If $A$ is the start state of $G$, then it produces a string of length $1$, which would not be allowed. But what about the case when $A$ is not a start state?

# Answer
The solution is to "substitute" the terminal rules into the binary rules.

Start with a grammar in Chomsky normalform. Then for every pair of rules $A\to BC$ and $B\to a$ we add the rule $A\to aC$.

This is only one of the possible combinations. Also substitute the right nonterminal, or both of them. Now keep all binary rules (old and new ones) and delete all the original terminal rules $A\to a$.

If we compare the derivation trees of the new grammar with those of the original grammar, we see that all terminals are moved one level up as a consequence of the substitutions.
> 0 votes

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


# Question
Title: Time Complexity Analysis When Merging Routes
I would like to know the best way to approach the time complexity analysis of the following algorithm. I have come up with 2 approaches so far.

We have a `std::map<int,vector<int>>` (Balanced Binary Search Tree). Each of the `std::vector<int>` will be called a route.

*Algorithm:*

```
1. while(true)
2. We pick the first two routes from the map and add their key values and if ((sum of key values)>capacity)
   then break else proceed to step 3.
3. Now we have two routes which we merge.
   After merging (we simply append one of the routes to the other), we delete the chosen two routes and
   insert the new route into the map.
   The key value of the new route will be the sum of the key values of the chosen two routes.
   Go to step 2.

```

*Time Complexity Analysis:*

* *Approach 1*

Let us consider the total number of routes to be `n`. Operations like insertion and deletion in the map will cost us `O(log(n))` and extraction of the first element of the map will be `O(1).` When it comes to merging two routes, let us consider the average length of a route (`vector<int>)` to be `N` and so merging will cost us `O(N)`. In the worst case, there will be `(n-1)`mergings and so overall time complexity in the worst case will be `O(nN)`.

* *Approach 2*

Let us consider the total number of routes to be `n` and let us also consider `k` to be the total sum of lengths (`vector.size()`) of all the routes (`vector<int>`). Now time complexity of operations involving map remains the same. When it comes to merging, in the worst there can be `(n-1)` mergings and in total, we have `k` elements in all of the routes, so overall time complexity in the worst case will be `O(nk)`.

Any help will be really appreciated.

# Answer
> 0 votes
I'll keep your terminology of $n$ being the number of routes, $N$ being the average length of a vector, and $k$ being the sum of the lengths of all vectors. Then $N = k/n$. Your first approach it's implying that the cost of merging can be assumed to be $O(N)$, but this is only true at the beginning; when you're approaching the end of the process, the average length will be much closer to $k$. I propose a way to analyze this getting to a reasonable bound.

First, let me suggest the following: when merging two lists $A$ and $B$, always concatenate the smaller one at the end of the larger one.

In order to understand the cost of the algorithm, let's decompose it into two parts, the ones associated with the map data structure, and the ones associated with the merging.

* If the main loop makes $i$ iterations, you'd be paying $O(i \lg n)$ in operations related to the map. As each iteration is reducing the number of routes by $1$, you can have at most $n$ iterations, and thus the total cost for interacting with the map is at most $O(n \lg n)$.
* On the other hand, for the merging cost, let us charge an element whenever it is merged into another list. For example, when merging $\[3,2,4,5\]$ with $\[2,9,7\]$ we would be charging one operation to $2$, one operation to $9$, and one operation to $7$. More in general, when merging $A$ and $B$ with $|A| \> |B|$, we charge every element of $B$ one operation. Note that as $|A| \> |B|$ then the resulting list is at least double the size of $B$; namely $|A \cup B| \> 2|B|$. As the final list has $k$ elements, and each time an element is charged its corresponding list doubles its size, we know that each element can be charged at most $\lg k$ times. But also we know that no element can be charged more than $n-1$ times. So the total number of times an element can be charged is $\min(n-1, \lg k)$ and thus the total cost is $O(k \min(n, \lg k))$.

We thus have that the total cost is $O(n \lg n + k \min(n, \lg k))$, and as $k \> n$, we can simply say $O(k \min(n, \lg k))$. Note that if $n \< \lg k$, then this approach results in $O(kn)$ as your second approach.

---
Tags: algorithms, time-complexity, algorithm-analysis
---


# Question
Title: Prove Permutation approach of finding best paranthesization to matrix chain multiplication is $4^n$
Suppose we have matrices $A\_0,⋯,A\_{n−1}$ (you can say $n $ matrices). Matrix $A\_i$ is with dimension $d\_i\times d\_{i+1}$. If we would like to find all possible permutations to find the best parnthesization possible, that would take $4^n$ time complexity, any idea here please? For example, $B$ is $3x100$, C is $100 \times 5$, $D$ is $5\times 5$, the best one is $(BC)D = 1575$ ops while $B(CD) = 4000$ ops, where in this example for 3 matrices we have only 2 permutations, and we find the best one to have 1575.

# Answer
What people often forget: They have a problem, and the have a sub problem that helps solving the problem. And then they try solving the (hard) sub problem - without realising there is a much better solution.

In this case: For every (i, j), 0 \<= i \<= j \< n, find the best way to multiply $A\_i$ to $A\_j$. There are j-i ways to calculate this product by multiplying two sub products, so you can solve this in $O(n^3)$.
> 1 votes

---
Tags: complexity-theory, matrices
---


# Question
Title: Why timeout in TCP is not a predefined fixed value?
Why timeout in TCP is not a predefined fixed value? I know there is a set value of 15 for a timeout value but I was asked why timeout in TCP is not a predefined fixed value which I couldn't find an explantion for.

# Answer
> 3 votes
the main reason for RTO to be variable is to avoid congestion collapse.

if the timer is set to a too shorter value, there is a danger that the sender starts retransmitting packets, that are still being in-flight, thus overloading the network with unnecessary packets (that may end up delivered twice). The Jackobson algorithm for calculating RTO is intended to achieve this.

unless you set an RTO to unreasonably high value, there is a danger of this happening. and if your RTO is unreasonably high, any flow that had lost a packet, especially at the end of the stream, where there are not enough ACKs for dupacks to trigger, might take forever to complete.

Also, Internet is extremely diverse. As of now, typical RTTs between network paths can vary by an order of magnitude. data center networks have extremely low (\<\<ms), normal paths in countries with good internet (~10ms), bad internet(~50-60ms), and satellite networks (i think about 200ms). It will be very hard to have a reasonable fixed value to accomodate all of then.

# Answer
> 2 votes
If I am running a high performance local area TCP network then I would want the timeout value to be low. On the other hand, if I am sending messages to a low performance, over loaded TCP server I would want the timeout value to be long because the server might not be able to get to my traffic right away.

---
Tags: computer-networks, tcp
---


title: Go back n on server side

text:
# Question
Title: Go back n on server side
I am implementing a UDP based go back n example and I am a bit stuck on how the server should respond to packets.

If my client has a sliding window of say 5, it can send 5 packets to the server without waiting, and any time it receives back an ack lower than its highest window value it will retransmit all packets from that point on (I think I understand this correctly). So for example:

* Server sends: 1, 2, 3, 4, 5
* Gets Ack: 3
* Server sends: 4, 5, 6, 7, 8

What I cannot understand is whether the server is supposed to be maintaining a window itself and only responding when it receives 5 packets, or whether it should respond to every packet received?

Wikipedia suggests the window is only ever 1 for the receiver which would imply it responds to every incoming packet but the requirement I am following asks for the server to remember the window size and take this into account when acknowledging, would this be cumulative acknowledgement?

I need to understand how the server should respond so any help is appreciated.

# Answer
assuming that the client only sends and the server only receives and acks:

(1) the server may or may not contain a buffer. Go-Back-N will function perfectly, if there is a buffer for only one packet on the receiver. However, you could include a buffer (which comes with a window) as an optimization.

(2) the server should not memorize the sender window, or do anything. if you choose to do so, it should go the other way around. the server informs client about how much it can receive

(3) the server needs to track last in-order received packet (or next expected in-order packet). when this packet is received, the server processes it, and sends an ACK. After this happens, **the server increases last in-oder received packet**. Thus the window (of potentially one) also slides at the receiver. receiving one slides the window to two, receiving two slides the window for three, etc

here is a demo for situation without buffer: ARQ Demo

(4) whatever packet is received and whatever server chooses to do with it, it responds with a value that depends on last in-order received packet. (It depends on our ACK semantic, you can choose to ACK last in-order received, or next in-order expected). Sequence number of the first packet needs to be know, before transfer started. You can opt for well-known values (e.g., 1) or negotiate it during connection exchange.
> 1 votes

---
Tags: computer-networks, network-analysis, tcp
---


# Question
Title: Trying to understand a Router's Forwarding Table
I am trying to understand how a router's forward table works. As such, I am working on the following problem.

Problem:
A router’s forwarding table has the following entries. \begin{array} {|r|r|}\hline Network \\, Number & Next \\, Hop \\ \hline 0.0.0.0/0 & 15.15.1.2 \\ \hline 192.140.20.0/24 & 15.15.1.8 \\ \hline 192.140.20.0/20 & 15.15.1.9 \\ \hline \end{array}

Now, if the router is given an IP address like $192.140.20.3$ which row of the table would be used?

Here is how I see it. The first row of the table is not a match. It is going to match either the second or third row. The addresses given in the two rows are the same expect for the qualification. That is, the first address has a subnet mask of $24$ bits. The second one has a subnet mask of 20 bits. We do not know how big the subnet mask of the IP Address given is. So, I do not know what the router will do.

In the forwarding table given there is no metric field. If there was, in this case, it would be used to select either row 2 or row 3. Am I right about this?

# Answer
> 1 votes
the router should choose the longest prefix match, or the most specific prefix that matches. so, here it will choose line 2, because of longest prefix (24 bit).

---
Tags: computer-networks, routing
---


# Question
Title: Which one of the following is NOT a function of transport layer?
A. routing B. flow-control C. congestion control D. All of the above

My guess is flow-control only because routing and congestion is part of the network layer. The network layer is the third later and it provides data routing paths for network communications. I'm still not sure if I am right though.

# Answer
> 1 votes
the answer to "is definitelly NOT is A."

> routing

routing is done by network layer

before i go in the next ones here is **disabmiguity warning**. B. and C. are performed by TCP which is transport layer. if the application is using a custom transport protocol on top of UDP, i.e., RTP for transmitting multimedia, then, depending on the definition, it won't be transport layer. But B is definitelly not done by network layer and C may be assisted.

> flow control

ensures that the sender is not overloading the receiver with too much data to send. in TCP receiver sends the sender its window, i.e., the number of packets the receiver is ready to receive

> congestion control

the goal of congestion control is for the senders not to overflow the network. in Internet, congestion control is responsibility of senders. TCP is required to implement congestion control. Non-TCP applications are required to implement TCP-friendly congestion control (i.e., one that coexists with TCP). The algorithm usually tries to estimate available bandwidth based on some heuristic.

Routers can assist in performing congestion control in form of active queue management and explicit congestion notification. However, both of them can only work, if TCP can react to what they do.

A "very long time ago" there was in-network congestion control in form of source quench messages. It didn't work. Approaches, that rely on senders seem to work better.

---
Tags: computer-networks, network-flow, tcp
---


# Question
Title: Proving that the given Context free grammar generates strings with unequal number of a's and b's
Here is the grammar given on the wikipedia:

$$ S \rightarrow T \\;|\\; U \\ T \rightarrow VaT \\;|\\; VaV \\;|\\; TaV \\ U \rightarrow VbU \\;|\\; VbV \\;|\\; UbV \\ V \rightarrow aVbV \\;|\\; bVaV \\;|\\; \epsilon $$

I can understand how $V$ generates strings with equal number of a's and b's. I want to prove that $T$ generates strings with more a's than b's. The case for U can be proven symmetrically.

Here is my attempt and doubt.

$P(0)$: Suppose $s$ is a string with one extra a. Let $s\_1$ be the longest balanced prefix of s. Then $s=s\_1 t$ where t necessarily starts with $'a'$. For otherwise t will have a non-empty balanced prefix and $s\_1$ won't be the longest prefix. Hence $s = s\_1 a s\_2$ where $s\_1$ and $s\_2$ are balanced and derivable from $V$. hence s can be derived as $S \rightarrow VaV=\>^\* s\_1as\_2$.

$P(n)$ : Suppose $T =\>^\* w$, where w has $n$ extra a's than b's. Let s be a string with $n+1$. Let $s\_1$ and $t$ be as above. Then $t = aw$. By construction, $w$ has $n$ extra a's and is derivable from T. Therefore $T \rightarrow VaT =\>^\* s\_1aw$.

My doubt is what is the need for the rule $T \rightarrow TaV$

# Answer
You said:

> Here is the grammar **given on the wikipedia**:
> \[...\]
> $T \rightarrow VaT \\;|\\; VaV \\;|\\; TaV$
> \[...\]
> My doubt is what is the need for the rule $T \rightarrow TaV$

Wikipedia said:

> Omitting the third alternative in the rules for T and U doesn't restrict the grammar's language.
> 2 votes

---
Tags: context-free, check-my-answer
---


# Question
Title: Boolean function represented as a column vector: easy way to see if it has full degree?
If you have a Boolean function $f: \\{0,1\\}^n \rightarrow \\{0,1\\}$ on $n$ variables, you can represent this function as a $2^n$ vector indexed by the input space such that $ f\_x = f(x)$. For concreteness I assume that $f$ is ordered as 00, 01, 10, 11, etc.

Is there an easy way to tell if $f$ is has full degree? For most examples I checked it seemed that if the vector $f$ is symmetric across its midpoint then the function cannot be full degree.

# Answer
> 2 votes
Every function $f\colon \\{0,1\\}^n \to \\{0,1\\}$, whose input we style $x\_1,\ldots,x\_n$, has a unique expansion as a multilinear polynomial in the variables $y\_i = (-1)^{x\_i} = 1-2x\_i$. It also has a unique expansion as a multilinear as a multilinear polynomial in the variables $x\_i = (1-y\_i)/2$. Both expansions have the same degree: given one of the expansions, substituting the expressions above (either $y\_i = 1-2x\_i$ or $x\_i = (1-y\_i)/2$) gives an expansion in terms of the other variables with the same degree.

A function $f\colon \\{0,1\\}^n \to \\{0,1\\}$ has full Fourier degree (that is, its expansion in the variables $y\_i$ has degree $n$) iff it has non-empty correlation with the parity character $$ \chi\_{\[n\]} = y\_1 \cdots y\_n = (-1)^{x\_1 + \cdots + x\_n}. $$ This is because the coefficient of $y\_1 \cdots y\_n$ in the unique multilinear expansion is exactly this correlation (suitably normalized).

Therefore, all you have to check is whether $$ \sum\_{x \in \\{0,1\\}^n} f(x) (-1)^{x\_1 + \cdots + x\_n} \neq 0. $$

---
Tags: boolean-complexity
---


# Question
Title: Why is it undecidable to check the emptiness and finiteness of a context-sensitive grammar?
Context-sensitive languages have context-sensitive grammars, and context-free languages have context-free grammars. Using context-free grammars, we can decide the finiteness and emptiness of context-free languages. Why can't we decide these properties of context-sensitive languages in the same manner, using context-sensitive grammars?

I want to understand the intuition rather than the details.

# Answer
Here is the idea in a nutshell:

* Given a Turing machine $M$, we can construct a context-free grammar $G$ such that if $M$ halts then $\overline{L(G)} = \\{t\\}$, where $t$ is the transcript of the halting computation of $M$, and if $M$ doesn't halt then $\overline{L(G)} = \emptyset$.
Consequently, given a context-free grammar $G$, determining whether $L(G) = \Sigma^\*$ is undecidable.
* Given a Turing machine $M$, we can construct a context-sensitive grammar $G$ such that if $M$ halts then $L(G) = \\{t\\}$, where $t$ is the transcript of the halting computation of $M$, and $L(G) = \emptyset$ otherwise.
Consequently, given a context-sensitive grammar $G$, determining whether $L(G) =\emptyset$ or whether $L(G)$ is finite are both undecidable.

(A *transcript* is the sequence of configurations describing the execution of the machine, and a configuration consists of the tape contents, the head location, and the state.)

The context-free grammar in the first bullet generates "illegal" transcripts. This requires nondeterminism, and indeed, determining whether $L(G) = \Sigma^\*$ for a *deterministic* context-free grammar (i.e., a context-free grammar corresponding to a deterministic pushdown automaton) is decidable.

The context-sensitive grammar in the second bullet is easiest to describe via the equivalent computation model of linear bounded automata: it is easy to construct a linear bounded automaton for the given language. This time the construction requires no nondeterminism, and so determining whether $L(G) = \emptyset$ or whether $L(G)$ is finite is undecidable even for "deterministic context-sensitive grammars", i.e., the subclass of context-sensitive grammars corresponding to deterministic linear bounded automata.
> 3 votes

---
Tags: context-free, context-sensitive, decidability
---


# Question
Title: Tearing down the FSM description of congestion control
I was going through the text *Computer Networking- A Top-Down Approach* by *Kurose* and *Ross*, there I found subtleties with the TCP congestion control FSM which is shown below:

>

Mainly I am having difficulty in understanding the action ***transmit new segment(s), as allowed*** and transition to the ***Fast Recovery*** state.

I have read the equivalent portions from the textbook *Data Communications and Networking* by *Forouzan* but there though the explanation is easy but there is no FSM or a programmatic approach.

Now let us consider the slow start phase as shown in the *Kurose & Ross* text:

> The time diagram which they explain about the $cwnd$ doubling after each transmission round is easy and is just like what the *Forouzan* text says. But I find it difficult to understand the implementation based on the arc labeled with :
>
> in the *slow start* phase.
>
> 1. Suppose the sender starts with $cwnd = 1$ $MSS$ then sends this (1st) segment to the network layer and awaits the acknowledgment.
> 2. The sender gets "new ACK" for the previous packet and increases $cwnd$ to $2$ $MSS$. Then in accordance to "transmit new segment(s), as allowed", the sender sends $2$ segments (2nd and 3rd) to the network layer and awaits the acknowledgments.
> 3. Now the sender receives "new ACK" corresponding to 2nd segment and increases $cwnd$ to $3$ $MSS$. Then in accordance to "transmit new segment(s), as allowed", the sender sends $3$ segments to the network layer and awaits the acknowledgments.
> 4. Now the sender receives "new ACK" corresponding to 3rd segment and increases $cwnd$ to $4$ $MSS$. Then in accordance to "transmit new segment(s), as allowed", the sender sends $4$ segments to the network layer and awaits the acknowledgments.
>
> From points 3 and 4, I find that the situation does not match with the slow start phase as shown in Fig 3.51. (i.e. the no. of segments sent are 1,2, 3,4 instead of 1,2,4)

---

I cannot understand the **Fast recovery** state's action. Specifically the *Forouzan* text says :

> Most TCP implementations have two reactions:
>
> 1. If a time-out occurs, there is a stronger possibility of congestion; a segment has probably been dropped in the network, and there is no news about the sent segments. In this case TCP reacts strongly:
>
> a. It sets the value of the threshold to one-half of the current window size.
>
> b. It sets cwnd to the size of one segment.
>
> c. It starts the slow-start phase again.
> 2. If three ACKs are received, there is a weaker possibility of congestion; a segment may have been dropped, but some segments after that may have arrived safely since three ACKs are received. This is called ***fast transmission and fast recovery***. In this case, TCP has a weaker reaction:
>
> a. It sets the value of the threshold to one-half of the current window size.
>
> b. It sets cwnd to the value of the threshold (some implementations add three segment sizes to the threshold).
>
> c. It starts the congestion avoidance phase.

In the *Forouzan* text, there is no such transition to the ***Fast Recovery*** state. But here in *Kurose* there is such a state and there is an arc labeled :

> whose working I do not quite understand in detail.

What extra work is the version in *Kurose* doing as compared to the one given in the *Forouzan* text? Can anyone explain me the subtleties with a comprehensive example covering all the cases of the FSM, so that I can understand the thing better.

# Answer
> 0 votes
the thing that needs to be grasped is how sliding window interacts with congestion control.

## Sliding Windows

Let's say for simplicity case that sequence numbers number segments starting from one ...

It is important to understand, that when ACK is received, two things can happen

* window is moved by one segment (segment is removed from sender window)
* window can increase/stay the same/decrease
    + if the window is not increased, one new packet can be sent (window end will be one segment, passed SND.NXT and this segment is sent)
    + if the window increases by N segments, one new packet from previous case + N extra packets can be sent (try moving window by one and then increasing by two - how many spaces open?)
    + if the window decreases, no packets can be sent (SND.NXT will be outside of window, and as long as it is outside of window, no packets are sent)

## Slow Start

So, what happens with slow start:

> Suppose the sender starts with cwnd=1 MSS then sends this (1st) segment to the network layer and awaits the acknowledgment.

window starts at 1st segment and is one segment long

> The sender gets "new ACK" for the previous packet and increases cwnd to 2 MSS. Then in accordance to "transmit new segment(s), as allowed", the sender sends 2 segments (2nd and 3rd) to the network layer and awaits the acknowledgments.

window is moved to second segment, and is increased by one segment: 2 new segments are sent, window is \[2,3\] **and packet 2 and 3 are sent**

> Now the sender receives "new ACK" corresponding to 2nd segment and increases cwnd to 3 MSS. Then in accordance to "transmit new segment(s), as allowed", the sender sends 3 segments to the network layer and awaits the acknowledgments.

now window moves to 3 and opens to 3 segments \[3, 4, 5\]. however, segment 3 is already sent, so only the new segments 4 and 5 can be sent, the sender starts sending 4, which will take some time.

> Now the sender receives "new ACK" corresponding to 3rd segment and increases cwnd to 4 MSS. Then in accordance to "transmit new segment(s), as allowed", the sender sends 4 segments to the network layer and awaits the acknowledgments.

the window moves to 4 and opens by 4, so the sender can send \[4, 5, 6, 7\]. The delta from previous case is that segments 6 and 7 can also be sent.

Now, sending packets takes some time - t\_s. Then two consequtive packets are delivered t\_s time appart, are ACKed t\_s times appart, and these ACKs arrive t\_s time appart. So, what will happen in this two steps: segment 4 is sent, then almost simultaneously segment 5 is sent and ack for 3 is received, which makes segment 6 be transmitted as soon as 5 finishes and 7 as soon as 6 finished.

## Fast recovery

this state is entered when 3 dupacks are received and ends, when acknowledgment for the missing segment, i.e., the one that caused 3 dupacks is received. it takes about 1 RTT and is not depicted on most congestion control diagrams. But it does exis. Although there may be better strategies for error recovery.

How sliding window works in fast recovery is answered here

---
Tags: computer-networks, communication-protocols, tcp
---


title: CLRS Rod Cutting Inductive proof

text:
# Question
Title: CLRS Rod Cutting Inductive proof
I'd like to preface this question by saying that it is not a homework question. However, it is a question regarding the course material. In the rod-cutting example an equation is presented to determine the maximum possible revenue attainable for give rod length:

$r\_{n} = max(p\_{i} + r\_{n-i})$ (15.2)

I'm trying to prove by induction that this equation does in-fact output the optimal revenue.

It's stated that, "A simple induction on n proves that this answer is equal to the desired answer $r\_{ n}$, using equation. 15.2"

While not required, I'm attempting to perform this induction and I'm stuck on the inductive step. Here is what I have so far:

Base Case n = 3, where $r\_{n}$ represents the maximum revenue attainable from a rod of length $n$ (note the following references a price list p, which corresponds to the price of a rod for a given length, and a list r which corresponds to the maximum revenue given a rod length).

$i = 1, p\_{1} + r\_{3-1} = 6 $

$i = 2, p\_{2} + r\_{3-2} = 6 $

$i = 3, p\_{3} + r\_{3-3} = 8 $

Assume,
$r\_{k} = max(p\_{i} + r\_{k-i})$

Inductive Step,
$r\_{k+1} = max(p\_{i} + r\_{(k+1)-i})$

I'm am unclear on how to proceed from here. I realize that the optimal revenue for a give rod length is defined in terms the optimal revenue for smaller rod lengths, which I believe means this problem displays optimal sub-structure. But i'm unclear on how to proceed. I'm prefer to not be given an answer but rather some direction.

# Answer
> 2 votes
First, be more precise in your writing. What does $\max$ range over? What is $k$ in the inductive hypothesis and step? What is the actual *statement* in the induction hypothesis?

In the step, you want to establish that $r\_n = \dots$ is optimal assuming all $r\_k$ as computed by the proposed formula for $k \leq n$ are *optimal*, for some fixed $n \geq 3$.

One way you typically do this is by contradiction. *Assume* (in addition to IH) that $\max \dots$ were not optimal. Derive that the chosen $r\_k$ is not optimal either, then, which is in contradiction with the IH.

# Answer
> 0 votes
I don't think the statement

> A simple induction on $n$ proves that this answer is equal to the desired answer $r\_n$, using equation. *15.2*

means to use induction to prove

\begin{equation} r\_n=\max\_{1\le i \le n}(p\_i+r\_{n-i}) \end{equation}

but instead, it means to use induction to prove the algorithm:

```
CUT-ROD(p,n)
1 if n == 0
2     return 0
3 q = -∞
4 for i = 1 to n
5     q=max(q,p[i]+CUT-ROD(p,n-i))
6 return q

```

has the same result as $r\_n$.

My proof is:

#Step0: A special case

$$CUT-ROD(p, 0) = r\_0$$

#Step1:

\begin{eqnarray\*} if \ n = 1, then \ CUT-ROD(p,1) &=& max(-\infty, p\_1) = p\_1\\ \because r\_1 &=& p\_1\\ \therefore CUT-ROD(p,1) &=& r\_1 \end{eqnarray\*}

#Step2: assume that

$$CUT-ROD(p,n-1) = r\_{n-1}$$

further,

\begin{eqnarray\*} CUT-ROD(p,n-1) &=& q\_{n-1} = \max\_{1 \le i \le n-1}(q\_{i-1}, p\_i+CUT-ROD(p, n-1-i))\\ r\_{n-1} &=& \max\_{1 \le i \le n-1}(p\_i + r\_{n-1-i})\\ \end{eqnarray\*}

therefore,

$$\max\_{1 \le i \le n-1}(q\_{i-1}, p\_i+CUT-ROD(p, n-1-i)) = \max\_{1 \le i \le n-1}(p\_i + r\_{n-1-i})$$

#Step3: let's calculate

\begin{eqnarray\*} CUT-ROD(p, n) &=& q\_n\\ &=& \max\_{1 \le i \le n}(q\_{i-1}, p\_i+CUT-ROD(p, n-i))\\ &=& \max (\max\_{1 \le i \le n-1}(q\_{i-1}, p\_i+CUT-ROD(p, n-1-i)), p\_n+CUT-ROD(p,n-n)) \end{eqnarray\*}

Remember the result of #Step2, therefore we have \begin{eqnarray\*} CUT-ROD(p, n) &=& \max (\max\_{1 \le i \le n-1}(p\_i + r\_{n-1-i}), p\_n+CUT-ROD(p,n-n))\\ &=& \max (\max\_{1 \le i \le n-1}(p\_i + r\_{n-1-i}), p\_n+r\_{n-n})\\ &=& \max\_{1 \le i \le n}(p\_i + r\_{n-i})\\ &=& r\_n \end{eqnarray\*}

q.e.d

---
Tags: algorithms, optimization, correctness-proof, induction
---


# Question
Title: I'm looking for best algorithms to compare two Circular Linked List?
I'm looking for best algorithms to compare two Circular Linked List?

For example :

List 1 = 1-3-5

List 2 = 3-5-1

I want to compare "same" or "not same" but need fast algorithm.

# Answer
> -1 votes
```
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* next;
};

Node* removeLeadingZeros(struct Node* a)
{
    if (a != NULL && a->data == 0)
        return removeLeadingZeros(a->next);
    else
        return a;
}

int getSize(struct Node* a)
{
    int sz = 0;
    while (a != NULL) {
        a = a->next;
        sz++;
    }
    return sz;
}

void push(struct Node** head_ref, int new_data)
{

    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

    new_node->data = new_data;

    new_node->next = (*head_ref);

    (*head_ref) = new_node;
}

int compare(struct Node* a,
            struct Node* b)
{

    a = removeLeadingZeros(a);
    b = removeLeadingZeros(b);

    int lenA = getSize(a);
    int lenB = getSize(b);

    if (lenA > lenB) {

        return 1;
    }
    else if (lenB > lenA) {
        return -1;
    }

    while (a != NULL && b != NULL) {
        if (a->data > b->data)
            return 1;
        else if (a->data < b->data)
            return -1;

        /* If we reach here, then a and b are
        not NULL and their data is same, so
        move to next nodes in both lists */
        a = a->next;
        b = b->next;
    }

    return 0;
}

// Driver code
int main()
{

    struct Node* a = NULL;
    push(&a, 7);
    push(&a, 6);
    push(&a, 5);

    struct Node* b = NULL;
    push(&b, 3);
    push(&b, 3);
    push(&b, 2);

    cout << compare(a, b);

    return 0;
}

```

---
Tags: algorithms, data-structures, java
---


title: Reduction of RE and Rec languages

text:
# Question
Title: Reduction of RE and Rec languages
Suppose $L\_1$ is reduces to $L\_2$ in polynomial time, $L\_1\leq\_p^\mathsf{}L\_2.$ we know that if $L\_2$ is RE then $L\_1$ is also RE and $L\_2$ is REC then $L\_1$ is also REC.

And also I know that if $L\_1$ is REC then $L\_2$ is RE **and** REC is false. Because by taking counterexample $L\_1=\emptyset$ and $L\_2=$halting problem. So see from this example **and** case fails to prove above postulation.

My first question is that **or** case could be true. I mean if $L\_1$ is REC then $L\_2$ is RE **or** REC$-$could it be true?

My second question "if if $L\_1$ is RE then $L\_2$ is also RE" $-$ could it be true? I don't want any details proof. I want counterexample for true and false case.

# Answer
If $L\_1$ is recursive and $L\_1 \le\_p L\_2$, they it is possible that $L\_2$ is not recursively enumerable (and hence not recursive).

For example pick $L\_1 = \emptyset$ and $L\_2$ as the set of (a suitable encoding of) all Turing machines that do not halt on empty input. Clearly $L\_2$ is not recursively enumerable. A possible Karp reduction from $L\_1$ to $L\_2$ is the constant function that returns (the encoding of) a Turing machine that immediately halts.

If $L\_1$ is recursively enumerable and $L\_1 \le\_p L\_2$ then it **might** be the case that $L\_2$ is also recursively enumerable. For example pick $L\_1 = L\_2 = \emptyset$, a Karp reduction from $L\_1$ to $L\_2$ is the identity function. Notice that, in this example, $L\_1$ is also recursive.
> 1 votes

---
Tags: complexity-theory, turing-machines, computability, reductions, polynomial-time-reductions
---


# Question
Title: complement of concatenate languages equal to complements concatenated?
please help me with this one. (a formal answer would be much appreciated)

∀L1, L2 ⊆ Σ:

(L1 · L2)^c = L1^c · L2^c

when · represents concatination and ^c the complement language. do not know if languages are regular.

Thank you

# Answer
Let $L\_1=L\_2=\\{a\\}$ (that is the language consisting only of the sentence $a$).

Then $\epsilon\in L\_1^c$ and $aa\in L\_2^c$.

Since $\epsilon\cdot aa=aa$, $aa\in L\_1^c\cdot L\_2^c$.

But $aa$ is certainly not in $(L\_1L\_2)^c$.
> 1 votes

---
Tags: formal-languages, computability
---


# Question
Title: Decidable languages unconditionally not in P/poly
What are some nice/natural examples of languages not contained in $P/\mathit{poly}$, preferably decidable ones?

I'm interested in *unconditional* results rather than examples such as the Karp–Lipton theorem, which states that SAT is not in $P/\mathit{poly}$ unless the polynomial hierarchy collapses.

# Answer
Let $H\_{f(n)}$ be the set of all pairs $(M,x)$ such that $M$ halts on $x$ within $f(|x|)$ steps. We encode the pairs in such a way that $|(M,x)| = |x| + C\_M$, where $C\_M$ is a constant that depends only on $M$. Suppose that $H\_{f(n)}$ has circuits of size $g(n)$ (note that it's a slightly different $n$).

Let $h(n) \leq \kappa 2^n/n$, for an appropriate $\kappa \> 0$. Let $M\_{h(n)}$ be the Turing machine which on input $x$ of length $n$ generates all $n$-input circuits of size at most $h(n)$, determines the lexicographically first truth table of an $n$-bit function $\Phi\_{n,h(n)}$ which is not generated by this circuit (such a function exists due to our assumption on $h(n)$), halts if $\Phi\_{n,h(n)}(x) = 1$, and enters an infinite loop otherwise. By construction, $\Phi\_{n,h(n)}$ cannot be computed by a circuit of size $h(n)$ or less.

The running time of $M\_{h(n)}$ on an input of length $n$ is $O(2^{h(n) + n})$, hence if we choose $f(n) \geq K 2^{h(n) + n}$ for an appropriate constant $K \> 0$, we can compute $\Phi\_{n,h(n)}$ using a circuit of size $g(n + C\_{M\_{h(n)}}) + O(1)$. This shows that for some constant $C\>0$, $g(n + C\_{M\_{h(n)}}) + C \> h(n)$.

Given $f(n)$, the best choice for $h(n)$ is $\min(\log\_2 f(n) - n - K',\kappa 2^n/n)$, where $K'$ is some constant. This implies the following result, which holds for some constant $C'$.

**Theorem.** Suppose that for all $D\>0$ there exists $n$ such that $\min(f(n),2^{\kappa 2^n/n}) \geq 2^{g(n + D) + n + C'}$. Then $H\_{f(n)}$ cannot be computed by circuits of size $g(n)$ or smaller.

In particular, $H\_{2^{r(n)}}$ doesn't have polynomial size circuits whenever $r(n)$ is super-polynomial. On the other hand, $H\_{2^{r(n)}}$ can be computed in time roughly $O(2^{r(n)})$.

(This is essentially the argument of Jeřábek in this answer.)
> 2 votes

---
Tags: complexity-theory, circuits
---


# Question
Title: Variation on Matrix Chain problem -- compute diagonal only?
How would you get an optimal schedule to solve matrix chain problem where you only need to obtain the diagonal? (assuming the resulting matrix is square)

First computing the matrix product and then extracting the diagonal can be suboptimal. Consider diagonal of outer product of two vectors uv'. We could get the diagonal by multiplying two vectors pointwise.

$$\text{diag}(uv')=u\odot v$$

More generally, we can compute diagonal of a square matrix product by viewing it as sum of outer products of rows/columns and applying the trick above $$AB=\sum\_i u\_i v\_i' = \sum\_i u\_i \odot v\_i$$

# Answer
> 1 votes
Use the standard dynamic programming algorithm to find the optimal cost of multiplying every subsequence of your matrices $A\_1,\ldots,A\_m$, which are of dimensions $d\_1 \times d\_2, d\_2 \times d\_3, \ldots, d\_m \times d\_{m+1}$. Assuming that the product matrix is $n \times n$ and that the optimal cost is $c(A\_i \cdots A\_j)$, the optimal cost for computing the diagonal of the product is $$ \min\_{1 \leq i \leq n-1} c(A\_1 \cdots A\_i) + c(A\_{i+1} \cdots A\_m) + nd\_{i+1}. $$ (The original problem has $n^2 d\_{i+1}$ instead.)

You can compute the actual schedule in the usual way, by tracing the minimizer at each step of the dynamic programming.

---
Tags: algorithms, dynamic-programming, matrices
---


# Question
Title: Replacing the moduleo operation with occasional subtraction and one comparison
> Suppose we have the following equation:
>
> $$k\_{i + 1} = (k\_i + 2i + 1) \bmod{n}, \quad k\_0=k, \quad i\ge 0$$
>
> Show how we can we replace the mod with one comparison and **occasional** subtraction.

**Attempt**: I understood elsewhere that occasional here doesn't mean one subtraction. So, to replace modulo, the only way that I understood it is to keep subtracting $k\_{i + 1} $ from $n$, but that means we should keep checking if it's less than $n$ or not each time, so we violate as I see it the one comparison limit if I am not wrong. Second, we are supposed to step once we get the comparison false, which will give a number between $\[0, n-1\]$ same as $\bmod$ would do? What do you think please?

# Answer
> 2 votes
Since $0 \leq k\_i \< n$, as long as $i$ is not too large, we will have $0 \leq k\_i + 2i+1 \< 2n$. Therefore you can compute the modulo by checking whether $k\_i+2i+1 \geq n$, and if so, subtracting $n$.

This works as long as $(n-1) + (2i+1) \< 2n$, that is, as long as $i \< n/2$. Usually $n$ is very large, and so we are never going to perform $n/2$ many iterations.

---
Tags: algorithms, arithmetic
---


# Question
Title: Edmonds-Karp shortest path vs largest bottleneck
Depending on where I look, some places (https://courses.engr.illinois.edu/cs473/sp2009/notes/19-maxflowalgs.pdf) describe EK algorithm as choosing the `st` path with largest bottleneck value, while others (wikipedia) describe it as the shortest path from $s$ to $t$. I'm not sure if they are the same, and I haven't been able to find a proof demonstrating that they are if it is the case. Why does largest bottleneck value correspond to shortest path?

# Answer
> 1 votes
The shortest path and the path with the largest bottleneck are not the same in general.

It is easy to construct a counterexample: pick $G=(V,E)$ with $V=\\{a,b,c\\}$, and $E=\\{ (a,b), (a,c), (c,b) \\}$ where $(a,b)$ has capacity $1$ while $(a,c)$ and $(c,b)$ have capacity $2$. The shortest path between $a$ and $b$ consists of the single edge $(a,b)$. The path between $a$ and $b$ with the largest bottleneck is $\langle a,c,b \rangle$.

Besides, the notes that you linked describe and analyze both variants of the Edmonds-Karp algorithm.

---
Tags: graphs, network-flow
---


title: Reduction of np to npc

text:
# Question
Title: Reduction of np to npc
Given that $A$ is $NPC$ problem. And I need to check "if $D$ belongs to $NP$ and $D\leq\_p^\mathsf{}A$ then $D$ is $NPC$" is true or not?

**My approach:** Since $D\leq\_p^\mathsf{}A$, therefore $A$ is at least as hard as $D$, and given $A$ is $NPC$, consequently $D$ could be like easy problem $P, NP. $ And to prove $D$ is $NPC$ we need to proof $D$ is $NPH$ but I am unable to proven. Therefore $D$ can't be $NPC.$

Don't know my approach and result is right or not. If I did anything wrong please correct me.

# Answer
> 1 votes
Saying that $D$ could be in $P$ does not disprove "$D$ is $\mathsf{NP}$-complete" since it could be the case that $\mathsf{P}=\mathsf{NP}$.

However the claim is false regardless of the $\mathsf{P}$ vs $\mathsf{NP}$ matter. Simply pick $D=\emptyset$ and $A$ as any $\mathsf{NP}$-complete problem. Clearly $D$ cannot be $\mathsf{NP}$-complete since it is not $\mathsf{NP}$-hard. To see that $D$ is not $\mathsf{NP}$-hard notice that, given any language $B \in\mathsf{NP} \setminus \\{\emptyset\\}$, it is false that $B \le\_p D$.

---
Tags: np-complete, np-hard, polynomial-time, p-vs-np, polynomial-time-reductions
---


# Question
Title: Is there an instance of 3-SAT in less than 100 variables that no one has been able to solve?
In number theory, progress is sometimes guided by people stating a specific Diophantine equation that they don't know how to solve. Is there anything similar in the field of Boolean satisfiability?

More specifically, is there an instance of $3$-SAT in less than $100$ variables that people have tried to solve (by exhibiting a satisfiability or an unsatisfiability certificate) but no one has succeeded?

# Answer
> 1 votes
I don't think such a 100-variable 3-SAT problem exists. PPSZ can solve satisfiable 3-SAT problems in ~ $O(1.321^n)$, which equates to well under 2 trillion decisions for a 100-variable 3-SAT problem. A simple PC hardware setup ought to be able to work through that in a year or two. This is a lot of time (but not much trouble) to grind through a problem no one really cares about, but it is certainly doable. Most 100-variable 3-SAT problems are going to be much, *much* easier than that to solve, so creating a small instance of that difficulty would be the interesting part.

---
Tags: np-complete, satisfiability, 3-sat
---


# Question
Title: If a 32-bit computer system is being used, what are the size of the data/address/control bus width?
Are they exactly 32bits for a 32-bit system ?

# Answer
> 4 votes
It depends.

To see what I mean, I'm going to take the Intel Pentium Pro as an example. This was top of the line in consumer hardware in 1995 (which, you will recall, was 25 years ago).

It had 32-bit integer registers, giving 32-bit integer arithmetic and a 32-bit virtual address space.

However, it also supported a 36-bit *physical* address space.

The external connections to the chip (I'm going from the data sheet, table 29 here) had address lines A3 through A35 and data lines D0 to D63. So that's 33 bits of external address bus, and 64 bits of external data bus. You can count the control lines for yourself if you are curious.

Remember, modern CPU cores generally don't write directly to and from memory, but rather write directly to and from *cache*. On the Pentium Pro, the on-chip cache line size was 32 bytes, so this is how the CPU could handle a 64-bit external data bus despite not being a 32-bit CPU: transfers from cache to RAM (and vice versa) used a burst of four 64-bit-wide transfers.

(Disclaimer: I don't know how uncached memory accesses, such as memory-mapped I/O, worked on the level of physical signals. It's probably in the data sheet, but this is beside the point I want to make here.)

While there is no strict definition of what constitutes "a 32-bit CPU", but we can safely assume for the sake of argument that we're talking about 32-bit integer registers, 32-bit integer arithmetic, and 32-bit virtual address space. So 32-bits is an abstraction. It is what a programmer sees.

A *hardware designer*, working at the level of pins and signals, may see something very different.

To a modern CPU, RAM is more like a peripheral than something directly attached to a CPU core. The core interacts with *cache*, and caches communicate with RAM (and other caches, in a multiprocessing environment) as if they were a device. Modern thinking on device interfaces is that transfers should be in "bursts" if possible, because it increases the amount of data that you can transfer for a given setup.

It gets even stranger than that. If you think of RAM as a device, then at boot time, that device may not have been initialised yet. Many modern CPUs can configure their cache controllers not to talk to RAM, so it effectively runs using cache only until enough of the peripheral hardware is initialised.

By the way, we haven't talked at all about the width of internal busses. In a superscalar CPU, that's a huge topic by itself, because the common data bus may, in reality, be multiple independent busses so that multiple instructions can be scheduled and retired in the same clock cycle.

We have also ignored floating point; most 32-bit CPUs support 64-bit floating point arithmetic, and hence any registers and internal busses must be able to handle that somehow. The Pentium Pro had floating point registers were 80 bits in width, and the P6 microarchitecture (of which the Pentium Pro was the first CPU) eventually supported 128-bit SIMD registers and streaming vector arithmetic.

So, back to the question you asked:

> If a 32-bit computer system is being used, what are the size of the data/address/control bus width? Are they exactly 32bits for a 32-bit system ?

It depends exactly what you mean by that question, but for the last 20 years at least, *probably* not.

# Answer
> 0 votes
A `k-bit` system has registers of size `k bits` i.e. each register is `k bits` in length (size), and, these are the primary units of data transfer. These are also called `word` and `word-size`. Data transfer to and from CPU happens in chunks of `words`, so, for a `32-bit` system, `32-bit word` is what drives data.

Now, `chunks of words` is the key here. There are many kinds of transfer happening - DATA, INSTRUCTIONs etc. So all these happen in multiples of word.

You can find some detail here

---
Tags: computer-architecture, operating-systems
---


title: Weighted maximum match for intervals

text:
# Question
Title: Weighted maximum match for intervals
Say I have two sets of intervals sorted by time $I\_1=\[(x\_1, y\_1),... (x\_n, y\_n)\]$ and $I\_2 = \[(a\_1, b\_1)... (a\_m, b\_m)\]$. where $x, y, a, b$ are times in seconds. None of the intervals within $I\_1$ intersect, i.e. $x\_1 \< y\_1 \< x\_2 \< y\_2 \< x\_3....$ and same holds for $I\_2$ $a\_1 \< b\_1 \< a\_2 \< b\_2 \< a\_3....$

There is however overlap between elements of $I\_1$ and $I\_2$ so for example $(x\_k, y\_k)$ can intersect with $(a\_j, b\_j)$ for some $k\in \[1, n\], j\in \[1,m\]$.

Any $(x\_k, y\_k) \in I\_1$ could overlap with multiple intervals of $I\_2$ and vice versa. We want to solve two problems

1. Find a bijective mapping M(or a matching interms of graph theory) from $I\_1 -\> I\_2$ without taking into account the length of the overlap
2. Find a bijective mapping M which maximizes the length of the overlap(maximal weight matching in graph theory).

Problem 1 is an easy, given the sorted intervals. Like even with a bruteforce geeedy could do a O(n+m) here; For each $(x\_1, y\_1)$ select the first $(a\_i, b\_i)$ that intersects and add it to a mapping M, then for $(x\_2, y\_2)$ start from $(a\_{i+1}, b\_{i+1})$ and repeat.

Problem 2 is not so trivial since we can have multiple candidates. For example the above algorithm that works for problem 1 fails to find an optimal solution for problem 2 $I\_1 = \[(1, 5), (6, 12)\]$ $I\_2=\[(1, 2), (3, 7), (8, 12)\]$ . One obvious solution is maximum bipartite matching, but maybe there is something else clever we can do to exploit the problem structure?

# Answer
> 2 votes
Yes, for problem 2, there is a more direct approach.

There is either none or one more overlapping pair of intervals when we add next interval in order of their left endpoints. That fact is the base for the following algorithm using dynamic programming.

1. Sort all intervals (in either $I\_1$ or $I\_2$) in order of their left endpoints, breaking ties by their right endpoints.
2. * Let variable `rightmost_interval` keep track of the interval inspected so far with the rightmost right endpoint. If there are two such intervals, choose the one that was inspected earlier.
    * Let variable `max_mapped` and `max_not_mapped` keep track of the max length of overlap for all possible partial mappings of intervals inspected so for, with `rightmost_interval` mapped to an overlapping interval or not mapped to another interval, respectively.
    Here "partial" means some of inspected intervals in $I\_1$ may not be mapped to any interval in $I\_2$. Only overlaps between corresponding (i.e., as defined by the partial mapping) intervals are considered.

Initially, `rightmost_interval` is the first interval while both `max_mapped` and `max_not_mapped` are 0.
3. Inspect the interval one by one, starting from the second one. For each interval inspected, update all variables according to the specification, as shown inside the `for` loop in the code below.
4. Return `max(max_mapped, max_not_mapped)`

```
    // Given non-overlapping intervals I1 and non-overlapping intervals
    // I2, we can select some intervals in I1 to pair each of them to a
    // different intervals in I2. This method returns the maximum sum of
    // lengths of overlaps between paired intervals.
    long max_overlap(int[][] I1, int[][] I2) {
        if (I1.length == 0 || I2.length == 0) {
            return 0;
        }

        // Combine `I1` and `I2` into one list, `I`.
        int[][] I = new int[I1.length + I2.length][2];
        System.arraycopy(I1, 0, I, 0, I1.length);
        System.arraycopy(I2, 0, I, I1.length, I2.length);

        // Sort `I` by the left endpoints, breaking ties by the right endpoints
        Arrays.sort(I, (i1, i2) -> {
            if (i1[0] != i2[0]) return i1[0] - i2[0];
            else return i1[1] - i2[1];
        });

        // the interval inspected so far with the rightmost right endpoint.
        int[] rightmost_interval = I[0];
        // max total overlap with `rightmost_interval` not mapped to an interval.
        long max_not_mapped = 0;
        // max total overlap with `rightmost_interval` mapped to an overlapping interval.
        // If there is no interval that overlaps `rightmost_interval`, `max_mapped` will be 0.
        long max_mapped = 0;

        for (int i = 1; i < I.length; ++i) {
            int[] current = I[i];
            if (rightmost_interval[1] >= current[1]) {
                max_mapped = Math.max(max_mapped, max_not_mapped + current[1] - current[0]);
                // `rightmost_interval` and `max_not_mapped` stay the same
            } else {
                long new_max_not_mapped = Math.max(max_mapped, max_not_mapped);
                if (rightmost_interval[1] <= current[0]) {
                    max_mapped = 0;
                } else {
                    max_mapped = max_not_mapped + (rightmost_interval[1] - current[0]);
                }
                max_not_mapped = new_max_not_mapped;
                rightmost_interval = current;
            }
        }

        return Math.max(max_mapped, max_not_mapped);
    }

```

---

The sorting takes $O(n\log n)$ time, where $n$ is the combined size of $I\_1$ and $I\_2$. Since each iteration in the `for` loop takes no more than some constant time, the `for` loop takes $O(n)$ time. So the whole algorithm runs in $O(n\log n)$ time.

To find the actual partial map that produces the maximum overlap (i.e., the maximum matching between $I\_1$ and $I\_2$), add variables and steps to keep track of that partial map. The added steps will not change the time-complexity analysis above.

---
Tags: algorithms, graphs, intervals
---


title: Build a priority queue using dictionary

text:
# Question
Title: Build a priority queue using dictionary
**QUESTION**: Can we Implementing priority queue with hash table please?

As I understand, dictionary/hash table does not have sorting mechanism inside. It adds pairs of $\<key,value\>$ to hash table. So the keys in PQ would correspond to keys in hash table, however, keys are added such that elements are assigned a priority (min/high), which is not part of hash table implementation. So, what would you suggest please here?

# Answer
> 1 votes
You just build a priority queue (usually implemented as a heap) with items that are pointers to keys in your hash table. Connected to the hash table, and the hash table will modify the priority queue whenever keys are added or removed. This requires of course that keys support not only "equality" but also "ordering".

You might only build the priority queue when someone wants an iterator, because a priority queue doesn't allow you directly to iterate in sorted order; you have to destroy the priority queue to achieve that. A priority queue can only give you the first element in the queue, not all elements in sorted order.

---
Tags: algorithms, hash-tables, priority-queues
---


# Question
Title: The preliminary of the Bandit Gradient Algorithm
In the papers introducing **The Bandit Gradient Algorithm as Stochastic Gradient Ascent**, the following relationship:

is always considered as a preliminary and lacks proof for it. Does anyone know how does this relationship come about? ($\pi\_t(x)$ is the probability of choosing action $x$ at time $t$ and $q\_\*(x)$ is the mean reward for action $x$)

# Answer
> 0 votes
This follows almost immediately from the definition of expectation, when we sample the actions with the distribution that $\pi\_t$ (the bandit) defines, and the inherent randomness of the model.

First, let us make sure we use the same terminology:

* $\pi\_t(x)$ is the probability that the bandit chose action $x\in\text{Actions}$
* $R(x,r)$ will be the probability we got reward $r\in \[0,R\_{max}\]$, when we play action $x\in \text{Actions}$
* $q\_\*(x)$ will be $\mathbb{E}\_{~r\text{~} R(x,\cdot)}\[r\]$, which is exactly the average reward when you play action $x$.

Now, notice that $$\mathbb{E}\[R\_t\]=\mathbb{E}\_{~x\text{~} \pi\_t(\cdot),~r\text{~}R(x,\cdot)}\[r\]=\mathbb{E}\_{x\text{~}\pi\_t(\cdot)}\[q\_\*(x)\]$$ This is true, since by definition $R\_t$ is sampled by choosing an action $x$ using $\pi\_t$, and then receiving a random reward that depends on the action $x$ we chose. Do note though, that the second equality is derived by substituting our definition of $q\_\*(x)$ into the expectation.

Now, $$\mathbb{E}\[R\_t\]=\\\mathbb{E}\_{x\text{~}\pi\_t(\cdot)}\[q\_\*(x)\]=\\\sum\_{x\in\text{Actions}} \pi\_t(x)\cdot q\_\*(x)$$

The last equality is the definition of expectation. Hence, $\mathbb{E}\[R\_t\]=\sum\_{x}\pi\_t(x)\cdot q\_\*(x)$ as we wanted to show.

---
Tags: greedy-algorithms, gradient-descent
---


title: Finding the most profitable path

text:
# Question
Title: Finding the most profitable path
I will be working on a project soon and as I'm clearly not a star (see what I did?) in CS, I'm not sure what to think about this.

To put it simply, the problem is the following:

* We want to go **from point A to point B**, nice and simple, we can easily find the shortest path.
* **Each cell on our grid has a certain value**, let's say we win some money by going through cells. So we do not want the shortest path but the most profitable one.
* But, **we have a step limitation** (known to be at least sufficient to make it from A to B). So we cannot just go on every cell, we have to find an optimized path.

Here is an example:

1, 2 and 3 represent cell values, the step limit is arbitrary but you get the idea.

The problem is: **How to find the most valuable path we can take, and still make it to point B ?**

Any thoughts on this?

# Answer
The problem is NP-hard even in case of grid graphs and profits in $\\{0,1,2\\}$ by a reduction from Hamiltonian path on graphs that can be embedded on grids (the Hamiltonian path problem remains hard in this case).

Here is a sketch of the reduction. Embed the instance of the input graph on a grid (this can be done in polynomial time). Make sure the grid is fine enough and that all the edges become paths of the same length $\ell \ge 2$.

Assign a profit of $1$ to each cell corresponding to an edge. Assign a profit of $2$ to the cells corresponding to the vertices. Assign a profit of $0$ to all other cells. There exists an Hamiltonian path from $s$ to $t$ in the input graph if and only if the maximum profit of a path of length at most $(n-1)\ell+n-1$ that goes from the location corresponding to $s$ to the location corresponding to $t$ in the grid is $2n + (n-1)\ell$.

Here is an example with $n=10$ and $\ell=2$:

The best path of length at most $(n-1)\ell + (n-1)=27$ encounters exactly $28$ cells: all $10$ cells corresponding to vertices, plus $28-10=18$ cells corresponding to $9$ edges. It's total profit is $10 \cdot 2 + 18 = 38$. Notice that this is the best possible profit since we collect all cells with profit $2$ and no cell with profit $0$.

Note: It seems that you allow diagonal moves. The above construction might allow some vertices to be "shortcutted" by moving diagonally but this can be fixed. An easy way to do so is to "rotate" everything by 45 degrees, so that edges correspond to diagonal lines.
> 3 votes

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


# Question
Title: Expected Lookup Length in Open Addressing Hash Table with Simple Uniform Hashing
In several proofs of the expected lookup length in an open addressing hash table, an assumption is made (which is said to follow from the "simple uniform hashing assumption":

> Given a hash table with n slots and m keys in it, the probability that any particular slot is occupied is m/n.

I'm having difficulty creating a mental model involving an experiment and a sample space in which I can derive this.

I'm thinking of a sample space consisting of m-tuples of keys. The experiment is to randomly select one such tuple. The event A is the set of all such tuples that have at least 1 key in them that hashes into the given slot.

The probability of A then is `1 - (the probability that none of the m keys hash to the given slot)`. So `1 - ((n-1)/n)^m`. But that's not equal to `m/n`...

# Answer
> 0 votes
Your probability analysis is incorrect. Let $s$ be any slot in the table.

Then, the probability that none of the $m$ keys maps to the slot $s$ is:

$$\frac{n-1}{n} \cdot \frac{n-2}{n-1} \dotsc \cdot \frac{n-m}{n-m+1} = \frac{n-m}{n}$$

Note that after inserting $t$ keys in the table, there are $n-t$ empty slots in the table including the slot $s$. Therefore, the probability that $s$ is empty in the $(t+1)^{th}$ iteration is $(n-t-1)/(n-t)$ using uniform hashing. Hence, we got the above formula.

Therefore, the probability that the slot $s$ is occupied is $1- (n-m)/n = m/n$

---
Tags: hash
---


# Question
Title: LP formulation for minimum edge covering
Given a simple graph $G(V,E)$, what is the LP formulation for the minimum edge covering? Minimum weight edge covering would also work here. If there are none, then that is an answer too.

I took a class on Theory of Algorithms and Operations Research last semester, and remembered there was an IP formulation for the minimum vertex covering. I couldn't recall if the edge covering formulation is from OpRes/ThAlg. Furthermore, it's near impossible to comb through the lecture material as it was online, and I no longer have access to the online material.

Also, supposing it is from Theory of Algorithms, there might be a chance that it was used to prove that something is NP-complete, I really couldn't remember.

# Answer
In the minimum edge cover problem, you have to find a smallest set of edges that covers all of the vertices. The first thing you want to do is decide which edges you want to include in your edge cover. This can be done by having a variable $x\_e\in \\{0, 1\\}$ for each edge $e$ of the graph. If $x\_e=1$, you include the edge $e$ in your graph. If $x\_e=0$, you don't. Since you want to minimize the number of edges you pick, you want to minimize the expression $\sum\_{e}x\_e$. However, you also want to make sure that each vertex gets covered. So, for every vertex $v$, you need a constraint that ensures that $v$ gets covered. You do this by having a constraint that enforces that at least one of the variables associated with the edges incident to $v$ is $1$. This constraint would look like the following:

$$\sum\_{\text{$e$ is incident to $v$}}x\_e\geq 1$$

This formulation is very general. Whenever you have a problem where you want to cover a set of $B$s using a set of $A$s, you set up $0$-$1$ decision variables for each of the $A$s, and have a constraint for each $B$ ensuring that it does get covered.

As pointed out in the comments, this is actually an integer program formulation since the decision variables are constrained to be integers. Such constraints are not allowed in linear programs. You can replace the constraints $x\_e\in \\{0, 1\\}$ with $0\leq x\_e \leq 1$ to get a true linear program. However, solving that linear program might give you a *fractional* edge cover where you're allowed to pick a fractional amount of an edge.
> 1 votes

---
Tags: linear-programming
---


# Question
Title: What are the width of data/control/address bus for a 32-bit CPU?
Are they exactly 32bits for a 32-bit CPU?

# Answer
If it is a 32-bit CPU I would expect the width of the data bus to be 32 bits. In addition, I would expect the size of the address bus to be 32 bits. However, you cannot count on that being true. For example, the 8088 was sold as a 16-bit CPU but it had a 8 bit path to memory.

In summary, they usually are 32 bits but they might not be.
> 3 votes

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