# Question
Title: 3xN tiling problem with blocks of size 3x1 or 2x2
I know there are a number of different tiling problems and some of them have been discussed here: Number of ways of tiling a 3\*N board with 2\*1 dominoes problem Domino and Tromino Combined Tiling DP tiling a 2xN tile with L shaped tiles and 2x1 tiles?. My domain has different requirements which are as below: https://www.codingame.com/ide/puzzle/3n-tiling

Height will be 3, tile sizes are: 2x2, 3x1, 1x3

there are possible choices for 3x6:

```
┌─────┬─────┐  ┌───┬───┬───┐  ┌─────┬─────┐  ┌─┬─┬─────┬─┐
├─────┼─────┤  │   │   │   │  ├───┬─┴─┬───┤  │ │ ├─────┤ │
├─────┼─────┤  ├───┴─┬─┴───┤  │   │   │   │  │ │ ├─────┤ │
└─────┴─────┘  └─────┴─────┘  └───┴───┴───┘  └─┴─┴─────┴─┘
┌─┬─────┬─┬─┐  ┌─┬─┬─┬─────┐  ┌─────┬─┬─┬─┐  ┌─┬─┬─┬─┬─┬─┐
│ ├─────┤ │ │  │ │ │ ├─────┤  ├─────┤ │ │ │  │ │ │ │ │ │ │
│ ├─────┤ │ │  │ │ │ ├─────┤  ├─────┤ │ │ │  │ │ │ │ │ │ │
└─┴─────┴─┴─┘  └─┴─┴─┴─────┘  └─────┴─┴─┴─┘  └─┴─┴─┴─┴─┴─┘

```

(illustration copied from Codingame problem section).

I have come up with the following DP relation:

```
dp[i] = (dp[i-1] + (i >= 3 ? dp[i-3] : 0) + (i >= 6 ? dp[i-6] * 2 : 0))

```

`dp[i-1]` means at each state, you can add a 1x3 (illustration below) to previous state to get to the current state.

```
┌─┐
│ │
│ │
└─┘

```

`dp[i-3]` means if your width is at least 3, you can stack up three 3x1 vertically to 3 states ago (width - 3) to get to current state.

```
┌─────┐
├─────┤
├─────┤
└─────┘

```

`dp[i-6]` means when my width is greater than or equal to 6, I can add three 2x2 squares horizontally next to each other, then put two 3x1 rectangles on top of them to 6 states ago(width - 6), in two ways, to get to current state).

```
┌───┬───┬───┐  ┌─────┬─────┐
│   │   │   │  ├───┬─┴─┬───┤
├───┴─┬─┴───┤  │   │   │   │
└─────┴─────┘  └───┴───┴───┘

```

But looks like I'm missing something, my solution for 3x12 returns 124, while it should be 154. Any help is appreciated.

**Edit**:

After a lot of thoughts and getting some ideas from answers, I came up with this solutions (Image represents a top down DP approach)

Basically, based on the image,

1. To get to 1xN state, we can take 1 time, 1x3 and so dpHeight1\[n\] = dpHeight1\[n-3\]
2. To get to 2xN state, we can either take 1 time 2x2 so dpHeight2\[n\] = dpHeight2\[n-2\] or we can take 2 times 1x3: dpHeight2\[n\] += dpHeight2\[n-3\]
3. to get to 3xN, we can either take 1 time 3x1, so dpHeight3\[n\] = dpHeight3\[n-1\] or we can take 3 time 1x3, dpHeight3\[n\] += dpHeight3\[n-3\] or take 1 time 2x2 and 1 time 1x3, exception here is we can take 1x3 first or after we take 2x2, but they both have same count, so: dpHeight3\[n\] += (dpHeight1\[n-3\] * dpHeight2\[n-2\] * 2)

And this the code:

```
dpHeight1[0] = 1//height = 1
dpHeight2[0] = 1//height = 2
dpHeight3[0] = 1//height = 3

for (int width=1; width <= n; width++) {
    //take out one 1x3
    dpHeight3[width] = (dpHeight3[width-1])%mod

    if width >= 2 {
        dpHeight2[width] = (dpHeight2[width] + dpHeight2[width-2])%mod
    }

    if width >= 3 {
        //put 1 time 3x1
        dpHeight1[width] = (dpHeight1[width] + dpHeight1[width-3])%mod

        //put 2 vertically stacked 3x1
        dpHeight2[width] = (dpHeight2[width] + dpHeight2[width-3])%mod

        //take out 3 vertically stacked times 3x1
        dpHeight3[width] = (dpHeight3[width] + dpHeight3[width-3])%mod

        //take out 1 time 2x2 and put it on top of 1 time 3x1
        // or take out 1 time 3x1 and put it on top of 1 time 2x2
        dpHeight3[width] = (dpHeight3[width] + 2 * (dpHeight2[width-2] * dpHeight1[width-3]))%mod
    }
}

```

But still not getting the result.

# Answer
This counting problem is one of the classical problems that can be solved efficiently by dynamic programming.

Since we should find the number of ways to fill a 3 by $n$ rectangle, a natural set of subproblems is the number of ways to fill a 3 by $m$ rectangle, where $m\le n$. However, it turns out it is practically impossible to find a recurrence relation *with finite terms* between them. The difficulty comes from the following configuration. And configurations that contain that kind of configurations.

```
┌───┬───┬─────┬─────┬─────┬ - - - - - - - - ─┬─────┬─────┬─────┬───┐
│   │   ├─────┼─────┼─────┼ - - - - - - - - ─┼─────┼─────┼─────┤   │
├───┴─┬─┴───┬─┴───┬─┴───┬─┴ - - - - - - - ─┬─┴───┬─┴───┬─┴───┬─┴───┤
└─────┴─────┴─────┴─────┴ - - - - - - - - ─┴─────┴─────┴─────┴─────┘

```

---

So, we have to select more subproblems. Here is one way to choose them.

* Let $W\_0\[m\]$ be the number of ways to cover the shape shown below, a 3 by $m$ rectangle. Our ultimate goal is $W\_0\[m\]$.

```
  ┌──────────┐
  │          │
3 │          │
  └──────────┘
       m

```
* Let $W\_1\[m\]$ be the number of ways to cover the first shape shown below, a 3 by $m$ rectangle with an extra 1x1 square at the top-right corner. By symmetry, $W\_1\[m\]$ is also the number of ways to cover the second shape shown below.

```
       m+1                              m
  ┌────────────┐                  ┌──────────┐
  │          ┌─┘ 1                │          │
3 │          │                  3 │          └─┐
  └──────────┘                    └────────────┘ 1
       m                              m+1

```
* Let $W\_2\[m\]$ be the number of ways to cover the first shape shown below, a 3 by $m$ rectangle with an extra 1x2 square at the top-right corner. By symmetry, $W\_2\[m\]$ is also the number of ways to cover the second shape shown below.

```
       m+1                             m
  ┌────────────┐                  ┌──────────┐
  │            │ 2                │          └─┐
3 │          ┌─┘                3 │            │ 2
  └──────────┘                    └────────────┘
       m                             m+1

```

---

How to find the recurrence relations?

We will try to cover the space at the rightmost boundary of the above shapes in all possible ways, always making sure that what is left to cover is still one of the above shapes.

Consider $W\_0\[m\]$. We have the following 4 ways to cover the rightmost space.

```
              ┌────────┬─┐       ┌────┬─────┐       ┌──────┬───┐      ┌────┬─────┐
              │        │ │       │    ├─────┤       │      │   │      │    └─┬───┤
              │        │ │       │    ├─────┤       │    ┌─┴───┤      │      │   │
              └────────┴─┘       └────┴─────┘       └────┴─────┘      └──────┴───┘
What is left: 3x(m-1)            3x(m-3)            3x(m-3)+2          3x(m-3)+2

```

So, we have $\quad\quad W\_0\[m\] = W\_0\[m - 1\] + W\_0\[m - 3\] + W\_2\[m - 3\] * 2. $

Consider $W\_1\[m\]$. We have the following 2 ways to cover the rightmost space of the first shape.

```
              ┌──────┬─────┐     ┌──────┬─────┐
              │      ├───┬─┘     │    ┌─┴───┬─┘
              │      │   │       │    ├─────┤
              └──────┴───┘       └────┴─────┘
What is left: 3x(m-2)            3x(m-3)+1

```

So we have $\quad\quad W\_1\[m\] = W\_0\[m - 2\] + W\_1\[m - 3\].$

Consider $W\_2\[m\]$. We have the following 2 ways to cover the rightmost space of the first shape.

```
              ┌────────┬───┐      ┌──────┬─────┐
              │        │   │      │      ├─────┤
              │        └─┬─┘      │    ┌─┴───┬─┘
              └──────────┘        └────┴─────┘
What is left: 3x(m-1)+1           3x(m-3)+2

```

So we have $\quad\quad W\_2\[m\] = W\_1\[m - 1\] + W\_2\[m - 3\]. $

---

Using the above three recurrence equations, now we can compute all $W\_0\[i\],W\_1\[i\],W\_2\[i\]$, in order of increasing $i$, starting from $i=3$, given the following initial conditions, $$ \begin{aligned} W\_0\[0\] &= W\_0\[1\] = W\_0\[2\] = 1,\\ W\_1\[0\] &= W\_1\[1\] = 0\quad \text{ and }\quad W\_1\[2\] = 1,\\ W\_2\[0\] &= W\_2\[1\] = W\_2\[2\] = 0. \end{aligned}$$

Here are the first 20 values for $W\_0(\cdot)$.

```
   m: 1  2  3  4  5  6   7   8   9  10  11   12   13   14   15   16   17   18   19  20
W_0:  1  1  2  3  4  8  13  19  35  58  89  154  256  405  681 1131 1822 3025 5012 8156

```

---

The above approach is fast enough for both the problem at codechef and the same problem at codingame.

However, if $n$ is very large, such as $10^{15}$, it may take days to compute. We will need to introduce the power of matrix or generating function. Those techniques can speed up the computation exponentially.

For more information about this sequence, check the On-Line Encyclopedia of Integer Sequences.

---

There is, in fact, a recurrence relation that involves only $W\[m\]$, the number of ways to fill a 3 by $n$ rectangle. (It was denoted $W\_0\[m\]$ in the above paragraphs.) For all $m\ge9$,

$$W\[m\] = W\[m-1\] + 3W\[m-3\] - 2W\[m-4\] - W\[m-6\] + W\[m-7\] + W\[m-9\]$$
> 4 votes

# Answer
Here is a systematic way to approach it. I suggest you define three values:

$A\_0(n)$ is the number of ways to tile a $3 \times n$ region.

$A\_1(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell already covered.

$A\_2(n)$ is the number of ways to tile a $3 \times n$ region with the upper-left cell and the cell to the right of it already covered.

Then you should be able to express each $A\_i(n)$ in terms of $A\_j(m)$ for $m \< n$. This gives you a mutual recurrence relation for these three values. It is easy to construct these recurrent relations based on a case analysis of how the leftmost column is covered.

You can then compute these using dynamic programming, in order of increasing $m$. Or, you can substitute into each other and get a single recurrence relation for $A\_0(n)$ in terms of $A\_0(m)$ for $m\<n$, if you prefer.

---

Regarding your solution:

Yeah, you're missing something. For instance, a solution could start

```
┌───┬───┬─────┐
│   │   ├─────┤
├───┴─┬─┴───┬─┴
└─────┴─────┴──

```

and continue from there; that won't be counted in your case analysis.
> 5 votes

# Answer
In general, you would change the question slightly: "How many ways are there to tile an X by N area by adding tiles individually and always adding the next tile so that it covers the topmost of the leftmost uncovered squares". Obviously that doesn't change the number of possible tilings at all since each square must eventually be covered.

Since you are tiling the area from the left to the right, you then analyse what the boundary between the tiled area and the untiled area could look like (or what the rectangle containing all the untiled squares could look like).

In your example, you start with a complete rectangle. You can then add 1x3 vertically, 1x3 horizontally at the top, or 2x2 at the top. 1x3 vertically gives the same shape. After 1x3 horizontally, you can add 1x3 horizontally in the middle row and are then forced to add 1x3 horizontally at the bottom, giving a complete square again. Or you can add 2x2 at the bottom, leaving the top left square covered. And so on. You can do that systematically.

And then as D.W. said, you get several mutually recursive formulas. Depending on the number X and the number of available shapes, this will be more or less complicated.
> 2 votes

# Answer
I spent a night on this problem and still can not get the right answer, I feel like I am missing something.

I tried to follow D.W. reasoning and ended up with those relations :

$A0(n) = A0(n - 1) + A0(n - 3) + 2×A2(n - 3)$

$A2(n) = A2(n - 3) + A3(n - 3)$

$A3(n) = A0(n) + A3(n -3)$

Am I wrong in those relations ?

If it's correct I guess it's my way to compute it, but I am too uncertain about those relations right now...

Here a pic to show you my thoughts process (**f()** would be A0 and **g()** would be A2 and **h()** would be A3)
> 0 votes

---
Tags: dynamic-programming, tiling
---


# Question
Title: How To Merge Together Two Circular Doubly-Linked Lists In O(1) Time?
I'm implementing a Fibonacci Heap, where the lists are stored as a circular doubly-linked lists. What I'm trying to do is given a pointer to a random node in one linked list, and a random node in another, I want to merge them together in O(1) time. I tried drawing this out, but I couldn't seem to figure out how to do this. Here is my first idea, in pseudocode:

```
union(Node one, Node two) {
    if other = nil
        return

    p1 = one
    p2 = one.right
    p3 = two
    p4 = two.right

    p1.right = p4
    p4.left = p1
    p2.right = p3
    p3.left = p2
}

```

Each `Node` has a `left` and `right` attribute, which stores the node to the left and right, respectively. However, this didn't work. Can anyone figure out how to merge together two linked lists?

# Answer
> 2 votes
There is no need to use temporary variables. See the following picture and the associated pseudocode below. You want to reassign the gray pointers to their colored counterpart. You just have to be careful with the order of the instructions.

```
one.right.left = two.left;  //red
two.left.right = one.right; //blue

one.right = two; //green
two.left = one;  //purple

```

---
Tags: linked-lists
---


# Question
Title: Number of parenthesizations and Catalan numbers
I read in CLRS that the number of possible parenthesizations for a product of $n$ matrices is given by the recursive formula:

$$ P(n)= \begin{cases} 1 & \text{if } n = 1,\\ \sum^{n-1}\_{k=1} P(k)P(n-k) & \text{if } n \ge2. \end{cases} $$

This comes from the following two facts:

* For $n=1$ there is only only item, so only one way to fully parenthesize a matrix product.
* For $n\geq2$ a fully parenthesized matrix product is the product of **two** fully parenthesized subproducts, and the split between the two subproducts may occur between the $k$th and $(k+1)$st matrices for any $k=1,2,\ldots, n-1$.

So far so good.

Now, I know that $\sum^{n-1}\_{k=1} P(k)P(n-k)$ has a strong relationship with Catalan numbers, and I'm hoping to establish that relationship with precision.

For background, Catalan numbers are defined as a sequence of the following form:

$${\displaystyle C\_{0}=1\quad {\text{and}}\quad C\_{n+1}=\sum \_{i=0}^{n}C\_{i}\\,C\_{n-i}\quad {\text{for }}n\geq 0,}$$

where a term in the sequence is also known to follow the alternative expression: $C\_n={\tfrac {1}{n+1}}{\tbinom {2n}{n}}.$

---

Expressing the original recurrence in terms of Catalan numbers shouldn't be hard, but the differences in summation and sequence indices are making it difficult for me. What's a good way to rearrange these types of Eqs. to re-express e.g. the first Eq. as a function of the second one?

# Answer
> 3 votes
Define function $Q:\mathbb N\to\mathbb N$ such that $Q(n)=P(n+1)$ for all $n\ge 0$. Or, what is equivalent, $P(n)=Q(n-1)$ for all $n\ge 1$.

We have $$Q(0)= P(0+1)=P(1)=1.\quad\quad\quad\quad\quad\quad\quad\quad$$

Also, for $n\ge0$, $$\begin{aligned} Q(n+1)&=P(n+2)\\ &=\sum^{(n+2)-1}\_{k=1} P(k)P((n+2)-k)\\ &=\sum^{n+1}\_{k=1} Q(k-1)Q(n+1-k)\\ &\stackrel{k=i+1}{=\\!=\\!=\\!=}\sum^{n}\_{i=0} Q((i+1)-1)Q(n+1-(i+1))\\ &=\sum^{n}\_{i=0} Q(i)Q(n-i).\\ \end{aligned}$$

We see that $Q(\cdot)$ and the Catalan numbers $C(\cdot)$ share the same initial condition and the same recurrence relation. So, we have, for all $n\ge0$, $$ Q(n) = C(n).$$ So, for all $n\ge 1,$ $$P(n)=Q(n-1)=C(n-1)={\tfrac {1}{n}}{\tbinom {2(n-1)}{n-1}}$$

**Exercise.** Define function $D$ such that $D(n)=C(n-1)$ for $n\ge1$. Show that $D(n)=P(n)$ for $n\ge1$, assuming that you have not seen the deduction above.

---
Tags: recurrence-relation, enumeration
---


title: data carried during TCP control flow

text:
# Question
Title: data carried during TCP control flow
I am learning about TCP control flow and came across a question about how much data is carried by the 4th segment. The answer is supposed to be 1200 (2230 - 1030) but I don't quite understand why.

By definition, I know that the acknowledgement number is telling the other side what is next expected from it. Thus 5 is the server acknowledging everything up to 2230 and telling the client that the server is expecting 2230 next, while 3 is the client acknowledging everything up to 3848 and telling the server that it next expects 3848. But I still don't understand why we're considering segment 5 and segment 2? If it's only "expecting" then how do we know how much data is being carried?

# Answer
> 0 votes
The data that will be carried in the 4th segment is 1200 why?we can know it by simpley look at the sequence number of the 6th packet -a packet's sequence number is in simple words:"im sending data from this certain number" if we take a look at the 3th packet we can see that it was sent from the client to the server with a sequence number of 1030 and we can see in the 6th packet that the sequence number of it is 2230 which means a total 2230-1030=1200 of data was sent from the clinet to server in the 4th packet

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


# Question
Title: Smallest set of balls under hamming distance that covers all $n$-bit strings
Suppose we defined a set $S = \\{x\mid0 \leq x \leq 2^n-1\\}$. Notice that all element in $S$ can be represented with a $n$-bit binary string. Now consider subset $S\_i$ such that,

$$S\_{y\_i} = \\{y \in S\mid d(y,y\_i) \leq t\\},$$

where $y\_i$ is the $i$th element of $S$ and $d(y\_j,y\_i)$ is the hamming distance between the binary representation of $y\_j$ and $y\_i$ and $t \< n$. Obviously, $S\_{y\_i} \subset S$.

Consider the family ${\Phi = \\{S\_0, S\_1, \ldots, S\_{2^n-1}\\}}$. Find ${\phi \subset \Phi}$ with smallest cardinality, so that the union of the all elements in $\phi$ is equal to original set $S$ (notice that, each element of $\phi$ is a subset of $S$).

I was not be able to solve. However, I believe it is possible to find $\phi$ with an efficient algorithm rather than using an exhaustive search.

**Edit: An example-**

Assume $n =3$ and $t = 1$

Then $S = \\{0, 1, 2, 3, 4, 5, 6, 7\\}$

So, $S\_0 = \\{y \in S\ |\ d(y,0) \leq 1;\\} = \\{0, 1, 2, 4\\}$

Similarly, $S\_1 = \\{0, 1, 3, 5\\}$; $S\_2 = \\{0, 2, 3, 6\\}$; $S\_3 = \\{1, 2, 3, 7\\}$; $S\_4 = \\{0, 4, 5, 6\\}$; $S\_5 = \\{1, 4, 5, 7\\}$; $S\_6 = \\{3, 4, 6, 7\\}$; $S\_7 = \\{3, 5, 6, 7\\}$;

So, $\Phi = \\{S\_0, S\_1, S\_2, S\_3, S\_4, S\_5, S\_6, S\_7\\}$; Now, for this case the $\phi = \\{S\_2, S\_5\\}$ as $S\_2 \cup S\_5 = S$

# Answer
> 6 votes
The object you are looking for is known as a covering code. Finding the smallest covering code for a given radius is generally a difficult problem, just like its more well-known dual problem, error-correcting codes.

---
Tags: algorithms, combinatorics, sets, coding-theory
---


title: What is "σ" in a context free grammar?

text:
# Question
Title: What is "σ" in a context free grammar?
I have a grammar like this:

```
A → BAB | B | ε
B → 00σ | ε

```

What is the meaning of σ in the second rule?

# Answer
Most probably, it means “for each letter $\sigma$ from alphabet $\Sigma$”.

If $\Sigma = \\{ 0, 1 \\}$, then `B → 000 | 001 | ε`.
> 2 votes

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


# Question
Title: Questions regarding CPU scheduling algorithms ( Round Robin and Priority scheduling )
Consider the following processes :

1) My First Question is if we need to schedule them using preemptive priority scheduling with Round-Robin for equal processes priorities with a quantum of 3. Here is my answer to this problem :

Sorry about that bad drawing. My problem here is at time 13. At this time we have two processes of equal priority ( p1 and p3 ) that we need to schedule them using RR with a quantum of 3 . My question is what process we will start scheduling it here ? I have started with p1 as it was already being executed by the CPU . Also is the rest of the answer is right ?

2) Now for the second question. Let's consider that We need to schedule the same process with a round-robin with a quantum of 4 . I have used this website to check my answer http://cpuburst.com/ and here its answer :

According to this answer, at time 20 p4 should be executed, but according to my answer p1 is the process that should be executed ?? And due to this difference, the rest of the answer is different to mine.

# Answer
> 1 votes
You had to make assumptions. Your problem is that “priority scheduling with round robin for equal priority” is not enough to specify exactly what happens.

Your scheduler will consider a change in the schedule when the running process finishes, when a new process is started with priority same or higher than the currently running process, or if the quantum is elapsed - but it’s not obvious if this is every three seconds, or three seconds after the last change in schedule. And exactly what “round robin” would pick isn’t clear.

You’d need the exact details of the scheduling algorithm.

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


# Question
Title: Why does a DFA have multiple final states?
I am taking a course on programming language design and we got to the DFA part. It is known to be formally defined by a 5-tupple but they did not make it very clear to us why a DFA can have multiple final states. I know that the languages that it can accept are involved, but nothing else.

# Answer
> 14 votes
A DFA is a machine that reads in its input left to right, and, while reading, keeps track of its internal state. At the end, it has to decide whether to "accept" or "reject" the input *based only on whatever internal state it has at the end.* The final states are used to indicate which internal states should inform the machine to accept.

The reason we need to have multiple final states, then, is because we might want to accept the input in multiple different scenarios. Here is a simple example. Suppose we want to design a machine that accepts if the input is either `ho`, `hoho`, or `hohoho` (so we want to accept, in total, three possible input strings). Then the "state" of the machine can keep track of what letters we have seen so far: we have 7 states for `[nothing]`, `h`, `ho`, `hoh`, `hoho`, `hohoh`, `hohoho`. If we get a letter that isn't going to be one of these strings (like if the input is `haha` or `asdf`), we need a different state to remember that the input was bad, and we can call that state `[bad input]`. So in total we have 8 states.

Now in this example, we want to accept three different strings: `ho`, `hoho`, and `hohoho`, so we need all three of those states to be final. It turns out that it would be impossible to accept these three strings if we have to have only one final state.

```
All states (8): [nothing], h, ho, hoh, hoho, hohoh, hohoho, [bad input]
Final states (3): ho, hoho, hohoho

```

In summary, **multiple final states gives us the ability to accept multiple different possible patterns in the input.** The above is one example of that, but there are many other examples where it is useful.

# Answer
> 5 votes
Consider an arbitrary nondeterministic finite automaton.

If it has multiple final states, you can create an epsilon transition from all of the final states to one common final state, remove the "final state" mark from all of the previously final states so that you have only one final state. So, a nondeterministic finite automaton can very well work with just one final state.

However, if you explode a nondeterministic finite automaton into a deterministic finite automaton, you'll find that you no longer can have epsilon transitions. The states of the exploded deterministic finite automaton correspond to sets of states in the nondeterministic finite automaton.

You will find that you need to mark a state as "final state" if at least one of the NFA states in the set is the final state. There may be multiple such states.

So, in summary: an NFA can very well work with just one final state. A DFA can't, unless you want to restrict DFAs arbitrarily. By arbitrarily restricting DFAs, you are creating a situation where there are NFAs that cannot be converted to DFAs, and that there are regular expressions that cannot be accepted by any DFA.

# Answer
> 2 votes
Let me provide a characterization of what languages DFAs with a single accepting state can accept.

**Proposition.** A language $L$ over $\Sigma$ is accepted by a DFA with a single accepting state if there exist two regular prefix codes $A,B$ such that $L = AB^\*$. Furthermore, this representation is unique, assuming $L \neq \emptyset$ and $\epsilon \notin B$.

(A prefix code is a set of words, none of which is a prefix of another one. It is regular if as a language it is regular.)

**Proof.** Let $A$ be the language of words which move the DFA from its initial state to its final state without transitioning through the final state (if the initial state is also final, $A = \\{\epsilon\\}$), and let $B$ be the language of non-empty words which move the DFA from its final state back to itself, again without transitioning through the final state.

The languages $A,B$ are clearly regular. To see that they are prefix-free, suppose to the contrary that $x,y \in A$, and $x$ is a proper prefix of $y$. Thus when reading $y$, the DFA passes through the accepting state upon reaching $x$. The case of $B$ is similar.

In the other direction, consider a minimal DFA for $A$. All words in $A$ are equivalent with respect to the Myhill–Nerode relation. Indeed, if $x,y \in A$ then $x\epsilon,y\epsilon \in A$ by $xz,yz \notin A$ for $z \neq \epsilon$ since $A$ is prefix-free. Thus the minimal DFA contains a unique accepting state. Similarly, the minimal DFA for $B$ contains a unique accepting state. Merging the accepting state of the former DFA with the initial DFA, we get the desired DFA.

Finally, let us show that the decomposition is unique. Given $L = AB^\*$, we an extract $A$ as the set of words in $L$ which have no proper prefix in $L$. Taking any $w \in L$, we can extract $B$ as the set of words in $w^{-1} L$ which have no proper non-empty prefix in $w^{-1} L$. (This step fails if $A = \emptyset$.) $\square$

---

In particular, if $L$ contains two words $x \neq y$ such that $x$ is a prefix of $y$ then $L$ is infinite (since $B$ must contain a word other than $\epsilon$). This shows that $\\{ho,hoho,hohoho\\}$ requires more than one accepting state.

From Myhill–Nerode theory, it is known that the minimal number of accepting states equals the number of Myhill–Nerode equivalence classes of words in the language. In the example $\\{ho,hoho,hohoho\\}$, each word is in its own equivalence class, so exactly three accepting states are needed. (With some work, it should be possible to identify a combinatorial parameter which determines the minimal number of accepting states in any finite language.)

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


# Question
Title: Find two contiguous subarrays with the greatest difference
Here's an interview question I've seen on a few sites. People claim that an `O(n)` solution is possible, but I've been racking my brain these last 2 days and I couldn't come up with a solution, nor find one anywhere on the web.

Given an array of integers, find two disjoint, contiguous subarrays such that the absolute difference between the sum of the items in each subarray is as big as possible.

Example input: `(2, -1, -2, 1, -4, 2, 8)`

Example output: `((1, 4), (5, 6))`

The output above is the indices of these two subarrays: `((-1, -2, 1, -4,), (2, 8))`

I've been trying to reduce this problem to the Maximum subarray problem but with no success.

# Answer
> 2 votes
Because the two subarrays are disjoint, there exists at least one index $m$ such that one entire subarray lies $\leq m$ and the other subarray lies $\gt m$.

But we do not know what this $m$ is, beforehand. So let us iterate over all the $n$ possibilities for $m$. Now if an $m$ is fixed, then the problem reduces to the Maximum subarray problem, and the Minimum subarray problem. This is because for the absolute difference to be the largest, one side of $m$ should have the maximum possible subarray, and the other side should have the minimum possible subarray. So we try both of these options and take the maximum absolute difference among the two.

But this is still $\mathcal{O}(n^2)$, because there are $n$ different values of $m$, and for each of those values, we have to spend $\mathcal{O}(n)$ time to compute the needed minimum and maximum subarrays.

The next observation is to note that a single $\mathcal{O}(n)$ run of the Maximum subarray algorithm on the entire array can actually give us one of the needed values for all values of $m$:

```
Given: int A[n]

MaxSubarrayTill[0] = A[0]
MaxSubarrayEndingAt[0] = A[0]
for(i = 1; i < n ; i++)
{
    MaxSubarrayEndingAt[i] = max{A[i], MaxSubarrayEndingAt[i - 1] + A[i]}
    MaxSubarrayTill[i] = max{MaxSubarrayTill[i - 1], MaxSubarrayEndingAt[i]}
}

```

Here, $\text{MaxSubarrayTill}\[i\]$ denotes the maximum sum subarray which ends $\le i$, and $\text{MaxSubarrayEndingAt}\[i\]$ denotes the maximum sum subarray which ends at index $i$.

Similarly, we can compute the $\text{MinSubarrayTill}\[i\]$ array in $\mathcal{O}(n)$ time. And by repeating the same two algorithms in reverse (ie. from the end of the array to the beginning), we can get $\text{MaxSubarrayFrom}\[i\]$ and $\text{MinSubarrayFrom}\[i\]$.

So in $\mathcal{O}(n)$ time we have precomputed all the values that we needed in the first algorithm, which we can now go back to. Interate over all the values of $m$, and find the largest absolute difference in $\mathcal{O}(n)$ time.

If the problem also stipulates that the two subarrays should be adjacent, then we can leave out $\text{MaxSubarrayTill}\[i\]$ and its analogous arrays, and instead only consider $\text{MaxSubarrayEndingAt}\[i\]$ and its analogous three other arrays. The rest of the algorthm remains the same.

---
Tags: algorithms, arrays, maximum-subarray
---


# Question
Title: Why create more faster processors despite of Processor Memory Bottleneck?
The shared bus between the program memory and data memory leads to the von Neumann bottleneck, the limited throughput (data transfer rate) between the central processing unit (CPU) and memory compared to the amount of memory. Because the single bus can only access one of the two classes of memory at a time, throughput is lower than the rate at which the CPU can work. This seriously limits the effective processing speed when the CPU is required to perform minimal processing on large amounts of data. The CPU is continually forced to wait for needed data to be transferred to or from memory. Since CPU speed and memory size have increased much faster than the throughput between them, the bottleneck has become more of a problem, a problem whose severity increases with every newer generation of CPU.

Source : https://en.m.wikipedia.org/wiki/Von\_Neumann\_architecture#Von\_Neumann\_bottleneck

There can be up to a 53% difference between the growth in speed of processor speeds and the lagging speed of main memory access.

So, if the processor-memory performance gap is so big then isn't creating more powerfull processors useless ?

# Answer
> 1 votes
Creating faster processors with more cores makes sense because more speed and more cores is not the only change.

Big changes are:

1. Bigger caches. Ryzen Threadripper has up to 288MB of cache. My iPhone has more than 16 MB of cache. Your processor can do an awful lot of work without ever touching RAM.
2. More memory bandwidth. Data transfer has gone from 32 bit to 64 bit to 128 bit to 256 bit transfers in parallel and not stopping there.
3. Improved streaming. The time needed to move consecutive data is very much improved, so the right algorithms can process data at massive speed.
4. Changed algorithms. If I know that memory access speed has become the bottleneck, then I can change algorithms that were optimal with a processor of ten years ago to be optimal on today's processors.

---
Tags: computer-architecture
---


# Question
Title: How can the 4-bit page number and 8-bit offset as well as the page table be used to a answer a question like, "how big is each page"? etc
No more information required. I would just like to know how to use the information provided.

# Answer
> 1 votes
4 bits page number + 8 bits offset = 12 address bits : A\[11:0\]

* A\[7:0\] selects an offset within a page
* A\[11:8\] selects the page
* 1792 = 7\*256 : A=0111\_00000000
* 2304 = 9\*256 : A=1001\_00000000
* 2814 =11\*256 : A=1011\_00000000
* 1024 = 4\*256 : A=0100\_00000000

What is the problem? You get 8 address bits within each page. So what is the page size?

---
Tags: scheduling
---


# Question
Title: Identifying useless vertices in a directed graph
I have a randomly generated directed graph with 3 types of vertices: input, output, and the rest (I'll call them hidden).

A **useless vertex** is a hidden vertex which:

* can't be reached from an input vertex, **OR**
* can't reach an output vertex.

For example:

* input = yellow/green
* output = blue
* hidden = white
* useless = red border

Note that:

* cycles and self-loops are allowed
* the graph may be disjoint
* inputs and output nodes are known (i.e. you can determine what type of node an edge connects to and from)

---

**So what do you call this type of problem? Is there any algorithm for this?**

I'm looking for more information about this. I have a python script which seems to work. I'm just not sure if it will work for all cases since I don't fully understand it myself. It was a mix of DFS, trial-and-error, manual hand-checking, and a bunch of if statements.

# Answer
> 4 votes
Let $n$ and $m$ be the number of vertices and edges of your input graph $G = (V,E)$, respectively. You can find all useless vertices in time $O(n+m)$.

You can discover the set $S$ all vertices reachable by at least one source in $O(n + m)$ **overall** time.

You do this by either:

* running one visit from each of the input vertices, marking discovered vertices as visited, and taking care of **not** revisiting already visited vertices; or
* adding a dummy "super-source" vertex $s$ with an outgoing edge towards every input vertex in $G$, and then running a visit from $s$.

By using the same technique on the reversed graph $G^R$, you can find the set $T$ of all vertices that are reachable from an output vertex in $G^R$. In other words a vertex $v$ can reach an output vertex in $G$ iff $v \in T$.

The set you are looking for is then $V \setminus (S \cap T)$.

---
Tags: algorithms, graphs
---


# Question
Title: Memory Addressing - Alignment Clarification
I'm reading "*Computer Architecture A Quantitative Approach*" (5th edition) and I'm having a hard time understing this table:

I understand how Misalignment happens, i.e., some byte, half-word, word, or double word it's not a multiple of the address where the element is being stored or accessed. The part that I don't understand is that it says in the caption: "that the byte offsets that label the columns specify the low-order 3 bits of the address"

My question is why are the low-order 3 bits of the address important or relevant in this situation? I'm assuming that the low order bits are the lowest binary values in the address. My intuition is that the 3 low order bits can tell us if the address is a multiple(2,4, or 8) of whichever data is being accessed, but I'm not sure.

# Answer
> 1 votes
Let's take a sample address, written in binary: 110100100110.

Now let's compute it modulo 2, 4, 8, 16, writing the answer in binary:

* mod 2: 0
* mod 4: 10
* mod 8: 110
* mod 16: 0110

(I recommend checking this.)

Hopefully you can connect the dots now.

As an additional hint, let's do a decimal example: 987348957943 mod 100 = 43. Why? Since the $i$th digit from the right (counting from 0) is "worth" $10^i$, so all the digits other than the two on the far right are "worth" some multiple of 100.

---
Tags: computer-architecture, memory-allocation
---


title: Quick Sort vs Radix Sort

text:
# Question
Title: Quick Sort vs Radix Sort
In an coding exam, I was once asked this question:

> Assuming that you are *only* sorting Integers in ascending order, which algorithm do you use when you want to prioritize speed the most, but you also want to save space?

The options were:

> * LSD Radix Sort
> * Merge Sort
> * Quick Sort

I think an argument can be made between *LSD Radix Sort* and *Quicksort*.

*Radix sort* would function in $O(k n)$ and *Quicksort* would function in $O(n \log n)$ and worst case, $O(n^2)$

I chose *Radix Sort* as the answer, but I'm curious as to what others had to say.

# Answer
> 1 votes
This depends... If the number of input numbers is $n$, assuming the word-ram model of computation, a word size of $\Theta(\log n)$ bits, and worst-case inputs:

* Radix sort would require $O(n \log n)$ time and $O(n)$ auxiliary space.
* Quicksort with fixed or random pivot selection would require $O(n^2)$ worst-case time and $O(\log n)$ auxiliary space.
* Mergesort requires $O(n \log n)$ time and $O(n)$ auxiliary space.

Radix sort and Merge sort are then equivalent in this setting.

Notice that using quicksort with random pivoit selection results in a time complexity of $O(n \log n)$ with high probability. Selecting the pivot deterministically in a way that partitions the elements into two sets whose cardinalities are at most a constant factor apart gives your an algorithm with worst-case time complexity of $O(n \log n)$ and $O(\log n)$ auxiliary space.

---
Tags: sorting, quicksort, mergesort, radix-sort
---


title: Number of satisfying assignments

text:
# Question
Title: Number of satisfying assignments
How many satisfying assignments does the following formula have?

(x1 ∨ x¯2 ∨ x¯3)(x1 ∨ x2)(x¯1 ∨ x¯2)

# Answer
You have 8 options:

T F F

T T F

T T T

F T T

F F T

F F F

T F T

F T F

When the first column is x1 the second is x2 and the third x3

Lets try each one: (T or T or T)and(T or F)and(F or T)=T and T and T=T

(T or F or T)and(T or T)and(F or F)=F And so on...

You can continue from here and you will get the right answer
> 1 votes

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


# Question
Title: Finding total valid strings of length N that could be formed using characters A,B and C which satisfies given criteria
You have to find out the number of good strings of length N characters in size which you can make using characters A B and C.

A string is a good String if it satisfies the following three criteria:

* The total number of C in the string should not be greater than equal to 4.
* There should not be more than two consecutive A's in the string.
* Any two B's should be at least two characters apart.

How do I find total possible good strings for N length string?

Any psudo code will really help. Thank you.

# Answer
> 1 votes
Let $0 \leq i \leq n, 0 \leq c \leq 3, 0 \leq a \leq 2, 0 \leq b \leq 2$, and $DP\[i\]\[c\]\[a\]\[b\]$, denote the number of good strings of length $i$, but which also have more restrictions:

1. It should have $\le c$ number of C's
2. At most $a$ of its ending characters are A
3. None of the last $b$ characters are B.

The final answer that we are looking for is $DP\[n\]\[3\]\[2\]\[0\]$. Note that having 2 in the third parameter adds nothing extra over the restriction that the string already be a good string. Similarly, the fourth parameter being 0 also adds no further restrictions.

To compute $DP\[i\]\[c\]\[a\]\[b\]$, we look at the possibilities of the last character:

If $c \> 0$, then the last character can be C, and the term that would be added is $DP\[i-1\]\[c-1\]\[2\]\[\text{max}\\{0, b-1\\}\]$.

If $a \> 0$, then the last character can be A, and the term that would be added is $DP\[i-1\]\[c\]\[a-1\]\[\text{max}\\{0, b-1\\}\]$.

If $b = 0$, then the last character can be B, and the term that would be added is $DP\[i-1\]\[c\]\[2\]\[2\]$.

The base case would be $DP\[0\]\[c\]\[a\]\[b\] = 1$.

This Dynamic Programming can thus be solved in $\mathcal{O}(n)$ time and space.

---
Tags: algorithms, dynamic-programming, combinatorics
---


# Question
Title: Are two languages regular if the union is regular?
Statement:

> For any two languages $L\_1$ and $L\_2$ if $L\_1 \cup L\_2$ is regular, then $L\_1$ and $L\_2$ are regular.

Why is this statement false? Could somebody give me an example.

# Answer
Pick $\Sigma = \\{a,b\\}$, $L\_1 = \\{ a^n b^n : n \in \mathbb{N}\\}$ and $L\_2 = \Sigma^\* \setminus L\_1$.

The union $L\_1 \cup L\_2$ is $\Sigma^\*$ and hence is regular, but none of $L\_1$ and $L\_2$ is.
> 2 votes

# Answer
Definitely not. Consider `L` to be non-regular, then L union its complement is the language of all words which is regular, but bot L and L complement are not.
> 0 votes

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


# Question
Title: How can I determine the start non-terminal of a CFG?
Suppose I have a grammar such that there exist $n$ production rules which contain only terminal symbols, and none of these rules produce the same terminal (*disjoint*).

> $A ::= x|y|z$
>
> $B ::= a|b|c$
>
> ...
>
> $N ::= l|m|k$

Further suppose that I cannot simply merge these production rules together as they are used in different parts of the grammar.

How can I hence determine or rather choose, the start non-terminal $S$, for purposes of $LL(1)$ parsing?

Thanks

# Answer
> 3 votes
By definition a grammar is a tuple $(N,T,P,S)$ where $N$ is the set of non-terminals, $T$ is the set of terminals, $P$ is the set of productions, and $S \in N$ is the start symbol.

Therefore if you have a grammar you already have $S$ (and if you don't know $S$ then you don't have a grammar).

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


title: Turing reducible in natural numbers?

text:
# Question
Title: Turing reducible in natural numbers?
I'm confused about Turing reducible things.

I understanded Turing reducible like this

`"There is an oracle algorithm which is about set A and when this algorithm is derived from oracle algorithm of set B, it is called A is Turing-reducible to B"`

So by this, I have to solve the problem.

> N is the set of natural numbers = {1, 2, 3, ...}
>
> Let A be the set of all even natural numbers.
>
> Let B be the set of all odd natural numbers.
>
> Prove that A is Turing-reducible to B.

Here is what I have thought.

The oracle algorithm of A is n%2==0 which n belongs to natural numbers.

And oracle algorithm of B is n%2==1 which n belongs to natural numbers.

How can I derive n%2==0 from n%2==1 ?

Or my approach is wrong?

Thanks for your help.

# Answer
To show that $A$ is Turing-reducible to $B$ you need to prove the existence of a Turing Machine that is able to decide $A$ when given access to an oracle for $B$.

In your specific case a possible Turing Machine $M$ takes as input a string $x \in \\{0,1\\}^\*$ encoding the natural number $n$ (I'm assuming $0 \in \mathbb{N}$) in binary and operates as follows:

* It flips the last bit of $x$. Now $x$ represents an odd number iff the input number $n$ was even.
* It invokes the oracle for $B$ with input $x$.
* It accepts iff, according to the oracle, $x \in B$.

Notice that the fact that $M$ has access to an oracle for $B$ does not mean that $M$ must use that oracle. The following is also a valid choice for $M$:

* Locate the last bit $y$ of the input string $x$.
* If $y=0$ accept. Otherwise reject.
> 2 votes

---
Tags: computability, reductions, discrete-mathematics
---


# Question
Title: Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value
GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is \<= T.

This question is a simplification of this dynamic programming question:

> It’s Tushar’s birthday today and he has N friends. Friends are numbered \[0, 1, 2, …., N-1\] and i-th friend have a positive strength S(i). Today being his birthday, his friends have planned to give him birthday bombs (kicks :P). Tushar’s friends know Tushar’s pain bearing limit and would hit accordingly. If Tushar’s resistance is denoted by R (\>=0) then find the lexicographically smallest order of friends to kick Tushar so that the cumulative kick strength (sum of the strengths of friends who kicks) doesn’t exceed his resistance capacity and total no. of kicks hit are maximum. Also note that each friend can kick unlimited number of times (If a friend hits x times, his strength will be counted x times)
>
> Example:
>
> R = 11, S = \[6,8,5,4,7\] Ans = \[0,2\]

Clearly, the maximum number of kicks = R/ min\_element(S) = 11/4 = 2

So the question reduces to find the lexicographic smallest order of 2 elements in the Array such that the total of N elements is less than or equal to 11.

I am having a tough time thinking about a solution for this. Any leads/ ideas would be appreciated!

# Answer
You are on the right track.

It turns out the original question can be solved by a greedy algorithm. (A full blown solution by dynamic programming as I tried a while ago is both an overkill on coding and short of performance.)

Let us use the notation in the original question. $R$ is for the resistance capacity. $S$ is for the array of strengths.

Let the index of the first minimum strength be $m$. Then the maximum number of kicks is $n = R/S\[m\]$. So $O=\[m, m, \cdots, m\]$, where the number of $m$'s is $n$, is a kick order with maximum number of kicks, with total strength $n\*S\[m\]$.

How can we get a lexicographically smaller order with the same number of kicks? If we can find an index $i$ smaller than $m$ such that we can replace a kick of strength $S\[m\]$ by a kick of strength $S\[i\]$ without overpassing the resistance capacity $R$, then we can replace the first element in $O$ by $i$, making the order lexicographically smaller. To make it as lexicographically as small as possible, we would like the index $i$ as small as possible and, then, we would like to use it as many times as possible.

For example, $R = 11, S = \[6, 8, 5, 4, 7, 4\]$. Then the first minimum strength is the first 4 whose index is 3. So $n=11/4=2$ and $O=\[3,3\]$ with total strength $4\*2=8$. To make it smaller, we will check the strengths before 4 in order. The first one is $6$. Since $8-4+6=10\<11$, we find a smaller order $\[0,3\]$. If we apply 6 again, we would get $10-4+6=12 \> 11$. So we go ahead to check the next strength 8, which is too large. So we go ahead to check 5. Since $10-4+5=11\le 11$, we find a smaller order $\[0,2\]$. Since the room left for replacement, $11-11 =0$, we stop our effort. The final answer is \[0,2\].

I have verified that my program wrote along the above approach works. Hopefully, I have written enough to encourage you to go ahead. Hopefully, I have not written too much to spoil the fun for you.

This problem is a variation of the unbounded knapsack problem.
> 7 votes

# Answer
JAVA Implementation of the above approach by Apaas.Jack:-

```
public class Solution {
    public int sumDiff(ArrayList<Integer> ans, ArrayList<Integer> B,int A){
        int sum = 0;
        for (int i = 0;i<ans.size();i++){
            sum += B.get(ans.get(i));
        }
        return A-sum;
    }
    public ArrayList<Integer> solve(int A, ArrayList<Integer> B) {
        int min = Integer.MAX_VALUE;
        int ind = -1;
        for (int i = 0;i<B.size();i++){
            if (min>B.get(i)){
                min = B.get(i);
                ind = i;
            }
        }
        int maxKicks = A/min;
        int temp = maxKicks;
        ArrayList<Integer> ans = new ArrayList<>();
        if (maxKicks==0){
            return ans;
        }
        for (int i = 0;i<maxKicks;i++){
            ans.add(ind);
        }
        int sum = maxKicks*B.get(ind);
        for (int i = 0;i<ind;i++){
            if (sumDiff(ans,B,A)==0||temp==0){
                Collections.sort(ans);
                return ans;
            }
            while ((sum-B.get(ind)+B.get(i))<=A && temp != 0){
                ans.remove(0);
                ans.add(i);
                temp--;
                sum += (B.get(i)-B.get(ind));
            }
        }
        Collections.sort(ans);
        return ans;
    }
}

```
> 0 votes

# Answer
\`c++ solution

```
#define deb(x) cout<<#x<<" : "<<x<<"\n"
vector<int> Solution::solve(int A, vector<int> &B) {
map<int,int> s;

  for(int i=0;i<B.size();i++)
  if(s[B[i]]!=0)
  s[B[i]]=min(s[B[i]],i);
  else
  s[B[i]]=i;
  int idx=min_element(B.begin(),B.end())-B.begin();
  int mini=*min_element(B.begin(),B.end());
 int x=A/mini;
 vector<int> ans;
 for(int i=0;i<x;i++)
 ans.push_back(mini);
 int sum=mini*x;
 int j=0;
 for(int i=0;i<idx;i++)
  {  //  deb(sum);
   while(j<ans.size() && sum+B[i]-mini<=A)
   {
       ans[j]=B[i];
       sum=sum+B[i]-mini;
       //deb(sum);
       j++;
   }
  }
  for(int i=0;i<ans.size();i++)
  {
    ans[i]=s[ans[i]];
   }
    return ans;

}

```

\`
> -1 votes

---
Tags: dynamic-programming, greedy-algorithms, knapsack-problems, subset-sum, coin-change
---


# Question
Title: Using substitution method to prove asymptotic lower bound of $T(n) = T(n-1) + \Theta (n)$
I try to prove that the asymptotics of the recurrence $ T(n) = T(n-1) + \Theta (n) $ is $ T(n) = \Theta(n^2) $.

By $\Theta$, I mean tight bound from above and below.

---

I can write the equation like this: $$ T(n) = T(n-1) + \Theta (n) = T(n-1) + cn. $$

I'm having a hard time proving the lower bound with this method, do you have any idea how?

What I did for *Upper bound* is:

Assume: $$ T(n-1) \leq c(n-1)^2, \quad c \in R $$

Therefore: $$ T(n) \leq c(n-1)^2 + cn = cn^2 - 2cn + c + cn = cn^2 - cn + c \leq cn^2 $$

Therefore I get: $$ T(n) \leq O(n^2) $$

For $O$, by which I mean just an upper bound.

So, how do I prove a matching lower bound using this method?

# Answer
Let $f(n) = \Theta(n)$. Thus there are $N,a,b\>0$ such that for $n \geq N$, we have $an \leq f(n) \leq bn$.

Now suppose that $T(n) = T(n-1) + f(n)$, with some base case $T(0) = C$. Unrolling the sum, $$ T(n) = C + f(1) + \cdots + f(n). $$ Let $D = C + f(1) + \cdots + f(N-1)$. For $n \geq N$, $$ T(n) \leq D + b(N + \cdots + n) = D + b\frac{(n-N+1)(n+N)}{2} = O(n^2). $$ Similarly, $$ T(n) \geq D + a(N + \cdots + n) = D + a\frac{(n-N+1)(n+N)}{2} = \Omega(n^2). $$
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Partition the indices of 2d array to minimize sum of sub-matrices
Given an $n\times n$ Matrix $M$, and the indices $\[{1,2,3,4,...,n}\]$ are divided into several intervals : $\[1,x\_1\],\[x\_1,x\_2\],...\[x\_k,n\]$, which further extract several squared sub-matrices along the $M$'s diagonal - $M\[1...x\_1,1...x\_1\],M\[x\_1...x\_2,x\_1...x\_2\],...M\[x\_k...n,x\_k...n\]$.

Suppose $Sum(Matrix)$ is the sum of all elements in a matrix. How to design an algorithm to find out an optimal partition that minimizes $Sum(M\[1...x\_1,1...x\_1\]) + Sum(M\[x\_1...x\_2,x\_1...x\_2\])+...+Sum(M\[x\_k...n,x\_k...n\])$

To visualize , find out a partition that minimizes the sum of all shaded elements in the table below

# Answer
> 1 votes
First we note that with $\mathcal{O}(n^2)$ precomputation, where we store the 'prefix sums', we can find the sum of all the elements in a given square subgrid in $\mathcal{O}(1)$ time.

Now, let $DP\[i\]$ be the optimal answer, if the input matrix had only the first $i$ rows and first $i$ columns. The final answer that we are looking for is $DP\[n\]$.

The base case would be $DP\[0\] = 0$.

To compute $DP\[i\]$, we iterate over all $j$ such that $1 \le j \leq i$, and we consider the last interval in the partition to be $\[j, i\]$. For a fixed $j$, the minimum sum would be $DP\[j-1\] + Sum(M\[j \ldots i\]\[j \ldots i\])$. So that leads to the equation

$$DP\[i\] = \min\_{1\leq j \leq i} (DP\[j-1\] + Sum(M\[j \ldots i\]\[j \ldots i\]))$$

So, $DP\[i\]$ can be computed in $\mathcal{O}(n)$ time, and the whole problem takes $\mathcal{O}(n^2)$ time and space.

---
Tags: dynamic-programming, recursion, heuristics, algorithm-design
---


# Question
Title: symmetrical subtraction between $L_1 \in \mathsf{P}$ and $L_2 \in \mathsf{NPC}$
If $L\_1 \in \mathsf{P}$ and $L\_2 \in \mathsf{NP-Complete}$ and $L\_3$ is the symmetric difference between $L\_1$ and $L\_2$, is $L\_3$ also in $\mathsf{NP-Complete}$ necessarily?

I'm pretty sure the answer is no but I can't find even one example that shows I'm right.

# Answer
> 2 votes
The answer is actually yes. Some intuition is that, when considering $\mathsf{NP}$-completeness (or in general, considering any complexity class under polynomial-time reductions), polynomial-time parts of the computation don't matter. Since $L\_1$ is polynomial time, and $L\_1 \Delta L\_2$ and $L\_2$ can be computed from each other knowing the answer to $L\_1$, they should both be equivalent languages, up to polynomial-time computations.

Formally, to show "equivalence" we use polynomial time reductions. So you could solve this problem by:

1. Finding a polynomial-time reduction from $L\_2$ to $L\_1 \Delta L\_2$. (How do we compute $L\_1 \Delta L\_2$ from $L\_2$?)
2. Finding a polynomial-time reduction from $L\_1 \Delta L\_2$ to $L\_2$. Hint: use the fact that $$(L\_1 \Delta L\_2) \Delta L\_1 = L\_2$$

Once you have done this, you have shown that $L\_2$ and $L\_1 \Delta L\_2$ are equivalent; if you are familiar with the notation, $$ L\_2 \le\_p L\_1 \Delta L\_2 \le\_p L\_2 $$ which means if one of them is $\mathsf{NP}$-complete, then both of them are.

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


title: Are interrupts only found in BIOS?

text:
# Question
Title: Are interrupts only found in BIOS?
I may be misunderstanding here-- but are interrupts only found in BIOS and not UEFI systems?

More context: "Through standardized calls to the BIOS (“interrupts” in computer parlance), the operating system can trigger the BIOS to read and write to the disk and interface with other hardware components."

I read this in a paper I'm reading and thought that interrupts may only be accessible in BIOS. I found some old stackoverflow answers (https://stackoverflow.com/questions/15101183/does-booting-in-efi-mode-mean-that-i-shall-not-have-access-to-bios-interrupts) that also confused me into thinking that interrupts are not programmable/accessible in UEFI.

# Answer
Almost all CPUs contain interrupt lines. Both Bios and UEFI provide services for handling interrupts on these lines. UEFI is an extended version of the old Bios. So, UEFI provides all services provided by Bios.
> 1 votes

# Answer
It was common in DOS days (where all programs ran with full privileges) to call directly into the BIOS (the Basic Input Output System, offering rock-bottom access to I/O of the PC, like reading a disk sector or writing a character to the screen), mostly for speed (the services offered by the operating system where not much fancier anyway, and more or less a superset of the above). The access to those services were by invoking an interrupt from software (the 8088 way of calling operating system services was to use a software triggered interrupt).

Higher end processors (starting at least with the intel 80286, but long standard on other processor lines) allow to rigurously control allowed user program actions, reserving direct hardware access (as offered by BIOS) to the operating system. This is needed to protect the operating system (and thus the workings of the whole system) and even different processes from wayward programs. Starting with Windows NT (released 1993) on PCs user programs don't have such access anymore.

The above is DOS/Windows/PC centric, the whole BIOS idea was to give an uniform interface to sometimes wildly different underlying hardware in the PC world.
> 1 votes

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


title: Find nearest neighbour in a radius

text:
# Question
Title: Find nearest neighbour in a radius
I have a set of points **A** in my space (geo points but I can assume they are on a 2D plane).

I have another set of points **B**.

For every point in **B** I want to find every point in **A** inside a radius **R** with center in the considered point from **B** set.

I did it with KDTree, this provide me a very fast and easy algorithm to create the data structure and find neighbours **but** it doens't find every point in a radius because it could avoid a path which contains element in my radius but not in the same subset of the radius center.

**Minimal example of KDTree failing**:

While exploring KDTree the target point (red) is under the line of point number 1. This will proceed to exploration of point under the line, this will miss the real point inside the red point radius.

What algorithm or data structure allow 100% correctness?

I know for sure I will performe worse but I am look for a balance between search speed and full correctness.

# Answer
The K-D tree is a good data structure for solving this. However you can't blindly apply the search procedure only to the center point, you must be a bit smarter.

While searching the K-D tree for your points, every time you must choose the left or right child to search in, check whether the splitting plane is to the left of your circle, intersects it, or is to the right of the circle.

If the splitting plane is to the left of your circle you must continue searching in the right child, and vice versa. However when the splitting plane *intersects* your circle you must search *both* children.
> 2 votes

---
Tags: data-structures, space-complexity, nearest-neighbour, space-partitioning
---


# Question
Title: Finding the language generated by a grammar
Forgive my lack of knowledge, I am new. I tried to find the language generated by this grammar

```
S → aA | bS | cS | ɛ
A → aA | bB | cS | ɛ
B → aA | bS | ɛ

```

And I came to $\\{a^pb^qc^r \mid p \ge 0 \text{ and } q \ge 0 \text{ and } r \ge 0 \\}$, but there seems to be a problem as the above language do not have a combination of `abc`.

# Answer
> 1 votes
In general, a grammar (or even a regular expression) describes a language that is very hard to describe succintly in other terms. They were devised as means to describe languages in simple, easy to handle, terms.

Sure, there are regular expressions/grammars that describe easy to write down languages; most (in some loose sense of "most") of them don't.

# Answer
> 0 votes
Notice that in this grammar, every non-terminal symbol $X$ has only rules of the form $$ X \to xX' $$ where $x$ is a terminal symbol and $X'$ is another non-terminal symbol. **This kind of grammar can be thought of as an NFA.** So you could try writint it down as an NFA.

* There are three states: $S, A, B$.
* $S$ is the initial state. "Final states" correspond to states that have a rule going to $\epsilon$, so that's all the states.
* Now draw the transitions. Starting in state $S$ or $A$, we can read any number of $a$s and $c$s and we stay in states $S$ and $A$. What happens on input $b$ is more interesting.

Once you have the transitions, you can use the procedure to turn an NFA into a regular expression to get a description of the language.

---
Tags: formal-languages, formal-grammars
---


title: Unordered pairs in Homotopy Type Theory

text:
# Question
Title: Unordered pairs in Homotopy Type Theory
It's conceptually simple to state what an "unordered pair" is supposed to be in set theory. Yet, in homotopy type theory I have trouble formalizing this. A first naive try in agda syntax:

```
data UPair (A : Type ℓ) : Type ℓ where
  mkpair : (x y : A) → UPair A
  uswap : ∀ a b → mkpair a b ≡ mkpair b a

```

This fails, since there are actually two different paths between e.g. `mkpair 1 2` and `mkpair 2 1`, that is we have `uswap 1 2` and `sym (uswap 2 1)`. Again, these can be forced equal by a one-higher path constructor, but one would have to continue for ever.

Obviously, if `A` is an `n`-truncated type, we can stop at some point. Generally truncating at some level fails because it might forget some non-trivial paths in `A`. Take for example the set-truncation of the above type and `A = S¹`, the circle, then the path `i. mkpair (loop i) base` is lost and identified with `refl (mkpair base base)`.

Can we generally write down the type of unordered pairs of a parameter `A : Type ℓ`? Can the resulting type live inside the universe ?

---

Clarification:

Let `A· = (A , a)` be a pointed type. Define `UPA· = (UPair A, mkpair a a)` as a pointed type. I would then expect `Ωₜ UPA· ≡ UPair (Ωₜ A·)`. These correspond to singleton sets.

Let `A∙ = (A, a, b)` be a bipointed type with `a ≢ b`. Then I expect that the map `(a ≡ a) × (b ≡ b) → mkpair a b ≡ mkpair b a` given by `(pa , pb) → (λ i → mkpair (pa i) (pb i)) ∙ uswap a b` is an equivalence.

# Answer
The type of unordered pairs in a type $A$ is defined to be $$\sum\_{(X:\mathcal{U})}\sum\_{(H:\\|X\simeq \mathsf{bool}\\|)}A^X.$$ In other words, an undordered pair in $A$ is simply a map $X\to A$ from a type $X$ that merely has two elements.

Note that in general, this is not a set, because the type of 2-element types is not a set but a 1-type. The way to think about this is that unordered pairs have some symmetries (swapping the order of the elements in the unordered pairs) that should be taken into account in homotopy type theory.

Note that the type of unordered pairs can also be used to define the type of fully coherent commutative binary operations on a type $A$. This type is simply $$\Big(\sum\_{(X:\mathcal{U})}\sum\_{(H:\\|X\simeq\mathsf{bool}\\|)}A^X\Big)\to A.$$ In other words, a fully coherent commutative binary operation on $A$ is an operation on the unordered pairs of $A$.
> 4 votes

# Answer
The *set* of unordered pairs of `A` can be defined using a higher-inductive type with set-truncation, just as you suggested, somewhat like this (I am writing this off the top of my head without verifying it in Agda, but you'll get the point):

```
data UPair (A : Type ℓ) : Type ℓ where
  mkpair : (x y : A) → UPair A
  uswap : ∀ a b → mkpair a b ≡ mkpair b a
  trunc : ∀ (u v : UPair A) (p q : u ≡ v) → p ≡ q

```

It is obvious that `UPair A` is a set (is a $0$-type) because `trunc` directly witnessess this fact. You do not have to add any higher-path constructors.
> 1 votes

---
Tags: homotopy-type-theory
---


# Question
Title: Understanding Randomized Select algorithm
Here is the algorithm in pseudo code:

Where $A$ is the array to search, $p$ is the starting index in the array, $r$ is the ending index and $i$ represent the number of smaller values we want from our goal value, the $i$ smallest number in the array.

I dont understand the $k$.

It gets a value that dont realy represent the index of the value in the original array, but the index value in the sub array we are at, at the recursion process.

Similarly, it doesnt represent the amount of values that are smaller than the pivot we are at, but the number of smaller values in the current sub array in the recursive process.

So how can we check between $i$ and $k$? They dont talk on the same arrays...

Thank you.

# Answer
The function Randomized-Partition accepts an array $A\[p\],\ldots,A\[r\]$ and partitions it around a pivot. The position $q$ of the pivot is returned. We are guaranteed that $A\[p\],\ldots,A\[q-1\] \leq A\[q\] \leq A\[q+1\],\ldots,A\[r\]$.

The location of the pivot $q$ within the array is $k := q-p+1$. That is, $q$ is the $k$th smallest element in $A\[p\],\ldots,A\[r\]$. To see this, let us assume from now on that all elements of $A$ are distinct (this will slightly simplify the arguments). Then the $q-p$ elements $A\[p\],\ldots,A\[q-1\]$ are smaller than $A\[q\]$, and the rest are larger than $A\[q\]$.

If $i = k$, then we are done. If $i \< k$, then the $i$th smallest element of $A\[p\],\ldots,A\[r\]$ belongs to the subarray $A\[p\],\ldots,A\[q-1\]$ (since the $i$th smallest element is smaller than $A\[q\]$, which is the $k$th smallest element), and moreover, it is the $i$th smallest element in that subarray. If $i \> k$, then the $i$th smallest element of $A\[p\],\ldots,A\[r\]$ belongs to the subarray $A\[q+1\],\ldots,A\[r\]$ (since the $i$th smallest element is larger than $A\[q\]$, which is the $k$th smallest element), and moreover, it is that $(i-k)$th smallest element in that subarray (since the $k$ elements $A\[p\],\ldots,A\[q\]$ are already smaller than it).
> 3 votes

---
Tags: algorithms, search-algorithms, selection-problem
---


# Question
Title: Why is the opcode 0 for all r-type instructions? Please explain your answer
I can't seem to find the explanation for why all r-type instructions have opcode 0 always. Can anybody explain why this is so.

# Answer
> 3 votes
In designing an ISA, there are many tradeoffs that can/need to be taken. This makes it slightly challenging to answer why questions but I will do my best.

In mips I am sure you are aware of the three instruction classes: I, J, and R.

For this explenation I belive only I and R are relevant.

```
    Type    [31-26] [25-21] [20-16] [15-11] [10-06] [05-00]
    R-Type  [opcode] [$rs]   [$rt]  [ $rd ] [shamt] [funct]
    I-Type  [opcode] [$rs]   [$rt]  [         imm         ]

```

First lets examine the implications of using \[31-26\] for R-Type \[funct\] information.

This would limit the total number of R + I + J instructions to 64. To increase this field for all instructions would limit the size of immediate values.

Additonaly, \[5-0\] of R instructions would be freed up but not used, not very efficient. By moving R-type opcodes to \[funct\] the total possible instructions jumps to ~127, while keeping 16 bit immediates.

Finally, if you notice in the data path below there is almost no cost to moving R instruction opcodes to the \[funct\] field, and it makes room for future instructions to be added to the ISA.

I hope this helps

---
Tags: computer-architecture, mips
---


# Question
Title: Why F-bounded polymorphism and F-bounded quantification are called, well, F-bounded
It's claimed in Wikipedia that:

> F-bounded quantification or recursively bounded quantification, introduced in 1989, allows for more precise typing of functions that are applied on recursive types. A recursive type is one that includes a function that uses it as a type for some argument or its return value

Here's the article which Wikipedia refers to, and F-bounded quantification is introduced in that article in following fashion:

> F-bounded quantification is a natural extension of bounded quantification that seems particularly useful in connection with recursive types.

My question is - why though it's F-bounded, what does "F" stands for in this particular context?

# Answer
> 4 votes
It appears that "F" does not stand for anything in particular: rather, it is the metavariable symbol that is used in the definition of *F-bounded quantification*. In the paper in which F-bounded quantification was introduced, *F-Bounded Polymorphism for Object-Oriented Programming*, the authors write:

> To solve this problem and related difficulties with other forms of recursive types we introduce a generalization of bounded quantification which we call F-bounded quantification, for want of better terminology.

suggesting that they do not view the name as particularly descriptive. Later, when they define F-bounded quantification explicitly, they write:

> We say that a universally quantified type is F-bounded if it has the form $$\forall t \subseteq F\[t\] . \sigma$$ where $F\[t\]$ is an expression, generally containing the type variable $t$.

As far as I can tell, the paper contains no other explanation and the most apparent explanation is that the "F" in the terminology is chosen to coincide with the symbol $F$ chosen, arbitrarily, for the definition.

---
Tags: terminology, type-theory
---


# Question
Title: Gas Station Problem - Dijkstra's Algorithm variation
## I am trying to find an algorithm which finds the least expensive route from one town to another.

This is the general setup.

There are a series of one-way roads from some towns to other towns. Not all towns have roads between them. Let R be the set of all the roads and let T be the set of all towns. For two towns u, v ∈ T, let (u→v)∈ R be the one-way road from u to v and let w(u, v) be the amount of gasoline required to travel along this road.

Let S ⊂ T be the set of towns which have gas stations. At a town u ∈ S, one can choose to pay c(u) dollars to fill up the gas tank. Note that the cost does not change depending on how much gas must be bought; if you need to buy gas, fill up the whole tank. The cost is only affected by which town u is.

The car’s tank can hold k units of gas and it is full at the start.

## My ideas:

I believe this uses a shortest path graph algorithm, but I am unsure how to implement it. I believe it uses Dijkstra's algorithm. I also recognize that the run-time depends on |T|, |R| and |S|.

Any advice will help! thanks :)

# Answer
We note that we can assume that the source node has a gas station with refilling cost as $0$, even if it doesn't. It just makes the algorithm cleaner, as we start out with a full tank, and we note that no optimal solution is ever going to come back to the source again and refill. Similarly, we also assume that the $\text{target}$ also has a gas station with some arbitrary cost of refilling - the cost here wouldn't matter. So in effect, we set $S = S \cup \\{\text{source, target}\\}$.

In the first phase of the algorithm, for every $s \in S$, we want to find all the other towns in $S$ that we can reach without refueling, if we start out with a full tank from $s$. For this, we can take two approaches:

1. Run Floyd–Warshall using $w(u, v)$ as the weight of every edge, to find the shortest distance from any town to any other. Now, for every $s \in S$, we iterate through every other $t \in S$ and if the shortest distance from $s$ to $t$ is $\leq k$, then we can reach $t$ from $s$ without refueling. So we create a new graph $G'$, whose vertex set is $S$, and add a directed edge $(s, t)$ with a weight of $c(s)$. This approach takes $\mathcal{O}(|T|^3)$ time and $\mathcal{O}(|T|^2)$ space.
2. Another way to construct the same $G'$, would be to start a Dijkstra's from every $s \in S$, and stop when the distance is more than $k$, which in the worst case wouldn't help our complexity. This approach would require $\mathcal{O}(|S| \times (|R| + |T|\log|T|)$ time and $\mathcal{O}(|T|^2)$ space.

The second approach is asymptotically better than the first one, but the first one is easier to implement. So you can decide which fits your needs better.

Now on to the second phase of the algorithm, where we have the graph $G'$ with us, which again is a directed weight graph, but now the weights are costs of refilling. So all we have to do is run a Dijkstra's on this graph starting from $\text{source}$. The answer is the shortest distance to $\text{target}$.

So the total algorithm needs $\mathcal{O}(|S| \times (|R| + |T|\log|T|)$ time and $\mathcal{O}(|T|^2)$ space.
> 3 votes

---
Tags: algorithms, graphs, shortest-path, greedy-algorithms, dijkstras-algorithm
---


# Question
Title: A grammar for my context free language {xy | x, y ∈ {a, b} ∗ , |x| =|y| , x != y}
This question is given as an exercise to me . I took a look at the solution given by the instructor which is not the same as my solution .

So I thought it would be wise to ask it here considering I am a newbie on that topic.

My solution basically is as follow :

S -\> aSa | bSb | aTb | bTa

T-\> aTa | bTb | aTb | bTa | e

My apporach to the problem is as follows : If I don't find any differences (if both characters are the same) , continue with S until you find make a difference then you can do whatever you want with the string as long as you obey the rule of x having the same lenght .

# Answer
> 0 votes
There can be multiple grammars for one language, all equally valid.

We generally don't check solutions to exercises here. The way to tell for yourself whether your answer is correct is to prove it correct: see How to show that L = L(G)? for techniques on how to do that.

---
Tags: context-free
---


# Question
Title: Is the knapsack problem NP-hard when $v_i=i$?
The knapsack problem is NP-hard and can be formulated as: $$\begin{align}&\text{maximize } \sum\_{i=1}^n v\_i x\_i,\tag{P1}\\\& \text{subject to } \sum\_{i=1}^n w\_i x\_i \leq W,\\\&\text{and } x\_i \in \\{0,1\\}.\end{align}$$

What if $v\_i=i$? Is it still NP-hard?

$$\begin{align}&\text{maximize } \sum\_{i=1}^n ix\_i,\tag{P2}\\\& \text{subject to } \sum\_{i=1}^n w\_i x\_i \leq W,\\\&\text{and } x\_i \in \\{0,1\\}.\end{align}$$

I am trying to reduce (P1) to (P2). Given an instance of (P1), I create the same number of items, same weights. Now, I have to relate the solutions to (P1) and (P2).

# Answer
> 5 votes
No, this problem is in $\mathbf{P}$. The main point being that the sum of all the values is $1 + 2 \ldots + n = \frac{n(n+1)}{2} = \mathcal{O}(n^2)$, which is polynomial in the input size. Without the extra restriction of $v\_i = i$, the sum of all the values could be exponential in the input size, as the values are represented in binary in the input.

So we can define $DP\[i\]\[v\]$, where $1 \leq i \leq n$ and $0 \leq v \leq \frac{n(n+1)}{2}$, to be the minimum weight needed to get a value of at least $v$, using only the first $i$ items. If it cannot be achieved, we'll set $DP\[i\]\[v\] = INF$. The final answer is the maximum $v$ such that $DP\[n\]\[v\] \leq W$.

The DP values can be calculated as follows:

$DP\[i\]\[v\] = \min(DP\[i-1\]\[v\], w\_i + DP\[i-1\]\[v - v\_i\])$.

The first term considers the possibility of the $i^{th}$ item not being chosen, and the second term is the possibility that it is chosen.

So the entire problem can be solved in $\mathcal{O}(n^3)$ time and $\mathcal{O}(n^3)$ space, which can be reduced to $\mathcal{O}(n^2)$ space by just reusing two arrays of size $\frac{n(n+1)}{2} + 1$.

---
Tags: reductions, np-hard
---


title: Formal definition of hash function

text:
# Question
Title: Formal definition of hash function
I was reading through the classic CLRS with the intention of reviewing the hash tables theory, more specifically the hash function definition I just wanted a reference to quote.

I cannot find a formal definition given but I think it's fair to say a hash function (not univerisal) $h$ is a surjective map from a set of keys $K$ to a subset of integers $U$, for each $k \in K$ we define $h(k)$ to be the *hash value of $k$*. From the explanation given in CLRS it seems though this restriction on $U$ (be integers) might be too restrictive, however since I think the definition has to show some practical aspects I think this might be correct.

Can you either give me: 1. A paper/book with a formal definition 2. Confirm if my definition is correct?

Thank you

# Answer
A hash function is used to map a set of keys to a subrange of the integers (it is used as an index into an array, in the end). So it must be (assuming zero based arrays, as in C), $h \colon \mathcal{U} \to \[0, m - 1\]$ if $\mathcal{U}$ is the universe of keys.
> 2 votes

---
Tags: hash, definitions
---


title: Is it decidable for a NPDA to halt?

text:
# Question
Title: Is it decidable for a NPDA to halt?
I know that it is decidable for an NPDA to accept a string $w$, i.e. a TM can receive as input the description of an NPDA along with a string and test if the NPDA accepts the string.

But are there languages where given an NPDA description as input, the TM may not halt, i.e. since the simulated NPDA also does not halt...

# Answer
> 4 votes
The (non)halting condition for PDAs doesn't make much sense; "non-halting" for a PDA means that there are one or more $\epsilon$-moves (not input read) that can cause a "loop" or an infinite stack expansion.

In order to test if a PDA accepts a string $x$, a Turing machine should not "barely simulate" it (i.e. recusively enumerate all reachable (partial input,stack content,state) configurations of the PDA. Otherwise such machine could never end if the PDA doesn't accept the string and it contains $\epsilon$-moves.

In order to test if a PDA accepts $x$ it you should build the equivalent CFG anc check if the CFG generates the string $x$.

Also note that for any PDA $A$ there is an equivalent (costructible) PDA $A'$ with no $\epsilon$-moves (*real-time* PDA, i.e. the PDA reads a letter from its input every step) and even there is an equivalent $A''$ with no $\epsilon$-moves and only one state (*simple real-time* PDA). See Greibach normal form.

A TM once constructed $A'$ (or $A''$) can barely simulate it, enumerating all the possible nondeterministic choices, but in this case it will surely halt.

# Answer
> 1 votes
Transform your PDA into a CFG (standard construction; huge grammar but finite), rewrite the CFG in Chomsky Normal Form (standard construction; again, large grammar but finite process), use CYK algorithm (cubic in input length) with the result.

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


# Question
Title: Why do grammars in Chomsky Normal Form have derivations of length 2n-1?
I would like to know how they obtained the expression $2n-1$ as said from the excerpt of article (p.3):

> The key advantage is that in Chomsky Normal Form, every derivation of a string of n letters has exactly 2n−1 steps.

I could get how $2n$ comes since there are only 2 variables on the R.H.S of each production but couldn't get how the expression $−1$ came in $2n−1$.

# Answer
Let $n$ be the length of a string. We start with the (non-terminal) symbol $S$ which has length $n=1$.

Using $n - 1$ rules of form $(non-terminal) \rightarrow (non-terminal)(non-terminal)$ we can construct a string containing $n$ non-terminal symbols.

Then on each non-terminal symbol of said string of length $n$ we apply a rule of form $(non-terminal) \rightarrow (terminal)$. i.e. we apply $n$ rules.

In total we will have applied $n - 1 + n = 2n - 1$ rules.

**example**

Observe following grammar in Chomsky-normal form.

$ \begin{align} S & \to AB \\ A & \to BC | AC\\ A & \to h|b\\ B & \to a \\ C & \to z \\ \end{align} $

Consider following derivation

$ \begin{align} \text{Current string} & & \text{rule applied} & & \text{#rules applied} & & \text{#length of string} \\ S & & \text{\\\} & & 0 & & 1 \\ AB & & S \to AB & & 1 & & 2 \\ BCB & & A \to BC & & 2 & & 3 \\ \vdots & & \vdots & & \vdots & & \vdots \\ A\cdots CB & & \text{\[multiple rules\]} & & n-1 & & n \end{align} $

This last line represents a string containing only non-terminals. You can see that a string containing $n$ non-terminals is derived using $n-1$ rules. Let's continue. Applying $n$ rules of form $A \to a$ to each non-terminal in the string above gives you a string containing only terminals and thus a string from the language decided by the grammar. The length of the string has not changed (it's still $n$) but we applied an additional $n$ rules so in total we have applied $n-1 + n = 2n - 1$ rules.

While this explanation hopefully gives you an intuitive understanding, I think it would be an useful excercise to construct a formal proof using induction.
> 7 votes

# Answer
And each of the $A \to B C$ produtions make the sentential form one longer. You start with length $1$, to reach $n$ means $n - 1$ steps. If a string has length $n$, there will be $n$ steps to get the terminals. In all, $2 n - 1$ steps.
> 3 votes

# Answer
Let us consider an simple example.

```
A -> BC
B -> b
C -> c

```

String to be generated is `bc`.

Then the steps are.

```
A -> BC
  -> bC
  -> bc

```

Thus no of steps required is 3. That is $2n-1$.
> 3 votes

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


# Question
Title: What is wrong with this simple proof of P=NP?
Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiabilty problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause contains exactly one literal from the set. $X3SAT$ is NP-Complete even when the instance is monotone and linear. Monotone means all literals are positive. Linear means no two clauses share more than one variable in common.

The algorithm I describe is basically Davis, Putnam, Logeman, Loveland ($DPLL$) with fixed variable order and without unit clause propogation or pure literal elimination. The algorithm also has a simple Conflict Driven Clause Learning ($CDCL$) procedure. This $CDCL$ procedure is key to the proof.

Order the literals in each clause lexicographically. Then, order the clauses lexicographically. Reorder the literals based on the first clause the literal appears in. This instance has $n=13$ variables and $m=10$ clauses. The clauses are in lexicographical order:

$\quad(a,c,k)(a,i,l)(b,j,m)(c,d,e)(c,f,g)(e,g,k)(e,h,l)(f,k,l)(g,j,l)(i,k,m)$

The order the literals first appear in a clause: $\quad a,c,k,i,l,b,j,m,d,e,f,g,k,h,l,j,i,m$

Algorithm description:

1) Choose the lowest order clause that has not been satisfied. Choose the lowest order unset literal in this clause and set it to true.

2) Process all clauses containing this true literal and set any unset literals in these clauses to false. Keep a list of the literals set to false by this true literal.

3) Reduce any learned clauses. If there are any unit learned clause that haven't already been listed, add the inverse of these unit clauses to the list of literals set to false on step 2.

4) They only way a conflict can occur is when all literals in a clause are set to false. If there are no such clauses go to step 1. Else, find the lowest order clause with all literals set to false. Determine which true literals forced the literals in this clause to be false. Create a disjunction of the inverses of these true literals. Note, this learned clause won't have more than three literals.

5) Add the new learned clause to the set of learned clauses and restart. If there are unit learned clauses when restarting, assume the inverses of these units clauses are set false. These starting unit learned clauses should be added to the list of literals set to false on the first step.

Example:

Set $a$ to true in $(a,c,k)$. Literals forced to be false are $c,k,i,l$.

Set $b$ to true in $(b,j,m)$. Literals forced to be false are $j,m$.

Set $d$ to true in $(c,d,e)$. Literal forced to be false is $e$.

Set $f$ to true in $(c,f,g)$. Literal forced to be false is $g$.

All the literals in $(e,g,k)$ are false.

$k$ was set false when $a$ was set true.

$e$ was set false when $d$ was set true.

$g$ was set false when $f$ was set true.

Create the learned clause $(\bar a \lor \bar d \lor \bar f)$ and restart.

Set $a$ to true in $(a,c,k)$. Literals forced to be false are $c,k,i,l$.

Set $b$ to true in $(b,j,m)$. Literals forced to be false are $j,m$.

Set $d$ to true in $(c,d,e)$. Literal forced to be false are $e,f$.

$f$ is set to false because of the learned clause.

$(f,k,l)$ is a new conflict.

$k$ and $l$ were set false when $a$ was set true.

$f$ was set false when $d$ was set true.

Create the learned clause $\quad(\bar a \lor \bar d)$.

Repeating this process eventually creates the following learned clauses;

$\quad(\bar a \lor \bar d \lor \bar f)(\bar a \lor \bar d)(\bar a \lor \bar b)(\bar a \lor \bar j)(\bar a \lor \bar e)(\bar a)(\bar c)(\bar k)$

The learned clauses $(\bar a)(\bar c)(\bar k)$ prove the clause $(a,c,k)$ can't be satisfied. The instance is unsatisfiable.

If an instance is unsatisfiable, this algorithm must find a conflict before it processes all $m$ of the clauses. A conflict generates an unique learned clause. There are at most $O(n^3)$ unique learned clauses and each learned clause requires processing fewer than $m$ clauses. This algorithm can determine if a monotone, linear $X3SAT$ instance is unsatisfiable in $O(m \cdot n^3)$ steps.

What is wrong with this proof?

At first, I wondered if the method for generating learned clauses was sound. Now, I think I can show all the learned clauses can be derived using resolution. An $X3SAT$ instance can be converted to a $2+SAT$ instance using this transformation:

$\quad (a,b,c) = (a \lor b \lor c)(\bar a \lor \bar b)(\bar a \lor \bar c)(\bar b \lor \bar c)$

The learned clause $(\bar a \lor \bar d \lor \bar f)$ can be derived from the $X3SAT$ clauses $(a,c,k)(a,i,l)(c,d,e)(c,f,g)(e,g,k)$. Converting to $2+SAT$ gives an expression that includes the clauses $(e \lor g \lor k)(\bar d \lor \bar e)(\bar f \lor \bar g)(\bar a \lor \bar k)$. Resolving these clauses gives $(\bar a \lor \bar d \lor \bar f)$. Transforming the clause $(f,k,l)$ allows us to resolve $(f \lor k \lor l)(\bar a \lor \bar k)(\bar a \lor \bar l)$ to get $(\bar a \lor f)$. Resolving $(\bar a \lor f)$ with $(\bar a \lor \bar d \lor \bar f)$ gives $(\bar a \lor \bar d)$. The resolution derivation can get quite long when numerous learned clauses are involved in the derivation. This $CDCL$ procedure can be easily modified to include unit clause resolution and can be modified to apply to $3SAT$.

---

There seems to be some confusion because I combine $X3SAT$ with $3SAT$. To eliminate the confusion, I will show how this algorithm can be used to solve Monotone 3SAT instances.

The monotone in monotone $3SAT$ has a different definition than the monotone in monotone $X3SAT$. Monotone $3SAT$ means every clause has all positive literals or all negative literals. I will use "positive clause" for clauses with all positive literals and "negative clause" for clauses with all negative literals.

Assume we have a monotone $X3SAT$ instance as above. Convert this instance to monotone $3SAT$ using the following tranformation:

$\quad (a,b,c) = (a \lor b \lor c)(\bar a \lor \bar b)(\bar a \lor \bar c)(\bar b \lor \bar c)$

The transfomed instance will have positive 3-clauses and negative 2-clauses. The algorithm above will need minor changes. We only need to order the positive clauses. The first step becomes:

1) Choose the lowest order positive clause. This might be a unit clause. Set the lowest order unassigned variable in this clause to true. The instance is satisfiable if there are no positive clauses. All remaining clauses have at least one negated literal. Assuming all the unset variables are false will satisfy all remaining clauses.

The second and third steps above get combined into one step.

2) Reduce the instance using the latest positive decision variable. Propagate any negative unit clauses. Keep a list of all negative unit clause that haven't already been listed. Do not propagate positive unit clauses.

The other steps remain the same as above. As before, any conflict can be shown to be caused by no more than three positive decision variables.

I removed the section about propagating positive unit clauses. At the moment, I can't show the learned clause created by propagating positive unit clauses can be created using resolution.

# Answer
The monotone version of X3SAT that your proof is based on has the nice property that setting a literal false in one clause will never cause the negation of that literal to be true in another, which means you can say

> The only way a conflict can occur is when all literals in a clause are set to false.

and it will be true because forcing two literals false in one clause will never force their two negations true in another, since there are no negated variables in the formula.

The problems come when you start learning clauses. First, you can't just learn a disjunction like $(\bar a \lor \bar d \lor \bar f)$ because that's not a X3SAT clause, it's a 3CNF clause. You'll have to convert this normal 3CNF clause to a set of equivalent X3SAT clauses, e.g. using Schaefer's method. This means more clauses, but it's a polynomial blowup so you're still OK.

The second problem is unfortunately a killer for your proof. The learned X3SAT clauses will have negated variables in them, making the formula no longer monotone. With a non-monotone formula you can no longer rely on all-false literals being the only kind of conflict clause; now you must worry about clauses with more than one true literal as they can now be produced by setting two other literals false elsewhere. Your proof has no provision for handling these unsatisfied clauses.
> 17 votes

# Answer
I found a flaw in my proof. There are situations were this algorithm will not find satisfying assignments.

Assume a set of clauses like:

$\quad(a,b,c)(d,e,f)(g,h,i)(j,k,l)(m,n,o)(b,k,n)(e,h,m)$

The clauses $(a,b,c)(j,k,l)(m,n,o)(b,k,n)$ would create the learned clause $(\bar a \lor \bar j \lor \bar m)$ from the conflict clause $(b,k,n)$.

Now assume we set $a$, $d$, $g$, and $j$ true creating the conflict clause $(e,h,m)$.

$e$ was set false when $d$ was set true.

$h$ was set false when $g$ was set true.

$m$ was set false because both $a$ and $j$ were set true. But, my algorithm says $m$ was set false when only $j$ was set true. My algorithm would create the learned clause $(\bar d \lor \bar g \lor \bar j)$. It should have created the learned clause $(\bar a \lor \bar d \lor \bar g \lor \bar j)$.

Now assume the $X3SAT$ instance has only one satisfying assignment where $a$ is false and $d$, $g$, and $j$ are true. My algorithm would never find this satisfying assignment.

I was correct to say this algorithm can determine if a monotone $X3SAT$ instance is unsatisfiable in $O(m \cdot n^3)$ steps. An algorithm that always returns "unsatisfiable" can do it in one step.
> 1 votes

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


# Question
Title: Is it assumed that lower bounds on the size of monotone circuits apply to general Boolean circuits too?
A **"general"** Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:

1. fan-in=2 for the AND and OR nodes
2. fan-n=1 for the NOT nodes
3. fan-in=0 for the IN nodes
4. fan-out=0 to exactly one node (the OUT node)
5. Unbounded fan-out to the rest of the nodes (but the OUT node)

A **monotone** circuit is a Boolean circuit with 0 vertices labeled as "NOT".

The size of a circuit is the number of "gates" (vertices with labels "AND", "OR" or "NOT") it contains.

We know many lower bounds on the size of monotone circuits, that we do not know how to prove on a general Boolean circuit (such as this one on the Clique problem).

My question is: do we assume that lower bounds proven on monotone circuits apply also for **equivalent** general Boolean circuits (since they compute monotone function), and we just don't know how to prove it; or we assume\ know that these lower bounds do not apply to equivalent general Boolean circuits?

In the latter case, could you supply me with an example of a monotone function computed by both a monotone circuit and a general Boolean circuit, whilst the size of the monotone circuit is gretater than the general Boolean circuit? (I have been stuck on this for hours, seeking for such an example, so I believe that there is no such an example..)

# Answer
Éva Tardos gave a function which can be computed by a polynomial size general circuit but requires an exponential size monotone circuit. The circuit computes a good enough approximation to the Lovász theta function of the input graph.

Razborov gave an $n^{\Omega(\log n)}$ lower bound monotone circuits computing the bipartite perfect matching function, for which polynomial size general circuits exist.
> 2 votes

---
Tags: complexity-theory, graphs, np-complete, combinatorics, circuits
---


# Question
Title: Why is addition in GF(2^8) the same as XOR?
I get the impression it has to do with either some quirk involved with limiting to 2^8 or that I'm misunderstanding what addition can be within the context of a finite field, but I'm not quite sure why it's described as 'addition' in the literature I read but the code I see implements it with XOR.

# Answer
> 4 votes
Finite fields are usually described as polynomials over the base field (in this case $GF(2)$) modulo some irreducible polynomial. If you represent each polynomial as a vector of coefficients, then addition of polynomials corresponds to elementwise addition of the coefficients, which in the case of $GF(2)$, translates to XOR.

For example, suppose that your field elements are $1+x^2$ and $x+x^2 + x^5$. Their binary representations are $101$ and $100110$ (LSB is the coefficient of $1$). Their sum is $1+x+2x^2+x^5 = 1+x+x^5$ (since $2=0$ over $GF(2)$), whose binary representation is $100011$. This is the XOR of $101$ and $100110$.

---
Tags: mathematical-foundations
---


# Question
Title: How can Machine Learning be used to find attributes/characteristics of graphs?
I am aware ML is not necessary for many graph classification problems (as the graph theorists have many clever solutions), but I'm specifically interested in ML approaches to these types of questions. I imagine if you had enough training examples (1000s?) you could use a supervised approach for classification type of questions. I also assume an adjacency matrix would be a good data representation to use for ML approaches to undirected graph classification. Example problems are shown below.

1.) Given an undirected graph represented by an adjacency matrix, broadly speaking, how (if possible) could machine learning be used to find if said graph has a hamiltonian path?

2.) Given an undirected graph represented by an adjacency matrix, how can ML be used to determine if the graph is a tree?

# Answer
ML is not likely to be a good approach for these kinds of problems. It will probably perform far worse than a hand-designed algorithm. Current ML is not magic; it is just a form of pattern-matching.
> 2 votes

# Answer
This depends heavily on the attribute you have in mind: I see no point in using ML for tree recognition for instance since we already have very practical exact algorithms for this. But sure, if you wanted to, nothing is stopping you from taking a bunch of graphs, representing them in some way and labeling them ("is a tree", "is not a tree") and training a classifier. Probably not very useful though.

With that being said, NP-hard problems could be more interesting but even then there are different approaches in the literature.

You can roughly say that there are at least three types of approaches:

* (i) using ML for choosing a heuristic that will perform well for a given instance,
* (ii) using ML for somehow finding the answer directly; and
* (iii) using ML for helping the human design heuristics.

For (i), a good keyword to search for is "algorithm portfolio". The distinction between say (ii) and (iii) is not that clear or easy to make. For (iii), you could have a look at \[1\]. For (ii), I can mention at least the works \[2\] and \[3\] for TSP and maximum clique, respectively. These areas develop at an enormous speed, so you will find plenty of follow-up work to this already recent work.

---

\[1\] Khalil, Elias, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. "Learning combinatorial optimization algorithms over graphs." In Advances in Neural Information Processing Systems, pp. 6348-6358. 2017.

\[2\] Prates, Marcelo, Pedro HC Avelar, Henrique Lemos, Luis C. Lamb, and Moshe Y. Vardi. "Learning to solve NP-complete problems: A graph neural network for decision TSP." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 4731-4738. 2019.

\[3\] Lauri, Juho, and Sourav Dutta. "Fine-Grained Search Space Classification for Hard Enumeration Variants of Subset Problems." In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 2314-2321. 2019.
> 1 votes

---
Tags: graphs, machine-learning, classification
---


title: Rank of root in AVL tree

text:
# Question
Title: Rank of root in AVL tree
Find a function that bounds from above and below (asymptotic) the rank of the root r in an AVL tree,
i.e. find a function $f(n)$ so there exists a constant $c\>0$ that for every AVL tree with $n$ nodes so $c * f(n)\le rank(r)\le n-c\*f(n) $.

$rank(r)$ gets his maximum value when his sub-left tree contains maximal number of nodes and because it's an AVL tree, for tree with height $h$ the sub left tree will be with height of $h-1$ and the number of nodes will be maximal when the sub tree is a full tree with $2^{h-2}-1$ nodes hence we get:
$rank(r)\leq 2^{h-2}-1+1=2^{h-2}$

On the other hand, $rank(r)$ gets his minimal value when his sub left tree contains a minimal number of nodes and it happens when the sub left tree is a fibonacci tree with height of $h-2$, therefore
$rank(r) \geq \phi ^{h-2}+1$.

Now I need to find f as a function of the number of nodes $n$ and not the height $h$. Am I in the right direction?
Would apricciate any help how to continue, Thanks.

# Answer
First of all, it's not $2^{h-2}$, it's $2^h$.

The number of nodes $n$ in a full binary tree, is at most $n=2^{h+1}-1$, where $h$ is the height of the tree. A tree consisting of only a root node has a height of 0.

Straight outta wiki https://en.wikipedia.org/wiki/AVL\_tree
> 1 votes

---
Tags: data-structures, avl-trees
---


# Question
Title: In determining whether any segments intersect, why there must be some sweep where segments $a$ and $b$ are consecutive?
In CLRS, Section 33.1, we are given the any-two-segments-intersect algorithm. It's a cool algorithm for sure but going through the correctness proof, I don't know how they arrived at the following conclusion:

"Given that we have two segments (call them $a$ and $b$) that intersect at some point $p$, then there must be some sweep line $x$ for which the intersecting segments $a$ and $b$ are consecutive in the total preorder."

Why must $a$ and $b$ be consecutive at some sweep line?

I do see why visually using the figure 33.4 (page 1023) but I don't know how to prove this statement. How can I prove it?

If anyone had read that section, please enlighten me. Thank you

# Answer
> 2 votes
Note that the statement you want prove is equivalent to showing that the shaded triangles in figure 33.4b are non-empty, or more precisely (for the left triangle) that there exists a vertical line $x$ with x-coordinate strictly less1 than $p$ such that the triangle enclosed by segments $a,b$ and line $x$ does not contain a point of any other segment.

To show this, take a vertical line $x'$ to the left of $p$ that intersects both $a$ and $b$. The triangle enclosed by segments $a, b$ and line $x'$ may contain or intersect with a number of other segments. Of those segments, consider the segment with the rightmost point of intersection with the triangle, call this point $q$. Note that $p\neq q$, since the assumption was made that no three input segments intersect at a single point. Since $q$ lies in the triangle, its x-coordinate $q.x$ is strictly less than $p.x$. Now take a line $x$ with an x-coordinate in the open interval $(q.x,p.x)$, then no other segments intersect with the triangle enclosed by $a,b,x$.

---

Note that this proof also shows that line $x$ can be taken arbitrarily close to the right endpoint of some segment, which are the lines that the algorithm considers.

Although this proof fails when a third segment intersects at $p$, you can still show that for any intersection point $p$, there exists a pair of segments $a,b$ that intersect at that point such that they are consecutive in the partial order, using similar ideas.

1: Depending on the definition of "consecutive", a line with x-coordinate equal to that of $p$ would do, but this is not useful for the algorithm.

---
Tags: algorithms, computational-geometry, correctness-proof
---