# Question
Title: Calculating CPU throughput on a single cycle vs multicycle datapath
When calculating the throughput of a CPU, how does it differ when it is implemented with a single cycle datapath versus a multicycle datapath? If for example the CPU is running 1 GHz freq, then obviously it would have 1,000,000,000 clock cycles per second...and in a single cycle, it takes 1 CPI. So what would be the throughput? And how would it be different in the multicycle datapath where clock cycles differ between instructions?

# Answer
Every instruction in a CPU goes through an **Instruction execution cycle**. In other words every instruction goes through multiple **stages** like Fetch,Decode,Execute,Writeresult. In modern processor the number of stages can go up to 20. So for single cycle instruction execution (all stages finish their work), the clock duration need to be large and hence the processor should operate at lower frequencies. CPI would be 1 and hence throughput is 1/F, where F is processors clock frequency.

But most modern processors use **pipelining**. They take advantage of the fact that each stage hardware is **different** and therefore multiple instructions can be at different stages of instruction execution cycle, at the same time. The clock frequency can be higher as amount of work being done (Max of all stage execution time) is smaller. The performance will be optimal if all stages of instruction execution cycle take equal amount of time. Hence a pipelined processor with n stage is able to provide a throughput of **one** instruction per cycle. CPI should be P where P is the number of pipeline stages. But often a pipeline get stalled and different types of instructions (integer,float, branch, load,store...) take different number of cycles to complete. Hence CPI will vary for each program depending on instruction mix.

Pipelined processor having **superscalar** execution capabilities are able to take advantage of the fact that there are multiple processing/execution hardware in a processor, e.g., Integer ALU, floating-point ALU, memory management unit. So taking advantage of this fact more than one instruction can be in its **execution stage** at the same time. To support this fetch and decode stages have the capability to read and process multiple instruction in parallel. They are then able to feed multiple instruction to the execute stage, and **more than one** instruction is then completed per cycle. CPI will be lower in this case, even going to a value **less than 1**. In other words more than one instruction is able to complete within a single cycle.
> 1 votes

---
Tags: cpu, performance, clocks
---


# Question
Title: Why is it not a good idea to branch a thread outside of a parallel region while other threads are still executing?
Say I have $n$ threads executing in a parallel region and one of them leaves the parallel region when others are still continuing to execute in the parallel region. Why this is a $BAD$ idea? For example you can consider this program.

```
$OMP PARALLEL IF(EXECUTE==true)

10 sum(id)=next(id)

30 result(id)=sum(id)*9.8
   if(converged(result(id)) goto 20
   go to 10

$SOMP END PARALLEL
   if(not_FINISHED) goto 30

20 print *,id

```

In this code we are branching out of the parallel region. I have read that its a $BAD$ idea to do so, but I have not got the reason. So it will be very helpful if someone can shed some light on this.

# Answer
OS functions are called to create and join a thread.

The main thread waits for all created thread to return (join). When a thread jump out in middle, the main thread will wait infinitely. In the example you have given one of the spawned thread jumps to a location in main thread. It will proceed and the program will eventually end. Any thread can exit/close the program. It may be the case that other spawned threads are in different stages of their execution and since parent (main) thread has exited, they will terminate inflight as well.

A lot of resources allocated to the abruptly terminated threads by OS, will waste. A properly terminated thread releases all the resources allocated to it properly, improperly terminated threads won't.
> 0 votes

---
Tags: parallel-computing, threads, high-performance-computing
---


title: Meaning of 'running time is $O(n^2)$'

text:
# Question
Title: Meaning of 'running time is $O(n^2)$'
I have a question from **Introduction to Algorithms** by CLRS,

> When we say "the running time is $O(n^2),$" we mean that there is a function $f(n)$ that is $O(n^2)$ such that for any values of $n$, no matter what particular input of size $n$ is chosen, the running time on the input is bounded from above by the *value of* $f(n)$.

What do the authors mean by saying there exists a function that is $O(n^2)$? Do they mean that this function is from the set $O(n^2)$? Is the last part which I highlighted correct? I think it must be "... from above by $O(n^2)$." I appreciate your answers.

# Answer
We say that a function $f(n)$ is $O(n^2)$ if there exist constants $C,N\>0$ such that $f(n) \leq Cn^2$ for all $n \geq N$. We usually denote "$f(n)$ is $O(n^2)$" by "$f(n) = O(n^2)$".

An algorithm has running time $O(n^2)$ if its *worst-case* running time is $O(n^2)$. That is, if we denote by $T(n)$ the maximum running time of the algorithm on inputs of length $n$, then the algorithm has running time $O(n^2)$ if $T(n) = O(n^2)$.

Equivalently (and this is the point of the CLRS formulation), an algorithm has running time $O(n^2)$ if there exists some function $f(n) = O(n^2)$ such that the running time of the algorithm on an input of length $n$ is always at most $f(n)$.

If we denote the running time of the algorithm on the input $x$ by $T(x)$, and the length of $x$ by $|x|$, then we can see the difference between these two equivalent definitions by writing them out formally.

The first definition is $$ \max\_{|x| = n} T(x) = O(n^2), $$ where the left-hand side defines a function of $n$, which we denoted above by $T(n)$.

The second definition states that for some $f(n) = O(n^2)$, $$ T(x) \leq f(|x|). $$

If the second definition holds, then in particular $$ \max\_{|x|=n} T(x) \leq f(n), $$ and so $$ \max\_{|x|=n} T(x) = O(n^2), $$ which is the first definition.

If the first definition holds, then we can take $f(n) = \max\_{|x|=n} T(x)$ to obtain a function satisfying the second definition: $$ T(x) \leq \max\_{|y|=|x|} T(y) = f(|x|), $$ where the first definition guarantees that $f(n) = O(n^2)$.
> 3 votes

# Answer
Having, for non negative case, formal definition $$O(f)=\\{g: \exists C\>0, \exists N \in \mathbb{N}, \forall n\>N, g(n) \leqslant Cf(n)\\}$$ then we of course are considering big-$O$ as set.

If some $g \in O(n^2)$, then words "the running time on the input is bounded from above by the $\text{value of f(n)}$" means, as it is in definition, existence some $N\_g, C\_g$ such that $g(n) \leqslant C\_gn^2$ for $\forall n\>N\_g$.
> 2 votes

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


# Question
Title: Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$
Can someone enlighten me why a recursive descent parser with backtracking that tries the productions $S \rightarrow aSa$ and $S \rightarrow aa$ (in that order) does not recognize the language formed by the grammar $S \rightarrow aSa\ |\ aa$.

It appears to only parse words from the language $\\{a^{2^n}\ |\ n \ge 1 \\}$.

I generated such a parser using this ABNF Parser Generator with the production rule `S = "a" S "a" / "aa"` and the parser does not recognize the word `aaaaaa`, for example.

I would expect it to use the production $S \rightarrow aSa$ until the concatenation of the parse tree's terminal nodes from the left starts with 7 `a`'s, and then go up the parse tree choosing the production $S \rightarrow aa$ instead until the tree looks like this:

```
   S
 / | \
a  S  a
 / | \
a  S  a
  / \
 a   a

```

# Answer
It's actually a property of the "singleton match strategy" usual in naive implementations of recursive descent parsers with backtracking.

I'll quote this answer by Dr Adrian Johnstone:

> The trick here is to realise that many backtracking parsers use what we call a singleton match strategy, in which as soon as the parse function for a rule finds a match, it returns. In general, parse functions need to return a set of putative matches. Just try working it through, and you'll see that a singelton match parser misses some of the possible derivations.

Also, this image available in this answer on StackOverflow will help to visualize what's happening in the case you exemplified:
> 3 votes

# Answer
This is not much of an answer, but the parse trees do not fit the normal comments.

Your grammar $S \rightarrow aSa\ |\ aa$ should parse the string $aaaaaa$.

But the parse tree has the following form:

```
      S
     /|\
    / S \
   / /|\ \
  / / S \ \
 / / / \ \ \
a a a   a a a

```

or if you prefer this presentation, with the terminals on different lines

```
     S
   / | \
  a  S  a
   / | \
  a  S  a
    / \
   a   a

```

I checked that the ABNF parser generator does not seem to work, but I do not know how to trace what it does.

It indeed seems to recongnize the set $\\{a^{2^n}\ |\ n \ge 1 \\}$ wich is not what the grammar defines.

It is a bit surprising to have such an elaborate site around a buggy parser, which furthermore uses a totally uninteresting parsing technique.

---

After a further look at it:

I think I found one source of the problem. The square brackets mean *optional*.

So your grammar should be written either `S = "a" S "a" / "aa"` or `S = "a" [S] "a"`. Then it seems to work correctly.

But the system is apparently lost when having twice the same rule in different forms. I am not sure why.

I did not find a page explaining these syntactic issues for specifying the grammar.

I still consider that buggy.
> 6 votes

# Answer
I wrote a very simple implementation of this parser in C++ (see below), and it has the same issue. This seems to be because whenever the function `s1()` for the production $S \rightarrow aSa$ returns `true`, `s()` will immediately return and never try `s2()` (the function implementing $S \rightarrow aa$) for that node of the parse tree.

Consider parsing the word `aaaaaa` again. At one point, the parse tree will look like this:

```
   S
 / | \
a  S  a
 / | \
a  S  a    <--
 / | \
a  S  a
  / \
 a   a

```

Then, `s()` will return `true` for the `S`-node at the 3rd level and the production $S \rightarrow aa$ will never be considered here, but instead one level higher, resulting in:

```
   S
 / | \
a  S  a
  / \
 a   a

```

I tend to consider this an issue with my implementation and not with backtracking recursive descent parsers in general, though.

```
#include <iostream>

char* next;
bool term(char token) {
    if (*next != '\0')
        return *next++ == token;
    else
        return false;
}

bool s();
bool s1() {
    return term('a') && s() && term('a');
}
bool s2() {
    return term('a') && term('a');
}
bool s() {
    auto save = next;
    return s1() or (next = save, s2());
}

int main(int argc, char* argv[]) {
    next = "aaaaaa";
    if (s() && *next == '\0') {
        std::cout << "match";
    }
    else
        std::cout << "no match";
}

```
> 3 votes

# Answer
## **It is a feature not a bug**

Have a close look at when & where backtracking occurs:

```
     1.           2.          3.          4.          5.          6.          7.          8.          9.          10.         11.         12.

     S            S           S           S           S           S           S           S           S           S           S           S
   / | \        / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \
  a  S  a      a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a
                / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       /   \
               a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
                            / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \       / | \
                           a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a
                                        / | \       / | \       / | \       / | \       / | \       / | \       / | \       /   \
                                       a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
                                                    / | \       / | \       / | \       / | \       / | \       /   \
                                                   a  S  a     a  S  a     a  S  a     a  S  a     a  S  a     a     a
                                                                / | \       / | \       / | \       /   \
                                                               a  S  a     a  S  a     a  S  a     a     a
                                                                            / | \       /   \
                                                                           a  S  a     a     a

w[] = 'aaaaaa'  //input
l[] = ''        //current tree leafs

 1. tree:   The parser starts with the start symbol S and tries first alternative S->aSa:       Result: w[0]  = l[0]     w = aaaaaa    l = aSa
 |          -- S->aSa works                                                                         | |     | |
 6. tree:   The parser matches a after a:                                                       Result: w[6]  = l[6]     w = aaaaaa    l = aaaaaaSaaaaaa
 7. tree:   The parser tries S->aSa again but there is no match!                                Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaSaaaaaaa
 8. tree:   The parser tries S->aa but there is still no match!                                 Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaaaaaa
 9. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaaaa
10. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaaaa
11. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaaaaaa
12. tree:   Backtracking after the last symbol that matched => Backtracking at l[7]             Result: w[7] != l[7]     w = aaaaaa    l = aaaa

```

**The crucial point here is that the parser backtracks after the position, where the last matching character was found.** That's why it "jumps" from tree 11 with *l = aaaaaaaa* to the 12th tree with *l = aaaa* by using *S -\> aa* at l\[7\].
> 2 votes

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


# Question
Title: Can any computably enumerable set be generated by a prefix-free set?
Downey and Hirschfeldt seem to assume that any computably enumerable set of sequences can be generated from some prefix-free set (in the sense that the set of all extensions of the strings in the prefix-free set is equal to the first set). I don't understand why this would be so.

Specifically, in a proof that a sequence is Martin-Löf random iff is there is no c.e. martingale on the sequence that produces infinite profit, on page 236, D&H assume that for each class $U\_n$ that makes up a Martin-Löf test, there is a "prefix-free generator" $R\_n$ (which I take to be what I described above, cf. p. 4). D&H's definition of Martin-Löf test is on 231: the sequence of $U\_n$ is merely required to be uniformly c.e. s.t. $\mu(U\_n)\leq 2^{-n}$.

I don't understand why such a generator must always exist.

For example, let $U\_n$ be$\\{00000\ldots\\}$ for all $n$. Then each $U\_n$ is null with respect to the uniform measure, so this is a Martin-Löf test. However, any finite sequence of zeros that would include a sequence of all zeros as an extension, would also have extensions such as $01\ldots$, $001\ldots$, etc., which are not in $U\_n$. So there is no generator of $U\_n$.

Clearly I am misunderstanding something (or have not noticed some constraint on Martin-Löf tests?).

# Answer
After a lot of thinking and reading, and getting a helpful answer and comments from Andrej Bauer to another question that my investigation prompted, I can answer my own question.

Downey and Hirschfeldt prove (2.19.2, p. 74) that every $\Sigma^0\_1$ set of infinite sequences is one that can be generated by a c.e. set of finite strings. Moreover, they define Martin-Löf randomness in terms of a sequence of $\Sigma^0\_1$ sets $U\_n$ of infinite sequences. This is why they have the right to assume that every such $U\_n$ can be generated by such a set of finite strings.

In my gloss of D&H's description of a Martin-Löf test, I stated the requirement that the test sets be $\Sigma^0\_1$ as a requirement that they be computably enumerable. One can see the equivalence of $\Sigma^0\_1$ and c.e. as implied by D&H's proposition 2.19.2, but it's proved directly by, for example, Nies, 1.4.12, p. 22. So the way that I characterized D&H's description of Martin-Löf tests was correct.

While it's true that $U\_n=\\{000\ldots\\}$ can't be generated by finite strings, my mistake was thinking that such a $U\_n$ is computably enumerable. It was surprising to me to realize that such a trivially simple set is not c.e. After all, the set has only one element, and a Turing machine that generates it or checks for it is trivial. The crucial point, though, is that that machine cannot halt on $000\ldots$, since the sequence of zeros is infinite. No program can ever successfully list or accept even (the) one member of this set. Thus my sequence of sets $U\_n$ do not form a Martin-Löf test.

(It is possible to define a Martin-Löf test that excludes only $000\ldots$ from the random sequences, but that test has to consist of sets such as, for example, $U\_n=\\{x:$ the first $n$ digits of $x$ are 0$\\}$. Each such set contains an uncountably infinite number of infinite sequences, but each is a subset of previous sets $U\_1, U\_2, \ldots, U\_{n-1}$. The one sequence contained in each of them is $000\ldots$ .)
> 2 votes

---
Tags: turing-machines, computability
---


# Question
Title: Min path cover problem in Cormen et.al. question about notation
In the book on algorithms by Cormen et.al, the problem 26-2 describes how to obtain a min-path cover for a DAG via max-flow. I have a question about the notation. First, let me quote the problem here:

---

A path cover of a directed graph $G = (V, E)$ is a set $P$ of vertex-disjoint paths such that every vertex in $V$ is included in exactly one path in $P$. Paths may start and end anywhere, and they may be of any length, including $0$. A minimum path cover of $G$ is a path cover containing the fewest possible paths.

a. Give an efficient algorithm to find a minimum path cover of a directed acyclic graph $G =(V, E)$ (Hint: Assuming that $V = {1, 2, ... , n}$, construct the graph $G' = (V',E')$, where:

$$V' = \\{x\_0,x\_1,\dots x\_n\\} \cup \\{y\_0, y\_1, \dots y\_n\\} $$ $$E'=\\{(x\_0,x\_i):i \in V\\} \cup \\{(y\_i,y\_0) : i \in V\\} \cup \\{(x\_i,y\_i):(i,j) \in E\\}$$ and run a maximum-flow algorithm.)

---

What are the $x\_i$ and $y\_i$ here? Am I missing something obvious?

# Answer
> 1 votes
The graph $G'$ has $2n+2$ vertices. We give them the names $x\_0,\ldots,x\_n,y\_0,\ldots,y\_n$ to make it easy to refer to them. So $x\_i,y\_i$ are just names of vertices. They have no value, and do not refer to anything. In that regard, they are akin to indeterminates.

What might be confusing you is the existence of a different graph $G$, which has $n$ vertices. The vertices $x\_i,y\_i$ are just vertices – they are *not* variables referring to vertices of $G$. The "value" of $x\_i$ is just $x\_i$.

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


title: derandomize a BPP algorithm

text:
# Question
Title: derandomize a BPP algorithm
Suppose we have a BPP algorithm $A$ s.t. its running time is random and is $O(n^2)$ in expectation. How do we create a new BPP algorithm $B$ to solve the same problem s.t. it has deterministic running time $O(n^2)$?

My effort: Denote the running time of $A$ as $T$. Suppose $E(T)\leq T(n)=O(n^2)$.

1. Run $A$ at most $kT(n)$ steps.
2. If it terminates, return its output; otherwise, output Yes with probability $q$.

But I just proved that this cannot be a BPP algorithm for any $q$... Any hint please?

# Answer
Derandomization is the process in which a randomized algorithm is converted to an equivalent deterministic algorithm. This is *not* what this exercise is asking you to do. The algorithm $B$ is still randomized – only its running time is deterministic.

Suppose that $A$ decides the problem $L$, in the following sense: if $x \in L$ then $\Pr\[A(x) = 1\] \geq 2/3$, and if $x \notin L$ then $\Pr\[A(x) = 0\] \geq 2/3$. Moreover, there is a function $f(n) = O(n^2)$ such that the expected running time of $A$ on $x$ is always at most $f(|x|)$. We want to construct a new algorithm $B$ with the same behavior regarding to $L$, and with the following additional property: there is a function $g(n) = O(n^2)$ such that the running time of $B$ on $x$ is *exactly* $g(|x|)$.

Suppose that $f(n) = Cn^2$, and consider your solution with $K = 3C$ and $q=1/2$. If we're careful, then there will exist a function $g(n) = O(n^2)$ such that the running time of $B$ on $x$ is exactly $g(|x|)$. What about the other property?

Suppose that $x \in L$ has size $|x|=n$. The expected running time of $A$ on $x$ is at most $f(n) = Cn^2$, and so $A$ terminates within $Kn^2$ steps with probability $p \geq 2/3$. If this happens, the probability that $B$ outputs $1$ is at least $2/3$. Otherwise, the probability that $B$ outputs $1$ is $1/2$. In total, $$\Pr\[B(x) = 1\] \geq p \cdot \frac{2}{3} + (1-p) \cdot \frac{1}{2} = \frac{1}{2} + p \cdot \frac{1}{6} \geq \frac{1}{2} + \frac{2}{3} \cdot \frac{1}{6} = \frac{11}{18} \> \frac{1}{2}.$$ Similarly, if $x \notin L$ then $\Pr\[B(x) = 0\] \geq 11/18$. This is *almost* what we want – we want $11/18$ to be replaced by $2/3$.

In order to enhance the success probability ("error reduction"), we need to run $A$ several times and take a majority vote. By running $A$ enough times and by increasing the value of $K$, we get drive the error probability of $B$ down to any positive constant. Details left to you.
> 3 votes

---
Tags: randomized-algorithms
---


# Question
Title: Is persistence a property of a database?
I was having a discussion in another forum on this topic, and I couldn’t get a satisfactory answer. Originally, a statement was made that a redis data store couldn’t be considered a database because it’s not persisted to disk. I queried that, because I didn’t see why persistence is a required property of a database. I understand a database to simply be some structured/organised data.

So: is persistence a required property of a database, and why?

# Answer
> 3 votes
The databases I've seen are persistent. But rather than trying to figure out the "one true meaning" of the word database, if this aspect matters in a specific context, then I suggest you just be explicit about how you are using the word. That's probably best in any case if this is critical.

A rose by any other name would smell as sweet. (Shakespeare)

---
Tags: database-theory, databases
---


# Question
Title: Formal proof of language accepted by a specific CFG
Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules: \begin{align} &S \to aS \mid B \\ &B \to abBc \mid \epsilon \end{align}

Please provide a formal proof for the following claim: $$ L(G) = \\{ a^i (ab)^j c^j : i,j \in \mathbb{N} \\}. $$

# Answer
Let $L = \\{ a^i (ab)^j c^j : i,j \in \mathbb{N} \\}$. The proof consists of two steps:

* $L \subseteq L(G)$.
* $L(G) \subseteq L$.

The first step proceeds by direct construction: we show how to produce each word in $L$ using the grammar. In order to produce the word $a^i (ab)^j c^j$, we first apply $i$ times the rule $S \to aS$, then once the rule $S \to B$, then $j$ times the rule $B \to abBc$, then once the rule $B \to \epsilon$. Formally, we could prove that this works by induction.

For the second step, we first prove by induction that all words generated by $B$ are of the form $(ab)^jc^j$. We show that by induction on the length of a production starting at $B$. If the first step is $B \Rightarrow \epsilon$ then we generate $\epsilon$. Otherwise, the first step is $B \Rightarrow abBc$. By induction, the $B$ on the right produces a word of the form $(ab)^jc^j$, and overall the produced word is $(ab)^{j+1}c^{j+1}$, which is of the same form.

We can now prove the required claim by induction on the length of a production starting at $S$. If the first step is $S \Rightarrow B$, then the preceding paragraph shows that the generated word is of the form $(ab)^jc^j$. Otherwise, the first step is $S \Rightarrow aS$. By induction, the $S$ on the right generates a word of the form $a^i (ab)^j c^j$, and overall the produced word is $a^{i+1} (ab)^j c^j$, which is of the required form.
> 0 votes

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


# Question
Title: is the intersection of a context free language and a regular language a two way street?
I wasn't sure how to word it correctly, hence the 'two way street' in the title. My question is:

The intersection of a context-free language and a regular language always results in a context free language, but does this also mean that if I have a language L1 and a regular language L2 that when L1 intersected with L2 is context free that L1 is also context free?

# Answer
Your clam is false even in the special case where $L\_1 \cap L\_2$ is regular.

To construct a counterexample let $L\_1$ be a language that is not context free (e.g., $L\_1 = \\{a^n b^n c^n: n \ge 0\\}$) and pick $L\_2 =\emptyset$ (other choices for $L\_2$ work too).

Both $L\_2 = \emptyset$ and $L\_1 \cap L\_2 = \emptyset$ are regular (and hence also context-free), but $L\_1$ was chosen as a non-context free language.
> 3 votes

---
Tags: automata, regular-languages, context-free
---


# Question
Title: How difficult is this matching-like problem?
Let $A$ and $B$ be two sets of integers with $|A|\>|B|$. Given a map $f: A \rightarrow B$ and $i \in A, j \in B$, let us use the shorthand "$i$ is matched to $j$" if $f(i)=j$. I am looking to solve $$ \min\_{f: A \rightarrow B} \sum\_{j \in B} (\mbox{ number of nodes matched to } j)^2, $$ $$ \mbox{ subject to } |i-f(i)| \leq 2 \mbox{ for all } i \in A. $$

In other words, the function $f$ should not "move" any $i \in A$ too far and should come as close to a matching as possible.

Has something like this been studied before? If so, is it known to be NP-hard, or is there an obvious reduction? Are there any known variations on this (e.g., by changing the cost) that are polynomial-time solvable?

# Answer
Observing that there exists an optimal solution such that for any $i\_1\<i\_2$ , $f(i\_1)\le f(i\_2)$ (otherwise, we can swap $f(i\_1)$ and $f(i\_2)$), there is a dynamic programming algorithm solving your problem.

We sort $A$ and $B$ firstly. Suppose $A=\\{a\_1,\ldots,a\_n\\}$ and $B=\\{b\_1,\ldots,b\_m\\}$, where $a\_1\<\cdots\<a\_n$ and $b\_1\<\cdots \<b\_m$. Let $D(i,j)=\min\_{f:\\{a\_1,\ldots,a\_i\\}\to\\{b\_1,\ldots,b\_j\\}}\sum\_{j'\le j}(\text{number of nodes matched to }j')^2$, then $$D(i,j)=\min\_k D(i-k,j-1)+k^2,$$ where the minimum is taken over all $k$ such that $a\_{i-k}$ is able to be matched to $b\_j$. The original objective is to compute $D(n,m)$. It can be done by this recurrence in $O(n^2m)$ time.
> 2 votes

# Answer
There is a variation on the cost function that might achieve similar goals and is polynomial solvable.

Consider the following problem: given sets of integers $A,B$ and a constant $c$, find $f:A \to B$ such that $|i-f(i)| \le 2$ for all $i \in A$, and $|f^{-1}(j)| \le c$ for all $j \in B$ (i.e., each $j \in B$ has at most $c$ nodes matched to it).

This problem can be solved in polynomial time by reduction to network flow. Build a flow graph with one vertex per element of $A$ or $B$, plus a source $s$ and a sink $t$. Add an edge of capacity 1 from $s$ to each $i \in A$, an edge of capacity 1 from each $i\in A$ to each $j \in B$ with $|i-j|\le 2$, and an edge of capacity $c$ from each $j \in B$ to $t$. Now use a network flow algorithm to find a maximum flow, and test whether you can find a flow of capacity $|A|$. Many network flow algorithms guarantee that if such a flow exists, they will find an integral flow. If such a flow exists, you have found such a function $f$; if none exists, then no function $f$ exists.

You can then use binary search on $c$ to find the minimal $c$ such that such an $f$ exists.

---

What's the connection to your original problem? Your original problem can be viewed as a $\ell\_2$ cost function, whereas my variant can be viewed as having an $\ell\_\infty$ cost function. Any solution with $c$ that is not too much larger than $1$ will be "close" to a matching.
> 0 votes

---
Tags: algorithms, np-hard, matching
---


# Question
Title: Solving the recurrence $ T(n) = \dfrac{T(n-1) + T(n-3)} {T(n-2)} $
What's the (asymptotic) solution of the following recurrence? $$ T(n) = \frac{T(n-1) + T(n-3)} {T(n-2)}. $$ I tried to solve this with generating functions to find an accurate bound.

# Answer
The solution depends on the initial conditions. For example, if $T(0) = T(1) = T(2) = 2$ then $T(n) = 2$ for all $n$, but in general the recurrence converges to a pattern of length $4$. The limiting patterns are of the form $$ a, \frac{ab\pm\sqrt{(ab)^2-4(a+b)}}{2}, b, \frac{ab\mp\sqrt{(ab)^2-4(a+b)}}{2} $$ For example, if $T(0)=T(1)=T(2)=1$ then $a ≈ 3.13200592382654$ and $b ≈ 1.35282312408545$. For large $n$, the values $T(4n),T(4n+1),T(4n+2),T(4n+3)$ are close to $$ 3.13200592382654, 2.06091243965066, 1.35282312408545, 2.17613759887451. $$ (So we choose $-$ in the $\pm$.)

The above was determined empirically. It would be nice to come up with a proof.
> 2 votes

---
Tags: recurrence-relation, generating-functions
---


# Question
Title: Recursive algorithm to find maximum value in 2D array
Imagine a 2D array of size `n x m`, where every column is a stack of positive values. I am trying to figure out a recursive pseudo code algorithm, where I have a number `k`, that is the maximum number of elements to pick from the array, which would find the indices in every column, that would maximise the sum of all the values of that index and all values above it.

```
[5 7 8]
[2 0 1]
[1 4 3]

```

For example here, if I took the number k to be 4 then I could only pick 4 values, s.t. the sum of them is maximised. For example, index 1 in the first column (value 2), index 0 in the second (value 7) and third column (value 8), which would result in

```
5 + 2 + 7 + 8

```

But I cannot grasp how could I implement the recursive algorithm to solve an issue like this. Would be grateful for any directions on this matter.

Thank you!

# Answer
You can solve this using dynamic programming. For each $i$ and $\ell \leq k$, find the best solution for the first $i$ columns, when you are allowed to pick at most $\ell$ values.
> 0 votes

---
Tags: algorithms, recursion, minmax-algorithm
---


title: Finding n0, asymptotic analysis

text:
# Question
Title: Finding n0, asymptotic analysis
I am attempting a textbook question about asymptotic analysis. The question goes:

\** The number of operations executed by algorithms A and B is 8nlogn and 2n^2, respectively. Determine n0 such that A is better than B for n ≥ n0. \**

So far my approach has been to draw a log-log graph with both lines and find the meeting point, I am thinking that this meeting point is at log(n0) so I can find n0 from it, the one that they are looking for, but things get strange here because the two lines never meet!

Here is the picture of my graph. https://drive.google.com/file/d/1eUFkawKXCWiRBV6BV34Acs5SK4mBHMN4/view?usp=sharing

Any help with this problem will be much appreciated.

# Answer
> 1 votes
In principle it could be that $2n^2 = 8n\log n$ could have several solutions. However, this doesn't matter much: the derivative of $n/\log n$ is $$ \frac{\log n - 1}{\log^2 n}, $$ and so if $2N^2 \geq 8N\log N$ for some $N \geq e$, it follows that $2n^2 \geq 8n\log n$ for all $n \geq N$.

Plugging in small values of $N$, we see that $2N^2 \> 8N\log N$ for $N = 9$.

---

Here is an alternative proof. We first prove that if $n = e^k$ and $k \geq 4$ is an integer, then $2n^2 \geq 8en(\log n + 1)$. You can calculate that it holds for the base case $k = 4$. Assuming that it holds for some $k \geq 4$, we prove it for $k + 1$. The induction hypothesis implies that $$ 2e^{2(k+1)} = e^2 \cdot 2e^{2k} \geq e^2 \cdot 8ee^k (k+1) = 8ee^{k+1} (k+2) \cdot e \cdot \frac{k+1}{k+2}. $$ To complete the proof, it suffices to check that $e (k+1)/(k+2) \geq 1$, or equivalently, that $e \geq (k+2)/(k+1) = 1 + 1/(k+1)$, which trivially holds since $k \geq 4$.

Now let $n \geq e^4$ be arbitrary, and let $k = \lfloor \log n \rfloor$. Then $$ 2n^2 \geq 2(e^k)^2 \geq 2ee^k(k+1) \> 2n\log n. $$

---
Tags: algorithm-analysis, asymptotics, big-o-notation
---


# Question
Title: prove upper bound of the recurrence $ T(n) =T(n-\sqrt{n})+1 $
i want to prove upper bound of the following recurrence $ T(n) =T(n-\sqrt{n})+1 $ is $ O(\sqrt{n})$.

# Answer
Define a sequence by $n\_0 = n$, $n\_{i+1} = n\_i - \sqrt{n\_i}$. Let $\ell$ be the maximal index such that $n\_\ell \geq n/2$. For $i \leq \ell$ we have $\sqrt{n\_i} \geq \sqrt{n/2}$, and so $n/2 \leq n\_\ell \leq n - \ell \sqrt{n/2}$. It follows that $\ell \leq \sqrt{n/2}$.

Let $\ell\_t$ be the maximal index such that $n\_{\ell\_t} \geq n/2^t$; so $\ell\_0 = 0$ and $\ell\_1 = \ell$. The preceding paragraph shows that $\ell\_{t+1} - \ell\_t \leq \sqrt{n\_{\ell\_t}/2}$. Since $n\_{\ell\_t+1} \< n/2^t$, it follows that $n\_{\ell\_t} - \sqrt{n\_{\ell\_t}} \< n/2^t$. If $t \leq \log\_2 n$ then $n\_{\ell\_t} \geq 1$, and so $(\sqrt{n\_{\ell\_t}}-1)^2 = n\_{\ell\_t} - 2\sqrt{n\_{\ell\_t}} + 1 \leq n\_{\ell\_t} - \sqrt{n\_{\ell\_t}} \< n/2^t$, and so $\sqrt{n\_{\ell\_t}} \< \sqrt{n/2^t} + 1$. Therefore if $n\_{\ell\_t} \geq 1$ then $\ell\_{t+1} - \ell\_t \leq \sqrt{n/2^{t+1}} + 1/2$. It follows that if $t \leq \log\_2 n$ then $$ \ell\_{t+1} \leq \sqrt{n/2} + \cdots + \sqrt{n/2^{t+1}} + t/2 = O(\sqrt{n} + t). $$ Choosing $t = \lfloor \log\_2 n \rfloor$, we get that the maximal index $s$ such that $n\_s \geq 1$ is at most $\ell\_{t+1} = O(\sqrt{n} + \log n) = O(\sqrt{n})$.

This shows that assuming an initial condition of the form $T(n) = O(1)$ for $n \leq 1$, you can bound $T(n) = O(\sqrt{n})$; a matching lower bound is obvious (at each step, the value of the parameter decreases by at most $\sqrt{n}$).

Using similar ideas, you can show that if you replace $\sqrt{n}$ by its floor or ceiling, then the resulting recurrence still grows like $\Theta(\sqrt{n})$.

What is the constant factor in the asymptotics of $T(n)$? If we define $\tau(s) = n\_s$ and think of $\tau$ as continuous, then $\tau' = -\sqrt{\tau}$, and so $\tau(s) = (c-s)^2/4$. Since $\tau(0) = n$, we find that $c = 2\sqrt{n}$, and so $\tau(s) = (2\sqrt{n}-s)^2/4$. Therefore $\tau(s) = 0$ for $s = 2\sqrt{n}$, and so we expect $T(n) \sim 2\sqrt{n}$. This is indeed borne out by experiments, which suggest that $T(n) = 2\sqrt{n} - \Theta(\log n)$.
> 1 votes

---
Tags: recurrence-relation
---


title: Big O and Little O

text:
# Question
Title: Big O and Little O
If $a\_n = O(n^\alpha)$ and $b\_n = o(n^\beta)$, prove that $a\_nb\_n = o(n^{(\alpha + \beta)})$ and $a\_n+b\_n = O(\max(n^\alpha, n^\beta))$.

For the part about $a\_nb\_n = o(n^{(\alpha + \beta)})$, I get that I am supposed to set it up so that

$|a\_n| \< Mn^\alpha$ for some positive real M for $n \geq n'$

$|b\_n| \< \epsilon n^\beta$ for all positive reals $\epsilon$ for $n \geq n''$

Then I choose the maximum of n' and n'', and I get

$|a\_nb\_n| \< M\epsilon n^\alpha n^\beta$.

My question is does this finish the proof? If there is a positive real M multiplied by $\epsilon$, does that map to all $\epsilon$? How do you denote this? I think this is some real analysis proof here or I can just say a constant multiplied by epsilon is just epsilon?

For the sum proof, does it become big-O rather than little-O because it cannot be mapped to $\epsilon$ when you add the two parts?

Thank you in advance for the help.

# Answer
For $a\_n$ you use correct definition i.e. $a\_n \in O(n^\alpha)$: $\exists C\>0, \exists N\_1 \in \mathbb{N}, \forall n\>N\_1, |a\_n| \leqslant C n^\alpha$.

For little-$o$ for $b\_n \in o(n^\beta)$ let's use following definition : $\exists \varepsilon\_n, \lim\limits\_{n \to \infty}\varepsilon\_n=0$ and $ \exists N\_2 \in \mathbb{N}$ such that $ \forall n\>N\_2, b\_n=\varepsilon\_n n^\beta$.

So, taking $n\>\max(N\_1,N\_2)$ we have $a\_n \cdot b\_n= \frac{a\_n \varepsilon\_n}{n^\alpha} \cdot n^{\alpha+\beta} = \phi\_n n^{\alpha+\beta}$. We need to prove, that $\phi\_n \to 0$: $|\phi\_n| = |\frac{a\_n \varepsilon\_n}{n^\alpha}| \leqslant C |\varepsilon\_n|\to 0$.

Hope you'll be able finish second using above.
> 1 votes

---
Tags: asymptotics, big-o-notation
---


title: How were operating systems even made?

text:
# Question
Title: How were operating systems even made?
By that, I don't mean what is needed to make an operating system. I know that OSes are built on top of kernels and whatnot. But what I mean is, it wasn't like anyone could just "program" the OS like any other software, right? Was an assembler first built? and then a C compiler on top of that? It's a chicken-egg problem I can't seem to find the answer to.

# Answer
There is some great mysticism around Operating Systems. They are sometimes treated like this dark wizardry that only a handful of the initiated are allowed to understand. (Compilers are treated like that as well.)

Here's the truth, though: an Operating System processes inputs and does something in reaction to those inputs. You know what also does that? *Every other program*.

An OS is just a program. There is nothing special or magical about it.

> But what I mean is, it wasn't like anyone could just "program" the OS like any other software, right?

Why not?

Linux was *literally* written *by accident*.

Linus Torvalds saved up to buy his dream machine, the pinnacle of computing at the time: a 32 bit 80386 PC clone. And he wanted to learn how to program the 80386 to get the most performance out of it. He spent a lot of time using a terminal program to connect remotely to the university, but all terminal programs that existed where too slow or too clunky.

So, he decided to kill two birds with one stone and teach himself 80386 assembly by writing a better terminal program. After a while, he realized that if he wanted to *really* dive into how the 80386 works *and* wanted the most performance, he should get rid of the Operating System and just boot into his terminal program directly. So, he wrote a boot loader that booted directly into the terminal program. Now, without the OS, he also needed a keyboard driver, so he could type commands into the terminal program, he needed a console driver so that the terminal could print answers back, and he needed a driver for the serial port, so he could connect to the university. Unfortunately, when he wanted to transfer files, he still had to boot into the OS, so he added a hard disk driver and a file system driver to the terminal program. And in order to be able to use the terminal program while it was downloading files, he added multithreading and a scheduler.

It was at this point, that he realized, that he had accidentally written an almost complete Operating System. So, he decided to further play around with it, add some missing features, etc.

Then, one day, he mistyped a command, and accidentally overwrote the partition with his Minix installation, thus destroying the existing OS that was installed on the PC.

Now, he had a decision to make: reinstall Minix or finish his OS. And the rest, as they say, is history.

So, writing an OS is really not that different from writing any other kind of program. Linux is the existence proof of that, because it *is* just a normal program that accidentally became an OS.
> 3 votes

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


# Question
Title: What do you call a data structure containing multiple lists?
I was thinking about a data structure to make concatenation of lists easier, something that contains multiple lists (in a sequence) internally, but can be treated as a single contiguous list. I know such a data structure must exist out there already, and I would like to find articles about its performance, but I don't know what it's called. The closest thing I've found so far is a skip list, but that seems to be more like a binary search tree and isn't just for dumping elements in.

I thought of implementing it something like this - the data structure L starts out containing an empty doubly-linked list of arrays.

```
[]

```

Then, when an array or other list-like data structure is added to it, it becomes the first element.

```
Add [100, -4, 2] to L
Head -> [100, -4, 2] <- Tail

```

The next array added becomes its second element, and so on.

```
Add [2, 6, 1] to L
Head -> [100, -4, 2] <-> [2, 6, 1] <- Tail

Add [4, 5] to L
Head -> [100, -4, 2] <-> [2, 6, 1] <-> [4, 5] <- Tail

```

L will only expose methods to iterate over it one at a time (in order), so it can be treated as a normal list.

# Answer
> 2 votes
If you don't care about the order of elements (e.g. you can deal with sets instead of lists) then the union-find structure gives an (amortized) constant time union operation.

There's also the unrolled linked list but the idea is to unroll a list for better cache performance rather than better performance when concatenating lists. For this reason, the number of elements at each node is generally bounded.

I don't think the data structure you describe has a name. It will act like a linked list in the worst case e.g. O(1) to add at the front/back and O(n) to search but you get the added bonus of O(1) concatenation that would be O(k) (for k new elements) with linked lists.

If that's all you're doing with your list then there doesn't seem to be any need to rearrange your list at any point e.g. by coalescing or splitting up nodes.

**Update:** An example of a specific data structure that seems to behave in the way you want is the Quicklist in Redis. It is described as a 'linked list of ziplists' where a ziplist is a contiguous bit of memory.

# Answer
> 2 votes
The short answer is I haven't seen this as a data structure before. I think generally it's just called a "list of lists", and **it's the operation for iterating through it that gets a special name**. Python's "itertools.chain", something like "flatten().iter()", or in lazy functional languages just "flatten".

The longer answer is, your data structure L is solving a (to me) weird use case I don't see often.

* You want to support only iteration and concatenation
* You don't know all the things to concatenate in advance
* You don't want to modify the original lists (concatenating linked lists destructively is already O(1), if you just store a tail pointer)
* You only want to concatenate primitive lists AFAIK, not more instances of L.
    + If you want more instances of L, I could see this being worth naming, but also probably worth optimizing. Chris Okasaki's "Purely Functional Data Structures" talks about how to support linked list concatenation efficiently, without destroying the original lists.
    + If you only want primitive lists, I would expect to see indexed lists used, not linked lists, and thereby supporting indexing efficiently on the master list. This could potentially require an additional master data structure (look up the "rope" data structure, which is used for efficient static list or string concatenation with indexing).

# Answer
> 0 votes
You appear to be describing a tree.

You have a list of lists. That corresponds to a two-level tree. Each list is a node in the tree, and each element of that list is one of its children.

---
Tags: data-structures, lists
---


# Question
Title: Monad in Haskell programming vs. Monad in category theory
I have a question about concept of monad used in Haskell programming and category theory in math.

Recall in Haskell a monad consists of following components:

* A type constructor that defines for each underlying type how the corresponding monad type is to be obtained. The name of this type constructor is often used synonymously with the whole monad. If $M$ is the name of the monad and $t$ is arbitrary fixed data type, then $M t$ is the corresponding monadic type
* A unit function that maps a value of the underlying type to the value of the corresponding monad type. The result is the "simplest" value in the corresponding type that can be obtained from the original value. In Haskell this function is called return. The unit function has the polymorphic type $t → M t$
* At least one further operation, which describes the combination of monadic operations.

On the other hand in category theory a monad is a triple $(T, \eta, \mu)$ of a category $C$ where

* $T: C \to C$ is a functor
* $\eta: 1\_K \to T$ a natural transformation in sense of category theory
* $\mu: T^2 \to T$ a natural transformation

and these objects should satisfy following diagrams: https://en.wikipedia.org/wiki/Monad\_(category\_theory)

Question: How are these monads from Haskell and abstract category theory related? Does the monad structure in Haskell have natural "monad structure" in sense of category theory, ie we can canonically associate to $M$ a canonical triple as described above?

# Answer
A monad in Haskell is intended to be a monad on the category of types, when the category theory is done internally to the type theory. The capabilities of Haskell and similar languages are somewhat limited, so there are a lot of basic constructions in category theory that cannot be done, but there are plenty of structures that can be encoded reasonably.

* `M :: * → *` is the object mapping of the functor, which you have instead named $T$ later.
* The arrow mapping part of the functor is given by `fmap`
* $η$ is the unit function, which Haskell calls `return` (or `pure`, which is a little more general)
* $μ$ is given by `join`.

The requirements expected of `Monad` instances are equivalent to the ones to be a monad in category theory.

Essentially, this is not much different than speaking specifically about monads on the category $\mathsf{Set}$, aside from the earlier mention of Haskell/etc. missing some constructions that set theory has (there are things that act enough like (co)products, but not like pullbacks/pushouts). You could do a lot only thinking about monads on $\mathsf{Set}$, because many structures in abstract/universal algebra give rise to one, and are presentable that way.

One might quibble that types in various programming languages do not technically form a category with good properties/structure, but you could instead imagine that you are using them as a means to talk about something better behaved, like System $F\_ω$, and it wouldn't really change the answer in an interesting way.
> 15 votes

---
Tags: programming-languages, mathematical-foundations, category-theory, haskell
---


# Question
Title: The running time of algorithm is at most $O(n^2)$
The problem is that if an algorithm is $O(n^2)$ then it is also $O(n^3)$ and $O(n^4), O(n^n), \ldots$ and the phrase 'at most' does not make sense in this situation.

For this reason, I am not sure whether this statement is correct or not.

# Answer
> 12 votes
The two phrases

> The running time is $O(n^2)$

and

> The running time is at most $O(n^2)$

mean the same thing.

This is similar to the following two equivalent claims:

* $x = y$ for some $y \leq z$.
* $x \leq y$ for some $y \leq z$.

Why would we ever use "at most $O(n^2)$", then? Sometimes we want to stress that the bound $O(n^2)$ is loose, and then it makes sense to use "at most $O(n^2)$". For example, suppose that we have a multi-part algorithm, which we want to show runs in time $O(n^2)$. Suppose that we can bound the running time of the first step by $O(n)$. We could say "the first part runs in $O(n)$, which is at most $O(n^2)$".

# Answer
> 10 votes
“At most” might mean “at worst” i.e. that the worst-case time complexity is $O(n^2)$.

For example one might say that “Quicksort is at most $O(n^2)$,” meaning that no matter what infinite subset of the inputs you look at, the complexity on that subset is never more than $O(n^2)$.

# Answer
> 6 votes
My reading is that it's not necessarily a tight bound, ie. we know the algorithm is $O(n^2)$, but we don't know if it's (for example) $O(n^{1.99})$

# Answer
> 4 votes
"f(n) is in O(n^2)" means f(n) ≤ c*n^2 for all large n and for some c \> 0. Clearly if f(n) ≤ c*n^2, then f(n) ≤ c*n^3, c*n^4 etc. So factually, "f(n) is in O(n^4)" is equally true. It just gives you much less information, so it may be less useful.

If someone says "f(n) is at most O(n^2)", I would interpret that as "I proved it is in O(n^2), but I couldn't be bothered to check whether it is possibly in a more narrow class". For example, if your algorithm does Step 1 which takes O(n^3) and then Step 2, and you can prove that Step 2 is in O(n^2), that's good enough for all purposes, and you wouldn't bother checking if it's maybe in O (n^2 / log n) or in O (n^1.5).

There's the class $\Theta(n^2)$ which means $c\_1 n^2 ≤ f(n) ≤ c\_2 n^2$ for all large n and for some $0 \< c\_1 \< c\_2$. Here you can't just substitute n^4 for n^2. And there is "asymptotic O(n^2)" which means f(n) is in O(n^2) and not in o(n^2), which means $c\_1 n^2 ≤ f(n) ≤ c\_2 n^2$ for infinitely many large n and for some $0 \< c\_1 \< c\_2$. Again, here you can't just substitue n^4.

# Answer
> 1 votes
You can just view $\mathcal{O}(n^2)$ as an anonymous function drawn from the underlying class.

The statement means: The running time of the algorithm is at most quadratic in the input length $n$.

I do not think there is anything controversial or wrong here.

# Answer
> 1 votes
I understand it so, that, perhaps, saying "$f$ is at most $O(n^2)$", the speaker wants to emphasize, exaggerate his attitude to upper bound $O(n^2)$ as least one.

Good point anyway.

# Answer
> 0 votes
First, just because it's O(n^2) doesn't mean it's O(n^3) or higher.

And sometimes "at most" is quite relevant. Consider, for example, Quicksort. In the real world it normally runs in very close to O(n log n) time, but for any given implementation you can devise an evil data set that makes it run in O(n^2) time. Certain naive implementations have a big problem with this as the evil data is simply already sorted data--add a few items and resort and it goes slow.

I am sure there are other algorithms that are like this but none come to mind right now.

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


# Question
Title: What was the first programming language with loop break?
While tracing the history of the BREAK and CONTINUE statements found in popular languages, I ran into a dead end right around ALGOL.

**Algol \_?** -\> CPL -\> BCPL -\> C -\> C++ -\> Java -\> JavaScript

What was the first programming language to introduce the feature of being able to break out of a loop from the body?

This feature existed in BCPL and is implied to have existed (from its manual) in CPL which was introduced in 1963.

ALGOL 60 was CPL's main influence, but ALGOL 60 did not have the feature.

The structured programming movement started around 1966.

Given the turmoil in the committee between ALGOL 60 and ALGOL 68 (which spawned many languages), was this the source of the feature? Did it exist under a different form at the time as a block EXIT perhaps?

# Answer
> 10 votes
I sent an email to Martin Richards to try and get some details/context about CPL and he gave me a reply. To partially quote:

> "CPL did have a break command to cause an exit from a repetitive command such as while or until. As far as I remember it did not have an equivalent of continue, but the equivalent loop command was added to BCPL early in 1967."

\[...\]

> "The introduction of break in CPL was almost certainly influenced by Dijkstra's paper..."

He also pointed me to the following document (see page 5):

http://www.cl.cam.ac.uk/~mr10/cpl2bcpl.pdf

# Answer
> -1 votes
I nominate Konrad Zuse's Plankalkül, developed in the early 1940s. It is somewhat debatable whether this is a valid answer, since the language was not actually implemented until the '70s. But it had the equivalent to a `break` (actually closer to `return` in Lisp, which doesn't mean "return from the current function" as it does in other languages). Here is Zuse's description from his book about the language (translated to English):

> Some plans\[1\] can be canceled before they have been fully calculated, because the desired result has already been produced, or because further computation turns out to be unnecessary. For example, a multi-part disjunction can be terminated as soon as one part is true, and a multi-part conjunction as soon as one part is false. Therefore an end-marking variable\[2\] $\mathrm{Fin}$ is introduced.
>
> \[Confusing example omitted.\]
>
> However, this kind of representation makes sense only if repetition plans\[3\] are used or if individual conjunctive/disjunctive elements making up a plan are very complicated.
>
> Normally, the range of the $\mathrm{Fin}$ sign extends over the whole plan. But the intention may be to skip only part of the plan, while still calculating the following parts. In this case, it is necessary to separate the plan into groups of partial plans, so that the $\mathrm{Fin}$ applies only to the desired part.
>
> Plans containing $\mathrm{Fin}$ may be nested multiple times. It can then be indicated by $\mathrm{Fin}^1$, $\mathrm{Fin}^2$, etc. whether the symbol applies only once or also at a higher level. This is particularly important in repetition plans.
>
> An expression following a ${\lower{2pt}{\rightarrow}\atop\kern{-1.5pt}\raise{2pt}{.}}$ sign\[4\] is considered to be a closed part of the plan.

Notes:

1. Zuse used "plan" (German *Plan*) to mean what we today might call an "expression", "statement", "program", "subprogram", etc. Note that the language is named Plankalkül, which means something like "plan calculus" (the calculus of plans).
2. I think you can read "variable" as "identifier" or "symbol" here.
3. A repetition plan (German *Wiederholungsplan*) is a loop.
4. In Zuse's language, conditional execution is expressed in a way remarkably like McCarthy's M-Expressions: An expression of the form $x{\lower{2pt}{\rightarrow}\atop\kern{-1.5pt}\raise{2pt}{.}}y$ causes $y$ to be executed only if $x$ is true.

---
Tags: programming-languages, history
---


# Question
Title: What does starvation freedom exactly mean?
Galvin offers the following definitions of starvation:

1. *Indefinite blocking, or starvation, a situation in which processes wait indefinitely within the semaphore.*
2. *A major problem with priority scheduling algorithms is indefinite block-ing, or starvation.A process that is ready to run but waiting for the CPU can be considered blocked. A priority scheduling algorithm can leave some low priority processes waiting indefinitely.*

What I understand from this is, starvation happens whenever a process has to wait indefinitely to get resources, the waiting may be finite, but you cannot specify the time limit. So by definition, starvation freedom must be definite waiting.

Michel Raynal defines starvation freedom as following:

*If a process wants to execute the critical section code, then that process eventually executes it.*

My question is, does starvation freedom mean a given process will have to wait for a specified finite time(definite waiting, according to Galvin) or does it mean that a process must wait for some unknown finite time(eventually executes it, according to Raynal).

# Answer
You cannot imply starvation freedom as *definite waiting* just because the definition of starvation says that the low priority processes have to wait indefinitely.

From Raynal,

> Starvation freedom means that a process that wants to enter the critical section can be bypassed an arbitrary but finite number of times by each other process.

---

Concurrent Programming: Algorithms, Principles, and Foundations By Michel Raynal
> 4 votes

---
Tags: operating-systems
---


# Question
Title: Showing resolution algorithm for 2SAT is polynomial time
I don't quite understand why the resolution algorithm completes in polynomial time for 2SAT but not 3SAT.

I'm looking at slide 42 of these slides for reference. It is clear that given two clauses of length at most 2, their resolvent has length at most 2. From $k$ propositional variables $x\_1,\dots,x\_k$, I see that there are $(2k)^2=4k^2$ possible clauses of the form $(a\lor b)$ where $a,b\in\\{x\_i\\}\cup\\{\lnot{x\_i}\\}$, so there are $O(k^2)$ possible clauses of length at most 2.

But how is this used to show that the resolution algorithm runs in polynomial time for 2SAT but not 3SAT?

# Answer
> 2 votes
In the case of 2SAT, resolving two clauses does not increase their width (the width of a clause is the number of literals appearing in it). This is not the case for 3SAT, where resolution could increase the width. For example, if we resolve $a \lor b \lor c$ and $\lnot a \lor d \lor e$, both of width 3, we get the clause $b \lor c \lor d \lor e$ of width 4.

When running resolution on an instance of 2SAT on $n$ variables, we necessarily get stuck after at most $4n^2 + 2n + 1$ steps, since this is the total number of clauses that we could encounter. This shows that resolution runs in polynomial time on 2SAT.

Showing that resolution does not run in polynomial time on 3SAT is much more involved, among else since resolution is not really an algorithm but rather a *proof system*. Perhaps the simplest proof can be found in Ben-Sasson and Wigderson's classic paper Short proofs are narrow – Resolution made simple.

---
Tags: complexity-theory, satisfiability, 3-sat, 2-sat
---


# Question
Title: Adapt a one-tape turing machine's algorithm that find the center of a string in O(nlog(n)) to find the first third
I have found this answer that finds the center of an input string in nlog(n) complexity. I have tried to use it as a starting point to find an algorithm that finds the character(s) that separate the string in two parts (1/3 + 2/3) by changing some elements of the initial algorithm but I can't find the right modifications that really works on every example. Which adaptations can be made to the initial algorithm that will work for every length ?

I add the image for the machine that finds the center.

Example: for n=3k+1 and n=3k+2

```
XXXX -> XMXX

XXXXX -> XMMXX

```

# Answer
Let's start with a new way of computing the center. First of all, it's not so clear what to do with a string of even length. Fortunately, it doesn't matter, since we can fix it once and for all: initially, we determine the parity of the length of the input, and then add one symbol at the beginning or end (according to the definition of center for strings of even length).

From now on, we assume that we are given a string of odd length. Here is the idea in a nutshell: \begin{align} &\verb|XXXXX| &\verb|XXXXXXX| \\ &\verb|X X X| &\verb| X X X | \end{align}

In words, we erase part of the input so that the remaining string has the same center. How we do this exactly depends on whether the input has length $4n+1$ or $4n+3$.

---

Let's move on to your case. The $1/3-2/3$ midpoint is well-defined for strings of length $3m+1$. You can reduce to this case by adding one or two symbols to either end of the string as before, so let us assume that our string has length $3m+1$. We again consider two cases, according to the parity of $m$:

\begin{align} &\verb|XXCXXXX| &\verb|XXXCXXXXXX| \\ &\verb|X C X X| &\verb| X C X X Y| \end{align}

We have highlighted the center using the letter C.

If the string has length $6n+1$, then we simply cross of every other letter. If the string has length $6n+4$, then we cross of every other letter (starting from the second), and then remove the final letter (which we denoted by Y in the example).
> 0 votes

---
Tags: algorithms, complexity-theory, turing-machines, mathematical-programming
---


# Question
Title: Sample compression scheme and bounding the VC dimension
There is a compression function takes any sample $S$, for which there exists a function $h ∈ H$ with $L\_S(h)$, and compresses it to a subset of $k$ sample points. Similarly, there is a decompression function $\rho$ which maps this compressed set back to a classifier $h'$ (not necessarily in $H$), such that $h'$ makes no mistakes on the original sample $S$. Let $C(H)$ denote the smallest natural number $k$ such that $H$ admits a compression scheme of size $k$. $\mathrm{VC}$ stands for VC dimension.

I want to prove that $$\mathrm{VC}(H) ≤ C(H).$$

# Answer
Suppose that $H$ shatters a set $S$ of size $\ell$, and has a compression scheme of size $k$. For each of the $2^\ell$ labelings of $S$, the compression scheme associates a labeled subset of size $k$, in an injective way. There are $2^k \binom{\ell}{k}$ such labeled subsets, and so $2^\ell \leq 2^k \binom{\ell}{k}$. Using $\binom{\ell}{k} \leq (e\ell/k)^k$, this shows that $2^{\ell-k} \leq (e\ell/k)^k$, and so $2^{\ell/k} \leq 2e\ell/k$, implying $\ell \< 5k$.

Here is an example showing that we cannot improve this to $\ell \leq k$. Consider the set of all functions from $\[k+1\]$ to $\\{0,1\\}$. We give a compression scheme of size $k$. Given a labelling $(\ell\_1,\ldots,\ell\_{k+1})$, we remove either $(1,\ell\_1)$ or $(2,\ell\_2)$ according to the parity of labels. This is injective, since we can reconstruct the missing label from the index of the missing point.
> 1 votes

---
Tags: learning-theory
---


# Question
Title: How can I examine the subnetworks of a nearly fully connected graph?
I have an almost fully connected graph in python with roughly 3k nodes and 9M edges. Each node in this graph is represented by a point in R3 and each edge represents the distance between them with a weight given by a weight matrix.

My goal is to visualize subnetworks (areas where points close to each other also have a dense set of edge weights) where the subnetwork is colored by the given weight. However, this is extremely computationally expensive, as there are 9M edges. I'm looking for an algorithm that can either return the subnetworks, visualize these subnetworks, or something similar.

# Answer
It sounds like you don't need to be talking about this as a "graph" data structure.. you have points in R3 and you want to partition them into clusters based on their distances (or their pairwise weight matrix). This is more a statistical clustering problem than a graph clustering problem.

Here are some python functions to accomplish these: https://scikit-learn.org/stable/modules/clustering.html
> 1 votes

---
Tags: graphs, graph-traversal, clustering, connected-components
---


title: Cache effective access time calculation

text:
# Question
Title: Cache effective access time calculation
In order to calculate the effective access time of a memory sub-system, I see some different approaches, a.k.a formulas. All are reasonable, but I don't know how they differ and what is the correct one.

Assume a two-level cache and a main memory system with the following specs:

```
h1 = 80%       t1 = 10ns    L1 cache
h2 = 40%       t2 = 20ns    L2 cache
h3 = 100%      t3 = 100ns   Main memory

```

`t1` means the time to access the L1 while `t2` and `t3` mean the penalty to access L2 and main memory, respectively.

I see two formulas as described below:

1- `Teff = t1 + (1-h1)[t2 + (1-h2)t3]` which will be 32. The logic behind that is to access L1, first. So, t1 is always accounted. Then with the miss rate of L1, we access lower levels and that is repeated recursively. I agree with this one! You can see further details here.

2- As discussed here, we can calculate that using `Teff = h1*t1 + (1-h1)*h2*t2 + (1-h1)*(1-h2)*t3` which yields 24. However, that is is reasonable when we say that L1 is accessed **sometimes**. You can see another example here. Although that can be considered as an architecture, we know that L1 is the first place for searching data. So, the L1 time should be always accounted.

Is there any suggestion for that?

# Answer
> 5 votes
This is the kind of case where all you need to do is to find and follow the definitions. There is nothing more you need to know semantically. What is actually happening in the physically world should be (roughly) clear to you. It is a question about how we translate the our understanding using appropriate, generally accepted terminologies. It is a question about how we interpret the given conditions in the original problems.

(By the way, in general, it is the responsibility of the original problem/exercise to make it clear the exact meaning of each given condition. A notable exception is an interview question, where you are supposed to dig out various assumptions.)

Let us take the definitions given at Cache Performance by gshute at UMD as referenced in the question, which is consistent with the Wikipedia entry on average memory access time.

> Cache Access Time
> The fraction or percentage of accesses that result in a hit is called the hit rate.
> The fraction or percentage of accesses that result in a miss is called the miss rate.
> It follows that hit rate + miss rate = 1.0 (100%).
> The difference between lower level access time and cache access time is called the miss penalty.
> Effective access time is a standard effective average.
>
> ```
> effective-access-time = hit-rate * cache-access-time
>                       + miss-rate * lower-level-access-time
>
> ```
>
> Miss penalty is defined as the difference between lower level access time and cache access time. Then the above equation becomes
>
> ```
> effective-access-time = cache-access-time + miss-rate * miss-penalty
>
> ```

Since "t1 means the time to access the L1 while t2 and t3 mean the (miss) **penalty** to access L2 and main memory, respectively", we should apply the second formula above, twice. That is,

```
Teff = t1 + (1-h1)[t2 + (1-h2)t3] = 32

```

For the sake of discussion, if we assume that t2 and t3 mean the time to access L2 and main memory **including the time spent on checking and missing the faster caches**, respectively, then we should apply the first formula above, twice. That is,

```
Teff = h1*t1 + (1-h1)*h2*t2 + (1-h1)*(1-h2)*t3 = 24.

```

For the sake of discussion again, if we assume that t2 and t3 mean the time to access L2 and main memory **directly assuming there is no caches at all**, respectively, then we should claim there is not enough information to compute a reasonable answer. Or if we can assume it takes relatively ignorable time to find it is a miss in $L1$ and $L2$ (which may or may not true), then we might be able to apply the first formula above, twice.

You could say that there is nothing new in this answer besides what is given in the question. I would actually agree readily. All I have done is basically to clarify something you have known as well as showing how to select the right definition or formula to apply.

---

Now that the question have been answered, a deeper or "real" question arises. Are those two formulas correct/accurate/make sense?

The picture of memory access by CPU is much more complicated than what is embodied in those two formulas. The actual average access time are affected by other factors \[\]. However, we could use those formulas to obtain a basic understanding of the situation.

# Answer
> 0 votes
Actually, this is a question of what type of memory organisation is used. There are two types of memory organisation- Hierarchical (Sequential) and Simultaneous (Concurrent). In the hierarchical organisation all the levels of memory (cache as well as main memory) are connected sequentially i.e. the CPU can access L2 cache only if there is a miss in L1 cache.

CPU -\> L1 -\> L2 -\> Main Memory

In this case the first formula you mentioned is applicable as access of L2 starts only after L1 misses. But, in sequential organisation, CPU is concurrently connected all memory levels and can access them simultaneously.

CPU -\>L1
CPU -\>L2
CPU -\>Main Memory

In this case, the second formula you mentioned is applicable because if L1 cache misses and L2 cache hits, then CPU access L2 cache in t2 time only and not (t1+t2) time. This is due to the fact that access of L1 and L2 start simultaneously. The hierarchical organisation is most commonly used. But it is indeed the responsibility of the question itself to mention which organisation is used.

---
Tags: cpu-cache, memory-access, performance
---


# Question
Title: Reference asking : High Performance Computer Architecture
## Topics

---

**Pipelining:** Basic concepts, instruction and arithmetic pipeline, data hazards, control hazards, and structural hazards, techniques for handling hazards. Exception handling. Pipeline optimization techniques. Compiler techniques for improving performance. Hierarchical memory technology: Inclusion, Locality properties; Cache memory organizations,Techniques for reducing cache misses; Virtual memory organization, Mapping and management techniques, Memory replacement policies.

**Instruction-level parallelism:** Basic Concepts, Techniques for increasing ILP, Dynamic scheduling (Tomasulo's Algorithm), Reorder buffer and instruction commit, Branch prediction and advanced instruction delivery, Speculative execution. Superscalar, Superpipelined and VLIW processor architectures.Array and vector processors.

**Multiprocessor architecture:** Taxonomy of parallel architectures. Centralized shared-memory Architecture. Synchronization, Memory consistency, Interconnection networks. Distributed shared memory architecture. Model of memory consistency, Cache coherency, Multiprocessing snooping protocol, Multiprocessing directory protocol. Cluster computers.

***These are the topics I have to learn.***

It will be great help if I am suggested any video resources or books regarding this. Although I am going through **Computer Architecture: A Quantitative Approach** by *John L. Hennessy and David A. Patterson* . But I need more resources.

# Answer
This is a pretty good book: Mike Johnson, *Superscalar Microprocessor Design*, Prentice-Hall, 1991, ISBN 0-13-875634-1.

Having said that, some of the original references are quite readable. For example:
> 1 votes

---
Tags: computer-architecture, reference-request
---


title: Complexity of two-party maximum

text:
# Question
Title: Complexity of two-party maximum
Given function $\max\colon \\{0, 1\\}^{n} \times \\{0, 1\\}^{n} \rightarrow \\{0, 1\\}^{n}$ that returns the maximum of two binary $n$-vectors (interpreted as encoding numbers in the range $0,\ldots,2^n-1$), find a communication protocol for two parties having vectors $x$ and $y$ such that both parties will get the vector $\max(x, y)$.

It's easy to get trivial bounds for the complexity of any protocol for maximum: $n \leq \texttt{CC}(\max) \leq 2n$, but how can we use only $\frac{3n}{2} + c$ bits for some constant $c$?

# Answer
Write $x = (x\_h,x\_l)$ and $y = (y\_h,y\_l)$, where $x\_h,y\_h$ are the high-order parts.

Alice sends $x\_h$ to Bob ($n/2$ bits). Bob sends Alice two bits, indicating which of the following holds: $x\_h \> y\_h$, $x\_h = y\_h$, $x\_h \< y\_h$. The protocol then proceeds as follows:

* If $x\_h \> y\_h$, then Alice sends Bob $x\_l$ ($n/2$ bits).
* If $x\_h \< y\_h$, then Bob sends Alice $y$ ($n$ bits).
* If $x\_h = y\_h$, then Alice sends Bob $x\_l$, and Bob sends Alice $y\_l$ ($n$ bits).

In total, at most $\frac{3}{2}n+2$ bits are sent (assuming $n$ is even).
> 2 votes

---
Tags: communication-protocols, communication-complexity, upper-bound
---


# Question
Title: Is it generally possible to convert CNF to Horn clauses?
My intuition is that it is not generally possible, but I cannot think of a proof.

# Answer
In "Renaming a Set of Clauses as a Horn Set" Harry Lewis showed that a CNF formula could be converted to Horn form iff a particular 2-CNF formula constructed from the original formula is satisfiable. The satisfying assignment to the 2-CNF formula tells you which literals to flip. The 2-CNF formula can be constructed in time quadratic to the number of literals appearing in the original formula. Faster algorithms have been published since which reduce the problem of Horn-renaming a CNF formula to linear-time if it is possible to do at all.
> 2 votes

---
Tags: satisfiability, propositional-logic
---


# Question
Title: Complexity of a decision problem: system of linear equations over finite field with restricted solutions
I have a system of linear equations over a finite field $\mathbb F\_p \cong \mathbb Z\_p$, and I'm interested in the decision problem of whether there exists a solution where all of the variables $x\_i$ are in the set $\\{0, 1\\} \subset \mathbb F$. In particular, I'm trying to determine whether this problem is $\mathcal{NP}$-hard.

### Example

One system of equations over $\mathbb F\_3$ is: $$ \begin{alignat\*}{2} &x\_1\begin{bmatrix}1 \\ 1 \\ 0\end{bmatrix} + x\_2\begin{bmatrix}0 \\ 0 \\ 0\end{bmatrix} + x\_3\begin{bmatrix}0 \\ 2 \\ 0\end{bmatrix} + x\_4\begin{bmatrix}1 \\ 0 \\ 1\end{bmatrix} \\ + \\, &x\_5\begin{bmatrix}2 \\ 1 \\ 0\end{bmatrix} + x\_6\begin{bmatrix}0 \\ 1 \\ 1\end{bmatrix} + x\_7\begin{bmatrix}1 \\ 0 \\ 0\end{bmatrix} + x\_8\begin{bmatrix}1 \\ 2 \\ 0\end{bmatrix} = \begin{bmatrix}0 \\ 0 \\ 2\end{bmatrix}. \end{alignat\*} $$ This system of equations *is* satisfiable with entries in $\\{0,1\\}^8 \subset \mathbb F^8$, namely $$ \begin{align\*} (x\_1, x\_2, x\_3, x\_4, x\_5, x\_6, x\_7, x\_8) &= (0,0,0,1,0,1,1,1) \hspace{1em}\text{or}\\ (x\_1, x\_2, x\_3, x\_4, x\_5, x\_6, x\_7, x\_8) &= (0,1,0,1,0,1,1,1). \end{align\*} $$

### An unhelpful (?) reduction

One suggestion that was given to me was turning this into a system of quadratic equations in the following way: define auxiliary functions coordinatewise $$ \begin{align\*} w\_1 &= x\_1 + x\_4 + 2x\_5 + x\_7 + x\_8 \\ w\_2 &= x\_1 + 2x\_3 + x\_5 + x\_6 + 2x\_8 \\ w\_3 &= x\_4 + x\_6 - 2, \end{align\*} $$ and use these to solve the system of quadratic and linear equations $$ w\_1 = w\_2 = w\_3 = x\_1^2 - x\_1 = \cdots = x\_8^2 - x\_8 = 0. $$

However, the MQ-problem (Multivariate Quadratic equations over a finite field) is $\mathcal{NP}$-hard, so this reduction doesn't help. However, this set-up is a quite special case, so I'm holding out some hope that the original problem might still be in $\mathcal{P}$.

---

Is there a polynomial-time algorithm for determining the existence of a solution of linear equations over a finite field with restricted variables? Or is it known if this problem is $\mathcal{NP}$-hard like the MQ-problem?

# Answer
You can reduce 1-IN-3 SAT to your problem (an instance is a 3CNF, and we want to find a satisfying assignment having exactly one satisfied literal per clause), assuming $p \geq 3$.

A clause $x \lor y \lor z$ is encoded as the constraint $x+y+z=1$.

A clause $\bar x \lor y \lor z$ is encoded as the constraint $1-x+y+z = 1$; and so on.

When $p = 2$, your problem becomes easy.
> 2 votes

---
Tags: complexity-theory, linear-algebra, polynomial-time-reductions, finite-sets
---


# Question
Title: About the pseudo polynomial complexity of the KnapSack 0/1 problem
I have read Why is the dynamic programming algorithm of the knapsack problem not polynomial? and other related questions, so this is not a duplicate but just a related pair of questions to clear some doubts.

A question that frequently arises when discussing the complexity of the dynamic programming solution for the KS problem is something like *¿Why $O(n \cdot W)$ is not considered polynomial?*.

The common answer is that, by definition, we are concerned with the running time of an algorithm as a *function of the **size** of the input*. So, while is correct to say the running time is bounded by a polynomial in the *value* of $W$, is not polynomial in the *size* of $W$, because in fact what we have is $O(n \cdot 2^W)$.

Here we can also ask *¿Why not $O(2^n \cdot 2^W)$?*, i.e. by the same reasoning $n$ should also be exponential in the length of the input. But the "trick" is that it seems $n$ is usually (always?) not considered part of the input at all. Instead, the input is (by convention i guess) just a list of $n$ weights, a list of $n$ values, and capacity $W$. Indeed, we don't need $n$ itself in the input.

Questions:

1. Suppose we have $n$ itself in the input, as nothing stops me of doing it in this way. The algorithm loops from $0$ to $n$ in the same way it loops from $0$ to $W$. Now, is correct to say the running time is $O(2^n \cdot 2^W)$ ?.
2. But if (1) is the correct, i dont think this algorithm with $n$ in the input have the same asymptotic behavior as the common one. How $O(2^n \cdot 2^W)=O(2^{n+W})$ compare with $O(n \cdot 2^W)$ ?.
3. Consider the usual naive recursive algorithm for the KS 0/1 problem. This is said to be $O(2^n)$, because in the worst case two recursive calls on $n-1$ are needed. In this case, $n$ is clearly in the input, but we are considering $n$ as a *value* when doing the recurrence analysis. So, considering earlier discussion, i'm tempted to say that in fact we have $O(2^{(2^n)})$ which is double exponential and not just exponential ... but does this make sense?

# Answer
> 2 votes
Whether $n$ is "included in the input" or not is irrelevant. No "tricks" are being used to sneakily hide $n$ from the input by implicitly including it as the length of a list.

The input is at least $n$ bits long because it *must* include a list of all the values and weights of items. If we are not given the values and weights of the items as part of the input, then how are we supposed to solve the problem (if we do not know the weight/value of some items)?

Now, since we know that the input has length (in bits) at least $n$, any running time of the form $n, n^2, n^3,...$ is polynomial *in the length of the input*.

However, the length of a (reasonable representation of the input) is at most $O(n\log W)$ (assuming the values of the items are on the same order of magnitude as their weights). For every item we must give the weight and value, and this can be done with $\log W$ bits per item (by giving the binary representation of the weight/value).

As Yuval noted, $nW$ is not polynomial in $n\log W$.

It does not matter if we consider the input as the lists only or the lists "together with" $n$. If we also include $n$ explicitly, it just makes the input $\log n$ bits *longer*. But since the input is already at least $n$ bits long, having $\log n$ extra bits makes no difference.

# Answer
> 1 votes
Suppose that there are $n$ integer weights of magnitude at most $W$. We can encode each weight in $O(\log W)$ bits, and so the total input length (in bits) is $O(n\log W)$. An algorithm is *polynomial* if its running time is $O((n\log W)^C)$ for some $C$. Dynamic programming runs in $\Theta(nW)$. Unfortunately, $nW$ cannot be bounded by $O((n\log W)^C)$ for any constant $C$.

---
Tags: algorithm-analysis, runtime-analysis, dynamic-programming, knapsack-problems, pseudo-polynomial
---


# Question
Title: Arithmetic Encoding vs Adaptive Arithmetic Encoding
I am working on a personal project and I am having some conceptual level questions on arithmetic encoding.

1. Let's take a scenario where I have an array of sensors and the data collected is transmitted over the internet to Alice. Naturally to decrease transmission cost I would want to transmit data in compressed form. But the data source is non stationary in nature and I have read that we use Adaptive Arithmetic Encoding in such scenario. But I can do this trick that, collect sensor data in a fixed size buffer and when buffer is full then use Normal Arithmetic Encoding and send the encoded sequence over the internet. So my question is why would I want to use Adaptive Arithmetic Encoding in this scenario and what advantage will it serve me? If the above stated scenario is not applicable please explain using other example.
2. Have I understood both the concepts correctly? (By checking algorithms of both and please point out mistakes if any)

```
    Arithmetic Encoding

    start
        statistical_model = collect_stats(data) //we need to perform single pass over data to collect stats
        for each symbol in data:
            probability_distribution = statistical_model(symbol) //calculate conditional probability distribution for the current symbol given previous n symbols
            current_state = artimetic_encoding(probability_distribution, previous_state)
        return current_state
    end

    Adaptive Arithmetic Encoding

    start
        statistical_model = init() // initialize the model in such a way which is known to both encoder and decoder (for example: zero initialization)
        for each symbol in data:
            probability_distribution = statistical_model(symbol) //calculate conditional probability distribution for the current symbol given previous n symbols
            current_state = adaptive_artimetic_encoding(probability_distribution, previous_state)
            update_model(statistical_model, symbol)
        return current_state
    end

```

# Answer
> 1 votes
The pseudocode looks good to me, except of course that in static arithmetic coding, you need to transmit the model before the decoder can use it.

Exactly how to do that in a space-efficient way is not obvious. One of the advantages of adaptive coding is that it gives you that for free: the loss of compression while the model is "learning" should be (if you did it correctly) exactly the minimal cost of transmitting the model.

But, of course, it's not free because updating an adaptive model isn't free. You pay for it in the CPU and memory efficiency of the encoder and decoder.

---
Tags: data-compression
---


# Question
Title: Why do we need two variables for implementing kleene star operation on a language using context free grammars?
I have a Context-Free Grammar (CFG) G which has a S for generating a language L. Now to produce a grammar for L\*, another variable T (which is not present in the variable set of G) is taken and the grammar is produced in the following way:

```
                                 G' = (V, A, T, P)

```

where,

```
  G'.V = G.V U {T} (V is the variable set)
  G'.A = G.A       (A is the alphabet here, I was't able to insert the symbol of capital sigma here)
  G'.T              is the starting variable
  G'.P = G.P U { T -> ST | NULL }   (P is a finite relation from V to (A U V)* )

```

My question is that why can't we use S-\> SS | NULL instead of introducing T?

P.S. : This is my first question so apologies for incorrect formatting. Also I am new to Theory of Computation so a basic and simple explanation will help me more. Thank you.

# Answer
In the general case, your grammar generates more words than those in $L^\*$. Consider this grammar:

$$ \begin{array}{l} S \to A \\ A \to (S)\ |\ a \end{array} $$

The above grammar generates $L = \\{ a, (a), ((a)), \ldots \\}$.

Using Kleene's star, we get $L^\* = \\{a,aa,a(a), ((a))(a), \ldots \\}$. Note that $(aa)\notin L^\*$.

However, if we add your proposed productions, we get

$$ \begin{array}{l} S \to A\ |\ SS\ |\ \epsilon \\ A \to (S)\ |\ a \end{array} $$

whose language is $L' = \\{a,(aa),((a)a)(a), \ldots \\}$, and this is a strict superset of $L^\*$.

Your construction looks correct in the cases where $S$ never occurs in the right-hand side of a production in the original grammar.
> 3 votes

---
Tags: context-free, kleene-star
---


title: Random numbers with condition in matlab

text:
# Question
Title: Random numbers with condition in matlab
I need **’n’** random numbers that:

* each one is bigger than **‘a’**
* their sum is smaller than **‘b’**

How can I have that in Matlab?

# Answer
> 0 votes
I'm assuming you are interested in non-negative integers and that your want to select one set of numbers uniformly at random among all sets of numbers that satisfy the stated conditions.

In this case, your problem is equivalent to finding $n+1$ random numbers $x\_1, \dots, x\_{n+1} \ge 0$ such that $\sum x\_i = (b-1) - (a+1)n$. Here $x\_{n+1}$ represents the difference between $x\_1 + \dots, + x\_n$ and $S$ and you can obtain the $i$-th sample as $x\_i+a+1$.

Let $S = (b-1) - (a+1)n$. To describe the set non-negative integers that sum to $S$, have a look at the stars and bars representation.

Essentially you have a bijection between the permutations of a set of $S$ stars and $n$ bars and the possible (ordered) tuples of $n+1$ integers $\langle x\_1, x\_2, \dots, x\_{n+1} \rangle$ such that $\sum\_i x\_i = S$. To see this, given a permutation $\pi$, simply chose $x\_i$ as the number of stars that appear after the $(i-1)$-bar (if $i \> 0)$ and before the $i$-th bar (if $i \< n$).

Notice that, in order to find $x\_i$ you only need to know the positions of the bars in $\pi$. This amounts to selecting $n+1$ random positions (integers), without replacement, from the set $\\{1, \dots, S+n\\}$.

If $S$ can be large, a simple way to do this is just to iteratively sample a value $y$ uniformly at random from $\\{1, \dots, S+n\\}$, if $y$ has already been sampled discard it, otherwise accept the sample and move on to the next one.

You can assume that $n+1 \le \frac{S+n}{2}$ (as otherwise you could sample the values in $\\{1, \dots, S+n\\} \setminus \\{x\_1, \dots, x\_{n+1}\\}$ instead) therefore each sample is accepted with probability at least $\frac{1}{2}$, i.e., the probability that a sample is discarded exactly $k$ times is $2^{-(k+1)}$ and the expected number of attempts per accepted sample is $1 + \sum\_{k=0}^\infty 2^{-(k+1)} = 2$. It follows that, in expectation, you will only need to generate $O(n)$ random numbers.

To check whether a previous number equal to $y$ has been accepted, you can use an hashset to store the accepted samples. This allows you to perform lookups and insertions in expected constant time. Alternatively, you could use any efficient implementation of a dynamic set (e.g., a binary search tree) to have a guaranteed worst-case time complexity of $O(\log n)$ per operation (although the total running time will be expected anyway, due to rejection sampling).

---
Tags: programming-languages, mathematical-programming
---


title: 1-OR-3-SAT is in P

text:
# Question
Title: 1-OR-3-SAT is in P
**1-OR-3-SAT**:

Input: 3-CNF formula $\varphi$

Question: whether there is an assignment $x$ such that in each clause there are one or three true literals.

I need to show that this problem is in $P$. I tried to construct a reduction from this problem to 2-SAT that is in $P$. What can I try here?

# Answer
> 3 votes
Hint:

> Can you express the clause in modular arithmetic?

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


# Question
Title: What is the relation between a web server and a local file serve in distributed systems?
I am learning distributed systems ( although I am an Electrical engineer ) using the book distributed systems concepts and design. The author says that "A web server is often a client of a local file server that manages the files in which the web pages are stored." I cant understand in the first place what is the relation between a web server and a local file server. So please someone explain this statement using a simple example. Thank you very much.

# Answer
> 1 votes
Often the content is stored on a local filesystem (or file server); the web server accesses the content by reading it from the local filesystem (or file server), then provides it to the web client on demand. So the web server is making use of a local file server -- in that sense the web server is a client of the local file server.

---
Tags: distributed-systems
---


# Question
Title: What is the time complexity of the SGVB estimator?
In the context of variational autoencoders, we want to maximize the evidence lower bound and this is typically done using Stochastic Gradient Variational Bayes (SGVB). I was curious if there is any work out there or ways to determine the time complexity of SGVB.

# Answer
> 1 votes
Asymptotic running time analysis is not terribly useful for gradient descent used to train machine learning models. In practical machine learning, we run gradient descent for some fixed number of epochs, e.g., 200 epochs; which takes time proportional to 200 times the size of the training set times the time per evaluation of the neural network. That value 200 is arbitrary and set based on what achieves the best accuracy results, and there is little theoretical basis for choosing it.

---
Tags: neural-networks, bayesian-statistics
---


# Question
Title: Complexity of simulating idle games (pt1)
An idle game (Cookie Clicker is a well-known example) is a game where you set up automatic resource production, and most of reasonable human play is then waiting as resources accumulate. Typical implementation is in the form of a "tick loop", where resources update say once per second, generally increasing.

But many games can implement an "offline mode" where instead you can exactly calculate any number of ticks in one step. For example if you were producing 1000 cookies/second, and you come back after 1 hour, you've produced 3.6 million cookies exactly--no need to simulate all 3600 ticks. Then the player can reduce the update rate on screen, or come back to the game in 5 hours without running a program continuously. *(Aside: many real games offer an "offline mode" which does NOT exactly match what would happen playing the game for the same length of time, but here I'm asking about exact simulation)*.

**I am trying to figure out for which idle games an it's possible to efficiently compute many ticks in one step ("offline mode").**

In a typical idle game (think "cookie clicker"), you have a bunch of resource generators, and each one generates some resources each tick. For example, maybe you have a cookie stove, which produces 5 cookies/tick. And you could also have a generator factory, which produces 1 cookie stove/tick.

* For each resource, it produces some fixed list of resources each tick. Let's say we just have a list of what each resource produces each tick.
* A resource costs something to buy. This is actually irrelevant for the simulation--buying is only a player action, and can't be done automatically.
* A problem input will be a set of starting resources, and a number of ticks to simulate. Output should be the resources after that number of ticks.
* If there are no cycles, an offline mode is definitely possible. The number of each resource is a linear (if it is not produced by anything else), quadratic (if it is produced by a linear resource), etc. So it's always a polynomial, which is easy to calculate.

My first question: is this still easy if we allow cycles, ex a "general purpose factory" that produces both general purpose factories, and cookies?

Second question: is this easy if we allow simple "autobuy"? Ex. convert 1000 cookies into a cookie factory, and buy as many as possible, on each game tick.

If it's easy, show how to do it. If it's hard, prove it!

# Answer
> 1 votes
Yes. It can be solved efficiently. You can denote the state of the system at any point by a vector $x \in \mathbb{N}^n$, where $n$ is the number of resources and $x\_i$ counts how many items of the $i$th resource you have.

Your system gives you linear equations that relate $x'$, the state after one tick, to $x$, the state before the tick. For instance, if $x\_1,x\_2,x\_3$ denote the number of cookies, cookie stoves, and cookie stove factories, respectively, then we have $x'\_1 = x\_1 + 5 x\_2$, $x'\_2 = x\_2 + x\_3$, $x'\_3 = x\_3$. Collect all of these linear equations into a linear system $x' = Mx$, so the matrix $M$ represents the generation process.

Now the state after $t$ ticks of offline operation is given by $x' = M^t x$. So, you can use efficient algorithms for matrix exponentiation (e.g., repeated squaring). They will let you compute $M^t$ in $O(n^3 \log t)$ time, after which you can compute $x'$ from $x$ in $O(n^2)$ time. (One can get further speedups: it is possible to compute $M^t$ in $O(n^3 + n \log t)$ time using an eigenvector decomposition.) This is very efficient and will let you handle trillions of ticks with no problem. It also gives you an exact answer.

# Answer
> 2 votes
As you have said in your question, non-cyclical resource production is easy to simulate, but let's describe the simple case before seeing how it impacts the answer. For our cookie-bakery scenario, this is the setup: $$ t\_i=0,\ t\_f=100 \\ C\_i=567,\ C\_{cpt}=0,\ C\_{bpt}=0 \\ B\_i=10,\ B\_{cpt}=2,\ B\_{bpt}=0 $$ The above describes the initial state of our game, we currently have 567 cookies and 10 bakeries. It also describes the production statistics, how much each resource produces per tick. For us, cookies produce nothing and bakeries produce 2 cookies per tick. How do we find how many cookies there are when the time is up? $$ C(t\_f)=\int\_{t\_i}^{t\_f}\frac{dC}{dt}dt+C\_i=2567 $$ This function will calculate how many cookies have been produced by time $t\_f$. In our simple case, $\frac{dC}{dt}$ is easy to calculate: $$ \frac{dC}{dt}=B\_{cpt}B(t)=20 $$ Since there are no new bakeries being generated, the number of bakeries is constant $B(t)=B\_i$.

---

### Question 1

The trouble begins when the resource production contains cycles. That is to say, $\frac{dC}{dt}$ is dependent on $C(t)$ itself. We have entered the realm of differental equations. For an example, here is a tweaked setup where cookies can also asexually reproduce every tick: $$ t\_i=0,\ t\_f=100 \\ C\_i=567,\ C\_{cpt}=1,\ C\_{bpt}=0 \\ B\_i=10,\ B\_{cpt}=2,\ B\_{bpt}=0 $$ Now the rate of change for cookies looks like: $$ \frac{dC}{dt}=B\_{cpt}B(t)+C\_{cpt}C(t)\text{ where }C(0)=C\_i $$ For our case, this is a linear first-order differential equation, our integrating factor is: $$ \mu(t)=e^{-C\_{cpt}t} $$ Plug it into the differential equation form: $$ C(t)=\frac{B\_{cpt}B(t)}{-C\_{cpt}}+ce^{C\_{cpt}t} $$ Find our constant $c$ by checking the initial condition: $$ C(0)=\frac{B\_{cpt}B(0)}{-C\_{cpt}}+ce^0=C\_i \\ c=C\_i+\frac{B\_{cpt}B\_i}{C\_{cpt}} $$ Plug it back into our original equation: $$ C(t\_f)=\frac{B\_{cpt}B(t\_f)}{-C\_{cpt}}+\bigg(C\_i+\frac{B\_{cpt}B\_i}{C\_{cpt}}\bigg)e^{C\_{cpt}t\_f} \approx 1.58\times 10^{46} $$ The asexual reproduction of cookies produces substantially more cookies than just bakeries, but keep in mind the cookie population is essentially doubling every time plus new cookies are being produced by bakeries.

This method can be extended for larger cycles instead of just self cyclical, but it requires higher order differential equations.

Note: Since we are just evaluating an exponential function, it is extraordinarily efficient, $O(1)$. However, this solution adapts the mathematics of population growth estimates to fit this discrete system and will only produce an approximation. Depending on how many timesteps are required to simulate, it may be preferable to spend more time computing an exact result.

---

### Question 2

Automatic buying is quite a bit more difficult to achieve because the functions showing resource counts are no longer smooth and continuous.

This graph shows the cookie production assuming starting with one bakery & zero cookies and buying another bakery every thousand cookies. The period of the function decreases with time because more and more bakeries are added to produce cookies. An estimation could be created by fitting a function to the period, but I do not know of a method to exactly count the number of bakeries and cookies without checking each timestep.

---
Tags: algorithms, board-games, computer-games, algebra
---


title: Faults in the halting problem reasoning

text:
# Question
Title: Faults in the halting problem reasoning
I find very interesting the problem of existence of a machine $H$ which given as input any algorithm $P$ outputs whether $P$ halts or not. Alan Turing disproved the existence of such an $H$ machine in the following way:

"Assume $H$ exists. The input of $H$ is any algorithm $P$. The output of $H$ is $YES$ if $P$ halts and $NO$ if $P$ doesn't. Create another machine $N$ with input in the set $\\{YES,NO\\}$ and without output. The machine $N$ does this: if the input is $YES \to \text{loop for ever}$ otherwise, if input is $NO \to \text{halt}$. Let us call the composition of $H$ followed by $N$ as $X$. We will simply write $X(P) = N(H(P))$. Now $X$ has as input a machine and no output (it either halts or loops forever). What Turing does is to "feed" $X$ with itself ... and reason as follows: if $X(X)$ halts then $X(X) = N(H(X)) = N(YES) = \text{loops for ever}$ from which somehow the contradiction arises ..." but here one should assume (in order to obtain a contradiction) that $X(X) = X$ ...

## Question

I do not know why such an assumption, $X = X(X)$ would be made. In fact, in my opinion, $X \neq X(X)$ for any input $P$ (that is all Turing is proving actually). Indeed assume $P$ is a machine which halts (runs for ever). Then $X(P)$ does not halt (does halt) when $X(X(P))$ does (does not). I do not understand therefore, why $H$ cannot exist! Where is my mistake ?

# Answer
The proof you wrote in the question is faulty, because it uses the wrong definition of the Halting oracle. You tried to fix the proof by inserting the assumption $X(X) = X$, but that is not the way to do it. Here is the correct proof.

**Definition:** A *halting oracle* is a machine $H$ which takes as input a pair $(M,I)$ where $M$ is the (description of) a machine and $I$ an input. $H$ always halts and outputs:

* "yes" if $M(I)$ halts,
* "no" if $M(I)$ does not halt.

**Theorem:** *A halting oracle does not exist.*

*Proof.* Suppose $H$ exists. We shall derive a contradiction.

Let $N$ be a machine which does the following upon receiving an input $I$:

* if $I$ is "yes" then $N$ loops forever,
* otherwise $N$ halts.

Let $X$ be the machine which takes an input $I$ and then acts as $N(H(I, I))$. We now prove two contradictory facts:

1. $X(X)$ does not halt.
2. $X(X)$ halts.

To prove the first claim, suppose $X(X)$ halts. Then $H(X,X)$ outputs "yes", therefore $X(X) = N(H(X,X)) = N(\text{yes})$, but $N(\text{yes})$ does not halt. Therefore it is not true that $X(X)$ halts.

To prove the second claim, suppose $X(X)$ does not halt. Then $H(X,X)$ outputs "no", therefore $X(X) = N(H(X,X)) = N(\text{no})$, but $N(\text{no})$ halts. Therefore it is not true that $X(X)$ does not halt, so it halts. $\Box$.
> 1 votes

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