# Question
Title: Flawed argument in the proof of function extensionality in cubical type theory?
I am reading the lectures about cubical type theory in this github repo. In lecture 1 the author defines function extensionality the following way:

```
funExt (A B : U) (f g : A -> B)
       (p : (x : A) -> Path B (f x) (g x)) :
       Path (A -> B) f g = <i> \(a : A) -> (p a) @ i

```

and writes

```
To see that this makes sense compute the end-points of the path:

  (<i> \(a : A) -> (p a) @ i) @ 0 = \(a : A) -> (p a) @ 0
                                  = \(a : A) -> f a
                                  = f

```

I don't follow. Specifically, when we replace `(p a) @ 0` with `f a` in my mind we use the following fact: `\(a : A) -> (p a) @ 0 = f a` to rewrite (let's give names to the left and right side) `fpa = \(a : A) -> (p a) @ 0` into `fa = \(a : A) -> f a`. But isn't this by itself *using* function extensionality with `f = fpa, g = fa`?

If I am not mistaken, this argument is circular. Can anyone clarify?

# Answer
The expression:

```
\(a : A) -> (p a) @ 0

```

parses as:

```
\(a : A) -> ((p a) @ 0)

```

So this is applying `p a : Path B (f a) (g a)` to the `0` point. This reduces to `f a`, because it is the beginning point of the path. It's essentially doing the same thing as the earlier step, which beta reduced the `(<i> ...) @ 0` to `(...)[i := 0]`, except `p a` looks abstract to us, *but* that doesn't matter, because we know what it reduces to when applied to `0` (or `1`) based only on its type.

So, it's not using function extensionality to prove extensionality. What it's doing is taking advantage of the fact that `Path` types are similar to function types, and that the two `Path` types in `funExt` are 'just' functions with different argument order (so it flips them).
> 7 votes

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


# Question
Title: Regular expression for capturing a "C-style" string
I have started to learn automata theory and languages. I am new to regular expressions.

As a use case in real world, I would like to construct a regular expression to accept a c-style string: enclosed by double quotes, allows escape sequences (\\" to escape a double quote, \ escape a backslash, \n escape a new line...) and allows all characters in between, and pretty much everything that the standard identifies as a string literal.

I don't have a specific language that the regex is to be used in, for I'm not going to use this in a program. I just want to know the theory behind constructing the regex, one step at a time. For example, Initially, how to account for the enclosing quotes ? then how to allow arbitrary sequences of characters between the quotes ? and then how to account for escaping ?

I don't have a regex tester. I just need the construction idea.

Strings that are to be accepted are, for example,

```
"hello world!"
"hi!\n"
"000022lkjads\t{"
"\0Hello World"

```

The following would be rejected

```
"hello

```

for there is no enclosing double quotes

```
"Hello World""

```

for it does not escape the quote

# Answer
Here is a regular expression for the set of all strings of the following form:

* They start and end with ".
* Every " in the middle must be escaped using a backslash.
* Every backslash must be followed by a letter from $A$.
* All other letters are from $B$; in particular, " is not in $B$.

For simplicity, I identify $A$ and $B$ with the regular expressions $\sum\_{\sigma \in A} \sigma$ and $\sum\_{\tau \in B} \tau$.

Here is the regular expression: $$ \text"(B+\backslash A)^\*\text" $$
> 2 votes

---
Tags: regular-languages, finite-automata, regular-expressions, strings, string-matching
---


# Question
Title: How to implement recursive solution with large number or parameterized possible next steps
I was looking at a recursive solution for the robot on a grid problem which basically states that there is a robot on the top left corner on a grid and you are supposed to find a path to the bottom right of the grid and the robot can only move down or to the right. Below is the recursive function for the solution

```
public static boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path) {
        // If out of bounds or not available, return.
        if (col < 0 || row < 0 || !maze[row][col]) {
            return false;
        }

        boolean isAtOrigin = (row == 0) && (col == 0);

        // If there's a path from the start to my current location, add my location.
        if (isAtOrigin || getPath(maze, row, col - 1, path) || getPath(maze, row - 1, col, path)) {
            Point p = new Point(row, col);
            path.add(p);
            return true;
        }

        return false;
    }

```

I understand the solution, at every recursive call it checks if it is at the bottom right or if going down one step or going right one step takes it to the bottom right.

However I was thinking that this solution only works because there are only two possible next steps (down or right) that we are easily able to hardcode and connect with the || operator. But what if there were N different next steps? In that case we would need to call the recursive `getPath()` function within a for loop from 1 to N. But then how would we check if any of the 1 to N recursive calls return True? In this case it would not be possible to connect all of them with an || operator. Would something like the following work?

```
public static boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path) {
        // If out of bounds or not available, return.
        if (col < 0 || row < 0 || !maze[row][col]) {
            return false;
        }

        boolean isAtOrigin = (row == 0) && (col == 0);

        if(isAtOrigin){
            Point p = new Point(row, col);
            path.add(p);
            return true;
         }

         for(int i:N){
             if(getPath(maze,row,col-i,path)){
                Point p = new Point(row, col);
                path.add(p);
                return true;
             }
         }

        return false;
    }

```

Is this a valid solution for the change in the problem that I suggested? I think what is throwing me off here is that in the original solution all the recursive calls are made at the same time within the if statement, but here they are called sequentially in the for loop. Is that still valid?

# Answer
> 1 votes
The way that that the short-circuit expression `A || B` is evaluated is as follows:

```
if A is True:
   return True
return B

```

In words:

* Run $A$. If it returns True, return True. Otherwise, continue.
* Run $B$, and return the result.

In particular, $A$ and $B$ are *not* run in parallel; they are run in sequence.

There is absolutely no problem generalizing this to a short-circuit OR of larger arity:

```
if A1 is True:
   return True
if A2 is True:
   return True
...
if An is True:
   return True
return False

```

We could also replace the last bit with simply `return An`, to make it match the previous pseudocode, but the form above is perhaps more easy to implement using a loop.

---
Tags: dynamic-programming, recursion
---


# Question
Title: Are multiple interrupts generated when I hold down a key on my keyboard?
When I hold down a key on my keyboard, a continuous stream of characters is generated and is displayed on the text editor, Now since pressing a key is a hardware interrupt, so does holding down a key continuously generates interrupt signals and does CPU constantly keeps acknowledging those ? or something else happens ?

# Answer
**TL;DR**: No.

---

It depends on the OS and the keyboard. I'll show you how to determine this yourself on a Linux machine. I'm using Ubuntu 16.04 on an x86 processor. So if you are using a fairly modern version of Linux and an x86 processor, then the steps will be pretty much the same. I have a USB keyboard (and mouse) and almost everyone else does.

Open a new terminal and execute the following command:

```
watch -n0.5 "cat /proc/interrupts"

```

This enables you to monitor hardware interrupts in real time. Examine the last column and look for the lines that contain `ehci_hcd:usbN` where N is some small number. On my system, there are two such line:

```
            CPU0       CPU1       CPU2       CPU3
 16:         17          3          0          9  IR-IO-APIC  16-fasteoi   ehci_hcd:usb1
 23:         88      72272     101007    1327899  IR-IO-APIC  23-fasteoi   ehci_hcd:usb2

```

The first column shows the interrupt request signal number (IRQ). It identifies a physical bus on the motherboard that is used by the I/O device to interrupt the processor. The four columns in the middle show the number of interrupts handled by each core. There are four (logical) cores on my system. Notice how the overall number of interrupts from IRQ 23 is very large while the number of IRQ 16 interrupts is almost zero. This is a strong indication that the keyboard and mouse both use IRQ 23 to send interrupts to the processor. In general, though, the mouse and keyboard may use different IRQs depending on the USB port they are connected to. Some USB ports may share the same IRQ line1.

Now you can observe what happens to the interrupt counts when using the keyboard. Hold the mouse still (so that the mouse does not generate any interrupts) and press some keys on your keyboard. When a keyboard key is pressed, the interrupt count on one of the CPUs will increase by exactly one. When a key is released, the interrupt count will also increase by one. In addition, you can see that, while the key is held down, the interrupt count does not change. Therefore, the keyboard does not send interrupts for the key held down. Instead, Linux uses a software keyboard repeat mechanism, by default, for USB keyboards. As long as the keyboard has not yet sent an interrupt indicating that the key has been released, Linux knows that it is held down.

Software keyboard repeat is implemented by using a timer interrupt. There are two parameters involved, both are configurable. The first is called the typematic repeat rate (also called autorepeat rate), which specifies the rate at which the keydown event should be repeated in terms of the number of characters per second. The second is called the typematic delay, which specifies how long a key must be held, in milliseconds, before it begins to repeat. You can print the current values of these parameters using `sudo kbdrate`. On modern versions of Linux, it prints:

```
Typematic Rate set to 10.9 cps (delay = 250 ms)

```

You can also modify these parameters using the same tool, and then observe the effects using `/proc/interrupts` as discussed above.

Since software keyboard repeat relies on the timer interrupt, it can support a wider range of typematic repeat rates and shorter typematic delays. This is in contrast to hardware keyboard repeat, which is the default mode for AT and PS/2 keyboards in old versions of Linux. People who used to suffer issues from hardware keyboard repeat were advised to use `atkbd.softrepeat=1`. Most keyboards are configurable regarding keydown repeat behavior.

For more information, you can refer to `/include/linux/input.h` and `/include/linux/input.c` of the Linux source code as a starting point.

---

**Footnote 1:**

You can determine with certainty which IRQ line the USB keyboard and mouse are connected to by executing the following command:

```
lsusb -v

```

This will print a list of all USB ports and controllers on the PCIe interconnect. On my system, all USB ports are either on Bus 001 or Bus 002. In `/proc/interrupts`, these are named `ehci_hcd:usb1` and `ehci_hcd:usb2`, respectively. So, for example, if `lsusb` tells you that the keyboard is on Bus 001, then the keyboard uses IRQ 16. When a key is pressed or released, the scan code of the key is simply stored in the keyboard buffer and the keyboard controller then raises an interrupt to one of the CPUs (as specified by I/O APIC interrupt affinity). Then the target CPU gets interrupted, calls the interrupt handler mapped to the IRQ, which in turn reads the scan code from the keyboard controller buffer and stores it into the kernel's keyboard buffer for further processing.
> 11 votes

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


# Question
Title: Artificial Intelligence: Condition for BFS being optimal
It is said in the book *Artificial Intelligence: A Modern Approach* for finding a solution on a tree using BFS that:

> breadth-first search is optimal if the path cost is a nondecreasing function of the depth of the node. The most common such scenario is that all actions have the same cost.

From that I understand that if the path cost is non decreasing function of depth, the BFS algorithm returns an optimal solution, i.e., **the only condition is the cost function being nondecreasing**. But I think the only way for BFS to be optimal is the scenario in which all the path costs are identical, therefore a node found in a certain level is necessarily the optimal solution, as, if they exist, the others are. Therefore I think for BFS to be optimal, cost function should be non decreasing **AND** the costs of nodes should be identical. However, the book says only one of the conditions (former one) makes BFS optimal.

Is there a situation in which the costs are not identical, the cost function is nondecreasing and the solution returned by BFS is guaranteed to be optimal?

# Answer
¡Nice question really!

The book is right and it just suffices for the path cost to be a nondecreasing function of the depth of the node ---though an additional note should be posted, see below. This directly implies that it is not necessary for nodes in the same level to have the same cost. Truth, however, is that it is hard to find such an example because the most obvious one consists just of considering all *grounded* actions to have the same cost.

Thus, let me try to start with the first statement (that it just suffices for the path cost to be a nondecreasing function of the depth of the node) with a theoretical example. Let $c(n,n')$ denote the cost of traversing the edge from node $n$ to node $n'$ and let us define it as:

$$ c(n,n')=2^{g^\*(s,n)} $$

where $g^\*(s,n)$ is the minimum number of actions required to reach node $n$ from the start node $s$. I am certainly defining the cost of the edge as a function of the depth of the source node but it seems to be that this is absolutely okay with the statement in the book. Think of this as an attractive force exercised from the start state $s$ so that the farer you get, the more costly it is to progress. This function is clearly non-decreasing as it progresses as follows: 1, 2, 4, 8, ..., the total cost paths progressing as: 1, 3, 7, 15, ...

Now, let me show that Breadth First Search would certainly find an optimal solution. I will make it by induction:

**Base case**: the queue is seeded with the start state $s$. In the first iteration of BFS it is extracted from the queue and its children are generated, all of them with cost $2^0=1$. These nodes have been certainly reached through an optimal path so this satisfies the base case.

**Induction step**: let us assume that all nodes of depth $(d-1)$ have been already generated through optimal paths with a path cost $\sum\limits\_{i=0}^{d-2}2^i=2^{d-1}-1$. In the induction step all nodes generated at depth $(d-1)$ are expanded to generate nodes at depth $d$ from the start state $s$. Obviously, all these nodes are generated through optimal paths as well since their cost corresponds to paths of minimum length from the start state (in other words, would there be a shorter path in terms of length instead of cost, it would have been discovered in a previous layer of the search tree traversed by BFS with a lower cost).

It seems to me that you would agree with this but it might not satisfy you because all nodes in the same level would have exactly the same path cost (and nodes at depth $d$ would have a total cost equal to $\sum\limits\_{i=0}^{d-1}=2^d-1$), but the previous proof was necessary in order to consider the following case now:

Let us re-define the cost function as:

$$ c(n,n')=\left\\{\begin{array}{l} 2^{g^\*(s,n)}, \mbox{in some cases, whichever}\\ 2^{g^\*(s,n)}+\delta, \mbox{otherwise}\end{array}\right. $$

where $delta$ is just a small number, say $\frac{1}{2}$, such that it is smaller than the smallest of all costs $2^0=1$. Now you have a lot of different ways to get different path costs of nodes lying at the same level. In this particular case, the path cost of a node at depth $d$ ranges in the interval $\[2^{d+1}-1, 2^{d+1}+\delta\times d-1\]$.

However, the optimality condition of BFS still applies because the maximum difference ($\delta\times d$) is not enough to shift any node at depth $d$ after nodes that lie at depth $(d+1)$ in the queue the reason being that the path cost of those nodes ranges in the interval $\[2^{d+2}-1, 2^{d+2}+\delta(d+1)-1\]$. For a value of $\delta$ small enough nodes with different costs (even if they lie at the same depth) are found through optimal paths. However, note that **I am assuming here $\delta$ to be small enough. If it is not, then BFS could be easily fooled and sub-optimal paths would be easily found by BFS**.

Nice question, really! Hope this contributes somehow,
> 6 votes

# Answer
BFS is checking the nodes by depth levels. So it will check the nodes on level with depth D, before the ones with depth greater than D. If the cost function is not decreasing in depth , than a solution found on certain depth by BFS is optimal , because :

-all nodes that are not checked yet have greater or equal path cost and

-all nodes which have lower path cost are already checked and they are not a solution

I think that the definition should also imply that all nodes on the same depth level have equal path cost.
> 0 votes

# Answer
> Therefore I think for BFS to be optimal, cost function should be non decreasing **AND** the costs of nodes should be identical.

Firstly, the latter is a subset of the former.

Secondly, to see why the non-decreasability (if it's a word) of the path cost function is enough you have to remember that it's a function of the **depth** of the node. Meaning, **all nodes at the same level will have the same cost**. Thus, the only thing we are concerned with is it's non-decreasability, such that deeper solutions won't result in a better path cost.
> 0 votes

---
Tags: optimization, artificial-intelligence, search-algorithms, search-trees, search-problem
---


# Question
Title: Processor pipelining question: number of instructions per second
A question from the textbook Modern Operating Systems by A. S. Tanenbaum reads as follows:

> A computer has a pipeline with four stages. Each stage takes the same time to do its work, namely, 1 nsec. How many instructions per second can this machine execute?

This was recently a homework question in my operating systems class (it's already been graded). Here's the reasoning I provided (screenshot):

---

---

The book's answer key says the following:

> Every nanosecond one instruction emerges from the pipeline. This means the machine is executing 1 billion instructions per second. It does not matter at all how many stages the pipeline has. A 10-stage pipeline with 1 nsec per stage would also execute 1 billion instructions per second. All that matters is how often a finished instruction pops out the end of the pipeline.

I was wondering if someone could explain this; the book's explanation doesn't make sense to me. One instruction emerges from the pipeline every second *only after the first second* because we lose those 3 nanoseconds initially. And it's only 1 billion instructions per second if we consider the limit.

# Answer
> 3 votes
The book quite rightfully ignores the three startup cycles. Nobody cares whether it performs $10^9$ or $10^9-3$ instructions. In reality, "1 ns" is never exactly one nanoseconds, so the deviation from the clock rate not being exactly one per nanosecond makes much more difference.

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


# Question
Title: Optimizing coin splitting - Is this algorithm as fast as I think?
In a recent exam, I've been asked to solve the following problem:

> ### The problem
>
> Two players play the following game: Given a sequence of coin values $v\_1,\ldots,v\_n (n \vert 2)$ the players take turns in taking one coin from either "end" of the sequence. The value of that coin is added to their score.
>
> Player 1 always starts. What is the maximum score that Player 1 can reach if Player 2 plays optimally (always minimizing their potential score)? What is the time-complexity of your algorithm? Prove your result.
>
> **Example:**
>
> Given the coin sequence $1,1,3,1,1,2$ one of the best playing sequence for player 1 is (scores denoted as the second tuple):
>
> $$(\lbrack 1,1,3,1,1\rbrack,(2,0)) \rightarrow (\lbrack 1,1,3,1\rbrack,(2,1)) \rightarrow (\lbrack 1,3,1\rbrack,(3,1)) \rightarrow (\lbrack 3,1\rbrack, (3,2)) \rightarrow (\lbrack 1 \rbrack, (6,2)) \rightarrow (6,3)$$
>
> The best score player 1 can reach is 6.

### My solution

I'm just going to roughly outline my proof here, the formal correctness is not the point of this question. I'm more interested in the correctness of my asserted upper bound of complexity.

---

For the following I will use tuples to denote ranges of values. $(i,j)$ specifies the value range $v\_i,\ldots,v\_j$.

We iteratively create a DAG $G = (V, E, \gamma)$ as follows:
Create a vertex $v$ named $(1,n)$. Create or refer to the previously created vertices $v\_1, v\_2, v\_3$, named $(2,n-1), (3,n), (1,n-2)$ respectively.

Create the edges $e\_1 = (v,v\_1), \gamma(e\_1) = v\_1$ and $e\_2 = (v,v\_2), \gamma(e\_2) = max\lbrace v\_1, v\_n \rbrace$ and $e\_3 = (v,v\_3), \gamma(e\_3) = v\_n$. Iterate through the vertices $v\_{\lbrace 1,2,3\rbrace}$ using a queue or similar to repeat the process until the sequence of coins denoted by the $v$ we iterate over is empty.

The number of edges in the created graph is bounded as follows: $\lvert E \rvert \leq 3\lvert V \rvert$.
The number of vertices is denoted by the following sum: $1 + \sum\_{i=0}^{\frac{n}{2}} 2i + 1 \leq n^2$

We can determine the maximum score for player 1 by "backpropagating" the edge weights through the graph, which takes $\lvert V \rvert * \lvert E \rvert$ steps.

This makes the overall algorithm asymptotically require $\Theta(n^2)$ steps

---

The problem I have with my answer is the upper bound for the number of vertices. I just pull that number out of thin air and my gut-feeling tells me that it is correct, but I might just be completely wrong.

**Assuming that this is indeed a correct way to calculate the answer to the question, is my time-complexity argumentation sound?**

# Answer
You have made significant progress on this problem. Your final conclusion, "the overall algorithm asymptotically requires $\Omega(n^2)$ steps" is likely to be correct as well.

## Analysis of Your Argumentation

Here are some unclear or unconventional or inconsistent notations found in your post, which makes it difficult to understand or justify your arguments about time-complexity.

* Does "$n|2$" mean $n$ is even? The standard convention for for "$a$ divides $b$" is $a|b$ according to math stackexchange answers and my years of practicing number theory. So $2|n$ is the prefered notation for $n$ is even. Anyway, in current case, I strongly prefer the plain English, $n$ is even.
* "use tuples to denote ranges of values. $(i,j)$ specifies the value range $v\_i,\cdots,v\_j$.". People use $(i,j)$ generally to mean the pair of elements $i$ and $j$ or an open interval with ends $i$ and $j$. I would suggest you use $v\_{i..j}$, where the two-dot notation $i..j$ are the convention for an integer interval.
* "create a DAG $G = (V, E, \gamma)$". Do you mean an edge-weighted DAG?
* "Create a vertex $v$ named $(1,n)$", which does not sound like English. It is better to write "Create a vertex $v$ that represents $1..n$".
* "Create or refer to the previously created vertices $v\_1,v\_2,v\_3$, named $(2,n−1),(3,n),(1,n−2)$ respectively". Although I can probably guess your intention, I am puzzled by the notations. Did you not notice that $v\_1, v\_2, \cdots, v\_n$ appears as the coin values in the quoted problem? It looks like you want to use "$(2,n-1)$" as a name, which would be very confusing, since I have never seen any name of a person, a item, a variable or whatever starts and ends with a parenthesis for years except for very few social online accounts.
* "Create the edges $e\_1=(v,v\_1),\gamma(e\_1)=v\_1$ and $e\_2=(v,v\_2), \gamma(e\_2)=\max\\{v\_1,v\_n\\}$ and $e3=(v,v\_3),\gamma(e\_3)=v\_n$". Now I am more into the wanderland. Is the codomain of $\gamma$ the vertices or the indices or the coin values?
* "Iterate through the vertices $v\_{\lbrace 1,2,3\rbrace}$". It is better to just write $v\_1, v\_2, v\_3$.
* "the sequence of coins denoted by the $v$". Didn't you say $v$ is a vertex?

Now Let us check your computation of the time-complexity.

* "The number of edges in the created graph is bounded as follows: $|E|\le3|V|$. The number of vertices is denoted by the following sum: $1 + \sum\_{i=0}^{\frac{n}{2}} 2i + 1 \leq n^2$". It looks like your estimates are correct, even though they can be tighter.
* "We can determine the maximum score for player 1 by 'backpropagating' the edge weights through the graph, which takes $| V | * | E |$ steps. This makes the overall algorithm asymptotically require $\Theta(n^2)$ steps". Since it is not clear how your backpropagating works exactly, it is hard to justify the number of steps. However, since $| V |\* | E | \le |V| * (3 |V|) \le 3 n^4 $, you can only say that your algorithm takes $O(n^4)$ time.

In summary, even assuming that your algorithm is indeed a correct way, there is not enough clear information to fully justify or disprove your time-complexity argumentation. There are quite some room for you to improve the description of your algorithm and the time-complexity argumentation.

## A Reference Solution

For simplicity, I will assume $n$ is even. Let $f(i,j)$ be the maximal score reachable by the first player if the two players start the game with the coins sequence $v\_i, v\_{i+1}, \cdots, v\_j$.

Then we have the base cases, $$f(i, i+1)=\max(v\_i, v\_{i+1})$$ and recurrence relation $$ f(i,j) =\max(v\_i+\min(f(i+2,j),\ f(i+1,j-1)),\ v\_j + \min(f(i+1,j-1),\ f(i,j-2)))$$

The parameter pair $(i,j)$ of any $f(i,j)$ that appears in the course of computation of $f(1,n)$ will be such that $1\le i\le j\le n$ and $(i-1)+(n-j)$ must be even. The number of all such parameter pairs are $n^2/4$. The base case and the recurrence relation together shows that we need some $O(1)$ operations to obtain $f(i,j)$ for a new parameter pair $(i,j)$, assuming that the usual memorization technique in dynamic programming is used. So the time-complexity of computing $f(1,n)$ is $\Theta(n^2/4)=\Theta(n^2)$.
> 3 votes

# Answer
Your algorithm may work, but FWIW it's more conventional to build game trees where the two players' moves form alternating layers of vertices rather than combining one move from each into a single edge. If you do this alpha-beta tree you get a graph with $|E| \le 2 |V|$ and $|V| = \frac{n(n+1)}{2}$.

---

> We can determine the maximum score for player 1 by "backpropagating" the edge weights through the graph, which takes $\lvert V \rvert * \lvert E \rvert$ steps.
>
> This makes the overall algorithm asymptotically require $\Theta(n^2)$ steps

If $|V| = \Theta(n^2)$ and $|E| = \Theta(|V|)$ then $|V| * |E| = \Theta(n^4)$.

However, the propagation should actually take $\Theta(|V| + |E|) = \Theta(n^2)$.
> 2 votes

# Answer
Aren't you just overcomplicating things? I'd use an n x n matrix, and a nested loop that finds the result in about five lines of code in O (n^2).

Let b\[i,j\] = the amount by which you can beat your opponent if you are allowed to start on the subsequence i,j.

```
for 1 ≤ i ≤ n
    b[i, i] = v[i]

for 1 ≤ d ≤ n-1
    for 1 ≤ i ≤ n-d
        j = i + d
        b [i, j] = max (v[i] - b [i+1, j], v[j] - b [i, j-1])

```

You can beat your opponent by b \[1, n\], found in O (n^2). In O (n) you calculate the total value of all coins, and that gives you the best possible score.

Now with a very simple O (n^2) solution available, I wouldn't be totally surprised if someone came up with a much more complicated and much more clever solution that runs faster.
> 2 votes

---
Tags: algorithms, graphs, runtime-analysis, check-my-answer
---


# Question
Title: Does there exist a travelling salesmen generating algorithm?
I'm curious if somebody has already figured this out. Is there an efficient algorithm that will generate (in $\mathbb{R}^2$) a sequence of points in such a way that the solution to the travelling salesmen problem is known a priori, and such that we have a uniform distribution on the set of points? For example, I can think of an algorithm that will generate such a sequence by plotting a polygon, and the minimum distance would be the points going around the outside of the polygon, but the distribution on point-sets from this algorithm is highly biased.

So I would hope for an efficient algorithm that generates a set of points in $\[0,1\]^2$ (and its corresponding TSP solution), with equal probability to any set of points, i.e., each point has iid uniform distribution on $\[0,1\]^2$. You could interpret "efficient" as "polynomial time".

PS: I strongly suspect that no algorithm could exist because if so, I imagine the problem would be solvable, so in this case, is there a database somewhere with a large number of solutions for randomly generated sets of points?

# Answer
For posterity and because I never received any answers in the end: my best guess is $\forall x\_0 \in \[0,1\]^2$ was to pick any point $x\_1 \in \[0,1\]^2$, then generate a second point $x\_2$ such that the interior angle between the line between $x\_0$ and $x\_1$ is greater than 90$^{\circ}$ and less than 180$^{\circ}$. Now I can see two paths forward, one is to make a sort of quasi convex structure (obviously not every solution) by alternating whether the angles are interior or exterior and staying within the bounds. The solution is then $x\_{0,...,n}$ for the minimum path.

The second possibility would be to put restrictions on the distance from the last point to the next point, (say halving each time) and again requiring the angle to be constrained, but perhaps this time we can loosen the constraint to greater than 90$^{\circ}$ and less than 270$^{\circ}$ and just require that we cannot cross a line we've already made. I can't guarantee this algorithm will always generate the correct solution, however I can guarantee that it won't generate all points in $\[0,1\]^2$, so the question remains unfortunately unanswered.

And for the PS in my original question: this might be a good place to get started for those looking.
> 1 votes

# Answer
Maybe you could find an algorithm that generates problems, and good, but not optimal solutions. So a TSP algorithm should find a solution that is as good or better than the optimal solution, and if it fails to do so, then it is not optimal.

To do this, you might start with n points and a purported optimal solution, then generate a point n+1 at random and spend some polynomial time to insert it into the solution for n points, which would tend to give a good solution. Then you use your TSP algorithm for the n+1 points. If it's worse than your good solution, then it's not optimal. If it's better than your good solution, maybe you can remove point n+1 and find a better solution to the n-point problem.
> 1 votes

---
Tags: algorithms, np-hard, traveling-salesman
---


title: Maximum induced tree

text:
# Question
Title: Maximum induced tree
Given an undirected graph $G(V, E)$, how hard is it to decide whether it has an induced tree consisting of $k$ vertices, where $k$ is also given in the input?

# Answer
This is $\mathrm{NP}$-complete. Reduce from **Independent Set** instance $(G, k)$. Add a new universal vertex $v$ to $G$. Connect $v$ with a very long path (only to $v$ not to any original vertex of $G$). And set $k' = k + 1 + \mathrm{length\\:of\\:the\\:long\\:path}$, where length of the long path is the number of vertices in it.

Clearly, if the induced tree does not touch $v$ then it either only stucks in the long path or being confined to $V$. So, in order to have $k'$ vertices, it must include $v$ and the long path. Since $v$ is connected to all $V$, the set of vertices in $V$ that are included the induced tree must form an independent set.
> 2 votes

---
Tags: np-complete, np-hard
---


# Question
Title: How is the control unit affected by pipelining?
Compared to not using instruction pipelining. What is different?

# Answer
> 1 votes
One, the control unit is pipelined. Two, because *everything* is pipelined, it's busy all the time and must be able to produce at least one instruction per cycle. Third, if you have a processor capable of executing more than one instruction per cycle, the control unit must be capable of handling more than one instruction per cycle, which includes decoding multiple instructions per cycle, preloading memory containing instructions before they are needed etc.

---
Tags: cpu-pipelines
---


# Question
Title: Average-case complexity of linear search where half of the elements in the array are duplicates
I know that for an array of size *n* **distinct** elements, the Average Case complexity for linear search is as follows:

A(n) = $\frac{n + 1}{2}$

However, I am having trouble coming up with the Average Case complexity in the case where half of the elements in the size *n* array are **duplicates**. Take, for example, this array of integers:

`1 2 6 6 5 4 6 6 6 3`

Here is my thought-process so far:

I know that if we are looking for a specific element **x** in the array, the probability of doing it in a certain number of comparisons is $\frac{1}{n}$, since the distribution is uniform. So the average number of comparisons is still $\frac{n + 1}{2}$. (referencing this question's approved answer)

If the element we are looking for **x** is the duplicate number, however, then what is that probability of doing it in a certain number of comparisons? From there, how would I then compute the average-case complexity?

# Answer
Let us assume the elements in the array are the multi-set $M=\\{1,2,\cdots,n-k, d, d, \cdots, d\\}$, where $d$, an element that is different from $1,2,\cdots, n-k$, appears $k\ge 0$ imes. The situation raised by OP is simply the special case when we let $n=2k$.

In order to discuss the average time-complexity of a linear search, we must specify the distribution of the array as well as the element or the distribution of the element we are searching for.

## The distribution of the array assumed

The most common distribution discussed in various articles and in people's mindset is probably the following simplest one. $$\text{All orderings of the multi-set are equally likely.}$$ That distribution is assumed throughout this answer.

## The average number of comparisons needed when we search for $d$

The following answer is given in the wikipedia analysis.

$$\begin{cases} n & \mbox{if } k = 0 \\ \displaystyle\frac{n + 1}{k + 1} & \mbox{if } 1 \le k \le n. \end{cases}$$

The above answer is easy to prove by induction on $n$.

## The average number of comparisons needed

Assume $k\ge 1$ from now on. Two cases will be shown.

## the case with one extra element

Let $o$ stands for an element not in the set $S=\\{1,2,\cdots,n-k, d\\}$. If we are searching for a specified element in $S\cup\\{o\\}$, where each element is equally likely to be specified, here is the computation. $$\begin{align} E\[\text{search for } x\] &= \sum\_{x!=d \text { and } x!=0}\frac 1{n-k+2}E\[\text{search for }x\] + \frac1{n-k+2}E\[\text{search for }d\] + \frac1{n-k+2}E\[\text{search for }o\]\\ &=\frac{n-k}{n-k+2}\frac{n+1}2 + \frac1{n-k+2}\frac{n + 1}{k + 1} + \frac1{n-k+2}n\\ &=\frac{n+1}2 + \frac1{k+1} - \frac{2}{(k+1)(n-k+2)} \end{align}$$

In particular, if we let $n=2k$, then $$E\[\text{search for } x\] =\frac {n+1}2 + \frac2{n+2}-\frac{8}{(n+2)(n+4)}$$

## the case with $M$ alone

What is the average number of comparisons need among the cases when the element we are search for turned out to be an element in $M$, assuming that we are searching for an element in the union of the multi-set $M$ and another multi-set $M'$ that is disjoint with $M$, where all elements in $M$ will be equally likely to be searched? The inclusion of the $M'$ is to ensure that we do NOT know whether the element to be found belongs to $M$ before we start the search.

Here is the computation. $$\begin{align} E\[\text{search for } x\] &= \sum\_{x!=d}\frac 1{n}E\[\text{search for }x\] + \frac k{n}E\[\text{search for }d\]\\ &=\frac{n-k}n\frac{n+1}2 + \frac k{n}\frac{n + 1}{k + 1}\\ &=\left(1-\frac{k-2}n -\frac2{n(k+1)}\right)\frac {n+1}2 \end{align}$$

In particular, if we let $n=2k$, then $$E\[\text{search for } x\] =\frac14\left(n+5-\frac 4{n+2}\right)$$

---

Please note that we have not computed the situations when we know the element to be searched is an element of array before we start the linear search, which might be the more common situations. Readers are encouraged to dive into those situations.

The wikipedia item is a good place to start your journey of finding, reading, and playing with the many variations and generalization of this question.
> 1 votes

---
Tags: algorithm-analysis, arrays, searching, average-case
---


# Question
Title: How do I show T(n) = 2T(n-1) + k is O(2^n)?
This is a practice problem I've come up with in order to study for an exam I have in a couple of hours.

Again, here's the problem: Show T(n) = 2T(n-1) + k is O(2^n) where k is some positive constant.

First of all, 2^n is indeed the upperbound, right? Since I've made this problem up myself, I'm not 100% sure, but from what I have seen, this should be O(2^n).

If so, here's my progress:

We want to show P(n) is true for all n \> n0, where P(n) is the statement "T(n) \<= c * 2^n" (for some fixed c, to be determined)

For now, let's fix c at T(1).

Base case: n = 1

We want to show T(1) \<= c * 2. Since c = T(1), our equation becomes T(1) \<= T(1) * 2, which is trivially true.

Inductive step: Assume P(n - 1) is true for n \> 1. We want to show that P(n) holds.

```
T(n) = 2 T(n - 1) + k, by definition
    >= 2 (c * 2^(n-1) ) + k = c * 2^n + k

```

Here's where I get stuck. How can we possibly show that c * 2^n + k \<= c * 2^n for any value of c? Did I make a mistake somewhere?

# Answer
> 4 votes
You are right. We can't show that $c \times 2^n + k \le c \times 2^n$. It doesn't matter how you choose $c$; you are doomed. So, this approach is a failure. You will need to find a different way to prove it.

This sometimes happens. Don't get discouraged. Often you'll need to try a couple different proof strategies before you find one that works. Back to the drawing board!

Here is what I suggest. To simplify your life, first pick a particular value of $k$: say, $k=1$, so your recurrence is $T(n) = 2 T(n-1) + 1$. Now, try writing out a table of the first 10 values of the recurrence, i.e., $T(1), $T(2), $T(3), \ldots$ Does that give you any clues or ideas about what you can say about $T(n)$? Do you spot a pattern?

---

This is a common strategy: look at small examples to see if you can spot a pattern, hypothesize a relationship (e.g., your closed form), then formally prove the relationship using proof by induction. If you read in a textbook, they might only show you the last step (the proof by induction) with no hint of where they got the relationship from in the first place, but now that you're doing it yourself, you get to learn how to do it for real. Once you've proved by induction that $T(n)=...$ (your expression), it is easy to prove in one step that this is $O(2^n)$.

This is also an instance of a common pattern when using proof by induction. The hardest step in proof by induction is figuring out what to prove: figuring out what the inductive predicate is. In your case, instead of trying to prove $T(n) \le 2^n$, you will fare better by proving something more specific: proving that $T(n) = 2^{n-1} T(1) + (2^{n-1}-1)k$. This is sometimes known under the name "strengthening the invariant". Here the invariant that we are trying to prove is $T(n) = 2^{n-1} T(1) + (2^{n-1}-1)k$. This is a "stronger" statement than $T(n) \le 2^n$ (it is more specific, it gives us more information, it narrows down the possible values of $T(n)$ further). Counter-intuitively, in this case, proving something more specific actually turns out to be easy. Sometimes induction is surprising!

# Answer
> 6 votes
In this case, your best bet is to just solve the recurrence by direct substitution.

$$\begin{align\*} T(n) &= 2T(n-1) + k \\ &= 2\big(2T(n-2) + k\big) + k \\ &= 2\big(2\big(2T(n-3) + k\big) + k\big) + k\\ &= \cdots\\ &= 2^rT(n-r) + k\sum\_{i=0}^{r-1} 2^i\\ &= 2^rT(n-r) + k(2^r-1)\\,. \end{align\*}$$

Putting $r=n$ gives $$\begin{align\*} T(n) &= 2^nT(0) + k(2^n-1) \\ &= 2^n(T(0) + k) - k \\ &= O(2^n) \end{align\*}$$ since, although you forgot to define $T(0)$, it is a constant and so is $k$.

# Answer
> 5 votes
Here is another idea, which works for the more general recurrence $T(n) = T(n-1) + k(n)$. Let $S(n) = T(n)/2^n$. Then $S(1) = 1/2$ and $$ S(n) = \frac{T(n)}{2^n} = \frac{2T(n-1)}{2^n} + \frac{k(n)}{2^n} = S(n-1) + \frac{k(n)}{2^n}. $$ If the series $\sum\_{n=1}^\infty \frac{k(n)}{2^n}$ converges then we deduce that $S(n) = \Theta(1)$ and so $T(n) = \Theta(2^n)$. This is certainly the case in your example since $\sum\_{n=1}^\infty \frac{1}{2^n}$ converges, and you get similar results even for $k(n) = c^n$ for any $c \< 2$, for $k(n) = 2^n/n^t$ for all $t \> 1$, and so on.

# Answer
> 2 votes
**By characteristic roots**

$$ \begin{align\*} t\_n - 2t\_{n-1} &= k\\ t\_{n-1} - 2t\_{n-2} &= k \end{align\*} $$

Subtract:

$$ t\_n - 3t\_{n-1}+ 2t\_{n-2} = 0$$

Characteristic equation is:

$$ x^2 - 3x + 2 = 0 $$

Roots are: $$ \begin{align\*} x &= 1\\ x &= 2 \end{align\*} $$

so the general solution is:

$$ t\_n = C\_1 1^n + C\_2 2^n $$

or

$$ t\_n = O(2^n) $$

**By generating functions**

You get homogeneous recurrence in the same way.

Now,

$t\_n = 3t\_{n-1}-2t\_{n-2}$

\begin{eqnarray\*} G(x) &=& \sum\limits\_{i=0}^\infty t\_ix^i \\ &=& t\_0 + t\_1x + \sum\_{i=2}^\infty (3t\_{i-1}-2t\_{n-1})x^i \\ &=& a\_0 + t\_1x + 3x\sum\_{i=0}^\infty t\_ix^i - 2k\sum\_{i=0}^\infty t\_ix^i \\ &=& t\_0+ t\_1x + 3xG(x)-2x^2G(x) \end{eqnarray\*}

Now,

\begin{eqnarray\*} G(x) &=& \frac{t\_0+t\_1x}{2x^2-3x+1} \\ &=& \frac{A}{1-x} + \frac{B}{1-2x} \end{eqnarray\*}

As we know, \begin{equation\*} \sum\_{i=0}^\infty \alpha^i x^i = \frac{1}{1-\alpha x} \end{equation\*} so \begin{equation\*} \frac{1}{1-x} = 1 x + x^2 + \ldots \end{equation\*} and \begin{equation\*} \frac{1}{1-2x} = 1 +2x + 4x^2+ \ldots \end{equation\*} Now,

\begin{equation\*} G(x) = \sum\_{i=0}^n (A\cdot 1+B\cdot 2^i)x^i, \end{equation\*} so

\begin{equation\*} t\_n = A + B\cdot 2^n = O(2^n). \end{equation\*}

# Answer
> 1 votes
Let $S(n) = T(n) + k$. Then $$ S(n) = T(n) + k = 2T(n-1) + 2k = 2S(n-1). $$ Therefore $S(n) = 2^n S(0)$, and so $$ T(n) = S(n) - k = 2^n S(0) - k = 2^n (k + T(0)) - k. $$

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Choose the best classifier to predict the label of strings of a regular language
I have to tackle this problem: I have some strings that are my training set. These strings belong to a regular language corresponding to a deterministic finite automata (hidden namely I don't now it, neither the language nor the automata). A string is labeled like positive if belong to hidden language and negative otherwise. The strings of training set are correctly labeled. I have to build a statistical classifier from training set that predicts the label of strings not seen (generalization) in the best way (better accuracy, respect to actual labeling of hidden language/automa). I have to choose between Support Vector Machine (SVM), Recurrent Neural Network and Convolutional Neural Network.

What could be the best choice and why?

# Answer
> 2 votes
My bet would go to a Recurrent Neural Network, as it closely models some (fuzzy, non-discrete) state machine as each character is output. A decent start to read up on RNNs for this purpose is to read the article The Unreasonable Effectiveness of Recurrent Neural Networks which describes character-level RNNs used to predict text.

---
Tags: regular-languages, finite-automata, machine-learning, classification
---


# Question
Title: What are the prerequisites for instruction pipelining to work?
When can it be applied? When can it not be used? I get the general idea but not what it takes to make it work.

# Answer
> 1 votes
The main use case for pipelining is when your latency is large, but actual work is small. You hide the latency by scheduling many operations such that the latencies overlap but the actual work does not.

It can't be used if the latencies are not independent. An example is calling people from a phone just to say "yes". The actual work is very small, the latency is very large, however your phone can only call one person at a time so you can't actually apply pipelining.

If you had multiple phones however you could start dialing the next person while the previous phone is still ringing.

---
Tags: cpu-pipelines
---


title: Pipeline question

text:
# Question
Title: Pipeline question
I have this multiple choice question from a computer architecture class, a mips processor executes a program at 10 sec, without pipelining and clock rate 100 MHz. When running the program on a processor with 500 MHz clock rate and 5 stages of pipelining which of the following execution times isn't possible. a:2,5 sec, b:3 sec, c:1,5 sec, d:3,3 sec.

My approach to it was to find the cycles of the clock for executing the program on the first processor which would be execution time * clock rate = 1000 * 10^6. From that the number of instructions would be 1000 * 10^6/ first processor's CPI. Since the second processor uses 5 stages of pipelining, I assume it's CPI to be 1 and thus the execution time for it should be 1000 * 10^6/(500 * 10^6 * first processor's CPI) = 2/first processor's CPI and since the CPI of the first processor would have to be 1 or higher the execution time for the second processor would have to be lower than 2 which would mean all choices are correct but c, yet we have been told that the correct answer is c. So c is in reality the only execution time that isn't possible for the second processor but I simply can't figure out why.

# Answer
From you question, it's not obvious which parts are constant and which are moving, but let's assume that first CPU has the same five execution stages, so each stage takes 2 ns. By pipelining them, we can't improve speed by more than 5x, making 1.5s indeed impossible.

OTOH, improvement may be less than 5x due to structural hazards (as well as memory delays), so all remaining times are possible.
> 1 votes

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


# Question
Title: Karp hardness of searching for a matching erosion
First, read the previous question: Karp hardness of searching for a matching cut

As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the problem has been proven to be $\mathrm{NP}$-hard even when restricted to bipartite graph of bounded diameter.

Now, I wanna restrict the notion of a **matching cut** even further to a **matching erosion**. A matching erosion is a matching cut whose removal separates the original graph into two connected components $A$ and $B$, where all the vertices of $A$ belong to the matching itself. In other words, a matching erosion is just a matching cut that **peels** off $A$ from $G$ like *cutting a thin slice of meat off a big meat block in a cafe bar*.

All the literature constructions seem not to be able to yield such a nice, thin matching erosion cut.

Our problem is defined as: Given an undirected graph, determining if there exists a matching erosion.

The question is what is the complexity of our problem?

# Answer
In the theory of finite undirected graph, a basic notion that is broadly studied is the notion of matching cut. A *matching cut* in a graph $G$ is defined to be a matching subgraph of $G$ that is also the edge set of a cut. A $\it cut$ of a graph $G = (V, E)$ is a partition of the vertex set $V$ into two sets $(A, B)$ such that $A$ and $B$ induces two disjoint induced subgraphs that were before incident to some crossing edges which are the edges in the corresponding so-called edge cut set. Specifically, the edge set of the cut $(A, B)$ is then defined to be the subset of $E$ containing all the edges with one endpoint in $A$ and the other endpoint in $B$, i.e. those edges $uv$ with $u\in A$ and $v\in B$. A matching cut is formally defined to be the edge set of such a cut, whenever its edge cut set is indeed a matching. It is worth noting that a matching subgraph which removal increases the number of connected components of a graph $G$ is not necessarily a matching cut, since it may contain edges inside the two separated induced subgraphs. It is a matching cut if it contains exactly the edges of the cut. In order to have more hard computational problems in our still very limited arsenal of proven hard problems, we want to restrict this notion further. We define a {\it matching erosion} as a matching cut $(A, B)$ such that $A$ is exactly one side of the matching. It means that each vertex $v\in A$ has exactly one edges out of $A$, and for any two different vertices $u, v\in A$ their crossing edges end in different vertices in $B$. Intuitively, such a matching split $M=(A,B)$ visually ''peels" off $A$ from $G$.

Formally, we define a matching erosion of an undirected graph as follows:

**DEFINITION 1**

Given an undirected graph $G=(V, E)$, a matching erosion $(A, B)$ is a partition of $V$ into two disjoint sets $V = A\cup B$ such that:

* $G\[A\]$ and $G\[B\]$ are two disjoint induced subgraphs
* The edge set of the cut is a matching: $M = \\{uv\in E\vert u\in A \land v\in B\\}$ is a matching
* Every $u\in A$ is incident to an edge in $M$

Then, our problem naturally asks whether a given undirected graph $G$ has a matching erosion.

**DEFINITION 2**

**Matching Erosion** of a graph:

**Input**: An undirected graph $G(V, E)$

**Output**: **Yes** if $G$ has a matching erosion $(A, B)$, otherwise **No**

In the next section, we will show that **Matching Erosion** is computationally hard.

We will reduce **Exact 3-Set Cover** problem to our problem. **Exact 3-Set Cover** is another decision problem defined as follows. In **Exact 3-set Cover**, we are given a universe set of elements $U=\\{e\_1, e\_2, \dots, e\_{3n}\\}$ and a collection $F=\\{s\_1, s\_2, \dots, s\_m\\}$ of subsets of $U$. Each subset $s\_j$ in $F$ contains exactly $3$ elements $e\_{s\_j1}, e\_{s\_j2}, e\_{s\_j3}\in U$. The decision problem asks whether there exists a subcollection $F'\subseteq F$ such that each element $e\_i$ of $U$ is contained in exactly one subset $s\_j$ in $F'$. Obviously, $F'$ will contain exactly $n$ subsets in the collection $F$. Such a collection $F'$ is called an *exact cover* of $U$.

**DEFINITION 3**

**Exact 3-Set Cover** problem:

**Input**: a universe $U = \\{e\_1, e\_2, \dots, e\_{3n}\\}$ and a collection $F=\\{s\_1, s\_2, \dots, s\_m\\}$ of subsets of $U$, where each $s\_j$ contains $3$ elements $e\_{s\_j1}, e\_{s\_j2}, e\_{s\_j3}\in U$

**Output**: **Yes** if there exists an **exact cover** $F'\subseteq F$, otherwise **No**

**Exact 3-Set Cover** is shown to be hard by Garey and Johnson. After describing and proving the correctness of the reduction in the next section, we will establish the following claim.

**CLAIM 4**

*We have that* **Exact 3-Set Cover** $\leq\_p$ **Matching Erosion**

**Reducing EXACT 3-SET COVER to MATCHING EROSION**

In this section, we prove the claim 4.

**Proof**:

*Describing the construction*: Given an instance $(U, F)$ of **Exact 3-Set Cover**, we will construct an undirected graph $G=(V, E)$ as the produced instance of our problem **Matching Erosion**. For each element $e\_i$ in the universe $U$, we create a new vertex $e\_i\in V$. Similarly, for each subset $s\_j\in F$, we create a new $K\_3$ consisting of 3 new vertices $s\_{j,1}, s\_{j,2}, s\_{j,3}\in V$. For each such subset $s\_j = \\{e\_{s\_j1}, e\_{s\_j2}, e\_{s\_j3}\\}$, we add the $3$ edges to $E$, namely $s\_{j,1}e\_{s\_j1},\\:s\_{j,2}e\_{s\_j2},\\:s\_{j,3}e\_{s\_j3}$. Finally, we add all edges between pairs of two different vertices of the $e\_i$'s vertices to turn these into a $K\_{3n}$ clique.

*Correctness of the construction*: Suppose that $(U, F)$ has an exact cover $F'\subseteq F$ consistig of $n$ subsets in $F$, then based on that solution to \textsc{Exact 3-Set Cover}, we will easily construct a solution to the produced instance $G(V, E)$ of our problem **Matching Erosion**. Namely, our matching erosion for $G$ would have $A$ to be the set of all the $K\_3$'s of the subsets included in the exact cover. Clearly, each vertex $s\_{j,k}$ (where $s\_j$ is included in the exact cover and $1\leq k\leq 3$) in this set $A$ is connected to exactly one vertex outside of $A$, namely its corresponding element $e\_{s\_jk}$ in the universe $U$. Obviously, this is a matching cut that happens to be also a matching erosion.

Conversely, if $G(V, E)$ has a matching erosion $M = (A, B)$, we shall show that none of the elements $e\_i$ in the universe is included in $A$. Indeed, if some $e\_i$ is included in $A$ then at most one $e\_l$ is not in $A$. This is because if there exist $e\_i\in A$ and $e\_{l1}, e\_{l2}\not\in A$ then $A$ cannot form one side of a matching erosion since $e\_i\in A$ is incident to two crossing edges $e\_ie\_{l1}$, $e\_ie\_{l2}$, recall that the universe $U$ is turned into a $K\_{3n}$ in $G$. So, if one element in $U$ is included in $A$, at most one element $e\_l$ can be in $B$, but this is also clearly not the case. Because if so, then all the other element $e\_i$'s (which are included in $A$) are connected to $e\_l\in B$ violating the definition of a matching erosion. So, we have shown that if some element $e\_i$ is included in $A$, then all of the $K\_{3n}$ corresponding to $U$ in $G$ are included in $A$. But, this also cannot be the case for a matching erosion. We need the following observation.

**Observation**: *For each* $K\_3$ *corresponding to a subset* $s\_j$, *a vertex* $s\_{j,k}$ *in this* $K\_3$ *is included in* $A$ iff. *all the three vertices of this* $K\_3$ *are included in* $A$.

Proof (of the observation): Obviously, by definition of a matching erosion.

Using this observation, we are able to show that a matching erosion cannot include all the $K\_{3n}$ to $A$. Indeed, if so, the matching erosion will then partition the $K\_3$'s into two disjoint sets of $K\_3$'s, those in $A$ and those in $B$. The $K\_3$'s in $B$ would then intuitively form an exact cover for $U$. But, unfortunately, in this case, those vertices of the $K\_3$ in $A$ cannot have any crossing edge in $M$, thus violating the definition of a matching erosion.

We have therefore shown that none of the elements $e\_i$ in the universe is included in $A$. This implies that $B$ contains all the $K\_{3n}$. So, the matching erosion needs to partition the set of $K\_3$'s into two disjoint sets of $K\_3$'s, those in $A$ and those in $B$ like before. But fortunately, the situation is now reversed. the $K\_3$'s in $B$ does not need any crossing incident edge (this is only required in a matching split). And, the $K\_3$'s in $A$ would form an exact cover for $U$.
> 1 votes

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


# Question
Title: Can data be compressed to size smaller than Shannon data compression limit?
I was reading about data compression algorithms and the theoretical limit for data compression. Recently I encountered a compression method called "Combinatorial Entropy Encoding", the main idea of this method is to encode the file as the characters presented in the file, their frequencies and the index of these characters permutation represented by the file.

These documents may help explaining this method:

https://arxiv.org/pdf/1703.08127

http://www-video.eecs.berkeley.edu/papers/vdai/dcc2003.pdf

https://www.thinkmind.org/download.php?articleid=ctrq\_2014\_2\_10\_70019

However, in the first document I've read that by using this method they could compress some text to less than the Shannon limit (They didn't consider the space needed to save the frequency of the characters and the space needed to save the meta data of the file). I thought about it and I found that this method won't be very efficient for very small files but on the other hand it may work well with large files. Actually I don't fully understand this algorithm or the Shannon limit very well, I just know it's the sum of the probability of each character multiplied by $log\_2$ of the reciprocal of the probability.

So I have some questions:

1. Does this compression method really compresses files to smaller than the Shannon limit?
2. Is there any compression algorithm that compresses files to less than the Shannon limit (the answer to this question as far as I know is no)?
3. Can a compression method that compresses files to smaller than the Shannon limit ever exist?
4. If combinatorial encoding really compresses files beyond the Shannon limit, isn't it possible to compress the file again and again until we reach the file size we want?

# Answer
> Actually I don't fully understand this algorithm or the Shannon limit very well, I just know it's the sum of the probability of each character multiplied by log2 of the reciprocal of the probability.

Herein lies the crux. The Shannon limit is not some universal property of a string of text. It is the property of a string of text **plus** a model that provides (possibly context-dependent) probabilities of symbols. It tells us how well that **model** could compress the text, *assuming the model is accurate*.

If you use one model to compute the Shannon limit and then a different model to compress, if the second model is more accurate you can beat the original Shannon limit you had computed, but that's not really relevant.
> 38 votes

# Answer
It's trivially simple to show that you can compress below the Shannon limit--take a cheating compressor that has a bunch of common files assigned to tokens. Said files are stored as those tokens. (Obviously, the compressor must be **very** large, or be drawing on a very large library.)

The compressor will inherently be less efficient at dealing with any file that isn't in it's library, though, as it must in some way distinguish a token from a normal compression.

What you can't do is have a compressor that beats the Shannon limit **on all files**.
> 13 votes

# Answer
You first apply the model to the data, computing the sequence of probabilities, f.e. $1/2$, $1/3$, $1/6$. Then, to encode each symbol with probability $p$, you need $log\_2(1/p)$ bits. And given some particular model, you can't compress data better than the Shannon entropy of probabilities produced by this particular model.

But if you apply another model, you will get another sequence of probabilities. F.e. the letter "u" is rather rare, so its probability over entire text may be 3%, and it's the probability you have to assign to this letter using an order-0 Markov model.

But in English texts, after "q" usually comes a "u", so using an order-1 model, you can assign much higher probability to "u" going after "q", thus improving the compression ratio.

Moreover, some models output less symbols than there are input ones, f.e. LZ77 replaces text repetitions with back-references, so "abababab" turns into "ab\[2,8\]".

When someone talks about Shannon entropy of some data rather than data compressed by a particular model, she usually means the Shannon entropy produced by an order-0 model, i.e. assigning to each symbol its probability over the entire text. Obviously, you can beat this margin by applying a more sophisticated model to the data.
> 11 votes

# Answer
Another possible interpretation of the text: the given compression algorithm is going to give you better compression of some texts, and worse compression on others. However, users generally care about some kinds of files (HTML pages in English, 80386 machine code) more than others (tables of truly random numbers, meaningless noise selected to minimize repetition). Any compression scheme is going to trade off being better at compressing real-world data with being worse than useless at compressing certain other kinds of strings.
> 3 votes

---
Tags: information-theory, data-compression
---


# Question
Title: Which queue does the long-term scheduler maintain?
There are different queues of processes (in an operating system):

*Job Queue:* Each new process goes into the job queue. Processes in the job queue reside on mass storage and await the allocation of main memory.

*Ready Queue:* The set of all processes that are in main memory and are waiting for CPU time is kept in the ready queue.

*Waiting (Device) Queues:* The set of processes waiting for allocation of certain I/O devices is kept in the waiting (device) queue.

The short-term scheduler (also known as CPU scheduling) selects a process from the ready queue and yields control of the CPU to the process.

In my lecture notes the long-term scheduler is partly described as maintaining a queue of new processes waiting to be admitted into the system.

What is the name of the queue the long-term scheduler maintains? When it admits a process to the system is the process placed in the ready queue?

# Answer
I found an appropriate answer. I was asking about the job queue (which I already described). The diagram included in this answer comes from a power-point that uses concise language to explain processes and schedulers and relates the topic to the diagram.

It may be of intrest to other users, also learning this topic, that sometimes time-sharing systems (such as UNIX) have no (or minimal implementations of a) long-term scheduler.

Check these sources for more information:

1.Wikipedia Article

2.Operating System Concepts (Pages 88-89)

©Bernard Chen 2007
> 3 votes

# Answer
The only work the long term scheduler does is to move the processes from job queue to the ready queue. But this is the most important thing as it controls the degree of multiprogramming. As soon as the processes are submitted to the job queue the long term scheduler checks for the amount of CPU bound and IO bound processes, then it decides when to place the process in the ready queue, thereafter the complete scheduling is handed over to the short term and medium term schedulers.
> 1 votes

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


# Question
Title: Is there an efficient algorithm for solving tiling puzzles?
As an example of the type of problem, consider Stewart Coffin's Cruiser puzzle:

> Let R be a 48 × 31 rectangle. Let T be a 30°-60°-90° triangle with hypotenuse 34.565 (so legs are 17.2825 and 29.934). Let P be a right trapezoid with base 20.0982 and altitudes 27.1178 and 15.514. Show how to place two copies of T and two copies of P inside R with no overlap.

Solution

The algorithm should be able to solve for any number of polygons of any shape within another polygon of any shape (or conclude that such a solution is not possible).

# Answer
> 1 votes
*Tiling figures of the plane with two bars* shows that this problem is NP-complete in the general case. Simply have the horizontal and vertical bar the same size $\geq 3$.

---
Tags: algorithms, tiling
---


# Question
Title: Compression of Random Data is Impossible?
A few days ago this appeared on HN http://www.patrickcraig.co.uk/other/compression.htm. This refers to a challenge from 2001 - where someone was offering a prize of \\$5000 for any kind of reduction to the size of randomly generated data (the entrance cost would be \\$100 and the contestant could choose the file-size).

I understand the result which shows it is impossible to compress all files of size \>= N to a smaller size (http://en.wikipedia.org/wiki/Kolmogorov\_complexity#Compression).

But in the challenge question the idea is to only compress a single randomly generated file. A simple approach is to find $l$ the longest recurring substring in a file and substitute that with $s$ the shortest non-occuring substring which would give a saving of $l-s$ (since the decompresser only needs one l,s pair).

To obtain an approximation for the single shortest non-occurring substring as Usul pointed using the approximation for the coupon problem: $$E(t) = nlog(n) + \gamma n + (1/2n)$$

In this case $t$ is the number of possible substrings and using bytes for simplicity that's respectively:

275 megabytes for 3 byte strings ($n=256^3$)

91 gigabytes for 4 byte strings ($n=256^4$)

The probability of a recurring substring in the random data is equivalent to the birthday problem over the size of the random data, $p = 1-e^{-((n^2)/2d)}$, for example at 91 gigabytes one can expect to find a recurring 9 byte substring with: $d=256^9$, $n = 91\*1024^3$. $p \approx .636$

With $5000:100$ odds it should be possible to optimize a little more. Of course the cost of `sed` delimiters will be 3 bytes, if the cost of the command counts this method isn't enough to be successful - but this is without doing anything particularly clever.

Am I missing something (It would seem that the majority of random data should not be in fact incompressible)? What is the basis on which someone offers such a challenge and presumes it is entirely unwinnable for the player?

---

Edit (updated calculations up top as well): Also I think its possible to have a savings of precisely $l-s$ without having to pay for a delimiter. This is because it is known that substring $s$ did not exist prior to insertion - therefore the pair can be arranged with $sl$ contiguously written in memory and either the length of $s$ is known ahead of time (by estimating the shortest substring) or the next byte following $s$ in the file does not collide with the first byte of $l$ with at least probability $255/256$ (this gets better actually by having a choice which non-occuring $s$ to substitute for which recurring $l$).

# Answer
> 10 votes
Here's the Kolmogorov complexity argument that @YuvalFilmus mentions in his answer.

Your input here is a `sed` script of some size plus an input file of some size. Say the total size of the `sed` script plus the file is $n$ bits.

There can be only $2^n$ inputs of size $n$ bits. Even if I let you have a `sed` script of less than $n$ bits (and don't charge you for telling me how long the input is) there can only be $2^{n+1}$ possible inputs. But there are $2^{n+8}$ possible strings of length $n+8$ bits, so you can produce at most $1/128$th of the possible $2^{n+8}$ bit strings. That's less than .01, so paying 50:1 my expected value for the bet would be positive (about 0.60). (And that's only giving you 1 byte to play with.)

In short, random strings that are compressible *at all* must be extremely rare.

## Why your scheme is broken

Your probability calculations look fine to me. And the idea of a birthday attack is so appealingly clever, it took me quite a while to see the real problem.

Your basic scheme doesn't compress.

Suppose you find a 4-byte substring that doesn't occur in the original string, and an 8-byte substring that occurs twice in the original string.

Then you are going to produce a "compressed" string of length $n$ bytes - 8 bytes - 8 bytes + 4 bytes + 4 bytes, plus a `sed` replacement script which must be of length at least 4 bytes + 8 bytes. Add that all together and we get $n+4$.

If the longer string is length $l$ and repeats $r$ times and the shorter string is of length $s$ then in general your scheme reduces the string length by

$$ (l-s) r - (l+s).$$ So $l=7$, $r=3$, $s=4$ "works" (saves 2 bytes), but the probability of finding a 7 byte substring that repeats 3 times is infinitesimal.

# Answer
> 6 votes
It is always possible to compress a single file. Given a file $f$, here is an encoding scheme which is especially good for compressing $f$. The *empty string* is used to encode $f$. Every other string encodes itself. We have succeeded reducing $f$ to zero bytes!

What is the catch? We didn't take into account the length of the decompression procedure. When we do take it into account, the problem goes away. The *Kolmogorov complexity* of a string $f$ is the size of the minimal problem generating $f$ in some fixed programming language. A simple counting argument shows that most strings of length $n$ cannot be generated by programs of length less than $n-1$, and at least one string requires a program of length at least $n$; we call such a string *Kolmogorov random*.

In your case, you need a compression/decompression procedure which works for several different files at once, which are not known in advance. The situation is slightly different but the conclusions are similar.

# Answer
> 1 votes
You have to be really careful with these kind of proposals to check your constants and arguments. And it's hard to get motivated to check the proposal carefully when we know it's proven impossible to work in general. But anyway, let's run some asymptotics for your proposal.

What is a guess at the length of the shortest non-occurring substring? Well, it will be just about $\log n$ (some details below). This boils down to a coupon collector's type problem. Now, what is a guess at the length of the longest repeated substring? Well, it will be about $2\log n$ (details below). This time it boils down to the birthday paradox, as you said.

This shows that at best you would hope to save $\log n$ bits with your replacement. But I am pretty sure you would lose these $\log n$ bits because you would need to delimit your strings and program and to do that requires some other unique non-occurring string, or some other "escape character" type strategy. So I hope this illustrates why these sorts of proposals are delicate/tricky.

---

Computing these probabilities and string lengths accurately is actually quite tricky, but this is an optimistic estimate that I think should be about right.

Coupon: Let's say we want the shortest non-occurring substring to have length $m$. Optimistically, we can divide the string into $n/m$ disjoint segments of length $m$ each, and just require that not all possible strings of length $m$ appear as one of these segments. This will be a bit more optimistic than reality because of the possibility that a string occurs as an overlap between two segments. But anyway there are $2^m$ strings of length $m$, so by the coupon collectors problem we expect to try $2^m \log(2^m) = m2^m$ independent trials until we collect them all. Thus the number of disjoint segments $n/m$ can be as large as about $m 2^m$, which we solve for $n = m^2 2^m$, or $m \approx \log n - 2\log\log n$.

Birthday: If we look at all the strings of length $m$, there are about $2^m$ possible strings. If we pretend for optimism that we get $n$ independent tries to draw a substring of length $m$ (one for each index a substring could start at), then we expect a number of collisions $1 = {n \choose 2} \frac{1}{2^m} \approx \frac{n^2}{2 2^m}$, or $m \approx 2\log n$.

# Answer
> 1 votes
It is in fact easy to prove that the average bit length under any compression scheme over all input strings of length $n$ **cannot** be less than $n-1$.

---

To see why, note that you can arrange the set of output strings first in lexicographic order and then by length, and then for each chain of strings (namely where each is a prefix of the next) add $1$ bit to each of them to make them no longer a chain (each is not a prefix of the next). Now you have a compression scheme that takes at most $1$ bit more than the original scheme but is also a **prefix-free code**. Let $T$ be the binary tree representing the codes (output strings) for all input strings of length $n$. The claim is that the average code length is at least $n$.

The first obvious way to prove it is by structural induction. Let $f(k)$ be the minimum average code length for a tree with $k$ leaves. Then I claim that $f(k) \ge \log(k)$ (binary logarithms). To prove it, for each $k$ there is some tree $T$ that has average code length $f(k)$, so letting $p,q$ be the sizes of the child subtrees of $T$, we have $k = p+q$ and $k·f(k) = k + p·f(p)+q·f(q)$ $\ge k + p·\log(p)+q·\log(q)$ by structural induction. And by Jensen's $p·\log(p)+q·\log(q)$ $\ge 2·\frac{p+q}{2}·\log(\frac{p+q}{2})$ $= k·(\log(k)-1)$, and thus $f(k) \ge \log(k)$, completing the structural induction.

A second non-obvious but elegant discrete way is to prove the following about an optimal tree (namely with minimum average code length): (1) Every internal node must have two children, otherwise you can eliminate that node to shorten the codes for all the descendant leaves. (2) There cannot be two leaves whose depths differ by at least two, otherwise you can modify it to create a better tree. (Move the `/\` containing the deeper leaf to the position of the shallower leaf, and check that the three affected codes have total length shortened.) From (1) and (2) it is clear that every code in the optimal tree with $k$ leaves has length at least $\log(k)$.

---

Thus even when we do not count the EOF marker needed to signal the end of the file, no compression scheme can compress input strings of length $n$ such that the average compressed length is less than $n-1$. And the above proof shows that if you require prefix-free encoding then the lower bound is $n$.

And so this means that it is definitely **false** that the majority of strings can be compressed. Even if you take advantage of an EOF marker (which is essentially cheating), the above shows that you cannot do better than $1$ bit on average.

In fact, that is a very tight bound if your objective is to only compress strings of a fixed size $n$, and I shall describe an encoding that achieves $(1-2^{-n})$-bit compression on average: Simply delete all leading zero bits. $\frac12$ of the strings will have their first bit removed, and $\frac14$ will have their second bit removed, and so on. Thus the average number of bits removed from all the codes is $\frac12+\frac14+\frac18+\cdots+\frac1{2^n}$, as claimed.

---
Tags: information-theory, data-compression, entropy
---


# Question
Title: How to express the existence of winning strategy of the starter of a game in temporal logic?
Consider a two-player game. A winning strategy of a player is a strategy following which the player can always beat his opponent, no matter how his opponent responds.

A game can be unfolded to a state space consisting of the possible ways of both sides of the game. How to express the existence of winning strategy of the starter of a game, say player 1, in temporal logic, defined on such a state space? The temporal logic formula can be used for model checking.

Using CTL, I get $\exists \Box (\exists \Diamond \textsf{Win}\_1)$, meaning that there exists a path (from the initial state) such that from each state of this path there exists a path that eventually leads to a winning state for player 1. Is this correct?

Can it be expressed in LTL or any other variants of temporal logic?

# Answer
> 4 votes
I don't think it's possible in CTL nor LTL to model two competing players.

You would probably need **ATL** (Alternating-time Temporal Logic). In ATL, the formula $\langle\langle A \rangle\rangle \phi$ says that agent (or coalition) $A$ can enforce $\phi$ to come about. In your case, $\langle\langle P\_1 \rangle\rangle \text{Win}\_1$.

In *modal µ-calculus*, it should definitely be doable. Something like $\mu Z . \big( \text{Win}\_1 \lor \Diamond \Box Z \big)$?

# Answer
> 0 votes
You can't express it in LTL. Have a look at the slides by Katoen (https://moves.rwth-aachen.de/wp-content/uploads/lec18-2.pdf), slide 108. From that and theorem 6.18 from book Principles of Model Checking, you know, that no equivalent LTL formula exists.

Intuitively, your CTL formula is correct. But keep in mind, that Player 1 can still lose if he chooses a wrong move every time. If you don't want that, change the second quantifier to "for all". With that you say: there exists a path, where always player 1 wins no matter what, i.e. $ \exists \square\forall \lozenge Win\_1 $.

---
Tags: formal-methods, game-theory, model-checking, linear-temporal-logic, computation-tree-logic
---


# Question
Title: Array contains elements that differ by K correctness proof
I have been puzzling over an algorithm that decides whether a *sorted* array of numbers contains two numbers that differ by `k`. I do not intuitively understand why this algorithm works, or what thought process might have led me to think of this algorithm on my own, although I believe that I can prove it's correctness.

```
CONTAINS_DIFFK(arr, k)
    n = size(arr)
    if n == 1 return false
    i = 1
    j = 2
    while i <= n and j <= n
        if i != j and arr[j] - arr[i] == k
            return true
        if arr[j] - arr[i] < k
            j++
        else
            i++
    return false

```

My questions are:

1. Is the following proof sound
2. Is there a more concise way to prove correctness?
3. What thought process might have lead me to derive this algorithm on my own? (I had to look up the solution)

### Proof by Induction

Let `arr` be an arbitrary sorted array of integers of length `n`. Assume for the sake of induction that `CONTAINS_DIFFK` return `true` if `arr` contains two numbers which differ by `k` and `false` otherwise. Let `arr'` be an arbitrary sorted array formed by adding a single arbitrary integer to the end of `arr`. We prove that `CONTAINS_DIFFK` return `true` if `arr'` contains two numbers which differ by `k` and `false` otherwise.

Assume that it is the case that `arr` contains two elements that differ by `k`. By our inductive assumption, `CONTAINS_DIFFK` will return `true` for `arr`. Because `CONTAINS_DIFFK` immediately returns after finding two elements that differ by `k` without considering further elements, and the first `n` elements of `arr` and `arr'` are identical, the `n+1`'th element of `arr'` will not be considered and will not affect the output of the algorithm. Thus `CONTAINS_DIFFK` returns `true` for input `arr'`.

Therefore we need only consider the case, which is now assumed, in which `arr` did not already contain two elements which differ by `k`. We must consider the cases in which the `n+1`'th element of `arr'` does not differ from any of the first `n` elements by `k` and the case in which it does.

First, consider the case in which the `n+1`'th element of `arr'` does not differ from any of the first `n` elements of `arr'`. We show that the algorithm returns `false`. Let `i'` be the value of `i` when `j` is incremented to be equal to `n+1`. Note that `i' <= n`. Now simply note that the last element of `arr'` will be compared to some subset of the elements after and including the `i'`th element. Since we assumed that the last element of `arr'` does not differ from any element by `k`, the condition for returning `true` will never be met and `false` will be returned.

Finally, we consider the case in which there exists some element `e` in `arr` which differs by `k` from the `n+1`'th element of `arr'`, and show that the algorithm returns `true`. Again, let `i'` be the value of `i` when `j` is incremented to `n+1` while processing `arr`. Now, critically, note that `j` was incremented to `n+1` because `arr[n] - arr[i'] < k`. If we note also that `arr'[n+1] >= arr'[n]` (because it is sorted) and `arr'[n+1] - e = k`, then we may derive `e > arr[i']`. Thus, we note that `i` will be increased from `i'` up to the index of `e` at which point `CONTAINS_DIFFK` will return `true` as desired.

### Base case

Let `arr` be an arbitrary sorted array of two integers. We may trace through the execution of this algorithm and note that if `arr[2] - arr[1]` then it will return `true` and it will return `false` otherwise. Thus, the induction is complete.

# Answer
> 3 votes
My line of thought for deriving this algo:

* there is well-known Merge algo (part of Merge Sort) combining two sorted arrays
* we can modify it to output only equal elements of arrays (i.e. producing intersection instead of union)
* we can further modify it to return true on the first match, and false at the end
* and finally, we can modify it to compare elements with given offset `k`

I suggest you to practice developing algos at leetcode or similar site, it will allow you to come up with similar solutions in a few minutes.

# Answer
> 1 votes
Your proof attempt is a bit hard to follow. Here is an alternative proof.

First note that we have to assume that $k \geq 0$. Indeed, if $k \< 0$ then the algorithm fails on the array $k,0$ since the only solution is $(i,j) = (2,1)$, but $j \geq 2$ throughout the algorithm.

Denote by $i,j$ the values of $i,j$ at the beginning of an iteration, and by $i',j'$ their values at the end of the iteration. Define $$P(i,j) := \exists I \in \[i,n\], J \in \[j,n\] \text{ such that } I \< J \text{ and } arr\[J\]-arr\[I\] = k.$$

**Lemma 1.** If $P(i,j)$ holds then either $arr\[j\] - arr\[i\] = k$ or $P(i',j')$.

**Proof.** Let $I,J$ be the indices whose existence is promised by $P(i,j)$. We consider several cases:

1. $arr\[j\] - arr\[i\] = k$. In this case, the lemma clearly holds.
2. $arr\[j\] - arr\[i\] \< k$, and so $i' = i$, $j' = j+1$. In this case, $arr\[j\] - arr\[I\] \leq arr\[j\] - arr\[i\] \< k$, and so $J \> j$. Therefore $P(i',j')$ holds.
3. $arr\[j\] - arr\[i\] \> k$, and so $i' = i+1$, $j' = j$. In this case $arr\[J\] - arr\[i\] \geq arr\[j\] - arr\[i\] \> k$, and so $I \> i$. Therefore $P(i',j')$ holds.

$\square$

**Lemma 2.** If there exist indices $I \< J$ such that $arr\[J\] - arr\[I\] = k$ and the algorithm halts then it returns *true*.

**Proof.** The proof is by contradiction. Suppose that there exist indices $i \< j$ such that $arr\[j\] - arr\[i\] = k$, but the algorithm never returns *true*. Denoting by $i\_t,j\_t$ the values of $i,j$ after $t$ iterations, we will show by induction that $P(i\_t,j\_t)$ always holds, and so the algorithm doesn't stop after $t$ iterations (since $P(i,j)$ is clearly false if $i \> n$ or $j \> n$); in particular, it never halts.

Clearly $I \geq 1$ and $J \geq I+1 = 2$, and so $P(i\_0,j\_0) = P(1,2)$ holds. Suppose now that $P(i\_t,j\_t)$ holds. Since the algorithm never returns *true*, necessarily $arr\[j\_t\]-arr\[i\_t\] \neq k$. Lemma 1 therefore implies that $P(i\_{t+1},j\_{t+1})$. $\quad \square$

**Lemma 3.** The algorithm always halts.

**Proof.** Suppose that the algorithm never returns *true*. In each step, $i+j$ increases by $1$. Initially, $i+j = 3$. If the algorithm continues for $2n$ iterations without stopping, then at the end of the $2n$'th iteration, $i+j = 2n+3$, which implies that either $i \> n$ or $j \> n$, and so the algorithm would exit the loop and return *false*. $\quad \square$

**Theorem 4.** The algorithm is correct: it always halts, and it returns *true* iff there exist indices $i \< j$ such that $arr\[j\] - arr\[i\] = k$.

**Proof.** Lemma 3 shows that the algorithm always halts. If it returns *true*, then clearly $arr\[j\] - arr\[i\] = k$ and $j \neq i$. If $k \> 0$ then necessarily $j \> i$, and if $k = 0$ then $arr\[j\] - arr\[i\] = arr\[i\] - arr\[j\] = k$, and either $i \< j$ or $j \< i$.

Conversely, if there exist indices $i \< j$ such that $arr\[j\] - arr\[i\] = k$ then Lemma 2 (in conjunction with Lemma 3) shows that the algorithm returns *true*. $\quad\square$

---

Finally, you ask what thought process would lead you to derive this algorithm. When the algorithm was first designed, it must have been a stroke of inspiration. Nowadays, most computer scientists are aware of this algorithm, so if there is any other algorithmic problem with a similar solution, computer scientists would come up with this kind of algorithm by analogy.

In other words, the way you would come up with this kind of algorithm is by being aware of a similar algorithm for a similar problem. The more algorithms you know, the more algorithmic tasks you will be able to solve.

---
Tags: correctness-proof, searching
---


title: Requirements for a TM to halt

text:
# Question
Title: Requirements for a TM to halt
I'm just beginning self-studying a course on computability and automata; my textbook, describing a generic Turing Machine, lists two following halt conditions:

1. A TM halts, if for a particular state $q \in Q$, $\delta(q, a) = (q, a, HALT)$ for all $a$ in the alphabet and this $q$ is called a halt state;
2. A TM also halts, when the TM reads $a$ while being in $q$, and $\delta(q, a) = (q, a, HALT)$ is true *only for this particular $a$*.

I have no problems comprehending the first one, but I'm a little frustrated by the second one, that is, I don't understand, why the exclusivity of $a$ is of any importance. Won't the machine halt if we have several $a, a'$, for both of which it's supposed to halt?

And in general, are there any other halting conditions possible?

# Answer
I've finally figured this out after some further research.

In this particular definition, one differentiates between halting states and a so-called "stalling action" or, rather, stalling with no further actions. The book of Robert Soare "Turing Computability" states:

> If the machine ever reaches the halting state $q\_0$, after say $s$ steps, then we say $M$ halts and the output $y$ is the total number of 1’s on the tape. \<...\> We may assume that $M$ never makes any further moves after reaching state $q\_0$, i.e., that the domain of $δ$ contains no element of the form $(q\_0,s)$.

At the same time,

> if the machine M enters a state $q \ne q\_0$ and reads a symbol $s$ from which $δ(q, s)$ gives no moves, then the machine **stalls**, i.e., makes no further moves, and gives no output. We **do not refer to this as halting** even though the machine stalls and stops forever. We use the term halting **only** if $M$ enters the halting state $q\_0$.

This way, the first definition that I initially cited would be equivalent to "no symbol gives the machine an order for further moves in this particular halting state", and the second one was referring to this stalling condition, with a little of messed up terminology.

So if the function $δ(q, s)$ provides no image with $q \ne q\_0$ for a particular symbol $s$, then it's considered to be an error for the symbol $s$.

With this definition, one doesn't need to declare the $δ$-function on the whole $Q \times S$ and provides a way to deal with these missing spots.
> 0 votes

# Answer
The first condition makes no sense whatsoever to me, and neither condition is expressed in the most obvious way. I can't imagine why you'd ever want to define halting in that way.

**A Turing machine halts exactly when it enters the HALT state.** It's as simple as that. The only alternative I've ever seen is to have two halting states, corresponding to accepting and rejecting the input. In that case, the machine halts exactly when it enters either one of them.

Your source seems to be adopting a different approach, in which "HALT" is not a state but an action of the machine in the same class as "move the tape head left" or "move the tape head right". That's unusual, but not problematic in its own right. However, neither definition of halting is the one that I would expect.

* The second one is the closest: the machine halts if it decides to stay in its current state, leave the current character on the tape and make the HALT action. But this is still strange – surely the HALT action on its own should halt the machine, regardless of what state the machine moves to and what it writes on its tape at that step? For example, the behaviour of hte machine at the next step would seem to be undefined if $\delta(q,a)=(q',a',\mathrm{HALT})$ and $q'\neq q$ and/or $a'\neq a$.
* The first definition is very unnatural. I can see no motivation for saying that the machine halts only if it's in a state where seeing any character whatsoever would cause it to stay in the same state, leave the tape as it is and making the HALT action. In fact, this is basically defining the state to be a halting state in the way that Turing machines are usually defined. If one wanted to go down that route, why not just use the conventional HALT state instead of making HALT an action of the machine?

Note, however, that these definitions of halting, and the standard one, are all equivalent in that they can simulate each other. So, whichever of these definitions you use, the same class of problems can be computed by Turing machines.
> 3 votes

---
Tags: turing-machines
---


# Question
Title: Counting tokens in compilers, lexical analyser
Let's start with the question. Say I have a C language statements follows

1. it 458cat 2.01 = 96.87abc a.2 ;

-my question is how many tokens are there in the above statements. Secondly does white space like tabs, newline, makes a token or not?
2. If you are interested in my solution then proceed on your own risk. Firstly I think in lexical analyser there is no such thing as white space so after removal of that the above statement would look catastrophic so, I have not taking that approach.
3. Now we see 'it' as an identifier similarly, '458' as integer, 'cat' as identifier, (please not that I may have mistaken here which i don't know that is '458cat' may be invalid identifier so the lexical analyser may report an error, but I don't know will that happen or not. you may argue that what I have written is wrong because if it was true then the identifier like '678hello' will be a valid identifier but since its not then iam wrong. But take a different approach like if all white space between '468 abc' being vanished (this is what lexical analyser does first) then it would like '468abc' . Initially in case of 468 abc we were taking 468 as integer and abc as valid identifier but after white space removal things are changed so what I think is it will be reported in syntax analyser but I don't know that am I right), similarly, '2.01' as real integers, '=' as operator, '96.87' as real number, 'abc' as identifier, 'a ' as identifier, .2 as real number and ' ; ' as special symbol.
4. I most certainly know that iam not right but if you could correct where I was wrong it will be helpful

# Answer
> 1 votes
In C, `458cat` is a single *ppnumber* token. It's not a valid number, so it will eventually produce an error message, but it is tokenised as a single token.

There's a longer explanation of this behaviour in this StackOverflow answer.

---
Tags: compilers, lexical-analysis
---


# Question
Title: How to define the natural numbers as a W-type?
I'm having trouble understanding the rules for W-types in type theory as defined here: https://ncatlab.org/nlab/show/W-type#wtypes\_in\_type\_theory

Can someone give an example of how these rules could be used to define a simple W-type such as the natural numbers? What would $A$ and $B$ be in the formation rule for instance?

# Answer
> 4 votes
The formation and introduction rules for W-types, as given on n-cat lab, are:

$$\frac{A:Type\quad x:A⊦B:Type}{(W x:A)B(x):Type}-\text{Formation}$$

$$\frac{a:A\quad t:B(a)\rightarrow W}{sup(a,t):W}-\text{Introduction}$$

You can define the natural numbers by setting $A=Bool$ and $B(a) = \text{if}\\; a\\; \text{then}\\; ⟂\\; \text{else}\\; Unit$. Where $⟂$ is the empty type and $Unit$ is the unit type.

Zero is then $sup(a,t)$ where $a=true$ and $t: ⟂ \rightarrow Nat = λn. abort(n)$. eg. we use the zero constructor (by choosing $a=true$) and fill in the only possible value of a function from $⟂$ to $Nat$.

The successor of $p$ can be defined as $a=false$, $t:Unit \rightarrow Nat = λx.p$.

---
Tags: type-theory, inductive-datatypes
---


title: NP languages definition

text:
# Question
Title: NP languages definition
Is it good to define a language $\mathcal{L}$ in NP as a language for which, given an element $x$, it is possible in polynomial-time to check whether $x \in \mathcal{L}$ or not? Because I need to have an informal definition of that, in order to give just an idea of it, without using formalism. Otherwise how could I define it roughly speaking?

# Answer
> 8 votes
> Is it good to define a language $\mathcal{L}$ in NP as a language for which, given an element $x$, it is possible in polynomial-time to check whether $x \in \mathcal{L}$ or not?

**No.** If you could do that you could "check" that this language would be in P, because you can check (or more formally *decide*) all possible words for membership in polynomial time this way.

A correct formulation would be:

> A language $\mathcal L$ is in NP if for every word $x$ in the language there exists a *witness* $w$ which is of length polynomial in the length of $x$ and given the witness and the word you can verify language-membership in polynomial time.

Note that you only need said witness (sometimes also called *certificate*) need only exist for words that actually are in the language, i.e. you don't need to be able to construct them for negative instances and constructing them is allowed to take super-polynomial time.

# Answer
> 7 votes
No! The definition you give is the definition of **P**!

**NP** is the class of languages $\mathcal{L}$ where given $x$ and what you might call a "proof" $y$, you can deterministically check in time polynomial in the size of $x$ and $y$ whether $y$ really does prove that $x\in\mathcal{L}$. In addition, the size of $y$ must be bounded by some polynomial in the size of $x$.

Examples of proofs would be satisfying assignments for $\text{SAT}$, colourings for $3\text{-COL}$, and so on. These proofs are more commonly called "certificates" or "witnesses".

The key distinction is that the language itself is a yes/no decision problem (e.g., "Is this formula satisfiable?"), whereas the proof tends to be a solution to the related function problem (e.g., "Give me a satisfying assignment for this formula, if it has one.").

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


title: Babyface vs Heel

text:
# Question
Title: Babyface vs Heel
So here's the question: "There are two types of professional wrestlers: "babyfaces"("good guys") and "heels"("bad guys"). Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O(n+r)-time algorithm that determines whether it is possible to designate some of the wrestlers as babyfaces and the remainder as heels such that each rivalry is between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it."

This was on a quiz I took today. So I assumed there was some sort of trait that we would be able to use to determine whether a wrestler was a heel or babyface whenever we went over them. What I thought would work would be to create an undirected graph containing each wrestler as a connected node. The order nor do the relationships matter. Then I would Breadth-first-search through all of them. Instead of just one queue, though, I would use two. After being visited, the node would either be placed in the babyface queue or the heel queue. When both queues weren't completely empty, then I would dequeue each and pair one and one together, before going back and continuing the search.

Would this work as a solution or no?

# Answer
Another way to state this problem is:

> Given an undirected graph, determine whether it can be 2-colored in $O(V+E)$. Equivalently, determine whether it is bipartite.

The simplest solution is to use what my algorithms professor called WFS: Whatever-First Search. That is, like BFS or DFS, except you don't care what order you traverse in. (You can replace "bag" with "queue" to get BFS, or "stack" to get DFS, if you like.)

```
while there are uncolored nodes:
    pick an arbitrary uncolored node
    color it red
    put all its neighbors in a "bag" (arbitrary container data type)
    while the bag is not empty:
        remove a node from the bag
        if it has neighbors of both colors, RETURN FALSE
        color it the opposite of its neighbors
        add its uncolored neighbors to the bag
RETURN TRUE

```

Here, "coloring a node red" = marking it as a babyface, and "coloring a node blue" = marking it as a heel. Edges are rivalries, nodes are wrestlers.

This aligns with the usual intuition for this problem: "start with some arbitrary node, color it red, color all its neighbors blue, color all *their* neighbors red…"
> 2 votes

---
Tags: graphs, search-algorithms, search-problem
---


# Question
Title: What is the Difference Between Many-to-Many (M:M) Threading and Hybrid (M:N) Threading?
I have been researching threading and come across several websites which all say contradicting statements about which and how many thread models exist. Some websites say there are only three: **1:1, M:1 and M:M**, while others say the three are **1:1, M:1 and hybrid (M:N)**. Still others say there are four types, including **2-level** threading?

Google and stack exchange haven't been able to come up with a clear answer as of yet. I was hoping for someone to shed some light on this situation, namely the difference (i.e pros & cons) between M:M, M:N and two-level threading types.

# Answer
> -1 votes
Go to a website selling computers (or phones). Check how many cores the computers have, and whether they support hyper threading. So there you get the number how many threads can actually *run* at the same time.

On the other side, your software can use a single active thread, or 100 active threads. Some software can actually make use of many threads, other software can't. Your computer however can run more than one software at the same time, so there will be more active threads.

So everything is M:N. M = 1 or N = 1 is possible but rare. If M \< N then some cores are unused and might as well not be there. If M \> N then at any point in time, at most N of the M threads are running. And M changes all the time.

---
Tags: concurrency, parallel-computing, threads, multi-tasking
---


title: How to get all in constant time?

text:
# Question
Title: How to get all in constant time?
We are planning to design a system where following operations are supported.

```
Increment("foo"): Increase the count of key 'foo'

Decrement("bar"): Decrease the count of key 'bar'

getMin():  Return the key which has minimum count

getMax():  Return the key which has maximum count

```

The catch is all operations should be in $O(1)$ time.

# Answer
If your keys are strings, you can use a prefix tree mapping keys to values. In this way each operation can be implemented in $O(h)$ time, where $h$ is the length of the key, which means it is $O(1)$ to the size of the collection.
To get the minimum key(or maximum) you can traverse the tree, by going through the edge from the lexicographically smallest (or largest if you need max) node on each level.
I don't think you can get better complexity than $O(h)$ for arbitrary sized keys as you need $O(h)$ time to output the key anyway.
> -1 votes

---
Tags: algorithms, data-structures, hash, heaps, linked-lists
---