# Question
Title: Can this special case of bin packing be solved in polynomial time?
Consider a multiset of $n$ integers, where each integer is between $1$ and $3 M$. The sum of all integers is $3 S$. There are three bins. The capacity of each bin is $C = S + M$. Is there a polynomial-time algorithm to decide whether all integers can be packed into the bins?

To explain why this specific case is special, consider some variants of the problem:

* When $C$ is not fixed, the problem is NP-hard, since it is a special case of the bin-packing problem.
* When $C = S$, the problem is NP-hard, since it is equivalent to 3-way number partitioning.
* When $C \geq S + 2 M$, the problem is easy since the answer is always "yes". *Proof:* put the items in an arbitrary order into the bins as long as there is room. Suppose by contradiction that not all integers are packed; let $x$ be some remaining integer. Then the sum in each bin is larger than $C-x$, so the sum in all bins is more than $3 C - 3 x \geq 3 S + 6 M - 3 x$. Since $x \leq 3 M$, this sum is larger than $3 S + 2 x - 3 x = 3 S - x$. But then the sum of all integers plus $x$ is larger than $3 S$ \- a contradiction.

The case $C = S+M$ is between these extremes: it is larger than $S$ for which the problem is hard, but smaller than $S+2M$ for which the answer is always yes.

Is this case is easy or hard?

# Answer
Yes, there is a polynomial time solution. It is not very pretty, so simplifications or alternative approaches are welcome.

TL;DR: the exact weights are rarely important, so we can round them up to a multiple of $K := \lceil \frac{3M}{n^3} \rceil$ or something similar (there are only $\approx n^3$ rounded item weights). Then, we can do dynamic programming that keeps track of rounded weights for two bins and *exact* weight for the third bin. If we somehow got a false negative result, then in *all* solutions *two* bins are almost full at the same time. Such cases turn out to be highly structured (all items have weights that are either close to $0$ or close to $3M$, the total weight of the former is small and there are exactly $3\ell + 2$ items of the latter type for some $\ell$) and can be solved by an algorithm that greedily moves items between bins.

Only the case when $M \> n^4$ is interesting, otherwise simple dynamic programming will do the job. Similarly, assume that $n \> 10^9$ to make things like $Kn^2$ negligible when compared to $M$. Do not worry, actual precise bounds are much better, I just chose these to not think about the details too much.

As mentioned above, the first step is to try finding a solution with "discretised" weights. Pick $K := \lceil \frac{3M}{n^3} \rceil$. For each item, its *discrete weight* is its weight rounded *up* to a multiple of $K$. For each bin, its *discrete size* is its size, rounded *down* to a nearest multiple of $K$. Items *discretely fit* into a bin, if the sum of their discrete weights does not exceed the discrete size of the bin. Clearly, if items discretely fit into a bin, then they do fit in the bin for real. The opposite implication is not true, but only because of rounding issues; if several items fit into a bin, but not discretely, then their total weight is at least $(S + M) - (n+1)K$ (at most $n$ items, each causes a rounding error of at most $K$; rounding of the bin size also causes a rounding error of at most $K$). Let us say that any bin with sum of weights at least $(S + M) - (n+1)K$ is *almost full*. Unless the bin is almost full, discrete fitting and real fitting is the same thing.

Consider any solution (by *solution*, I mean a correct distribution of items to bins). There can be at most two almost full bins; otherwise the total weight of items is at least $3(S + M) - 3(n+1)K = 3S + (3M - 3(n+1)K) \> 3S$, as $K \approx \frac{3M}{n^3}$).

We can find all solutions with at most *one* full bin by simple dynamic programming, which answers the following question: suppose that we distributed some prefix of items to bins and we know the sums of *discrete* item weights in the second and the third bins (there are only $n \cdot \lceil \frac{3M}{K} \rceil \approx n^4$ possible discrete weights for each bin), what is the minimal possible total *real* weight of items in the first bin in this case? We will not miss out the solutions where there is at most one almost full bin (because we can track the weight in *one bin* precisely).

The only remaining problem is the case when *all* optimal solutions have *exactly two* almost full bins. Let us study the structure of the solutions in this case (this is not an algorithmic part, but rather only a mathematical setup; so, we are not interested in algorithmic aspects for the following few paragraphs). Suppose that the first bin is filled up to $S + M - \varepsilon\_1$ and the second is filled up to $S + M - \varepsilon\_2$, where $\max(\varepsilon\_1, \varepsilon\_2) \leqslant (n+1)K$. Then, the third bin is filled up to $3S - (S + M - \varepsilon\_1) + (S + M - \varepsilon\_2) = S - 2M + \varepsilon\_1 + \varepsilon\_2$.

Let us try to move some items from the first bin to the third (in order to make them both *not* almost full). Why cannot we do that? Because all items in the first bin are either *small* (have weight at most $(n+1)K$) and the first bin will not stop being almost full, or because all items in the first bin are *big* (have weight at least $3M - 3K(n+1)$), so the third bin will become almost full (or, maybe, there is not even enough space for the item). About the latter part: if the weight of an item is less than $3M - 3K(n+1)$, then the third bin will be filled up to less than \begin{equation\*} S - 2M + \varepsilon\_1 + \varepsilon\_2 + (3M - 3K(n+1)) = S + M - (3K(n+1) - \varepsilon\_1 - \varepsilon\_2) \leqslant S + M - K(n+1), \end{equation\*} because $\max(\varepsilon\_1, \varepsilon\_2) \leqslant K(n+1)$.

Now, let us move all small items from the first bin to the third bin one-by-one. Then, either the first one stops being almost full at some point (while the third one is still not almost full, it still had almost $3M$ space left before all operations), or we move them all. Similarly, move all small items from the second bin to the third bin.

Now, *all* items in the first and the second bins are big, but they are still almost full. As before, denote the space left in the first and the second bins by $\varepsilon\_1$ and $\varepsilon\_2$. I claim that no items in the third bin have weight in the range $\[10K(n+1), 3M - 10K(n+1)\]$. Why? Because we can take any such item and swap its places with a big item from the first bin. Then, the total weight of items in the first bin will decrease by at least $(3M - 3K(n+1)) - (3M - 10K(n+1)) = 7K(n+1)$, hence it will not be almost full anymore. On the other hand, the total weight of items in the third bin was $S - 2M + \varepsilon\_1 + \varepsilon\_2 \leqslant S - 2M + 2K(n+1)$ and will increase by at most $3M - 10K(n+1)$. So, the third bin will be filled up to at most $S + M - 8K(n+1)$ and still will not be almost full.

In the end, there are only items of weight at most $10K(n+1)$ (now, forget about the previous terminology and call *such* items *small*) and items of weight at least $3M - 10K(n+1)$ (call them *big*). As per gnasher729 answer, small items can be easily distributed to the bins in the end, because $10K(n+1) \< 3M/2$. Unfortunately, we cannot *ignore* small items, because they affect $3S$ (the total weight of items) and, therefore, the sizes of the bins.

Fortunately, we know from the above manipulations that we can move all small items to the third (*not* almost full) bin. Hence, we are left with the following problem: there are $m$ big items with weights $3M - v\_1$, $3M - v\_2$, $\ldots$, $3M - v\_m$, where $v\_1 \leqslant v\_2 \leqslant \ldots \leqslant v\_m \leqslant 10K(n+1)$. There are also $n - m$ small items with total weight $R = 3S - (3Mm - V)$, where $V = v\_1 + \ldots + v\_m$. The exact weights of small items is not important.

There is barely any difference between weights of big items, because $10K(n+1)$ is negligible when compared to $M$. Moreover, the total weight of small items is also negligible. Because otherwise we could do something similar to the way we proved that all items are either big or small: we can pick small items (remember that they are all in the third bin) until their total weight exceeds $20K(n+1)$ for the first time (at such a moment, their total weight will exceed $20K(n+1)$ by at most a weight of a single small item; in other word, it will be in the range $\[20K(n+1), 30K(n+1)\]$) and then swap all these items with a single big item from the first or the second bin.

Hence, $R \< 20K(n+1)$. Therefore, "from a bird's view", we have $m$ items of weight $3M$ and $n - m$ items of weight $0$. I claim that $m \bmod 3 = 2$. Indeed, consider the other cases.

When $m \bmod 3 = 0$, we can place arbitrary $m/3$ big items in each bin. Distribute small items arbitrarily as well. Then, the total weight of items in each bin will not exceed $3M \cdot (m/3) + R \< Mn + 20K(n+1)$. On the other hand, \begin{equation\*} S + M - K(n+1) \geqslant (3M - 10K(n+1)) \cdot (m/3) + M - K(n+1) = Mm + (M - K(n+1) - 10Km(n+1) / 3), \end{equation\*} which is greater than $Mm + 20K(n+1)$, because $Km(n+1) \leqslant Kn(n+1)$ is negligible when compared to $M$. Hence, in this case, there is a solution with *no* almost full bins. Contradiction.

When, $m \bmod 3 = 1$, or $m = 3\ell + 1$, there is a bin with $\ell + 1$ items in any solution. Hence, their total weight is at least $(\ell + 1)(3M - 10K(n+1))$. On the other hand, the size of bin is $S + M \leqslant (R + (3\ell + 1) \cdot 3M) / 3 + M = R/3 + (3\ell + 2)/3 \cdot 3M$. Again, the multiplier before $3M$ is the deciding factor here, and $\ell + 1 \> (3\ell + 2)/3$. Hence, there is no solution in this case, contradiction.

Finally, $m \bmod 3 = 2$, or $m = 3\ell + 2$ corresponds to the case when two bins have $\ell + 1$ big items in them and one has $\ell$. This case is actually nontrivial: not only there are inevitably exactly two almost full bins, but we also cannot distribute big items without considering their weights, like in the case $m \bmod 3 = 0$. The remaining text deals with this case.

The good thing is that we can distribute all small items and $\ell$ heaviest big items to the third bin and this is optimal. Intuitively, some bin *has* to contain at most $\ell$ big items, and this leaves a lot of free space left regardless of big items chosen. Formally, $\ell$ big items and all small items have total weight $3M\ell + R$, but $S + M \geqslant (3M - 10K(n+1)) \cdot (3\ell+2)/3 + M = 3(\ell + 1)m - \textrm{something small}$. Hence, there is *almost* $3M$ of free space left, even if we choose $\ell$ heaviest items to place in the bin (because the number of big items is more important than the actual items involved). On the other hand, other two bins have little free space left, because the total weights of items in them is $3M \cdot (\ell + 1) - \textrm{something small}$.

Hence, we need to actually compare small numbers and cannot get away with rough bounds, as we did in the first algorithmic part and in the arguments above.

Recall that we place $\ell$ heaviest big items (or $\ell$ items with the smallest values of $v\_i$, which is the same) in the third bin. Hence, let $L$ be the multiset of $\ell$ smallest values of $v\_i$ and $U$ be the multiset of $2(\ell + 1)$ largest values of $v\_i$. Moreover, denote $u\_i = v\_{i+\ell}$ for $i := 1, 2, \ldots, 2(\ell + 1)$, so $U = \\{u\_1, u\_2, \ldots, u\_{2(\ell + 1)}\\}$ (here, $u\_i$ is non-strictly increasing).

Then, we want to distribute items of weights $3M - u\_i$ for $i \in \[1, 2(\ell + 1)\]$ into two bins of size \begin{equation\*} S + M = (3M \cdot (3\ell + 2) - \mathrm{sum}(U) - \mathrm{sum}(L) + R))/3 + M = 3M \cdot (\ell + 1) - (\mathrm{sum}(U) + \mathrm{sum}(L) - R)/3, \end{equation\*} where by $\mathrm{sum}(X)$ I mean the sum of elements in the multiset $X$.

Because we distribute exactly $\ell + 1$ items in both bins, we can focus on the space we saved when compared to $3M(\ell + 1)$. That is, we need to find a submultiset $X$ of $U$ with size $\ell + 1$, such that $\mathrm{sum}(X) \geqslant (\mathrm{sum}(U) + \mathrm{sum}(L) - R)/3$ and $\mathrm{sum}(U \setminus X) \geqslant (\mathrm{sum}(U) + \mathrm{sum}(L) - R)/3$. Here, $X$ represents the items that go to the first bin and $U \setminus X$ represents items that go the second bin. In other words, we need to find $X$ with \begin{equation\*}\mathrm{sum}(X) \in \[(\mathrm{sum}(U) + \mathrm{sum}(L) - R)/3, \mathrm{sum}(U) - (\mathrm{sum}(U) + \mathrm{sum}(L) - R)/3\] = \[(\mathrm{sum}(U) + \mathrm{sum}(L) - R)/3, (2 \cdot \mathrm{sum}(U) - \mathrm{sum}(L) + R)/3\].\end{equation\*}

In the end, we need $\mathrm{sum}(X)$ to get in the *gap* of length \begin{equation\*}(2 \cdot \mathrm{sum}(U) - \mathrm{sum}(L) + R)/3 - (\mathrm{sum}(U) + \mathrm{sum}(L) - R)/3 + 1 = 1 + (2R + \mathrm{sum}(U) - 2\mathrm{sum}(L))/3.\end{equation\*} This gap always has positive length, because $\mathrm{sum}(U) \geqslant 2\mathrm{sum}(L)$: $\min(U) \geqslant \max(L)$ by definition of $U$ and $L$ and there are $2(\ell + 1)$ elements in $U$, but only $\ell$ elements in $L$. Moreover, the gap is centered at $\mathrm{sum}(U)/2$ (both by formulas and its "physical" meaning, which must be symmetric with respect to swapping the first and the second bin).

Now, we can do the following: start from some submultiset $X$, such that $\mathrm{sum}(X) \leqslant \mathrm{sum}(U) / 2$ and gradually change it to its complement $U \setminus X$ by replacing its elements with elements of its complement, for which $\mathrm{sum}(U \setminus X) \geqslant \mathrm{sum}(U) / 2$. Then, either at some moment $\mathrm{sum}(\textrm{current subset})$ will get in the gap, leading to a valid way to place the remaining $2(\ell + 1)$ items in the first and the second bins), or we will somehow "*jump over*" the whole gap in a single move, meaning that the difference between two elements of $U$ is somehow greater than the length of the gap. Intuitively, the length of the gap is usually quite large. Hence, jumping over the gap is an extremely rare situation.

Not all ways to change $X$ into $U \setminus X$ work similarly well, so let us choose some fixed $X$ and some fixed way to transform $X$ into $U \setminus X$. Specifically, split all $2(\ell + 1)$ elements of $U$ into $\ell + 1$ pairs. One of the pairs is $u\_{2\ell + 1} \leftrightarrow u\_{2\ell + 2}$ (we pair up two largest elements), all other pairs are $u\_{i} \leftrightarrow u\_{i + \ell}$ (we pair up elements on the distance $\ell$, of course $i \in \[1, \ell\]$). Initially, $X$ contains the smaller element in each pair. If $\mathrm{sum}(X)$ is *already* in the gap, we won and do not have to do anything.

Otherwise, replace the elements of $X$ one-by-one by elements that they are paired up with, as long as we can do that *without jumping over* the gap. In the end, we are left with at least one pair that makes us jump over the whole gap (as mentioned before, we cannot reach $U \setminus X$ without either falling in the gap or jumping over it, because the gap is centered in $\mathrm{sum}(U)/2$).

I claim that only the pair $u\_{2\ell + 1} \leftrightarrow u\_{2\ell + 2}$ can lead to such a big jump. Assume the contrary, suppose that, for some $i \in \[1, \ell\]$, the jump $\Delta := u\_{i + \ell} - u\_i$ is more than $1 + (2R + \mathrm{sum}(U) - 2\mathrm{sum}(L))/3$ (the length of the gap, as shown before). Then, $u\_{i + \ell} = u\_i + \Delta \geqslant \max(L) + \Delta$. Because $i + \ell \leqslant 2\ell$, $u\_{2\ell+2} \geqslant u\_{2\ell+1} \geqslant u\_{i + \ell} \geqslant \max(L) + \Delta \geqslant \Delta$. In the end, \begin{equation\*} \mathrm{sum}(U) \geqslant u\_{2\ell + 1} + u\_{2\ell + 2} + (2\ell) \cdot \max(L) + (u\_{i + \ell} - \max(L)) \geqslant 2\ell \cdot \max(L) + 3\Delta \geqslant 2 \cdot \mathrm{sum}(L) + 3\Delta\end{equation\*} (compared to "doubled $L$", $U$ has two extra elements, which are both at least $\Delta$, and an element that is at least $\Delta + \textrm{the corresponding element of "doubled $L$"}$). Hence, the length of the gap is \begin{equation\*}1 + (2R + \mathrm{sum}(U) - 2\mathrm{sum}(L))/3 \> 0 + (0 + 3\Delta)/3 = \Delta,\end{equation\*} contradiction.

Therefore, the only way to "jump over" the gap is to replace $u\_{2\ell + 1}$ with $u\_{2\ell + 2}$. Let us do that immediately (as the first operation, while $X$ still contains $u\_1$, $u\_2$, $\ldots$, $u\_{\ell}$). Did we jump over the gap? If we did not, we will never jump over it, so we will successfully find a solution. If we did, then the largest element of $U$ is *so large*, that even putting it in the same set with $\ell$ smallest elements of $U$ is already making the sum of the corresponding set too large. In this case, there is no solution, because the largest element of $U$ has to go *somewhere* (either to $X$, or to $U \setminus X$).
> 2 votes

# Answer
Tricky. You’d sort the items in descending order and put them into the bins. If all items are in the bins, there is a gap of $3 M$. You can show easily that any item of size $x \leq 1.5 M$ will fit. In general, if the gap is $G$, any item $\leq G/2$ will fit. So we start with $G=3 M$, and as long as the smallest item is $\leq G/2$ we know it will fit somewhere, so we remove it from the problem and increase $G$ by its size. As soon as $G \geq 6M$ we know everything will fit (this is the case $C=S+2M$ presented in the question).

Otherwise, the smallest item of size $x \> G/2$ is not guaranteed to fit. And if $G+x \< 6M$, the next smallest item is not guaranteed to fit if it has size $y \> (G+x)/2$. The third smallest and larger items at guaranteed to fit.

If the smallest item has size $x = 2M$ for example then all the other items have sizes between $2 M$ and $3 M$ and we must fit them into bins such that one bin has $\geq 2M$ empty space, and the other two have a combined empty space $\leq 3 M$. My guess is that would be difficult. quite likely NP complete. Not sure.
> 1 votes

---
Tags: combinatorics, packing
---


# Question
Title: MST for a graph that does not have distinct weights
We all know that:

> Every graph has an MST. The MST need not be unique, but it is unique if all the edge weights of the graph are distinct.

But if the weights of the edges in a *connected* graph are not all distinct, does it mean that there is more than one minimum spanning tree?

# Answer
> 4 votes
The MST can be unique even if edge weights repeat. For example, consider the graph on $\\{1,\ldots,n\\}$ in which the weight of $(1,2),(2,3),\ldots,(n-1,n)$ is $1$ and the weight of all other edges is $2$.

---
Tags: graphs, minimum-spanning-tree
---


# Question
Title: Dijkstra's algorithm in a weighted graph
The Dijkstra's algorithm is never used for a graph with a negative weight. The following graph has negative weight but when the Dijkstra's single source shortest path algorithm run from vertex a, it computes the correct shortest path distance to all the vertices.

But when I solve it for the following graph:

I am not getting a shortest path, why does the Dijkstra's algorithm working for the first graph and not the other one, or did I make any mistake? Could anyone make me understand it? Run Dijkstra’s algorithm on the graph below considering D as the source vertex, it would make this easier to understand if you also describe the status of the distance array at each iteration.

# Answer
In the second graph, we can replace each undirected edge with two directed edges. For example we can replace edge between D,C with a directed edge $D\to C$ and directed edge $C\to D$ such that each edge weight is equal to $-8$. This means we have a reachable negative cycle from source, so there is no algorithm to compute shortest path in a such instance of shortest path problem. Because, for example
$d\[D\]=-\infty$.
> 2 votes

# Answer
The first graph is a directed graph with no negative cycles.

However, the second graph is an undirected graph that *has* a negative cycle. This means that there is no shortest path, since we can always walk any number of times we want in that negative cycle - which will just continue to decrease the path's cost.

Essentially this means you tried to compare two things that cannot be compared: one with a valid shortest path, and one without it.
> 1 votes

---
Tags: dijkstras-algorithm
---


# Question
Title: What defines how many lookahead a lexer has?
if a lexical grammar has multiple token which start with the same character like `>` `>>` `>>=` and their longest length is 3, does it have 2 character lookahead?

Or is it implementation defined. Does the number of character required to produce a fixed size token like a keyword - 1 also count.

What is the formal definition of number of lookahead a lexer has?

# Answer
> 2 votes
"Lookahead" is an aspect of a particular parsing algorithm, and might be different for different parsing algorithms using the same grammar. You can't talk about lookahead without specifying which parsing algorithm is in use.

If you are using a top-down LL parsing algorithm, parsing decisions need to be made very early, as soon as the parser reaches the start of the non-terminal to be applied. I think that corresponds with your intuition that distinguishing `12345` from `12345h` requires arbitrarily much lookahead. But that is not the case for all parsing algorithms. A bottom-up LR parser doesn't need to decide which non-terminal to apply until much later, often not until the end of the non-terminal. So the following grammar will recognise both numeric forms with lookahead of 1:

```
dnum ::= [0-9] | dnum [0-9]
hpfx ::= [a-f] | dnum [a-f] | hpfx [0-9a-f]
hnum ::= hpfx 'h'

```

In practice, lexical analysis is not easy if lookahead is bounded. All of the scannerless parsing frameworks I know of use parsing algorithms which do not limit lookahead, such as GLR or PEG. Most lexical scanner frameworks use regular expressions. Although a regular expression can be converted to a context-free grammar, that grammar is often ambiguous. This doesn't matter for lexical analysis because a token is presumed to have no internal structure; consequently it's irrelevant how many possible different parses could be produced.

Even so, it is possible to talk about lookahead for a lexical scanner, because the scanner generally returns the longest possible token. Thus, the scanner almost always has to look at the next character in order to be sure that the token cannot be extended, and in some cases it needs to look at more characters. This is usually phrased as "backtracking" or "fallback", but it would be equivalent to view it as lookahead. For most real languages, the required lookahead or maximum fallback is a small number like 1 or 2, but there are exceptions. A typical case is the `...` token in C. Since `..` is not a C token, if the scanner sees `.`, it may need to look at the next two characters before returning a `.` token.

# Answer
> 0 votes
In general, it could depend on the language.

Consider, for example, Microsoft MASM syntax for numbers, where the radix of a number is specified by a postfix, so `12345` is a decimal constant, but `12345h` is a hexadecimal constant. Depending on how you understand what a distinct token is, this could require an arbitrary number of characters of "lookahead" to determine what token it is.

But we don't usually think of it this way. Rather, we typically specify lexical languages in terms of the "maximal munch rule", which states that the "correct" token is the one which consumes the largest amount of input.

---
Tags: lexical-analysis, definitions
---


# Question
Title: Are the halting problem proofs refuted by software engineering?
Can D simulated by H terminate normally? The x86utm operating system based on an open source x86 emulator. This system enables one C function to execute another C function in debug step mode. When H simulates D it creates a separate process context for D with its own memory, stack and virtual registers. H is able to simulate D simulating itself, thus the only limit to recursive simulations is RAM.

```
// The following is written in C
01 int D(int (*x)())
02 {
03    int Halt_Status = H(x, x);
04    if (Halt_Status)
05      HERE: goto HERE;
06    return Halt_Status;
07 }
08
09 void main()
10 {
11    H(D,D);
12 }

```

**Execution Trace**
main() calls H(D,D) that simulates D(D) at line 11

**keeps repeating:**
simulated D(D) calls simulated H(D,D) that simulates D(D) at line 03 ...

Is this clear enough to see that D correctly simulated by H can never terminate normally? (because D remains stuck in recursive simulation)

> For any program H that might determine whether programs halt, a "pathological" program D, called with some input, can pass its own source and its input to H and then specifically do the opposite of what H predicts D will do. No H can exist that handles this case. https://en.wikipedia.org/wiki/Halting\_problem

The relationship between H and D exactly matches the above specified pathological relationship.

**Simulation invariant:**
D correctly simulated by H cannot possibly reach its own line 04.

When one applies a simulating (partial) halt decider to the Turing machine based proofs the same non-terminating result is derived as indicated by the exact match with the above criteria.

# Answer
```
// The following is written in C
01 int D(int (*x)())
02 {
03    int Halt_Status = H(x, x);
04    if (Halt_Status)
05      HERE: goto HERE;
06    return Halt_Status;
07 }
08
09 void main()
10 {
11    H(D,D);
12 }

```

**Execution Trace**
main() calls H(D,D) that simulates D(D) at line 11

**keeps repeating:**
simulated D(D) calls simulated H(D,D) that simulates D(D) at line 03 ...

D correctly simulated by H can never terminate normally because D remains stuck in recursive simulation.

The fully operational source code of H/D and the x86utm operating system shows that H correctly matches a non-halting behavior pattern that is equivalent to infinite recursion.

H(D,D) fully operational in x86utm operating system: https://github.com/plolcott/x86utm

Source-code of several different partial halt deciders and their sample inputs. https://github.com/plolcott/x86utm/blob/master/Halt7.c
> -6 votes

---
Tags: undecidability, halting-problem, simulation, c, decidability
---


# Question
Title: Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem
*Introduction to Algorithms*, 3rd edition (p.95) has an example of how to solve the recurrence

$$\displaystyle T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log(n)$$

by applying the Master Theorem.

I am very confused by how it is done. So, $a=3, b=4, f(n) = n\cdot \log(n)$
First step is to compare $n^{\log\_b a} = n^{\log\_4 3}= O(n^{0.793})$ with $f(n)$.

I have no clue on how they compared this. The book explains:

> $f(n) = \Omega (n^{\log\_4 3+\epsilon })$, where $\epsilon \approx 0.2$, case 3 applies if we can show that the regularity condition holds for $f(n).$

Followed by:

> For sufficiently large n, we have that: $af\left(\frac{n}{b}\right) = 3\left(\frac{n}{4}\right)\log\left(\frac{n}{5}\right) \le\left(\frac{3}{4}\right)n \log n = cf(n)~ for~ c=\frac{3}{4}.$

Where did $3\left(\frac{n}{4}\right)$ come from?

# Answer
> 11 votes
If our recurrence takes the form $T(n) = aT(n/b) + f(n)$, then to use the "third case" of the Master method we must have the following hold:

> $f(n) = \Omega(n^{\log\_b a + \epsilon})$ for some $\epsilon \> 0$ and if $a f(n/b) \leq c f(n)$ for some constant $c \< 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$

Our recurrence is defined as $$T(n) = 3T(n/4) + n \log n.$$

By definition we have, $a = 3, b = 4, f(n) = n \log n$.

We now need to show that $f(n)$ is polynomially larger than $n^{\log\_b a}$. That is the "$f(n) = \Omega(n^{\log\_b a + \epsilon})$" part from above. Defining $\epsilon \approx 0.2$ achieves this. The reason being that $\log\_4 3 \approx 0.793$ and $f(n) = \Omega(n^{0.793 + \epsilon})$.

We are left to show that $f(n)$ satisfies the regularity condition. That is the "$a f(n/b) \leq c f(n)$ for some constant $c \< 1$ and all sufficiently large $n$" part.

We simply plug in our values of $a,b$ to get: $$a f(n/b) = 3(n/4) \log (n/4).$$ All we did was take the "$n$" in $f(n)$ and plug in "$n/4$".

To make this easier to see, let $k = n/4$ and observe that $a f(k) = a k \log k$. Swapping $k$ with $n/4$ we have $$3(n/4) \log (n/4) \leq (3/4)n \log n = c f(n)$$ where $c = 3/4$.

This finishes our necessary requirements and we have that $T(n) = \Theta(n \log n)$.

# Answer
> 0 votes
This is the solution. we have to compare with the general equation of master theorem

---
Tags: asymptotics, recurrence-relation, landau-notation, mathematical-analysis, master-theorem
---


# Question
Title: How to design fast/efficient algorithms?
Let's say, if you could travel to the past, what would you teach your younger self? Which key points define efficient algorithms?

# Answer
The whole "how to design efficient algorithms" theme is (surprise!) treated in books usually called "Algorithms" or sometimes a variation like "Introduction to Algorithms". Areas of active research (some more advanced textbooks available) are approximation algorithms (get a decent, not the best possible, solution with reasonable cost) and probabilistic algorithms (surprisingly, many hard problems can be best solved --often, not always-- by tossing a coin and using the result to guide the algorithm's decisions). It is a *vast* area.

Important techniques, that are widely applicable, include **greedy algorithms** (divide the solution into steps, at each step take the most promising alternative; almost never works, but when it does, it is hard to beat), **general graph search** (depth first, breadth first, various heuristic variants like $A^\*$), **dynamic programming** (like greedy algorithms, but consider several alternatives for each step, save partial solutions for reuse), **divide and conquer** (divide a large problem into several smaller ones of the same type, solve recursively and combine).

But there are scores of specialized algorithms that don't fall into any of the above categories, based on insight into the problem's particular structure.

As Euclid is widely reported to have said, "There is no royal road to mathematics". Or algorithms.
> 2 votes

---
Tags: algorithms, efficiency
---


# Question
Title: Proof of approximation ratio for approximate triangle inequality version of k-center
Consider the standard $k$-center problem i.e find $k$ disks of radius $r$ that cover all points in a point set $P$. This problem has a well known greedy 2-approximation algorithm where you (essentially) choose points from $P$ as the centers of each of the $k$ disks and each time you pick a point you pick the one that maximizes the distance from the one chosen just prior (see details here).

My slight variation of this is more formally described as follows; Given a set of points $P$ with a distance between two points $i,j \in P$ as $d\_{ij} \geq 0$ and by convention $d\_{ii} = 0$. The triangle inequality does not quite hold, but we know that for any triple of points $i,k,j \in P$ we have that $d\_{ik} + d\_{kj} \geq d\_{ij}/c$ for some positive constant $c$ \- call this the approximate triangle inequality. Let $S\subseteq P,|S|=k$ be our center clusters. Let $d(i, S) = \min\_{j\in S} d\_{ij}$ i.e the closest cluster center to point $i$ hence the radius of $S$ is $\max\_{i\in P} d(i, S)$. The goal is thus to find a set $S$ of size $k$ of minimum radius. Employing the same greedy algorithm, in this case, would yield what approximation factor?

****Attempted proof** for the approximation factor so far:** If we look at an optimal solution $S^\*$ with optimal radius $r^\*$ (this solution partitions the points into $k$ clusters $C\_1, C\_2, ..., C\_k$), any two points in the same cluster can not be more than $2r^\* / c$ apart by the approximate triangle inequality. Now consider $S \subseteq P$ as chosen by the greedy algorithm. We have two cases: (i) if $S$ is chosen such that each points is from a different cluster from the optimal solution $S^\*$ then any point $p \in P$ is at most $2r^\* / c$ from every point in $S$. (ii) if we chose two points from the same of cluster relative to the optimal solution then we know that we only chose that second point from a cluster because it was the furthest from any of the nodes in $S$ which is at most $2r^\* / c$, hence the approximation factor is $2/c$.

However this approximation factor doesn't really makes sense to me (it would yield a shorter radius than the optimal one if c \> 2).

# Answer
> 1 votes
You are doing everything correctly. You are just making a typo: any two points in the same cluster are at most $2c \cdot r^{\*}$ distance apart. Therefore, the approximation guarantee would be $2c$.

---
Tags: algorithms, algorithm-analysis, approximation, correctness-proof, clustering
---


# Question
Title: What's a good way to sort a set of several correlated vectors?
Let's say I have a bunch of lists of real numbers which we'll call `a`, `b`, `c`, etc. Moreover, let's say all of these vectors are correlated, in the sense that `a[1] < a[2]` implies that there's a better-than-even chance that `b[1] < b[2]`. I want to sort each one of these lists individually, returning `a'`, `b'`,... with the same elements as `a`, `b`, ... but ordered. How can I sort all of these lists simultaneously in a way that takes advantage of these correlations to speed up the sorting? Does the answer to this change if the lists might be either correlated or anticorrelated? (We can rule out relationships like `b = x^2` -- let's say the relationship is monotonic, but not necessarily linear.)

# Answer
There are a variety of possible algorithms you could consider. It's hard to say which will be optimal without more details and analysis. Here are two ideas you could try out.

One approach is to sort the first list using a comparison-based sorting algorithm; and whenever you swap two items in the first list, swap the corresponding items in all subsequent lists. Then, do the same on the second list. If you use an adaptive sorting algorithm, and if the correlation is high enough, then sorting each subsequent list might be a lot faster (because the previous sort got it into approximately sorted order).

Another option is to use a comparison-based sorting algorithm, where to compare item $i$ and item $j$, you count compare the $i$th item comes to the $j$th item in all list and take a majority vote. You could pre-sort all lists using this comparison operator; then follow it up with an adaptive sorting algorithm on each list separately.
> 1 votes

---
Tags: sorting
---


# Question
Title: Where to learn about filesystem file placement strategies?
I'm facing a task similar to what filesystems do. I have a bunch of continuous allocated space and I need to place pieces of variable length data into it, each piece of data can change size over time.

Now I could just place the pieces one after another as they come, then when they grow too big to fit I'd fragment the data or move the whole thing or whatever. To me it seems like a recipe for a fragmented mess though.

I'm sure there is no way to avoid a mess completely but I'd like to keep it to a minimum. Filesystems have to be using some cool strategies for placing data around the partition, right?

I do have some things to consider that differ from filesystems, like some data pieces I'd like to keep close together to be able to go through them with a sequential read.

Anyways, I tried googling the topic but was unable to find anything useful. Is there a special word for data distribution strategy? I'd like to see whats been done before, like for ext4 or ntfs.

# Answer
> 1 votes
Filesystems are optimized to make *very* slow hard disks (uneven access times, getting nearby data is much faster) perform decently. A simple way of doing this is the original Unix file system. If that is not your case, take a look at memory management strategies, perhaps including garbage collection.

---
Tags: filesystems
---


title: Number of comparisons in Quicksort

text:
# Question
Title: Number of comparisons in Quicksort
So would it be correct to say that the number of comparisons from level 1 to level 2 would be $2(n/2-1)$?

Or would it be more correct to say that the number of comparisons is $2^i(n/2^i-1)$?

# Answer
> 1 votes
Splitting the list entails comparing **every** element in the current list with the pivot. That is, if the list is of size $n$, you would have $n-1$ comparisons.

Then, the list is split into sizes $|B|$ and $|S|$ and continues recursively. On the $B$ part you will choose a pivot and make $|B|-1$ comparisons to split them into two (sub)lists. Same with $S$. This continues until you get list of size $1$, for which you computes $C(1)$.

---
Tags: quicksort
---


# Question
Title: How come the set of all binary strings is uncountable?
Sorry for bumping this very old problem which already has answers on multiple SE sites, but I just cannot understand any of the answers.

Let $\Sigma\_{bool} = \\{0, 1\\}$.

Then, $(\Sigma\_{bool})^\*$ is the set of all binary strings, as far as I know. I've seen many posts claiming this set is uncountable. But how is that possible? If I sort the elements by length and then lexicographically, I get an ordering. Ordering of a set is, by definition, a bijection to a subset of natural numbers.

I would get:

| $\Sigma\_{bool}$ | $\mathbb{N}$ |
| --- | --- |
| 0 | 0 |
| 1 | 1 |
| 00 | 2 |
| 01 | 3 |
| 10 | 4 |
| 11 | 5 |
| 000 | 6 |
| 001 | 7 |
| ... | ... |

This post claims that it matters if the strings are of infinite length - why does it matter? I don't see it, can you please explain?

# Answer
> 1 votes
Ok more theoretic proof here

### If you are only looking at finite strings

by definition $$\Sigma\_{bool}^\* = \bigcup\_{i \in \mathbb{N}} \Sigma\_{bool}^i$$

(where $\Sigma\_{bool}^i$ is the set of strings of length $i$)

$\Sigma\_{bool}^i$ is finite, therefore countable. So this is a countable union of countable sets, and therefore countable.

### If you are looking at infinite strings

Your set is actually the set of sequences on $\Sigma\_{bool}$ or equivalently, the set of mappings from $\mathbb{N}$ to $\Sigma\_{bool}$.

$$\Sigma\_{bool}^{\mathbb{N}}$$

It is bijective to the powerset of $\mathbb{N}$

This is not countbale because of Cantor's theorem

# Answer
> 2 votes
Suppose you have the set of all the *infinite binary strings* (i.e. $\Sigma^{\omega}$), then whatever enumeration $E = (s\_1, s\_2, s\_3, ... )$ you build for them you can build a string $s'$ that is not in $E$ using a simple diagonalization argument:

$s'\[i\] = 1 - s\_i\[i\]$, $i \geq 1$

where $s\_i\[i\]$ is the $i$-th digit of $s\_i$.

$s'$ (which has infinite length) is different from any (infinite) string in $E$.

If you only consider the set of all *finite binary strings*, the enumeration you wrote in the question is enough to prove that it is countable.

---
Tags: binary, uncountability, ordering
---


# Question
Title: Prove that { $\langle M \rangle$ : $M$ is a TM and $L(M)$ is decidable} is undecidable
So I want to prove that $$ \big\\{\langle M \rangle : \text{ M is a TM and } L(M) \text{ is decidable} \big\\}$$ is undecidable.
To do so I want to reduce it from$\ \overline{A\_{TM}}$ with a function which looks like this :
On input $\langle M,w \rangle$ run $M$ on $w$, if $M$ accepts $w$ output $M'$ where $M'$ should be a TM for an undecidable language.
Furthermore the function loops if $M$ does not accept $w$ such that if $M$ reject $w$, $M'$ loops on every input.
Hence if $\langle M,w \rangle \in \overline{A\_{TM}}$, $M$ rejects $w$ and $L(M') = \emptyset$ which is decidable.
My problem is when $\langle M,w \rangle \in A\_{TM}$ and I want to output a TM $M'$ such that $L(M')$ is undecidable but I don't know how to create such a TM.

# Answer
> 1 votes
Maybe try to use Rice' theorem, instead of reducing from $\overline{A\_{TM}}$.

# Answer
> 1 votes
I finally understood what was blocking me.
We only need a TM that **recognizes** an undecidable language so we just have to take a TM $M'$ that recognizes $A\_{TM}$ for example and return it when $M$ accepts $w$.
We have $L(M') = A\_{TM}$ which is undecidable.

---
Tags: complexity-theory, turing-machines, decidability
---


title: Time Complexity of Logarithmic For loop

text:
# Question
Title: Time Complexity of Logarithmic For loop
Say I have a `for` loop like this

```
for(int i=1;i<n;i=i*2)
{
    for(int j=1;j<i;j=j*2)
    {
         cout<<"hello";
    }
}

```

What is the time complexity of this loop?

I have approached this problem like this. The outer loop runs `log(n)` times and the inner loop runs `log(i)` times, so in total the complexity becomes $O(log(log(n)))$

Whereas, my friend has approached it like this. The outer loop is running,

$i=2^0$+$2^1$+$2^2$+$2^3$.... $2^{log(n)}$

times and since the inner loop is running `log(i)` times, so the total time complexity we have is

$TC=0+1+2+3...log(n)= O( (log(n))^2 )$

Which of these two is correct $O(log(log(n)))$ or $O( (log(n))^2 )$ ?

# Answer
> 6 votes
Our approach is to finding a recursive formula for the time complexity of the code. For each value of $i$, the inner loop runs $\log i$ times.

Suppose $T(n)$ is time complexity of given code, so: $$T(n)=T(\frac{n}{2})+\log n$$.

At each step we have a $\log i$ cost for inner loop, and outer loop divide our $n$ by $2$. So we get above $T(n)$ that after solving by any known method (suppose $n=2^k$): $$T(n)=\sum\_{i=1}^{\log n}\log\frac{n}{2^i}$$ $$=\sum\_{i=1}^{\log n}(\log n-i)=\sum\_{i=1}^{\log n}i=O(\log^2n)$$ As a result: $$T(n)=O(\log^2n)$$

# Answer
> 2 votes
When you are working on loops like these you can simplify them with sums to count the number of iterations:
For example the time it takes on this loop

```
for(int i=1;i<n;i=i*2)
{
   cout<<"hello";
}

```

Can be rewritten as $\sum\_{i=1}^{\log(n)}{c}$, where $c$ is the constant time for printing "hello".
Hence your double loop can be rewritten as $$\sum\_{i=1}^{\log\_2(n)}{\sum\_{j=1}^{\log\_2(2^i)}{c}} = \sum\_{i=1}^{\log\_2(n)}{ci} = \frac{c}{2}\log\_2(n)(\log\_2(n)+1) = O(\log\_2^2(n))$$

# Answer
> -1 votes
What this code does and what you think it does are not the same thing.

The outer loop doesn't iterate at all if n \<= 0, and runs forever if n \> 0. The inner loop will never iterate at all. That's all because i and j will be zero forever.

If you start the loops with i = 1, j = 1, then the code still doesn't do what you think it does, and if n \>= 3 then the inner loop will run forever when it's run the second time, since j never gets a value different from 1.

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Prove that the Language $L=\{code(M)\;|\;L(M)\; \text{is closed under reversal}\}$ is undecideable
I want to solve this problem using Many-One-Reduction, which involves, if I understood it correctly, reducing another problem on the problem stated in the title, i.e. $$ H \leq\_M L $$

I would try reducing the Halting problem $H$ onto $L$, because we know that $H$ is not decideable. Would this be the correct approach? If so, what would be next step and if not, which approach would be superior?

# Answer
Your approach is in the right direction. You can indeed reduce the halting problem to this problem.

Big hint: For some TM $M$ and input $w$, construct $M\_w$ that ignores its input and simulates $M$ on $w$, and accepts if $M$ halted. Fix some non-palindrome word of your choice, like the word $10$, and consider $L(M\_w)\cup\\{10\\}$. What can you say about it?
> 1 votes

---
Tags: reductions
---


# Question
Title: What's the difference between a protocol and a distributed algorithm?
What's the difference between a protocol and a distributed algorithm? My internship supervisor told me they are not exactly alike.

A protocol is more communication-oriented (e.g. TCP), whereas a distributed algorithm allows more complex interactions (e.g. a cryptocurrency system).

However, I still can't fully grasp this difference. Can someone enlighten me? Is it important to not conflate the two?

# Answer
A protocol and a distributed algorithm are completely different things.

A protocol is defined mechanism for communication that the communicating parties use to exchange information. It is the rules of the language used to carry the information.

An algorithm is a recipe for solving a problem that is made of a sequence of steps to follow that will lead to a solution.

A distributed algorithm is a recipe that uses many parties to contribute to the solution of the problem.

In a distributed algorithm the different parties may need to communicate either with each other or back to some central location where the solution is collected. They will use a communication protocol to achieve that transfer of information, so a distributed algorithm is very likely to use a protocol, but that is not the sole purpose of the protocol and that protocol can be used for many other things besides distributed algorithms.

It is very important not to conflate the two, in the same way that it is essential not to confuse chalk with cheese, otherwise it would be bad for the recipe.
> 2 votes

---
Tags: algorithms, distributed-systems, protocols
---


# Question
Title: Show that $L = \{1^n w 1^n | n > 0 \text{ and } w ∈ \{0,1\}^*\}$ is regular
> Show that the following language $L$ is regular by describing it using a regular expression. $$L = \\{1^n w 1^n \mid n \> 0 \text{ and }w ∈ \\{0,1\\}^\*\\} $$

**My (apparently incorrect) answer:**

Given $w ∈ \\{0,1\\}^\*$ , we can rewrite $L$ as: $1^n(0\cup1)^\*1^n\ for\ n ≥ 0$

However, since the language specifies that the number of leading and trailing $1$s must be the same - this language is not regular.

**My justification:**

1. For every regular language, there is (by definition) a finite automaton that accepts that language
2. The given language $L$ requires an equivalent count of leading and trailing $1$s
3. Finite automata are not capable of maintaining a count.

Since no finite automata can accept the language $L$, $L$ is not regular.

**Can anyone explain to me why this language *is* regular?** I'm completely stumped. I can see that it could be pumped using the Pumping Lemma (thereby proving regularity), but my brain just refuses to recognize that an FSM could accept this language.

# Answer
> 2 votes
Believe it or not the language $L$ is equivalent to:

$L' = 1(0 \cup 1)^\*1$ which is regular

Proof:

Given $x \in L'$, then $x=1^1w1^1$ with $w \in (0 \cup 1)^\*$, so $x \in L$ (just take $n=1$)

Given $x \in L$, then $x = 1^n w 1^n = 1 (1^{n-1}w1^{n-1}) 1$ which is always possible because $n \> 0$; but $(1^{n-1}w1^{n-1}) \in (0 \cup 1)^\*$ so $x \in L'$

so $L = L'$

To prove $L'$ is regular jus note that it is the concatenation of three trivial regular languages:

$L\_1 = \\{ 1 \\}$, $L\_2= \\{ (0 \cup 1)^\* \\}$, $L\_3 = \\{1\\}$

$L' = L\_1 \cdot L\_2 \cdot L\_3$

And regular languages are closed under concatenation.

# Answer
> 3 votes
My answer is just a hint. The following pattern should lead you to the right answer:

These strings belong to the language:
$w = 11 \Rightarrow 1^1\epsilon 1^1, n=1$
$w = 1011 \Rightarrow 1^1(01) 1^1, n=1$
$w = 11011 \Rightarrow 1^1(101) 1^1, n=1$ or $1^2(0) 1^2, n=2$
$w = 1001011 \Rightarrow 1^1(00101) 1^1, n=1$
$w = 11111 \Rightarrow 1^1(111) 1^1, n=1$ or $1^2(1) 1^2, n=2$
$w = 101010011 \Rightarrow 1^1 (0101001) 1^1, n=1$
$\cdots$
Finally, if $w=1^nw 1^n$ then it can be written as $1v1$, where $w,v \in (0+1)^\*$, i.e. 1Σ\*1.

These strings DO NOT belong to the language:
$w=0$
$w=01$
$w=100$
$w=0000$
$w=0001$
$w=1000010$
$\cdots$

Yo may want to look at the first and the last symbols of each string.

# Answer
> 2 votes
Let $x=1^kw1^k\in L$ (with $n=k$).
Then, define $w':=1^{k-1}w1^{k-1}$, and we will have $x=1w'1\in L$ (with $n=1$).

Try to use this trick to "remove" the $n$ in the question. After "removing" it, constructing a finite state machine is easy.

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


title: Does ⌊1/⌋∈Θ(1/) or to Ω(log)

text:
# Question
Title: Does ⌊1/⌋∈Θ(1/) or to Ω(log)
⌊1/⌋ - represents the floor function Does the floor or ceiling function affect the complexity under which a function falls?

```
⌊1/⌋∈Θ(1/) or to Ω(log)

```

Found this interesting question in a Cornell paper

Thanks

# Answer
> 1 votes
Neither of those. For $n\>1$, $\lfloor\frac{1}{n}\rfloor=0$. Hence, $\lfloor\frac{1}{n}\rfloor=0=O(0)$.

Also, you can easily rule out $\Omega(\log(n))$ since $\log$ is an increasing to infinity, while $\frac{1}{n}$ is a decreasing function.

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


# Question
Title: Optimal online algorithm to guess the tree
I have a tree on $n$ vertices. Your goal is to find the adjacency list for it.

$n$ is known to you from the start. You can pick a vertex and ask for the lengths of the shortests paths from it to the other $n-1$ vertices (i.e. you input an integer $1\leq i \leq n$ and get $n-1$ integers $1\leq d \leq n-1$). The lengths are listed in the order consistent with the enumeration of the vertices.

What is the algorithm using as few queries as possible (without making any additional assumptions about the tree)?

After the first query you can bipartition of the tree by the parity of the shortest path so $\lceil \frac{n}{2} \rceil$ queries are always sufficient. An algorithm that keeps adapting after each query might do better.

# Answer
> 1 votes
You may indeed find some improvements, like :

* never query on a vertex, you know to be a leaf.
* guess some distant edges.

But this does not change the worst case for a totally unknown tree which is indeed $n/2$ as you guessed. Just imagine this tree:

* one root vertex with edges to $N$ other vertices.
* each of these $N$ vertices has one (and only one) additional edge to a leaf vertex. this tree has a $2 \times N + 1$ vertices.

And even if you identify quickly the pattern, you still have to query once per "branch", thus $N$ times.

---
Tags: algorithms, graphs, trees, online-algorithms
---


# Question
Title: How to arrange a sub-array for Quick sorting algorithm?
Alghorithm : Quick sort .

idea : devide and conqure .

steps : 1- find the pivot point from array like first element . 2- partiotioning the array so that elements are smaller than pivot point are in the left side and ones are bigger in the right side . **3- sorting both sub arrays (recursion)**

Question : i know all of the steps but i don't know how to sorting sub arrays in step 3 . i can't find any example that explains this ending part .

Example :

if you look at this you see that both sub arrays are unsorted and we should complete steps with recursion method to solve this and this is my question .

but can you explian this for me ?

# Answer
> 0 votes
The conceptually simplest way is to simply use the same algorithm recursively to sort the sub arrays; hence why it's labeled as recursion. As long as the base cases for very small arrays are correctly defined, this will yield a correct result.

As an example, let's Quicksort some alphabet, using first symbol as pivot:

```
sort(FHDEBACG) -> sort(DEBAC) F sort(HG)

```

Then, we recursively sort `DEBAC` and `HG`. I'll demonstrate with the former:

```
sort(DEBAC) -> sort(BAC) D sort(E) -> sort(BAC) D E
sort(BAC)   -> sort(A) B sort (C) -> A B C

```

thereby getting the desired result:

```
sort(DEBAC) -> A B C D E

```

In practice, Quicksort implementations are often modified to sort small enough (sub-)arrays with Insertion Sort, which usually exhibits superior performance for sufficiently small input arrays. Arrays and sub-arrays larger than this are sorted, as above, usually by recursively applying the same algorithm.

---
Tags: quicksort
---


# Question
Title: Time Complexity Analysis of a Minimum Bottleneck Tree Algorithm
The following is the solution to an exercise in the book CLRS.

The question: Give a linear-time algorithm that given a graph G and an integer b, determines whether the value of the bottleneck spanning tree is at most b.

The algorithm:

To do this, we first process the entire graph, and remove any edges that have weight greater than b. If the remaining graph is connected, we can just arbitrarily select any tree in it, and it will be a bottleneck spanning tree of weight at most b. Testing connectivity of a graph can be done in linear time by running a breadth first search and then making sure that no vertices remain white at the end.

I don't understand why the following algorithm runs in linear time. Creating a minimum spanning tree out of a graph takes at least m\*log n with Prim or Kruskal (which are the only algorithms on the topic discussed in the book at that point). So does the time to create the spanning tree not count because of the phrasing of the question, and if so is there a linear time algorithm to solve this problem even taking into account the time for making a minimum spanning tree?

# Answer
> 1 votes
Nobody said anything about a minimum spanning tree. Since you are looking for a bottleneck spanning tree with cost $b$, you only need a tree with edges that have weight $\le b$. You can construct such a tree using $BFS$ for example, and you don't need $Kruskal$ or $Prim$ to compute it (also, they compute the *standard* minimal spanning tree, not the minimal bottleneck spanning tree).

---
Tags: minimum-spanning-tree
---


# Question
Title: Efficient structure for pruning on job scheduling
This is an issue I encountered on several applications with different variants. But here is the common base for which I suspect to miss a more efficient approach.

There are $K$ different tasks to schedule on something (a product, some data, whatever...). Any order of actions is acceptable, but the cost (in time for exemple) of a task may be estimated with a complex function depending on the task and the combination of tasks already realized. The goal is to minimize the cost to achieve all tasks completion.

I use a bit array to keep track of the realized tasks (1=completed, 0=to do) and then explore the different paths with Dijkstra algorithm if $K$ is reasonable enough to look for optimal solution else with some heuristic variant. A state is a total cost and a task bit array.

Each time a new state is explored, one has to decide to eventually prune it. My idea is that if any other cheaper explored state (previously explored state using Dijkstra algorithm) has a greater task completion, it may be pruned. By greater, I mean that any task completed in the former is done in the latter. Using bitwise operations on two task bit arrays $A$ and $B$, it means: $A \ge B \implies A \\& B = B$
Note that this is not an ordering, there is no way to compare for exemple $0011$ and $0110$.

But of course, it is not efficient to test every previously explored state at every new one. The best solution I found until now, is to keep a list $L$ of previous states to compare to. When a new state $A$ is explored, I compare it to every state $S$ of $L$ :

* if $S \ge A$, $A$ is pruned (stop looping)
* else if $S \le A$, A replaces $S$ in $L$ and is accepted (stop looping)

if I reach the end of the loop without filling one of these two conditions, I append $A$ to $L$ and accept it.

But I feel that there is a more efficient structure for explored states. Any idea ?

# Answer
> 2 votes
If you don't assume anything more about the "complex function" that returns the cost of a task, then in the worst case you will be forced to explore $\binom{n}{n/2}$ subsets of tasks.

Consider the following game for sake of argument. I play the role of the adversary (I decide the complex function) and you play the scheduler. I (hidden from you) select a special set S of $n/2$ tasks. As long as you ask what is the cost of a task, I will return 0 for the first $n/2 - 1$ tasks. Then when you get to the $n/2$ task, I will return 0 if and only if the set of tasks you selected so far is exactly S, and otherwise I return a large value $M$. Since there is no way for you to find out any information about S until you selected $n/2$ elements, all you can do is try all possible subsets of $n/2$ tasks.

---
Tags: np-complete, scheduling
---


# Question
Title: First-order logic - Does there exist a sentence that is satisfiable by all infinite models and only by them?
> Prove or Disprove:
> There is $\boldsymbol{no}$ alphabet $\Sigma$ and closed formula (no free variables) $\varphi$ above $\Sigma$, such that for any Model $M$ it holds that $M\models\varphi\iff\\,|D^M|=\infty$.

I'm not sure what is the classic way to approach this. I do think that the statement is correct. I tried the next proof:
Assume by contradiction that there exist $\Sigma,\\,\varphi$ as mention above. So it also holds that for any model $M$:
$M\models\neg\varphi\iff\\,|D^M|\<\infty$
Let $M$ be a model for $\Sigma$ such that $D^M=\\{1,...,n\\}$ and $M$ defines functions and relations in $\Sigma$ arbitrary.
$M$ domain is of finite size so we have $M\models \neg\varphi$
Define $M'$ to be an expansion of $M$:$\\,\\,$ $D^{M'}=\mathbb{N}$, and for every $k\in\mathbb{N}$,$\\,\\,\\,M'$ treats $k$ the same way $M$ treats $k\\,\\,mod\\,\\,n$.
Then I proved by induction on $\varphi$'s structure that:
$M\models\neg\varphi$ $\iff$ $M'\models\neg\varphi$
and becuase we know that $M\models\neg\varphi$ we have $M'\models\neg\varphi$ which is contradiction, becuase $M'$ domain is of infinite size.
Is my proof correct? Or should I build additional model $N$, of finite domain, isomorphic to $M'$, and show with $N$ the contradiction?
Is there a better known way to prove this? Sometimes there are claims that there is a classic way to prove / disprove, I wonder if in this case as well.

Would appreciate help! :-)

# Answer
> 2 votes
Probably the easiest way to prove this is using the compactness theorem: assume for contradiction that $\varphi$ is such a sentence. For every $n\in\mathbb N$, let $E\_n$ denote the sentence $\exists x\_1,\dots,x\_n\bigwedge\_{i\<j}x\_i\ne x\_j$, which asserts that there are at least $n$ elements. Since every finite subset of $S=\\{\neg \varphi\\}\cup\\{E\_n:n \in \mathbb N\\}$ is true in a sufficiently large finite structure, $S$ is consistent by the compactness theorem. But a model $M\models S$ is an infinite structure that does not satisfy $\varphi$, a contradiction.

---
Tags: first-order-logic, predicate-logic
---


# Question
Title: Is a constant literal an example of a built-in?
My understanding is that in a programming language, *built-ins* are bindings that exist without the user having to make them. (Like `+` to its referent, for example.)

My understanding of a *constant literal* is that it is a variable whose name encodes its value. (Like `3`, or `{"Name": "Steve", "age": 47}` in JS.

Is a constant literal considered a type of built-in?

# Answer
> 2 votes
A literal is not a variable. See https://en.wikipedia.org/wiki/Literal\_(computer\_programming).

I wouldn't consider a literal a "built-in", but I'm not familiar with a precise formal definition of "built-in".

---
Tags: terminology, programming-languages, language-design
---


title: Is whole OS copied to ram when running?

text:
# Question
Title: Is whole OS copied to ram when running?
If so, for any OS more than 10gb, how does it run on a computer with limited ram like 4gb? If not, which part of OS is copied to the ram? Or is it dynamically loaded whenever certain part is needed?

# Answer
> 3 votes
Operating systems are typically made of multiple parts. Typically, one of these parts, the kernel, is loaded into RAM when the OS starts, and never unloaded. Other parts of the OS are loaded when needed and unloaded when not needed.

The exact mechanisms are very dependent on the operating system. OSes that include gigabytes of code typically consist of hundreds or thousands of programs with specific purposes. For example, there might be a program to copy files (no need to load it unless a file is being copied), a program to play sounds (no need to load it unless sound is being played), a program to configure the network firewall (no need to load it except when reconfiguring the firewall), etc. Not only are those programs only loaded to RAM when they're executed, but such large OSes typically only load the parts of the program code that is actually needed. They rely on a the processor's memory management unit to load and unload individual pages from disk to RAM. Smaller operating systems running on platforms without an MMU can use overlays to load and unload parts of a program as needed (usually, with overlays, the program itself takes care of managing its own optional components).

Some embedded operating systems consist of a single executable image which is fully loaded into RAM when the OS starts. This can encompass more than the kernel, depending on the OS architecture: when the OS has different parts running at different privilege levels, the kernel is just the part that runs at the highest privilege level, but the part that's permanently in memory can be more than the kernel. In larger OSes, the part that's permanently in memory can also be less than the kernel; for example, on Linux, most device drivers are part of the kernel but there is a mechanism for loading and unloading them.

---
Tags: operating-systems
---


# Question
Title: Number of unique values in array in $\theta(n)$ average expected time
My idea is to initialize a hash table (with chaining) with $n$ cells, having load factor $\alpha = 1$ hence having $\theta(1)$ expected number of values in each cell in the hash table, then go cell by cell, sort it, count the number of distinct values and add them to a global variable holding the count and return it.

The problem is I'm using the constant load factor to reason that the sorting of each hash table cell in $\theta(1)$ on average. Not sure how to explain this reasoning or if it is legal.

How to show the runtime is $\theta(n)$ in average, or if it is not actually $\theta(n)$, how can we do it in this time?

# Answer
> 3 votes
Going through the entire hash table contents is usually considered a bad idea.

Instead, while you insert to the hash table, you can keep a counter of the number of unique elements you have seen so far. When you want to add a new element to the hash table, check if it already exists. If it doesn't, insert it and increase the counter.

I'm sure this approach is much more intuitive to why it works in $\Theta(n)$ average :)

---
Tags: sorting, randomized-algorithms, hash-tables
---


# Question
Title: Approximation of rational sequences via linear recurrences of small order
I wish to approximate a sequence of rational numbers using a linear recurrence of order $k$ for some small $k$ (preferably as small as possible). The Berlekamp-Massey algorithm solves the exact version of this problem, finding the optimal such $k$, and even the coefficients of the linear recurrence generating the sequence.

However, a sequence might have a shorter approximation than the exact solution if we allow some error. For example the sequence -1,0,-1.02,-2.05,-5,-12.03,-29 is well-approximated by the recurrence $a\_n = 2a\_{n-1} + a\_{n-2}$ to within a total error of $\varepsilon \leq 1$.

Is there an algorithm that, given a sequence of rational numbers, a target order $k$ and a target error bound $\varepsilon \> 0$, tells me whether there is a linear recurrence of order $\leq k$ that approximates the given sequence with a total (square / absolute / etc.) error less than $\varepsilon$, and if possible exhibits such a linear recurrence?

\[Note that this is a duplicate of this Mathematics SO question which has been unanswered since October 2020.\]

# Answer
> 3 votes
Your problem appears to be an instance of the following: given a $m \times k$ matrix $M$, does there exist a $k$-vector $x \in \mathbb{Z}^k$ such that $\\|Mx\\| \le \epsilon$. (Here $x$ represents the linear recurrence weights, and $M$ is derived from the sequence.) This is essentially an instance of a shortest vector problem, which appears to be NP-hard (depending on the norm). You might be able to find a reasonable approximation using LLL lattice reduction or similar methods.

I don't know if there are any methods that take advantage of the special structure of $M$ in your situation to do better than solving a general SVP problem. So, this is not a proof of hardness for your particular problem.

---
Tags: recurrence-relation, approximation
---


title: Ray tracing tree

text:
# Question
Title: Ray tracing tree
Let's suppose that we have a light source. Which of the following are correct for the tree of recursive ray-tracing (ray tree) that create when we make the colors for each pixel in the screen. Which of the following are correct:

a) if the scene contains one non-convex polyhedron (random shape and position) then we can't have a bound for the height of the tree in general. (Even the camera is outside of the object)

b) if the scene contains two convex polyhedrons then the height of the tree can be at most 2 independent of the position of the camera and the position of objects (the camera is outside two objects)

c) if the scene contains two non-convex polyhedrons (random shape and position) then we can't have a bound for the height of the tree in general. (Even the camera is outside of the object)

d) if the scene contains one convex polyhedron then the height of the tree can be at most 1 independent of the position of the camera and the position of objects (the camera is outside of the object)

e) if the scene contains one non-convex polyhedron then the height of the tree can be at most 1 independent of the position of the camera and the position of the object (the camera is outside of the object)

I am confused about the choice of polyhedrons (convex or non-convex), I can't understand the difference. The ray that inserts into an object from the front after we have polyhedrons always leave from the back?

Also, I don't understand how the camera inside or outside of objects can help to make the ray tree. If the camera is inside an object which the difference of been out of one?

# Answer
> 1 votes
Note: Questions like this may be a better fit on Computer Graphics SE.

I assume that you're talking about reflective surface interactions only, and are ignoring transmission, subsurface scattering, and other kinds of interaction like that. In which case, the outgoing ray of the interaction must always be within a hemisphere centred on the normal to the surface at the interaction point. That is what "reflective" means.

So if the object is convex and the incoming ray originates from outside the object, the outgoing ray cannot possibly intersect the *same* object.

This isn't true if the object is concave (since part of the object may be "visible" inside the hemisphere), or the incoming ray originates inside the object (an internal reflection is internal).

Did that answer your question?

---
Tags: computer-graphics
---


# Question
Title: Is there a way to find the correct element in the array for the given index x?
In quick sort, in each iteration we are able to find correct index for an element (i.e. pivot element).

Is there any algorithm to find correct element for a given index ?

Here, correct index of an element means the final index of the element which would appear after sorting the array.

Reference:

https://en.wikipedia.org/wiki/Quicksort

https://www.geeksforgeeks.org/quick-sort/

# Answer
Yes. This is exactly what a selection algorithm does. It can be done in linear time.
> 1 votes

---
Tags: algorithms, sorting, quicksort
---


# Question
Title: How B Tree guarantees self balancing property?
Let's say we have a b tree of order 4 and it has 3 levels. All nodes are completely filled. Now if we want to insert a key with maximum value ( than all keys present in the tree). For this, we have to go to the rightmost node at the last level. As this last level is also filled, now how can we proceed further as all the nodes are full. We cant do a split here. So we are left with creating a new node below the rightmost node. But this tree contradicts the balancing property. I want to know the intuition behind self-balancing nature.

# Answer
> 3 votes
That's not how insertion into a full B-tree works. You can read about this in detail in CLRS chapter 18, section 18.2.

In brief, when you want to insert you start at the root and work your way down to the appropriate leaf node, *splitting any full nodes you find on the way*. That way when you come to insert the new value you are guaranteed that the parent of the node where you do the insert isn't full. There is a special case when the root is full, when you create a new empty root as a parent to the old root, so that the old root can be split. This is the only time that the tree increases in height, and of course it causes every leaf to increase its depth by 1, maintaining the same-depth property.

---
Tags: b-tree
---


# Question
Title: Total bits required for a direct-mapped cache
I'm taking a course in computer architecture in which the main reference is the Computer Organization and Design by Patterson and Hennessy. I came across an example which I couldn't grasp its answer:

Example: how many total bits are required for a direct-mapped cache with 16 KiB of data and 4-word blocks, assuming a 32-bit address?

In the answer, it says "We know that 16 KiB is 4096 (2^12) words. With a block size of 4 words (2^2), there are 1024 (2^10) blocks".

But how do we know how many words would be 16 KiB?

And then it goes on and says the total bits are `(number of blocks) * (data (32 * 4) + tag and validation bits)`. why don't we count index or offset bits in total bits?

And finally, it says the number of tag bits is (32 - 10 - 2 -2). we have 10 bits for the index part, 2 bits for offset, what're the second 2 bits we are subtracting from 32?

Honestly, I think I have missed something when studying the textbook, or there are some assumptions I'm missing.

BTW the answer according to the textbook is 147 Kibibits (18.4 KiB).

# Answer
You have `16 kB = 16*1024 = 16384 bytes of data`. Since word has 4 bytes, this makes `16384 bytes / 4 bytes per word = 4096 words` . Block size is 4 words, that makes `4096 words/4 words per block = 1024 (2^10) blocks` . This means 10 bits are used for the index. The size of the tag field is (assuming 32-bit address) `32-(n+m+2)` where n is the number of bits used for the index, m is the number of bits used for the word within a block and 2 bits are used for the byte part of the address. So, in this example `total number of bits = number of blocks * (number of bits per block + tag size + validation bit) = 2^10 * (4*32 + (32-10-2-2) + 1)`.
> 1 votes

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


# Question
Title: Decide if the edges of a mixed graph can be directed in order to be an Eulerian Graph
I'm very stuck with this problem. Given $G = (V, E, A)$ a mixed graph where every edge in $E$ is directed and every edge in $A$ is undirected. Thinking as a max-flow problem, decide if it's possible to give a direction to every $a \in A$ in order to make $G$ an $eulerian$ graph.

The model I've thinking so far is to translate the problem as a matching problem. For every non directed edge, I would like to determine to which node this will point. For example, if $e=(u,v)$, from the vertex source there should be an edge connecting to $e$ and this one will be connected to $u$ and $v$. Every edge will have a flow capacity of 1, except for the edges of the target, which will have a capacity of $?$. I don't know if this model it's okay, but any clue (or another model) will help, thanks!

# Answer
> 3 votes
You want each node to have the same number of incoming and outgoing edges.

Let $\alpha(v)$ be the number of edges in $A$ outgoing in $v$ minus the number of edges in $A$ outgoing from $v$. Consider the graph $H=(V,E)$ and let $\delta(v)$ be the degree of $v$ in $H$.

We need to find an orientation of the edges in $H$ such that each vertex $v$ has an out-degree that is exactly its in-degree minus $\alpha(v)$. In other words, if $k$ is the number of edges in $E$ that need to be oriented towards $v$, we must have: $$ \delta(v) - k(v) = k(v) - \alpha(v), $$ equivalently: $$ k(v) = \frac{\delta(v) + \alpha(v)}{2}, $$ where we can assume that all $k(v)$s are non-negative integers and that $|E| = \sum\_{v \in V} k(v)$ (otherwise there is no feasible orientation).

Create a graph $H' = (\\{s,t\\} \cup E \cup V, F)$ where $F$ contains the following directed edges:

* All edges in $\\{s\\} \times E$ with capacity $1$;
* An edge $(v,t)$ with capacity $k(v)$ for each in $v \in V$.
* Two edges $(e, u)$ and $(e, v)$, both of capacity $1$, for each $e \in E$.

Now compute a max flow $f$ from $s$ to $t$ in $H'$ and check whether its value $|f|$ is exactly $\sum\_{v \in V} k(v)$.

If that's the case at least one valid orientation exists and it can be found by orienting $e = (u,v) \in E$ towards the unique endpoint $x \in \\{u,v\\}$ such that $f( \\, (e,x) \\, ) = 1$.

---
Tags: graphs, network-flow, eulerian-paths
---


# Question
Title: How to prove the same states are repeating in Synchronizable DFA?
I'm trying to prove the if $$ is a $$-state synchronizable DFA, then it has a synchronizing sequence of length at most $^3$. first I have to prove that if a string syncs two states, then its length is at most $k^2$.

The question was answered here.

> The proof of this a standard shrinking argument: if such a word is longer than $^2$, then during the runs from $\_1,\_2$, a pair of states repeats, and we can shrink $$.

But how to know if the repeating string in both paths from $\_1,\_2$ to some states like $q\_i$ is the same? and shrinking the string won't damage the synchronization?

To make it more clear I drew the below picture.

The string $abcd$ takes $\_1,\_2$ to $q\_i$ but after eliminating the loops, string $acd$ takes $\_1$ to $q\_i$ and string $abd$ takes $\_2$ to $q\_i$, thus removing the loops will break the synchronization.

Any suggestions would be greatly appreciated, thanks.

**Edit:** This is the visualisation I drew from Hendrik Jan's helpful answer:

Consider two arbitrary states $q\_1$ and $q\_2$ where $(q\_1, w)=(q\_2, w)=q\_i$.

Suppose $|w|=k,\ w=v\_1…v\_k$ then:  The loop happens when $((q\_1^j, q\_2^j),\ v\_{j+1})=(q\_1^i, q\_2^i)$.

# Answer
I am afraid that "a pair of states repeats" is a little ambiguous.

Both computations (from $q\_1$ and $q\_2$) have to be considered in parallel. So we get a pair of "synchronized" computations $(q\_1,q\_2), (q^1\_1,q^1\_2), (q^2\_1,q^2\_2), \dots, (q\_i,q\_i)$. If in such a sequence-pair a state-pair repeats we can remove the sequence in between (from both components).

That is also consistent with the $k^2$ bound, as that is the total number of state pairs.
> 3 votes

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


# Question
Title: Show that the Turing Reduction is transitive: if $A\leq_{T}B$ and $B\leq_{T}C$ then $A\leq_{T}C$
I am struggling with this question, because I came up with an relatively easy proof for mapping reduction:

if $A\leq\_{M}B$ and $B\leq\_{M}C$ then $A\leq\_{M}C$. We know that $w \in A$ $\Leftrightarrow$ $f(w) \in B$ and $w \in B$ $\Leftrightarrow$ $f(w) \in C$.

Let $h = g \circ f$. since $w \in A$ $\Leftrightarrow$ $f(w) \in B$ we can conclude that $f(w) \in B$ $\Leftrightarrow$ $g(f(w)) \in C$ $=$ $h(w) \in C$. Thus, we know that $A\leq\_{T}C$. Now this proof might be wrong, but the more important question for me is, is that proof applicable to

$A\leq\_{T}B$ and $B\leq\_{T}C$ then $A\leq\_{T}C$?

My intuition says no, and I am looking for a different approach. All I know is that a solution of $B$ is a subalgorithm in $A$ and a solution of $C$ is a subalgorithm in $B$. It seems logical that $A\leq\_{T}C$ holds aswell then, but this doesn't proof anything.

# Answer
> 1 votes
A Turing reduction from $A$ to $B$ is a Turing Machine $M$ with an oracle for $B$ that decides $A$.

Suppose that there is also a Turing reduction $M'$ from $B$ to $C$. We can get a Turing reduction from $A$ to $C$ (i.e., a Turing machine with an oracle for $C$ that decides $A$) by considering the Turing Machine obtained from $M$ by replacing each call to the oracle for $B$ with an execution of $M'$ (which decides $B$ given an oracle for $C$, which we have available).

---
Tags: turing-machines
---


# Question
Title: Is ANN a data structure or an algorithm?
When I read about Artificial Neural Networks (ANN), no one says what ANN is.

For instance, Wikipedia says:

> Artificial neural networks (ANNs), usually simply called neural networks (NNs), are **computing systems** vaguely inspired by the biological neural networks that constitute animal brains.

This is a vague definition. This definition begs question "What does it mean by a ***Computing System***?"

IBM's definition is as follows:

> Neural networks, also known as artificial neural networks (ANNs) or simulated neural networks (SNNs), are a subset of machine learning and are at the heart of deep learning algorithms. Their name and structure are inspired by the human brain, mimicking the way that biological neurons signal to one another.

This is also an unclear and vague definition. This is also a recursive definition that depends on the definition of machine learning.

So, my question is,

1. What is an ANN?
2. Is ANN a data structure or an algorithm?

# Answer
An "artificial neural network" is usually just referred to as "neural network" (NN) in the literature.

The term NN is used to describe a set of functions, that can be described by a parameter. Think of it like you would think of the function $f\_a(x)=ax$, it is a function that has a parameter $a$, and differs by different choices of $a$. For example, if $a=1$ then $f\_a(x)=x$ and if $a=5$ then $f\_a(x)=5x$. In the same sense, a neural network is a function with a vector-type parameter, usually denoted by $\theta$.

Hence, a NN is a function.

If you would like to know more about what exactly neural networks are, how they compute things, and how they can "learn" (and also see some real code demonstrating those abilities), then I can recommend you to read this (mini) book.
> 3 votes

---
Tags: neural-networks
---


title: Question about reduction Proof

text:
# Question
Title: Question about reduction Proof
I've recently seen a proof that the set of Turing machines $L = \\{encode(M) |L(M) \text{is closed under reversal}\\}$ is not decidable.

The proof used following idea: Reduce from the $A\_{TM}$ problem by taking input $\langle M, w \rangle$ and by constructing $M'$ such that $L(M') = \text{some language that is closed under reversal; if M accepts w}\\ L(M') = \text{some language that isn't closed under reversal}; \text{if M rejects w}$

Now, I have some confusion about this proof. I can see the contradiction because an algorithm for $L$ would solve $A\_{TM}$. However, how can you construct $M'$ in such a way? Wouldn't that require to already have solved $A\_{TM}$ to begin with? How would you notice that w is rejected or accepted without using $A\_{TM}$ and how would you build the Turing machine $M'$ based on that observation in more detail? I am quite confused about that. It seems contradictory to me, in a way. I hope someone can help me with that!

# Answer
> 0 votes
You are right. Its certainly hard (or not intuitive) to why its possible to do such a reduction, since it intuitively says that we know how to solve $A\_{TM}$. The key point lies in constructing $M'$ in such a way that we won't need to know beforehand if $M$ accepts or rejects $w$.

Since this question has been asked before, take a look at my answer for it

---
Tags: complexity-theory, formal-languages, turing-machines, reductions, mapreduce
---


# Question
Title: Under which circumstances a process in ready state can switch to exit without transition into any other intermediate state?
I was studying for an exam when I stumbled across this true or false statement:

> In a system of 7 states diagram, a process could switch from ready state to exit state directly.

The answer to this question was "True".

After some digging into books, I found this:

> Ready -\> Exit: For clarity, this transition is not shown on the state diagram. In some systems, a parent may terminate a child process at any time. Also, if a parent terminates, all child processes associated with that parent may be terminated.

That is an excerpt from Stallings 8th edition, page 119.

I don't understand how a process that never happens to execute is able to terminate. Could someone explain to me how is this done?

# Answer
Imagine you have the following code in the parent:

```
child = create_child()
terminate(child)

```

Now, lets say that the scheduler decided to let the parent run one line only. Then, the child is created, but is yet to execute any code (its in the `ready` state, as you called it).

Now, there are two options:

1. The scheduler decides to let the child run some code. In this case, the child goes through an "intermediate" state.
2. The scheduler decides to let the parent run another line of code. In this case, the child will be terminated, but it never ran any code (since the scheduler didn't let it to). So, in this case the child process directly transitioned from `ready` to `exit` without executing at all.
> 1 votes

---
Tags: scheduling, process-scheduling
---


# Question
Title: Avoid Storing Keys in Key-Value Store by Replacing the Key with 128-bit Murmur3 Hash
I want to develop LRU key-value data store and in that wanted to get rid of space to store the key itself. Instead wanted to store a 128 bit murmur hash. The structure of data-store that I want to explore is similar to CPU k-way set-associative caches.

So the algorithm I want to pursue is -

1. Compute a murmur 3 hash for given key.
2. Using the hash find the set where the data should be stored.
3. Let us say the cache is 4 way associative, therefore I have four slots where I can store the data.
4. If the slots are already full I kick out the one earliest used.
5. I store the hash in-place of key itself. But I understand that collisions are possible.
6. Banking on avalanche effect (this is risky and hence the question), I am assuming that if the two strings differ only by a little, the hash will be different. However, two 'largely' different strings may still collide.
7. Since the hash is of fixed size (128 bit) let us say, I can get rid of `memcmp()` of the whole key length, which is 256-byte long (max) in my system.
8. I store just the hash, and compare hash to the stored hash (which acts like TAG in the cache). In case the two strings collide, I also store few bytes (say 15-20 bytes) along with their offsets which needs to be compared only if hash values match.

Assumed benefit of this is -

1. no need to store keys and hence huge space can be saved
2. avoid `memcmp()` on full length of the key, and the hash which is calculated once is used both for matching keys and identifying slots.

I want evaluation and review of this method and if there are ways on we can solidify this. I understand that comparison of bytes at some offsets may not be the reliable way. Are there any other existing methods which avoid storing of keys?

# Answer
> 1 votes
I think this is a reasonable approach. To make it more solid, I suggest replacing Murmur3 with a cryptographic hash, such as SHA256. Then we get a kind of guarantee: it is believed to be intractable to find a collision for the hash function. In other words, for all engineering purposes, we expect you will never in your lifetime encounter a pair of inputs with the same SHA256 hash. So, you can ignore the risk of collisions. There's no need to store an extra 15-20 bytes -- just rely on the SHA256 hash. As a side benefit, the SHA256 hash is only 256 bits long, not 256 bytes, so it'll save you additional space.

---
Tags: data-structures, search-algorithms, hash
---


title: Iteration Vs Induction Method

text:
# Question
Title: Iteration Vs Induction Method
I am working on different methods to solve Recurrence Relations. I am using Iteration method and substitution method, which involves Induction, but I feel that sometimes Induction method creates a bit confusion, so I want to know that which of these two methods is more reliable?

# Answer
> 3 votes
I don't know what exactly you mean by the iteration method, but I think that this question has no definitive answer no matter what you mean by that.

The best method is the one that works, and that depends on the recurrence relation. After solving many of them you will get a sense of what can work in different cases. But you will still come across problems where you pretty much have to test all the methods you know to find one that works (and sometimes even that is not enough and you either get stuck or have to learn/figure out a new technique or new twist on a technique you already know).

---
Tags: algorithms, recurrence-relation, discrete-mathematics, iteration
---


# Question
Title: Loop Invariants: Can someone explain this concept?
I am reading Algorithms Unlocked By Tom Cormen and find this concept a little confusing.

Why is it that we require loop invariants and how does it help in analyzing algorithms?

# Answer
Loop invariants are crucial for showing an algorithm is correct (cf. proof by induction).

For example, suppose you need to sort an array of distinct integers. One simple way to do it is by using selection sort. Why is selection sort correct, i.e., why does it actually solve the problem? If we understand intuitively why the algorithm works, we can also formalize the loop invariant along the lines you mention: at every step, it holds that the subrange processed so far is sorted. So what happens at the end? The subrange equals the whole input range and not surprisingly, that subrange is now sorted as required of any solution for the problem.
> 1 votes

# Answer
We don't "require" loop invariants. They are a technique used when proving algorithm correctness.

Lets take a look at a simple example of how loop invariants are useful:

Consider the problem where we get an array $A$ and have to find the maximal value of it, i.e. compute $max(A)$.

We created the following algorithm for the problem, and we want to show that it indeed returns the maximal element in $A$.

```
cur_max = A[0]
for element in A:
    if element > cur_max:
        cur_max = element
return cur_max

```

Now, this code is simple. Our loop invariant in this case would be "At the $k$'th iteration, `cur_max` is the maximum value of all first $k$ elements in $A$".

Proving this loop invariant can be easily done in induction. But more importantly, what does this say to us when the loop is finished? It says that `cur_max` is the maximum value of **all** elements in $A$, hence we get the correctness of the algorithm.
> 1 votes

---
Tags: algorithms, programming-languages, loops
---


# Question
Title: non-existence of sentence that captured specific property
> For a sentence $\varphi$, we'll define $Spec(\varphi)$ to be the set of all $n\in\mathbb{N}$ for which there is a model $M$ with $|D^M|=n$, such that $M\models\varphi$.
> Let $\Sigma=\\{P(\cdot),R(\cdot)\\}$, where $P,\\,R\\,$ are relations.
> $\boldsymbol{Disprove:} $ There is a sentence $\psi$ above $\Sigma$ such that $Spec(\psi)=\\{n\\,|\\,n\in\mathbb{N}\_{odd} \\}$.

I have a disproof, but I wonder if part of it is unnecessary.
This is the disproof I have which got all the points (the question taken from an exam):
Assume by contradiction that such $\psi$ exists. Because $1$ is an odd number, there is a model $M$, with $|D^M|=1$ such that $M\models\psi$. Without loss of generality let $D^M=\\{a\\}$.
Define a new model, $M'$, such that: $D^{M'}=\\{a,b\\}$ and the next holds:
$\\{a\\}\in R^M \iff \\{a,b\\}\in R^{M'}$
$\\{a\\}\in P^M \iff \\{a,b\\}\in P^{M'}$
$M'$ is an expansion of $M$. We will define an equivalence relation, $\boldsymbol{\sim}$, with respect to the relations $P,R$. Namely, $\boldsymbol{\sim}$ will have four equivalance classes: as the number of options to be in $P$ or $R$.
By the way $M$ defines $P$ and $R$, there is only one equivalence class, which is: $\\{a,b\\}$. Let $\[\bar{a}\]$ be it's representor.
Now we will define an additional model, $N$, as follow: $D^N$ will contain the representatives of the equivalence classes of $\boldsymbol{\sim}$ with respect to $M$. $N$ will define the realtions $P$ and $R$ as follows:
$\\{a,b\\}\in R^{M'}\iff \\{\bar{a}\\}\in R^N$
$\\{a,b\\}\in P^{M'}\iff \\{\bar{a}\\}\in P^N$
So we actually have:
$M'\models\psi \iff N\models\psi$
From transitivity we have:
$\\{a\\}\in R^M \iff \\{\bar{a}\\}\in R^N$
$\\{a\\}\in R^M \iff \\{\bar{a}\\}\in P^N$
Namley $N$ is isomorphic to $M$, and becuase $M\models\psi$ we have due to isomorphism $N\models\psi$ which is contradiction, $|D^N|$ is an even number (2).

My question is: wasn't it sufficient to show that $M\models\psi \iff M'\models\psi\\,\\,$?
Or the whole reason for defining $N$ was because we can't show the above? I can't really understand what $N$ was needed for.

Would appreciate help!

# Answer
You are right that $N$ is used in this way. If you want a proof without $N$, you will have to prove in some other way (for example, by sentence induction) that $M'\models\psi$.

I understand you that it is very intuitive why $M'\models\psi$, but sadly formalism doesn't care about intuition, so we need a rigorous proof.
> 2 votes

---
Tags: first-order-logic
---


# Question
Title: What would be the big O notation for a function that attempts to find pairs of users that participate in different discussions?
Recently, I started to think of a problem involving the use of Twitter data that would involve finding pairs of users that participate in the most conversations. For example, with each tweet, you get the root conversation id along with a user id for that specific tweet. What I want to do is find pairs of users that participate in the same threads and also find the pair of users that have participated in the most threads (participation in a thread means that in one tweet, you would see a user id associated with the same conversation id as another user id.

This would involve first scanning every tweet (N) to fetch conversation, user id pairs. After doing this, I would have a list of user ids for each conversation id. I would then scan every user id association with each conversation id and then proceed to the next conversation id, scan each user id and compare against the previous list associated with previous conversation ids.

At the very least, I feel like the best method to do this would be, at a minimum, nlogn, but the method I'm proposing seems like it would make more comparisons than nlogn, but not as many as n^2.

How would I go about computing big O in this scenario?

Edit: I don't know if it is good form to edit one's question with a possible solution, but it appears you would need to scan each conversation (K) to get a list of tuples that associate users for that conversation (N^2-N)/2. You can then hash the tuple and increment the value of that dict key by one each time you discover the same tuple in another conversation. So ultimately you have to do (N^2-N) comparisons times K (each conversation). So the Big O would be larger than nlogn but not N^2. If I remember correctly, you drop the constants for big O so the running time would be somewhere around N^2-N * K (for each conversation). I'm not sure how to correctly form the big O here (what do you do with K?).

# Answer
> 2 votes
It might be nice to model the problem as a bipartite graph $(U, C, E)$ where $U$ is the set of users, $C$ is the set of conversations, and $E \subseteq U \times C$ are edges for participation.

In this setting, for each user, the set of other users that participate in the same conversations are its neighbors-of-neighbors. Let's make a new graph where each user is connected to its neighbors-of-neighbors. In the new graph, give each edge a weight which is the number of unique conversations in which those two users participate. ~~This can all be computed in O(|E|) because each edge in the new graph corresponds to two edges of the original.~~

In the new graph, look at the edge with the largest weight. The endpoints are the pair of users that converse the most with each other.

(I *think* this is approximately the algorithm that you had in mind. Using a bipartite graph makes things clearer.)

~~All together, that gives you O(|E|) for computing the result.~~ I don't think there's any other algorithm that can do better than $O(|E|)$ in the worst case.

**EDIT: this is too slow, because the new graph can be huge, much larger than |E|. See comments.**

# Answer
> 2 votes
It's a bit pedantic, but *problems* and *functions* don't have big-O representations, *algorithms* do. There are many algorithms that could implement the function you describe, and they have different big-O performance. It's confusing, because generally people want the fastest algorithm for a given problem, so you'll hear things like "sorting is n\*log(n)", which is not formally true.

The second thing to think about for your problem is "What does N represent?"

In a problem where there are several "sizes", it's perfectly reasonable to use different letters to represent different things. So let's say that there are N conversations and the longest one is M posts long.

An algorithm to generate your answer (ignoring a lot of details) could look something like:

```
# maps every pair to the number of conversations they've shared. e.g. "alice$bob" -> 10
pair_frequency = dict()
for convo in conversations:
  for tweet in convo:
    for other_tweet in convo:
      pair_frequency[tweet.userid + "$" + other_tweet.userid] += 1

# which pair is most frequent?
max = 0
max_pair = null
for pair, freq in pair_frequency:
  if freq > max:
    max = freq
    max_pair = pair
return max_pair

```

This algorithm is O(N * M^2), since, for each tweet in each conversation, it iterates over every other tweet in the conversation.

This might or might not be a good algorithm for you to actually use, but it's how I would start thinking about the problem in terms of big-O.

Something to think about - in reality, it's probably important to know the *average* number of tweets in a conversation, but for big-O analysis I chose M to be the length of the longest thread.

---
Tags: algorithms, big-o-notation
---


# Question
Title: Minimum number of groups such that every element in graph is included?
## Problem Description

**Note**: I originally posted this question on Stack Overflow but was referred to this community instead.

I have a graph containing *selectors* and *elements*. An element can have multiple selectors associated with it. As a graph, it looks something like this:

In the example, any node prefixed with an S is a selector and any node prefixed with an E is an element.

As you can see, elements can only connect with selectors. No elements will be connected with elements and no selectors will be connected to other selectors.

I want to **choose the minimum number of selectors such that their neighbors include every element in the graph**. In the above example, I would want my algorithm to return `S1, S3, S4`. *However, I don't need to return the groups that they represent. I only want the selectors* This is illustrated below:

In the example, we do not need to use the `S2` selector as it is redundant. Furthermore, even though `E1` occurs in both `S4` and `S1`, we still need to include `S4` because of the `E5` and `E6` nodes. In other words, these groups do not need to be exact covers and can overlap if necessary.

After some research, I've heard that this might be a version of the Dominating Set Problem. Maybe that helps?

## Possible Solution

Greedily, I could create an adjacency list of the selectors and the elements that are connected to them and select the selector with the largest elements. Then I could eliminate the elements from every other node's list and repeat the process until I have no elements left.

## What I'm Looking For

I would like to see if there is anything that is more efficient/elegant than this approach. Even if it ends up being NP-Complete or NP-Hard, I am sure that there is a better algorithm than the greedy approach that I outlined above.

I'm also open to suggestions about the different ways I could frame this problem or how I should title it so that it is more clear to other readers.

# Answer
> 4 votes
Your problem can be *equivalently* stated as a set cover problem. The universal set $U$ is composed of all elements $e\_1,\dotsc,e\_n$. For every node $s\_i$ define a subset $S\_i$ of $U$ that contains the elements it is connected to. For example: $S\_{1} = \\{e\_1,e\_2,e\_3\\}$ from the the example given in the question. Let $\mathcal{C}$ be the collection of all such subsets. Now, the task is to pick the minimum number of subsets whose union gives the set $U$.

The best possible polynomial-time algorithm for the set cover problem is the greedy algorithm only. It the same as the one you mentioned in your question. It gives $\Theta(\log n)$-approximation guarantee. Note that it is $\mathsf{NP}$-hard to approximate set cover with better than $\log n$ factor (see this). So this is the best possible approximation guarantee that you can achieve.

I know that the greedy algorithm is quite simple but that is the beauty.

---
Tags: graphs, group-theory, subgraphs
---


# Question
Title: Parts of a function used in Space Complexity
I'm finding contradictory information online where some places only consider auxiliary space and others define it as

> Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.

What parts of a function are used in space complexity? Does it include input, output, and auxiliary space?

For example, consider the following function:

```
vector<int> mult2(vector<int> nums)
{
    vector<int> result;

    for (int i=0; i < nums.size(); i++)
    {
        result.push_back(2*nums[i]);
    }

    return result;
}

```

Then the space complexity would be:

If $n$ is the size of input (nums), then there is nums and result of size $n$ each or $2n$. Along with constant auxiliary space for int i.

In other words, $O(2n+1)$ or $O(n)$, where $n$ is size of input (nums).

In the case of the input nums being passed by reference would it then not be counted in the space complexity?

**Edit** Seems the confusion is generally around if the input is included or not.

Example 2:

```
int sum(vector<int> nums)
{
    int sum = 0;

    for ( auto n : nums )
        sum += n;

    return sum;
}

```

Is the space complexity O(n) or O(1)?

# Answer
We usually don't count the input as part of the space used by a procedure.

In your case, however, this makes no difference, since $O(2n+1)$ and $O(n)$ are the same.

Whether you pass the vector as reference or not, what is copied is only a pointer to the underlying array. If, instead, the vector was passed by creating a fresh copy, then it would make sense to count it somewhere — possibly at the caller's expense rather than at the callee's expense. This is a convention which is up to you to decide.
> 3 votes

---
Tags: space-complexity
---