# Question
Title: Disproving well-quasi-order by providing an infinite anti-chain
I am currently studying the theory behind Well-Quasi-Orders. However I am having some issues in understanding how an infinite anti-chain can be produced to disprove the claim that a partial order $P$ is a w.q.o.

In particular I am wondering whether it is logically sound to present as proof not the infinite anti-chain but rather an algorithm to produce it.

More specifically, I've been trying to solve an exercise from the following lecture which asks whether the class of $P\_{3}\text{-free}$ graphs is a w.q.o or not on the induced subgraph operation $\leq\_{i}$

I've proved that said class contains unions of cliques and defined an ordering of this set as follows $P=\lbrace G\_{0},G\_{1},G\_{2},.... \rbrace$ with $G\_{i}$ representing all $P\_{3}\text{-free}$ graphs on $i$ vertices (and graphs in $G\_{i}$ being represented in a touple-like alpharithmetic form $(a\_{1},....,a\_{i})$ such that $a\_{1} \leq a\_{2} \leq.... \leq a\_{i}$ to avoid repetitions and $\sum\_{j=1}^{i} a\_{j}=i$ to define an order. For example $(0,0,2,2)$ $\in G\_{4}$ encodes the graph with two disconnected $P\_{2}$ components.

I have defined an algorithm $B$ that produces an anti-chain that grows bigger and bigger at each step

The algorithm uses gadgets defined as $B\_{a,c}$ which represent the graph with $c+1$ connected components, the first $c$ of which are $K\_{1}$(i.e a sole vertice) and the last component representing $K\_{a}$

The steps of my algorithm are the following:

1. Define $L$ as the sequence
2. Add $B\_{a,0}$ to $L$ ($a$ any number $\>$ 0)
3. repeat $\infty$ times:

4.Replace each item $B\_{a,c} \in L$ by $B\_{a^{'}=a+1 + 10^{6},c}$ and produce $L^{'}$ this way.

5.Let $X=B\_{a^{'},c}$ be the graph with the maximum $c$ amongst those in $L^{'}$

6.Add to $L=L^{'}$ the graph $B\_{a^{'}-2,c+1}$

Certainly, this algorithm does create an anti-chain( in each step I create a graph with more connected components yet less vertices). However I am not sure that such a technique is valid for disproving w.q.o on the infinite anti-thesis claim because of the fact that it works on a step by step basis.

Any help is appreciated. Thank you very much!

# Answer
> 3 votes
Your algorithm produces an infinite sequence of antichains whose size is unbounded. However, it doesn't produce a *single* antichain of infinite size.

It is perfectly fine to specify an infinite chain by giving an algorithm that enumerates its members, and even more complicated constructions are possible (e.g. the priority method). However, the end result of the construction should be a *single infinite chain* rather than *a sequence of antichains of unbounded size*.

I suggest taking a look at Higman's lemma.

---
Tags: graphs, partial-order
---


# Question
Title: Tool for generating all the consequences of the logical theory (general logic programming framework)?
I am reading article https://arxiv.org/pdf/cs/0511055v1.pdf (about defeasible deontic logic) and it mentions on page 10 the operator T that constructs extension (set of immediate consequences) from the theory D (set of statements). Such extensions form s.c. Kleene sequence and the fixed point exists for the operator T - this fixed point is the complete set of consequences of the set D of statements.

Such construction is known for many logics and I guess that it is the basis of the logic programming using forward chaining approach. This approach is known in business software as well and is called business rules (e.g. JBoss Rules Drolls of IBM ILOG). Such construction has very wide practical applications, e.g. if norms are encoded as logical statements then the set of consequences consist of all the obligations and permissions. More practical applications can be found as well - e.g. application of complex discounting rules in retail trade.

My theory question is:

* Do I understand correctly that generation of set of consequences is the essence of logic programming and such logic programming can be devised for almost any logic?

My systems questions are:

* Are there general framework (system) which receives 1) syntax of logic; 2) operator T and which generates program that can find set of consequences for any set D? I.e. should I construct logical programming tool for my logic from scratch (only parser can be generated automatically) of can I use some framework?
* How such logic programming framework is connected with proof assistant and theorem prover frameworks (like Isabells of Coq)? As far as I understand then there is no connection - theorem provers use backward reasoning approach and logic programming uses forward reasoning approach? However - maybe any connections exists and maybe proof assistant/theorem prover frameworks can still be used for logic programming?

# Answer
> 5 votes
You understand incorrectly. That is not how logic programming works.

The number of consequences typically grows exponentially, or is even infinite. For instance, some consequences of $\forall x \in \mathbb{N} \\,.\\, \phi(x)$ are $\phi(0)$, $\phi(1)$, $\phi(2)$, $\phi(3)$, $\phi(3 + 2)$, $\phi(x \cdot 2)$, and so on. Generating *all* consequences is infeasable and useless. It's a bit like trying to write good literature by generating all grammatically correct sentences.

The gist of logic programming is *proof search*. A logic program follows a particular *strategy* to look for the proof of a given query. So in this sense, it does things *backwards*.

---
Tags: logic, proof-assistants, interactive-proof-systems
---


# Question
Title: Regular expression at least 2 out of 3 consecutive characters should be 1
How can I build a regular expression that, using only the concatenate, union and star operations, over the alphabet {0,1}, describes the language "Every three consecutive characters contain at least two 1, and the input has length at least 3"? For instance 110011, 0101 and 11 should be refused. I was thinking on using the logic from this (incomplete) DFA, but I can't figure out how to get a regular expression that follows the rule. Thanks!

# Answer
Assume that string $s$ is in $L$. We will look at the last two characters of the string:

* `00`, impossible, because this string could not be in $L$.
* `01`, next character must be 1, new last two characters is `11`.
* `10`, next character must be 1, new last two characters is `01`.
* `11`, next character may be 1 or 0, new last two characters is `10` or `11`.

Note that no matter your current state, you will always pass through the `11` state within two steps. Assuming that $s$ ended with `11`, we get the following loop:

```
(1|(011))*

```

This will be the middle section of any string in $L$. All we need to do now is handle possible prefixes, making sure not to allow any with size \< 3:

```
(111|011|1011|11011)

```

And finally, possible suffixes (note the empty union to express that the suffix is optional):

```
(|0|01)

```

Now all that's left is to concatenate them:

```
(111|011|1011|11011)(1|(011))*(|0|01)

```
> 1 votes

---
Tags: regular-languages, automata, finite-automata, regular-expressions
---


title: What is the name of this quantum gate?

text:
# Question
Title: What is the name of this quantum gate?
As I was watching a video about single qubit quantum gates, I came across the following gate: $$\begin{bmatrix}e^{i\sigma}&0\\0&e^{i\theta}\end{bmatrix}$$ The video didn't mention the name of the gate. It gave only the matrix and the following information:

* $|0\rangle \rightarrow e^{i\sigma}|0\rangle$
* $|1\rangle \rightarrow e^{i\theta}|1\rangle$
* $\alpha |0\rangle + \beta|1\rangle \rightarrow \alpha e^{i\sigma}|0\rangle + \beta e^{i\theta}|1\rangle$

In the comments below the video, someone asked what $\sigma$ and $\theta$ could be, and the reply was all real numbers, but this was from someone other than the video maker, so I don't know if this is true.

What is the name of this gate?

# Answer
> 2 votes
This is a phase shift gate.

Notice that

$$\begin{bmatrix}e^{i\sigma}&0\\0&e^{i\theta}\end{bmatrix}= e^{i\sigma}\begin{bmatrix}1&0\\0&e^{i(\theta-\sigma)}\end{bmatrix} $$

Multiplying the state by a constant (with unit norm) will not affect your measurements.

---
Tags: logic, quantum-computing
---


# Question
Title: Spacial complexity of an $O(2^N)$ time-complexity algorithm
For the following code sample:

```
int f(int n) {
    if (n <= 0) {
        return 1;
    }
    return f(n - 1) + f(n - 1)
}

```

I understand that the time complexity is $O(2^N)$. However, what I don't understand is how the space complexity is $O(N)$. The argument I have heard for this is that although we have $O(2^N)$ nodes in the tree total, only $O(N)$ exist at any given time. What does that mean, how is that so? If the recursive calls are going to be made until the base case is reached, then don't we have $O(2^N)$ calls to make instead of $O(N)$?

# Answer
The number of calls is indeed $O(2^{n})$. However, the memory footprint will be $O(n)$.

I guess the point is to clarify how the memory stack works during a recursion. Perhaps the easiest way is to draw a recursion tree to follow the recursive calls. Lets see how the size of the stack changes during these calls through a very small example.

Lets say you want to compute $f(1)$. Your tree will have only three nodes: the root ($f(1)$), a left child ($f(0)$) and a right child ($f(0)$).

Initially the stack is empty. We invoke the function with argument $n=1$. We store what we need in the stack (e.g., temporary variables of this call). This takes constant space, and for convenience lets say that stack size is now equal to $1$.

Next, we invoke the left child $f(0)$. The stack size becomes 2. But $f(0)$ returns immediately. So the stack size is back to 1.

Next, we invoke the right child $f(0)$. The stack size is now 2. $f(0)$ immediately returns 1. So the stack size is now back to 1.

Back at the root node, $f(1)$ has computed both the left and right child and returns its value. The stack size is now 0.

This was a very small example, but you see the stack size was never $3$ (equal to the size of the recursion tree) because the memory stack grows and shrinks as you traverse the tree. For a larger example, you will see that when you visit a node (i.e. at some point of the recursion), any memory you used for the left subtree has now been cleared. You only need memory for the nodes between the root and the current node. Hence, the maximum size is equal to the depth of the tree which is $O(n)$.
> 5 votes

---
Tags: algorithms, asymptotics
---


title: Intuition behind the Hadamard gate

text:
# Question
Title: Intuition behind the Hadamard gate
I'm trying to teach myself about quantum computing, and I have a decent-ish understanding of linear algebra.

I got through the NOT gate, which wasn't too bad, but then I got to the Hadamard gate. And I got stuck. Mainly because while I "understand" the manipulations, I don't understand what they really do or why you'd want to do them, if that makes sense.

For example, when the Hadamard gate takes in $|0\rangle$ it gives $\frac{|0\rangle + |1\rangle}{\sqrt{2}}$. What does this mean? For the NOT gate, it takes in $|0\rangle$ and gives $|1\rangle$. Nothing unclear about that; it gives the "opposite" of the bit (for the superposition, it takes in $\alpha|0\rangle+\beta|1\rangle$ and gives $\beta|0\rangle + \alpha|1\rangle$) and I understand why that is useful; for the same reasons (basically) that it is useful in a classical computer. But what (for example) is the Hadamard gate doing geometrically to a vector $\begin{bmatrix}\alpha \\ \beta \end{bmatrix}$? And why is this useful?

# Answer
The Hadamard gate might be your first encounter with superposition creation. When you say you can relate the usefulness of the Pauli $X$ gate (a.k.a. `NOT`) to its classical counterpart – well, Hadamard is exactly where you leave the realm of classical analogue, then. It is useful for *exactly* the same reason, however, namely that it is often used to form a universal set of gates (like clasical `AND` with `NOT` and fan-out, or `NOR` with fan-out alone).

While a single $H$ gate is somewhat directly useful in random number generation (as Yuval Filmus said), its true power shows when appearing in more instances or in combination with other gates. When you have $n$ qubits initialized in $|0\rangle$, for example, and apply one $H$ to each of them in any order, what you get is $$(|0\rangle + |1\rangle) \otimes (|0\rangle + |1\rangle) \otimes \ldots \otimes (|0\rangle + |1\rangle) / 2^{n/2}$$ which can be expanded to $$1/2^{n/2} \cdot (|00\ldots00\rangle + |00\ldots01\rangle + |00\ldots11\rangle + \ldots + |11\ldots11\rangle)$$ Voilà, we can now evaluate functions on $2^n$ different inputs in parallel! This is, for example, the first step in Grover's algorithm.

Another popular use is a Hadamard on one qubit followed by a `CNOT` controlled with the qubit you just put into a superposition. See: $$CNOT \big(2^{-1/2}(|0\rangle+|1\rangle)\otimes|0\rangle \big) = 2^{-1/2} CNOT(|00\rangle + |10\rangle) = 2^{-1/2} (|00\rangle + |11\rangle)$$ That's a Bell state which is a cornerstone of various quantum key distribution protocols, measurement-based computation, quantum teleportation and many more applications. You can also use a `CNOT` repeatedly on more zero-initialized target qubits (with the same control) to create $$2^{-1/2} (|00\ldots00\rangle + |11\ldots11\rangle)$$ which is known as the GHZ state, also immensely useful.

Last but not least, it's a quite useful basis transform that is self-reversible. So another Hadamard gate undoes, in a sense, what a previous application did ($H^2 = I$). You can experiment around what happens if you use it to "sandwich" other operations, for example put one on the target qubit of a `CNOT` gate and another after it. Or on both of the qubits (for a total of 4 Hadamards). Try it yourself and you'll certainly learn a lot about Quantum computation!

---

Re "what is the Hadamard gate doing geometrically to a vector": read up on the Bloch sphere, you'll going to hear about it everywhere. In this representation, a Hadamard gate does a 180° rotation about a certain slanted axis. The Pauli gates (`NOT` being one out of three) also do 180° rotations but only about $x$ or $y$ or $z$. Because such geometrical operations are quite restricted, these gates alone can't really do much. (Indeed, if you restrict yourself to those and a `CNOT` in your quantum computer, you just build a very expensive and uneffective classical device.) Rotating about something tilted is important, and one more ingredient you usually need is also rotating by a smaller fraction of the angle, like 45° (like in the Phase shift gate).
> 13 votes

# Answer
The Hadamard gate operates on a single qubit. The state of a single qubit can be described as $\alpha \left|0\right\rangle + \beta \left|1\right\rangle$, where $|\alpha|^2 + |\beta|^2 = 1$. If you measure the qubit, the output is $0$ with probability $|\alpha|^2$, and $1$ with probability $|\beta|^2$. From a linear-algebraic perspective, the state of a qubit is just a unit norm vector of length two over the complex numbers. The two vectors $\left|0\right\rangle,\left|1\right\rangle$ span a vector space of dimension two (over the complex numbers), and every unit norm vector in that vector space can be the state of a qubit.

Since the state always has unit norm, the only linear operators possible on qubits are those that preserve norms. From linear algebra, we know that these are exactly the Hermitian operators. To describe an operator, it suffice to describe its effect on a basis. For example, the value of your operator on the vector $\left| 0 \right\rangle$ is $\frac{\left| 0 \right\rangle + \left| 1 \right\rangle}{\sqrt{2}}$.

According to Wikipedia, the Hadamard gate is used to form a "random input". If applied to a constant qubit (i.e., $\left| 0 \right\rangle$, $\left| 1 \right\rangle$, or a rotation of these by a unit norm complex number), the Hadamard gate forms a "uniformly random" qubit, which when measured behaves like a fair coin toss. This is the kind of behavior we want when "trying all possibilities in parallel".

I suggest you continue your reading on quantum computation; when you get to quantum algorithms (like Grover's and Shor's), you will understand what all these quantum gates are useful for.
> 12 votes

---
Tags: logic, quantum-computing
---


# Question
Title: Can someone give me an explanation of how dcaches works?
So, I'm trying to do a computer architecture assignment and there's a question about dcaches. Here's the question:

> Given a 16 word dcache initially filled with word address 0, 1, 2, …15 memory data (referenced by the datapath in that order). Below is the next sequence of data memory address references given as word addresses. 1, 18, 2, 3, 4, 20, 5, 21, 33, 34, 1, 4
>
> a) Assuming the dcache is direct-mapped with one-word blocks, list if each reference is a hit or a miss. Show the state of the dcache after the last reference. What is the hit rate for this reference string?

I'm not asking for a solution but would just like to know what is considered a miss or hit and how this is calculated? Also, what would be the difference if the dcache had a two-word blocks instead of 1?

Any help is greatly appreciated.

# Answer
> 1 votes
> what is considered a miss or hit and how this is calculated

A *hit* occurs if the request word is in the cache; if not, we have a cache *miss*.

It isn't clear how much you understand about hardware caches from the question, but I'll assume you at least know the definition of cache *sets* and *lines*.

In a direct-mapped cache, each cache set can hold only one line. Thus, the number of sets is equal to the number of cache lines. Usually, cache lines are many words long (e.g. 64-byte cache lines), but in your example a cache line consists of a single word. Since the cache can hold 16 words (lines), we can deduce that there are 16 cache sets.

Each memory address is mapped to a set. The set holding a memory address is determined by the address's *set-index bits*. If there are 16 sets, then each address must have $lg 16 = 4$ set-index bits. Let's assume these are the lower-order bits of the address. So, for example, address 7 will uses cache set 7 (because the binary representation of 7 is 00000111).

In this problem, the cache starts full (often referred to as a *warm* or *hot* cache). You are given a sequence of memory addresses. Each memory address will be either a *hit* or a *miss*, as defined earlier. If the address is a *miss*, the word at that address must be brought into the cache, and the old value is ejected from the cache.

> Also, what would be the difference if the dcache had a two-word blocks instead of 1?

If the size of a cache line is two words, then you have twice as many values in your cache. It is then possible that a requested word is already in the cache, *even if you have never requested that address before*. This will happen if you previously addressed a word in the same cache-line as that word.

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


# Question
Title: To build a special unary regular expression
Say that there's a prime number P, And we can easily build an unary regular expression \[E0\]for every number that is divisible by P: E0::= (aaaa...a)\*,with p "a",

The question is, how do we build the opposite unary regular expression \[E1\], for every number that isn't divisible by P?

Do I need to build the E1 by listing all the number mod p=1,2, to p-1, or there can be a easier way to build it ?

# Answer
There is a "smart" way of following your approach: $$ (a^p)^\*a(\epsilon+a)^{p-1} $$ Here $r^p$ is shortcut for $r$ concatenated $p$ times.

This regular expression has length $O(p)$. On the other hand, using the pumping lemma it is not hard to show that the minimal NFA for the language contains at least $p$ states, and this gives a lower bound of $\Omega(p)$ on the size of a regular expression for the language, since a regular expression can be translated to an NFA with only a constant multiplicative blow-up in size.
> 4 votes

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


# Question
Title: Modeling a sequential circuit as a transition system
I was asked to model the following sequential circuits C1, C2 as transition systems (i.e. identify the output y function and register functions r1, r2, r3)

For C2 there appears to be not input x and only output y with a register R3. I assumed that there would be two possible states R3 = 0, R3 = 1 and then Y2 = !R3. But then what is the register function for R3?

For C1 I really had no idea how approach the problem as it was just an intimidating maze and while I thought it may be possible to break the circuit up and try find the functions that way, I wasn't sure. I would like to know how I can find the output and register functions of these circuits

# Answer
> 2 votes
To build a transition system from a sequential circuit, in general, one needs to define three components:

1. the states of the transition system, which are all possible combinations of values of your inputs and registers in the circuit
2. transitions between states in the transition system, which result from the functions that determine the output and the registers (according to used logical circuits and wire connections)
3. labels for states in the transition system, which consist of all variables and registers that are evaluated true given the valuations in the circuit

As per the (contrived) circuit in C2, the states reflect only the possible values of the single register. In turn, the function of the output equals to the register (`Y2=R3`), while the current value of the register is the negation of its previous value. This should give you enough insights to build the transition system.

The circuit given in C1 is indeed more convoluted, but it can be decomposed into functions on how values (for the registers and the output `Y1`) change, which then can be used to derive possible transitions in the system. (This is done with respect to possible changes of the input `X`.) For example, `Y1 = R1 && R2` and the form for the value of `R1` is `R1 = (X AND ...) OR (... AND ...)`, while the missing values `...` can be traced down according to the wire connections of the circuit.

More details on modelling sequential circuits as transition systems can be found in \[1\].

\[1\] Baier, Christel, Joost-Pieter Katoen, and Kim Guldstrand Larsen. Principles of model checking. MIT press, 2008.

---
Tags: model-checking, software-verification, transition-systems
---


# Question
Title: Is there a decision algorithm with time complexity of Ө(n²)?
Is there a decision problem with a time complexity of Ө(n²)?

In other words, I'm looking for a decision problem for which the best known solution has been proven to have a lower bound of N².

I thought about searching for the biggest number in matrix but the problem is that matrix is an input of O(n²) so the solution is linear.

It doesn't need to be known problem, a hypothetical one would suffice as well.

EDIT I looking for a regular programing problem - not a Turing Machine.

It's could be an arrays, strings, graph etc.

# Answer
> 6 votes
Yes: Checking that a string is a palindrome takes $\Omega(n^2)$ on a single tape Turing machine.

In general the time hierachy theorem implies that there are such problems for most reasonable functions.

For RAM, edit distance can't be solved in $O(n^{2-\epsilon})$ for $\epsilon \> 0$ unless the strong exponential time hypothesis is false.

---
Tags: complexity-theory, time-complexity, lower-bounds
---


title: Show a predicate is primitive recursive

text:
# Question
Title: Show a predicate is primitive recursive
Let $S(i,x\_1,\ldots, x\_n)$ be a primitive recursive predicate. \begin{equation} f(i\_1,i\_2,x\_1,\ldots, x\_n) = \begin{cases} 1 &\text{ when for all i, }\\; i\_1 \le i \le i\_2,\\; S(i,x\_1, \ldots, x\_n)=1\\ 0 &\text{ otherwise} \end{cases} \end{equation}

Show that $f(i\_1,i\_2,x\_1,\ldots, x\_n)$ is also primitive recursive

I use Davis Computability and Complexity book. I get I need to write as described in this page. Show $x^y$ is a primitive recursive function

But how to do for predicates? Even a similar example which has predicates would be very helpful.

# Answer
Do not get confused by the word "predicate". It is actually quite common to show that a function is primitive recursive by using another function for which we already know that it is primitive recursive in its definition.

For example, in the proof that multiplication is primitive recursive one usually defines multiplication using addition, which is not a basic primitive recursive function.

If "predicate" confuses you check out its definition, e.g., wikipedia. It is just a function $f: \mathbb{N} \rightarrow \\{0,1\\}$. So you can use a primitive recursive predicate just as a primitive recursive function of that kind.

All you need to show is, as mentioned in the comments, that the bounded quantification is primitive recursive.
> 2 votes

---
Tags: complexity-theory, computability, recurrence-relation, primitive-recursion
---


# Question
Title: What questions can denotational semantics answer that operational semantics can't?
I am familiar with operational semantics (both small-step and big-step) for defining programming languages. I'm interested in learning denotational semantics as well, but I'm not sure if it will be worth the effort. Will I just be learning the same material from a different point of view, or are there insights I can only gain from understanding denotational semantics?

# Answer
> 13 votes
There is no real agreement what characterises denotational semantics (see also this article), except that it must be **compositional**. That means that if $\newcommand{\SEMB}\[1\]{\lbrack\\!\lbrack #1 \rbrack\\!\rbrack} \SEMB{\cdot}$ is the semantic function, mapping programs to their meaning, something like the following must be the case for all $n$-ary program constructors $f$ and all programs $M\_1$, ..., $M\_n$ (implicitly assuming well-typedness):

$$ \SEMB{f(M\_1, ..., M\_n)} = trans(f) (\SEMB{M\_1}, ..., \SEMB{M\_n}) $$

Here $trans(f)$ is the constructor corresponding to $f$ in the semantic domain. Compositionality is similar to the concept of homomorphism in algebra.

Operational semantics is not compositional in this sense. Historically, denotational semantics was developed partly because operational semantics wasn't compositional. Following D. Scott's breakthrough order-theoretic denotational semantics of $\lambda$-calculus, most denotational semantics used to be order-theoretic. I imagine that -- apart from pure intellectual interest -- denotational semantics was mostly invented because at the time (1960s):

1. It used to be difficult to reason about operational semantics.
2. It used to be difficult to give axiomatic semantics to non-trivial languages.

Part of the problem was that the notion of equality of programs was not as well-understood as it is now. I'd argue that both problems have been ameliorated to a substantial degree, (1) for example by bisimilation based techniques coming from process theory (which can be seen as a specific form of operational semantics) or e.g Pitts work on operational semantics and program equivalence, and (2) by the developments of e.g. separation logic or Hoare logics derived as typed versions of Hennessy-Milner logics via programming language embeddings in typed π-calculi. Note that program logics (= axiomatic semantics) are compositional, too.

Another way of looking at denotational semantics is that there are many programming languages and they all look kind-of similar, so maybe we can find a simple, yet universal meta-language, and map all programming languages in a compositional manner to that meta-language. In the 1960s, it was thought that some typed $\lambda$-calculus is that meta-language. A picture might say more than 1000 words:

What is the advantage of this approach? Maybe it makes sense to look at it from an economic POV. If we want to prove something interesting about a class of object program we have two options.

* Prove it directly on the object level.
* Prove that the translation to the meta-level (and back) 'preserves' the property, and then prove it for the meta-level, and then push the result back to the object level.

The combined cost of the latter is probably higher than the cost of the former, *but* the cost of proving the translation can be amortised over all future uses, while the cost proving the property for the meta-level is much smaller than that of the proof on the object level.

The original order-theoretic approach to denotational semantics has so far not lived up to this promise, because complicated language features such as object orientation, concurrency and distributed computation have not yet been given precise order-theoretic semantics. By "precise" I mean semantics that matches the natural operational semantics of such languages.

---

Is it worth learning denotational semantics? If you mean order-theoretic approaches to denotational semantics, then probably not, unless you want to work in the theory of programming languages and need to understand older papers. Another reason for learning order-theoretic approaches to denotational semantics is the beauty of this approach.

# Answer
> 6 votes
I'll write $O(p,\sigma)$ for the only $\sigma'$ so that $\langle p, \sigma \rangle \to \sigma'$ (and $\bot$ if it doesn't exist) and $D(p)$ for the denotational semantics of $p$. Note that if you define both semantics properly, you'll most likely have $O(p,\sigma)=D(p)(\sigma)$. I'll write $S(p)$ to mean either $\sigma\mapsto O(p,\sigma)$ or $D(p)$.

Now take a compiler $C:X \to X'$. Saying that it's a compiler means that it preserves semantics, i.e. $S(C(p))=S'(p)$. If you were to try to prove that using operational semantics, you'd have to prove that for any $p$ and for any $\sigma$, $O(C(p),\sigma)=O'(p,\sigma)$. To prove it using denotational semantics, you only have to prove that for any $p$, $D(C(p))=D'(p)$. Not having to quantify on $\sigma$ often saves a lot of work.

Silly example:

$C(p)=$ replace all $(q;q')$ by $(skip;q;skip;q';skip)$.

In denotational semantics, you'll just do a proof by induction on $p$ and you'll easily get that $C$ is a compiler. In operational semantics, you'll have to take your derivations and plug pieces of derivations everywhere to account for the skips and it'll be a nightmare.

---
Tags: semantics, operational-semantics, denotational-semantics
---


title: Software mutexes and consensus number 1

text:
# Question
Title: Software mutexes and consensus number 1
There are numerous possibilities to implement a software mutex using only shared memory (e.g. Dekker's algorithm).

Recently I've read the following from a paper "Wait-free Synchronization" by M. Herlihy:

> there exists no two-process consensus protocol using multireader/multiwriter atomic registers.

And then the theorem: "Read/Write registers have consensus number 1".

I guess I am missing something in my understanding of the definitions. Shared memory is an array of atomic registers, right? And Wikipedia says Dekker's algorithm is deadlock and starvation free. So how is that possible with consensus number 1?

# Answer
> 4 votes
Herlihy's result, indeed the whole paper, is about *wait-free* synchronization. Corollary 1 states that there is no wait-free two-process consensus protocols using atomic registers. Wait-free is defined informally at the beginning of the introduction, and defined formally in the automata model in §2.3.

Dekker's algorithm is not wait-free. The busy-wait loop to enter the critical section is a wait in the sense of Herlihy. It's possible to have P0 set its `wants_to_enter` flag, then P1 sets its own, then P0 sees that P1 wants to enter and one of the processes busy-waits (depending on the `turn` value).

Think of wait-free as “must work even with a hostile scheduler”, i.e. with a scheduler that always switches between processes at the most inconvenient time. Dekker's algorithm requires a scheduler that's at least weakly fair, i.e. guaranteeing that if a process is schedulable then it's eventually scheduled (as opposed to being locked in an order of execution that causes a livelock, such as never exiting the busy-wait loop). Wait-free algorithms complete in finite time with any scheduler that doesn't completely lock up the system if there's work to do (no fairness requirement).

Busy-wait loops require the scheduler to be preemptive (otherwise the loop runs forever). In practice a busy-wait loop would be written with a yield call, and even non-preemptive schedulers try to avoid immediately re-scheduling a process that just yielded. But even with a preemptive scheduler, busy-wait is generally bad: if nothing else it uses up CPU time and electricity. A case where Dekker's algorithm doesn't work at all is if the two processed have different priorities and the scheduler never schedules the process that would enter the loop because the busy-waiting process has a higher priority.

A naive solution to avoid waiting is to put in a time delay. It isn't a good solution because in practice it means an additional useless delay when there is contention on the mutex, and in theory the delay isn't enough since the scheduler could take that long to make its decision and so end up scheduling the busy-wait loop only anyway. A good solution avoid busy-wait altogether is to add a primitive that lets a process block until some shared variable is modified; with such a primitive, I think it's easy to achieve an infinite consensus number.

It is instructive to contrast Dekker's algorithm with a wait-free consensus solution, such as the one Herlihy gives for two processes (fig. 7).

```
prefer[P] := input
if RMW(r,f) = v
  then return prefer[P]
  else return prefer[Q]
end if

```

`RMW` is a primitive operation with a consensus number of at least 2, for example test-and-set. There's no busy-wait in the consensus protocol itself: both processes run pretty much instantly, without ever waiting for the other one. In a real scenario, the processes that doesn't acquire the mutex may well wait for it; but the process that does acquire the lock isn't stopped, and in practical terms that means at least an expected performance gain both when there is contention and when there isn't.

---
Tags: concurrency, mutual-exclusion
---


# Question
Title: Why does the cumulative order in which nodes are first visited with Iterative deepening is effectively breadth-first
I have had comparative algorithm exercise to do about algorithm propoerties such as completeness, time complexity, memory complexity... I discovered **Iterative deepening depth-first search algorithm**.

On Wikipedia, it is said that it visits the nodes in the search tree in the same order as depth-first search, *but the cumulative order in which nodes are first visited is effectively breadth-first*.

I know what breadth-first algorithm is but I don't understand that last sentence... What does it actually means?

# Answer
> 1 votes
What this statement means is that if you list the order in which vertices are "discovered" (first visited) in iterative deepening DFS, then it will be the same order in which vertices are discovered in BFS.

---
Tags: algorithms, search-algorithms
---


# Question
Title: Algorithm Complexity Analysis on functional programming language implementations
I've learned today that algorithm analysis differs based on computational model. It is something I've never thought about or heard of.

An example given to me, that illustrated it further, by User @chi was:

> E.g. consider the task: given $(i,x\_1 ,…,x\_n )$ return $x\_i$ . In RAM this can be solved in $O(1)$ since array access is constant-time. Using TMs, we need to scan the whole input, so it's $O(n)$

This makes me wonder about functional languages; From my understanding, "Functional languages are intimately related to the lambda calculus" (from a comment by Yuval Filmus on here). So, if functional languages are based on lambda calculus, but they run on RAM based machines, what is the proper way to perform complexity analysis on algorithms implemented using purely functional data structures and languages?

I have not had the opportunity to read Purely Functional Data Structures but I have looked at the Wikipedia page for the subject, and it seems that some of the data structures do replace traditional arrays with:

> "Arrays can be replaced by map or random access list, which admits purely functional implementation, but the access and update time is logarithmic."

In that case, the computational model would be different, correct?

# Answer
It depends on the semantics of your functional language. You can't do algorithm analysis on programming languages in isolation, because you don't know what the statements actually mean. The specification for your language needs to provide sufficiently detailed semantics. If your language specifies everything in terms of lambda calculus you need some cost measure for reductions (are they O(1) or do they depend on the size of the term you reduce?).

I think that most functional languages don't do it that way and instead provide more useful statements like "function calls are O(1), appending to the head of a list is O(1)", things like that.
> 6 votes

---
Tags: complexity-theory, algorithm-analysis, computability, computation-models, lambda-calculus
---


title: Enumerating sets in a random order

text:
# Question
Title: Enumerating sets in a random order
I have multiples arrays. I'd like to enumerate all sets containing exactly one item from each array in a (pseudo-)random order, without explicitly building the array of all sets.

Any solution, even with poor pseudo-randomization, is welcome.

EDIT: Example for clarity:

Say I have arrays

```
A = { a1, a2 }, B = { b1, b2 }, C = { c1 }

```

I want to enumerate all the sets containing exactly one ax, bx and cx

```
{ a1, b1, c1 }, { a1, b2, c1 }, { a2, b1, c1 }, { a2, b2, c1 }

```

I want to enumerate them in a random order. The naïve solution would be to enumerate them in an array, then shuffle this array. But the solution is huge and I don't want to store it explicitely in memory.

# Answer
> 4 votes
Suppose that you have arrays $A\_1,\ldots,A\_d$ of sizes $n\_1,\ldots,n\_d$. The total number of tuples is thus $n\_1 \times \cdots \times n\_d$. Given a number in the range $1,\ldots,n\_1 \times \cdots \times n\_d$, you can decipher it into a tuple (I leave this part to you). It now remains to compute a pseudorandom permutation of the numbers $1,\ldots,n\_1 \times \cdots \times n\_d$, another task I leave to you.

---
Tags: algorithms, sets, randomness, enumeration
---


title: "Functorial" reductions?

text:
# Question
Title: "Functorial" reductions?
If I understand correctly, $\mathsf{NC}^0$ reductions are taken as the formalization of the concept of "local" reduction, i.e., a reduction that acts locally on substructures of the instances of the problem to be reduced: they map fixed-size "gadgets" of the source problem to fixed-size structures of the target problem. It is my (hopefully correct) understanding that this kind of reductions occur ubiquitously in structural complexity theory.

An example: to reduce CIRCUIT VALUE to MONOTONE CIRCUIT VALUE (or MCV), one applies the following local transformations, which "double" every gate and every input (see e.g. Cook and Nguyen's *Logical Foundations of Proof Complexity*, proof of Theorem VIII.1.7, or slide 6 of this): $$ \begin{align\*} a &\mapsto (a\_+,a\_-) \\ 0 &\mapsto (0,1) \\ 1 &\mapsto (1,0) \\ \lor(a,b) &\mapsto (\lor(a\_+,b\_+),\land(a\_-,b\_-)) \\ \land(a,b) &\mapsto (\land(a\_+,b\_+),\lor(a\_-,b\_-)) \\ \lnot(a) &\mapsto (\land(a\_-,a\_-),\land(a\_+,a\_+)) \end{align\*} $$ After applying this transformation, we obtain a monotone circuit with $2$ outputs, call them $o\_+$ and $o\_-$, such that the value of the output $o\_+$ is exactly the value of the original circuit ($o\_-$ is its negation). To obtain an instance of MCV (a circuit with only one output), one simply projects on $o\_+$, which means plugging a constant (i.e., independent of the original circuit) $2$-input, $1$-output circuit to the outputs of the circuit obtained above.

The whole operation is obviously in $\mathsf{NC}^0$, because bounded-depth circuits can not only implement the local transformation above (taking gadgets to substructures) but can also add arbitrary "constant" substructures (in this case, circuits), where "constant" means depending only on the size of the source instance.

I am interested in reductions which are, so to speak, "purely functorial", in the sense that they map gadgets to substructures but are not allowed to add any "constant". In the above example, the first part of the reduction would be functorial, whereas projecting on the $o\_+$ output breaks functoriality. My question is:

> Have "functorial" reductions ever been considered and, if so, under what name and for what purpose?

(The term "functorial" comes from the identity $F(f\circ g)=F(f)\circ F(g)$ which is at the basis of the definition of functor. If one sees problem instances as freely built out of basic gadgets, then functoriality means exactly "gadget to substructure". One could also say "homomorphic". Another analogy may be made with linear algebra: functorial reductions would be linear maps wheras $\mathsf{NC}^0$ reductions are affine maps).

I am pretty sure that "functorial" reductions are too restrictive to be of general interest. For instance, I do not see how CIRCUIT VALUE could be $\mathsf P$-complete under such reductions. However, the variant of CIRCUIT VALUE in which one asks for the value of a *specified* output out of possibly many, would still be $\mathsf P$-complete (this "multi-output" variant is of course equivalent to CIRCUIT VALUE under $\mathsf{NC}^0$-reductions), as well as the similar variant of MCV. So the notion is not completely void of significance. Also note that "functorial" reductions are incomparable w.r.t. projections: they are more general in one sense (the local dependence is not necessarily "bitwise") but more restrictive in another (projections are still allowed to add arbitrary substructures, i.e., break functoriality).

# Answer
> 2 votes
You might be interested in the Universal Algebra point of view of Constraint Satisfaction Problems; see for example this survey by Libor Barto. One classical result in this area is Schaefer's dichotomy theorem.

---
Tags: complexity-theory, reductions
---


# Question
Title: How does the 3-opt algorithm for TSP work?
I understand that the 3-Opt Heuristic for solving the Traveling Salesman problem involves removing three edges from a graph and adding three more to recomplete the tour. However, I've seen many papers that mention that when three edges are removed, there remain only 2 possible ways to recombine the tour - this doesn't make sense to me.

For example, I found a paper \[1\] that says:

> The 3-opt algorithm works in a similar fashion, but instead of removing two edges we remove three. This means that we have two ways of reconnecting the three paths into a valid tour1 (ﬁgure 2 and ﬁgure 3). A 3-opt move can actually be seen as two or three 2-opt moves.

However, I count 3 different ways to reconnect the tour. What am I missing here?

Also, can someone link me to an algorithm for 3-opt if possible? I'm just trying to understand it, but I haven't come across any clear algorithms yet: all resources I find simply say "remove three edges, reconnect them". That's it, which is sort of vague.

Here are the 3 tours that seem to me to be 3-opt moves after removing three edges.

---

1. Heuristics for the Traveling Salesman Problem by C. Nilsson

# Answer
> 6 votes
You missed the footnote — these ways are "not including the connections being identical to a single 2-opt move". Indeed, there are only two permutations in $S\_3$ without fixed points (also known as *derangements*), namely $(123)$ and $(132)$. More generally, for a $k$-opt move it is enough to consider permutations without fixed points, since those with $t$ fixed points are $(k-t)$-moves.

The algorithm for $k$-opt local search is as follows. Start with some initial solution, say the one produced by Christofides's algorithm. Repeatedly try to improve it by performing a $k$-opt: choose $k$ edges and reconnect them in a different way (this time it's OK if the move is also an $\ell$-move for some $\ell \< k$) that results in a shorter tour.

The way this is implemented is by going over all sets of $k$ edges and over all ways of reconnecting the edges, perhaps in some intelligent order, and computing the difference in length (there is no need to recompute the length of the entire tour, just the different of length; that takes $O(k)$ instead of $O(n)$); if an improvement is found, we make the switch and repeat from the beginning. We continue like that until we get stuck.

A different variant is to always try all possibilities, and use the one that results in the best improvement. There are also other variants which you can probably find in the literature.

# Answer
> 0 votes
Lets say we have 3 points A, B and C. First we swap(A,B) and then we only can swap(B,C) or swap(A,C). This way we only have two different possibilities.

# Answer
> 0 votes
I could find 4 3-opt moves (which are not 2-opt):  If i gave the hexagon tour a numbering of 123456 (starting from the top left vertex), the other tours would have numbers of 125634, 124365, 126534 and 125643, which are a subset of the derangement of 12\[3456\] (where 3456 is being deranged).

---
Tags: algorithms, optimization, heuristics, traveling-salesman
---


# Question
Title: In what cases is graph rewriting not enough to avoid duplicate work?
As I understand, evaluating something like the following in normal order evaluation is inefficient due to duplicate work:

```
double x = (x,x)
main     = double some_hard_computation

```

I remember someone telling me

* That there are two ways to avoid this: strictness analysis (to recognise that `double` is strict in its one argument, and then deviating from normal order evaluation and evaluate the argument first) and graph rewriting (store pointers to `some_hard_computation` such that both elements of the tuple point to the same computation, and evaluating one side of the tuple automatically evaluates the other side as well).
* That neither of the ways are sufficient on their own to avoid all cases where duplicate work can be introduced, and that it is best to apply both when writing a compiler.

I can imagine that strictness analysis can be hard, but in what concrete case can duplicate work be introduced when utilising graph rewriting? Or is either of the two bullet points above incorrect?

*Note*: while strictness analysis is done statically (as far as I know), graph rewriting is an evaluation strategy, not a compiler optimisation. It attempts to solve the same problem as the strictness analyser, but on a different level (runtime vs. compile time).

# Answer
> 2 votes
Consider this program:

```
f (m : Nat) x y = (x, if H(m,m) then x else y)

my_f = f my_number
my_f hard harder

```

where `H(x,x)` returns `True` if Turing machine number `x` halts on input `x` and `False` otherwise. Detecting duplicate work (always) would mean solving the halting problem, no matter whether you want to do the analysis statically or dynamically.

Hence, no method can be complete.

---
Tags: compilers, functional-programming, term-rewriting, evaluation-strategies
---


title: Proof of Diameter of a network topology

text:
# Question
Title: Proof of Diameter of a network topology
How do I prove that diameter of undirected Ring Topology is n/2?

# Answer
To prove that the diameter of the undirected ring topology is $n/2$:

1. Find two vertices $x,y$ at distance $n/2$.
2. Show that any two vertices $x,y$ are at distance at most $n/2$.

By the way, the diameter is more accurately $\lfloor n/2 \rfloor$.
> 1 votes

# Answer
I tried this:
If n is even then n/2th node is the **farthest node**, else (n-1)/2th or (n+1)/2th node would be the farthest node.
In case of 'n' nodes the number of edges is 'n'
Assuming : If we have a ring of n/2 nodes(in case of **even** number of nodes) or (n-1)/2 (in case if n is **odd**) then the number of edges would be n/2 or (n-1)/2 for the rings to be connected which we can consider as the diameter.

Hence, n/2 with a lower bound would be the answer.
> 0 votes

---
Tags: graphs, computer-networks, network-topology
---


# Question
Title: Can you operate on and draw conclusions on functions described asymptotically?
This question is homework based (not using actual problem though)!

Say you have a function described as:

$$f(n) \in O(2n^2) \\, .$$

Can you then go on the treat this as:

$$f(n) = 2n^2$$

and performs mathematics on it and keep its asymptotic meaning?

In the above case could I conjecture that $f(n) \in O(2n^2)$ implies $f(n) / 2 \in O(n^2)$ (assuming coefficients matter in this example)?

# Answer
> 8 votes
For some operations, such as addition, multiplication, you can operate directly on the asymptotic notation. For example, if $\small g(n) = \mathcal{O}(n^2)$ and $\small f(n) = \mathcal{O}(n^2)$, then $\small g(n) + f(n) = \mathcal{O}(n^2)$ and $\small g(n) \cdot f(n) = \mathcal{O}(n^4)$. For some other operations, such as division, it depends then. For example, for $\small g(n) = \mathcal{O}(n^2)$ and $\small f(n) = \mathcal{O}(n^2)$, it is not correct to say $\small \frac{g(n)}{f(n)} = \mathcal{O}(1)$ (consider $\small g(n) = n^2$ and $\small f(n) = n$). However, if $c$ is a fixed constant, then $\small \frac{g(n)}{c} = \mathcal{O}(n^2)$.

# Answer
> 3 votes
To answer questions like your conjecture, use the definition of $O$. Paraphrasing from wikipedia at time of writing:

$f \in O(g)$ iff $f(x) \leq M\times g(x) $ for all $ x \> x\_0 $, for some constants $M$ and $x\_0$.

So if $f(n) \in O(2n^2)$, then $f(n) \leq C \times 2n^2 \ \ \forall n \> n\_0$ for some constants $C$ and $n\_0$ (I'm calling it $C$ instead of $M$ to avoid confusion later). You'll notice we can combine the $2C$ into one constant, which tells you $O(2n^2) = O(n^2)$.

What can we say about $f(n)/2$? We can now use normal algebra on the inequality, such as dividing both sides by 2 to get:

$f(n)/2 \leq Cn^2 \ \ \forall n \> n\_0$

Is this still $O(n^2)$? To check this, we need to find constants $M$ and $x\_0$ such that the definition above holds. In this case, $M = C$ and $x\_0 = n\_0$ works. Notice that $M = 327.6C$ is also valid; you can use whatever method you want to find these constants, as long as you know they are constant.

In the real world you'll be able to "shortcut" most of this when doing your analysis, as NP-hard does in his answer, but those *are* just shortcuts for writing it out rigorously like this (which is what I would expect on homework specifically about $O$). If you're not sure whether it's valid, get the $O$s out by using the definition, perform algebra on the inequality, then get it back into $O$ by finding the appropriate constants (or simply showing that they do exist).

---
Tags: asymptotics, landau-notation, mathematical-foundations
---


# Question
Title: Is converting boolean formulas to sum-of-products a hard problem?
My reasoning is as follows.

1. Every boolean formula can be expressed as a sum-of-products.
2. Every sum-of-produts is a list of minterms.
3. For each minterm, there is 1 combination of inputs that satisfy the formula.

So if I have the sum-of-products representation of a boolean formula I can tell if it satisfiable.

But that is the SAT problem, which is hard.

So the hard part of the 3 step procedure above must be transforming a boolean formula into a sum of products.

Is this reasoning right?

# Answer
> 1 votes
Your reasoning is correct. Your "sum-of-products" is more commonly known as disjunctive normal form (DNF). It is easy to show that conversion from conjunctive normal form (CNF) to DNF is NP-hard, so converting from general Boolean formulas to DNF can't be any easier.

---
Tags: complexity-theory, satisfiability, normal-forms
---


# Question
Title: How to show that a language {w|ww^R in A} is regular, A being regular?
Been working on my homework and I've been stuck on a question for over a week now. Not really asking for a solution but if someone could point me towards the right direction that would be great, as I have literally no idea of how to go about this. A previous question asked us to show that for any DFA that accepts A, we can create a NFA that accepts {wR | w in A}, which was pretty easy (just reverse the DFA).

This question asks: Show that if A is a regular language, then so is {w|wwR in A}, where wR is the reverse of the string w.

I know that if I have two regular expressions, then their concatenation is also a regular expression, that's simple. But this asks me to show that the first-half of *some* of the strings in A is a regular expression. No idea how to show that this is true. It's not even intuitive to me that this *is* true, except that the question implies it is.

Anyone got any idea of where to start about this? Thanks!

# Answer
You might want to study If $L$ is a regular language then so is $\sqrt L=\\{w\mid ww∈L\\}$.

The solution is to simulate the DFA in parallel with itself, from both sides of the string. For each letter one step forward (for $w$) and one step backward (for $w^R$). If the forward state reading $w$ reaches the same state as the backward simulation, both parts joined form a computation on $ww^R$.
> 6 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: Proving that quantum circuits not involving entanglement are inefficient
I heard in a video that it can be proven that quantum circuits not involving entanglement can be efficiently simulated on a classical computer; i.e., that there is no point to building quantum circuits not involving entanglement. I have heard this referenced elsewhere in google searches, but nowhere can I find this proof mentioned. What is the proof of this?

# Answer
A general state of $n$ qubits can be written as follows :

$|\psi\rangle = \sum\limits\_{x=0}^{2^{n-1}}\alpha\_x|x\rangle$

Which means you need $2^n$ complex numbers to describe an arbitrary state of $n$ qubits.

A non entangled state on $n$ qubits can be written in the following way:

$|\psi\rangle = \bigotimes\limits\_{i=1}^{n}\left(\alpha\_i|0\rangle + \beta\_i|1\rangle\right)$

Which means we only need $2n$ complex numbers to describe it. If we assume that we only deal with circuits such that two different qubits are never entangled, this property holds throughout the entire computation.

This is enough to see how to simulate the circuit, always remember the $2n$ complexes describing your non entangled state, and apply the desired operators on specific qubits (remember that it is garunteed that applying cnot will not result in entanglement).

That said, don't take this as evidence to the fact that quantum computing without entanglement doesn't extend classical computation in any way. For example, see this paper (Quantum computation without entanglement, Eli Biham et al). They reproduce some known results in the blackbox model (which are impossible on a classical computer) without entanglement.
> 2 votes

---
Tags: proof-techniques, quantum-computing, circuits
---


# Question
Title: Why unsafe state not always cause deadlock?
I was reading Operating Systems by Galvin and came across the below line,

> Not all unsafe states are deadlock, however. An unsafe state may lead to deadlock

Can someone please explain how *deadlock != unsafe* state ? I also caught the same line here

> If a safe sequence does not exist, then the system is in an unsafe state, which MAY lead to deadlock. ( All safe states are deadlock free, but not all unsafe states lead to deadlocks. )

# Answer
> 17 votes
*Deadlock* means something specific: there are two (or more) processes that are *currently* blocked waiting for each other.

In an *unsafe* state you can also be in a situation where there *might* be a deadlock sometime in the future, but it hasn't happened yet because one or both of the processes haven't actually started waiting.

Consider the following example:

```
Process A                  Process B
lock X                     lock Y           # state is "unsafe"
                           unlock Y
lock Y                                      # state is back to "safe" (no deadlock this time.  We got lucky.)

```

There's a more interesting example in Section 7.5.1 of the link you gave:

> Consider a system with 12 tape drives with:

```
Process       Max Need       Current
P0:             10              5
P2:              9              3

```

This is an unsafe state. But we're not in a deadlock. There's only 4 free drives, so, for example, if P0 *does* request an additional 5, and P2 *does* request an additional 1, we will deadlock, but it hasn't happened yet. And P0 might *not* request any more drives, but might instead free up the drives it already has. The `Max need` is over all possible executions of the program, and this might not be one of the executions where we need all 10 drives in P0.

# Answer
> 10 votes
Just to expound on what Wandering Logic was saying.

Say I have two threads that both need access to X and Y, and have no synchronization and no mechanism to fix deadlock. This is unsafe, as one could lock X and the other Y and then neither could proceed. But it isn't guaranteed.

```
Thread 1                    Thread 2
Lock X
Lock Y
OS Interrupts Thread 1 and passes control to Thread 2
                            Unable to lock needed resources.
OS Interrupts Thread 2 and passes control to Thread 1
Unlock X
Unlock Y
                            Lock Y
                            Lock X
 ....

```

This scenario didn't wind up in deadlock, but it could have. Due to the way threading works, there isn't a set flow. The OS controls the threading and so it could occur something like the following:

```
Thread 1                    Thread 2
Lock X
OS Interrupts Thread 1 and passes control to Thread 2
                            Lock Y
DEADLOCK Thread 1 needs Y, Thread 2 needs X. Neither knows to back down and simply waits.

```

# Answer
> 1 votes
Safe state is deadlock free for sure, but if you cannot fulfill all requirements to prevent deadlock it might occur. For example if two threads may fall in deadlock when they start thread A, then thread B, but when they start the opposite (B, A) they will work fine - let me assume B is nicer ;) The state of system is unsafe, but with fortunate starting sequence it will be working. No deadlock, but it is possible. If also you synchronize them by hand - start in good order - it is hazardous - for some reason they might not be fired as you like - system still is unsafe (because of possible deadlock) but there is low probability to that. In case of some external events like freezing threads or interupts after continuing it will fail.

You have to realise - safe state is sufficient condition to avoid deadlock, but unsafe is only nessesary condition. It is hard to write code out of head right now, but I can search for some. I did encountered code in Ada that more than 99/100 times it was perfectly working for several weeks (and then stopped due to server restart not deadlock) but once in a while it was crashing after several seconds into deadlock state.

Let me add some easy example by compare to division: If your function divides c / d and returns result, without checking whether d is equal 0, there might be division by zero error, so code is unsafe (same naming intended), but until you do such division, everything is fine, but after theoretical analysis code is unsafe and might fall into undefined behaviour not handled properly.

# Answer
> 0 votes
A trivial unsafe state: Thread 1 takes lock A, then lock B, then unlocks both. Thread 2 takes lock B, then lock A, then unlocks both.

This will only lead to a deadlock if Thread 2 takes lock B *just* between Thread 1 taking lock A and trying to take lock B, or Thread 1 takes lock A *just* between Thread 2 taking lock B and trying to take lock A.

If Thread 1 and Thread 2 do this randomly once an hour, and there is a microsecond gap of time that would actually lead to a deadlock. this can run a very long time in the hand of customers until eventually you get a deadlock by chance.

Walk across a street with your eyes closed. It's unsafe. But you don't *always* get killed.

# Answer
> 0 votes
Here is my understanding on this (please correct me if I am wrong): (A) If deadlock, means there exist a cycle (one of the necessary condition) (B) A cycle is mandatory condition for deadlock (for both single and multi instance resources)

So we can prove now that there exist a cycle which may not lead to deadlock,  You can see here a cycle exist meaning an unsafe state is found, but this might not lead to a deadlock since resource R2 which is participating in cycle may break the cycle as soon as process P3 finishes and releases it (remember P3 is not having any dependency or waiting for any other resource).

---
Tags: operating-systems, deadlocks
---


# Question
Title: What happens internally when you remove an object from a treemap
I am wondering what happens if you remove an object in the middle of a treemap. If the treemap would look something like this:

So what would happen if you remove the number 30? Because 27 and 34 will disconnect from the tree.

# Answer
> 2 votes
I think there are two cases here

1. **Java Collections implementation** : In this case Java uses red black tree to keep the tree balanced and to maintain the order. Thus if you are removing a node in such a tree it will adjust itself without breaking anything and will form a perfect BST even after removal. Red black trees are self balancing trees so it will also arrange itself to maintain log(n) height where n is the number of nodes. Thus for sure you will not lose any data here.
2. **Your custom implementation** : In this case you have to do all the painful things which I have explained above. However you have an option to maintain the order or to rebalance the tree as per your requirements.

---
Tags: data-structures, search-trees, dictionaries, binary-search-trees
---


# Question
Title: What is the advantage of heaps over sorted arrays?
I'm fairly new to heaps and am trying to wrap my head around why min and max heaps are represented as trees when a sorted array appears to both provide min / max properties by default.

And a follow up: what is the advantage of dealing with the complexity of inserting into a heap given an algorithm like quick sort handles sorting very well?

Context: I'm working through CLRS / MIT 6.006 in python and have only seen integer representations of leaf values. Is this more applicable in a language like C where each leaf contains a struct that can't easily be sorted?

# Answer
> 29 votes
$\small \texttt{find-min}$ (resp. $\small \texttt{find-max}$), $\small \texttt{delete-min}$ (resp. $\small \texttt{delete-max}$) and $\small \texttt{insert}$ are the three most important operations of a min-heap (resp. max-heap), and they usually have complexity of $\small \mathcal{O}(1)$, $\small \mathcal{O}(\log n)$ and $\small \mathcal{O}(\log n)$ respectively if you implement a min/max-heap by a binary tree.

---

Now suppose instead you implement a min-heap by a sorted (non-decreasing) array (The case for max-heap is similar). $\small \texttt{find-min}$ and $\small \texttt{delete-min}$ are of $\small \mathcal{O}(1)$ complexity if $\small \texttt{insert}$ is not required in your application, since you can maintain a pointer $\small p$ that always points to the minimum element in your array. When the minimum element is removed, you just need to move $\small p$ one step to the next element in the array.

Dealing with insertion in a sorted array is not trivial. Given a new element $\small e$, we can use binary search to locate its position in the array to insert it. But the point is that if you want to insert it there, you have to move a lot of old elements (can be $\small \mathcal{O}(n)$) around to make a vacancy for the new element to reside. This is quite inefficient for most applications. You may also choose to re-sort the array after an element is inserted, this requires $\small \mathcal{O}(n\log n)$ time however.

---

The last point, how you implement a data structure really depends on your application. **NO** single implementation is best for all cases. Analyze your application, find out the most frequent operations, and then decide the appropriate implementation.

# Answer
> 6 votes
To answer your questions, you have to define which different actions you will perform and how often, and you have to evaluate the time complexity of each action.

Which method is performing better overall will depend on the individual complexities and how often each action is performed.

Sorting an array has a very high time complexity; heap operations are so cheap that they are actually used for a decent sorting implementation. Using a heap to find the smallest element is definitely a lot faster than sorting an array. Two heaps for the smallest and largest element are still a lot faster (but that situation is quite rare; for example in a horse race everyone wants to know the winner, but nobody cares who comes last).

Where a heap absolutely, completely beats sorting arrays is a situation where small numbers of items are removed or added, and after each change you want to know again which is the smallest element.

---
Tags: data-structures, arrays, heaps
---


title: Creating a decision tree?

text:
# Question
Title: Creating a decision tree?
So I'm trying to split on an attribute "Color" that has possible values (Blue,Green,Red,Orange,Pink).

I'm splitting on entropy values, and the best split can either be Multi-Way 5, Multi-Way 4, Multi-Way 3, or Binary. For example:

```
5: (Blue, Green,Red,Orange,Pink)

4: (Blue, Green), (Red), (Orange), (Pink)
   (Green,Pink), (Blue),(Red),(Orange)

3: (Red,Orange), (Blue,Green), (Pink)
   (Red,Blue), (Green, Orange), (Pink)

2: (Blue,Green,Red), (Orange,Pink)
   (Pink), (Blue, Green, Red, Orange)

```

And so on. But how can I make a comprehensive list of all the possible splits? Is there a specific algorithm I could use? Or how would I even know how many max possible combinations there are with this?

Any help would be greatly appreciated, thanks!!!

# Answer
> 2 votes
The entropy of a given attribute is non increasing over refinement of partitions. This means that the best possible partition is singletons (one value per set). This is the method used for discrete attributes in known algorithms such as ID3 or C4.5.

As a side note, the number of partitions is given by Bell's number.

---
Tags: trees, enumeration, bdd
---


# Question
Title: Why do depth-limited search algorithm and BFS have different memory complexity?
Let be $b$ the branching factor of the tree.

Let be $d$ the depth of the shallowest solution.

Let be $l$ the limit given to depth-limited search algorithm

Why is depth-limited search algorithm memory complexity $\mathcal O(b)$ times something (which is actually $\mathcal O(bl)$) whereas BFS is $\mathcal O(b)$ power something (which is actually $\mathcal O(b^d)$)?

# Answer
> 1 votes
> Let be b the branching factor of the tree.
>
> Let be d the depth of the shallowest solution.
>
> Let be l the limit given to depth-limited search algorithm

**Breadth-first search (BFS)**

In the worst case, suppose that our solution is at depth d, and we expand all nodes but the last node at level d, then the total number of generated nodes is $ O(b^{d}) $.

As all these nodes must retain in memory while we expand our search, then the space complexity is $O(b^{d})$.

**Depth-limited search algorithm**

Unlike BFS, Depth-limited search algorithm has a very modest memory requirements, it needs to store only the path from the root to the leaf node, beside the siblings of each node on the path. Depth-limited search algorithm removes a node from memory once all of its descendants have been expanded.

DFS requires storage of only $O(bl)$ nodes thus space complexity is $O(bl)$.

---
Tags: algorithm-analysis, space-analysis, searching
---


# Question
Title: Best improvements to do to the DPLL SAT algorithm
As part of a college class, I'm asked to improve the performance of a basic DPLL sat solver. I'm already provided a basic, slow working version (essentially the DPLL algorithm; furthermore, to select the next variable, it just loops an array and gets the next unused one). I have been reading papers on ways to improve it, but I'm a bit overwhelmed by the amount of optimizations one can do. I'm not looking to make an extremely efficient solver; just something that works better than a plain basic DPLL one. I have read about 2WL, VSIDS, and a handful more. Which optimizations will give me the most performance without overcomplicating things? The input with the most variables that I have to solve is of the order of 300, with 1500 clauses, if that is of any interest.

I apologize if something similar has been asked before, but I haven't found anything. I would appreciate any other tips if you guys have. Thank you.

# Answer
> 2 votes
The most improvement with the least effort will come from adding rapid random restarts to your solver. DPLL is known to exhibit heavy-tailed behavior, producing both short and long search times for instances depending on initial search conditions. Random restarts allow the solver to bail out of exponentially long searches of unfruitful assignments and give the solver more chances to find one of those short searches sooner.

Implementing two-watched-literals will produce the next big improvement because it eliminates a major backtracking cost. Backtracking is done exponentially often in the worst case, so any improvements there offer unequivocal improvements in search speed. Implementing two-watched-literals will require a significant overhaul of your solver, but it will teach you a lot about how real-world SAT solvers work.

# Answer
> 0 votes
I suggest to implement CDCL with 1-UIP (UIP = unique implication point) as heuristic to minimise the learned clause. Use 2WL to speed up unit-propagation. See here for a basic implementation of CDCL in Python.

Things like VSIDS make sense only for CDCL, and are used to prune learned clauses. CDCL has a tendency to learn too much. But if you have only approx. 1.5k clauses, you should probably be able to live without pruning,

---
Tags: algorithms, satisfiability, sat-solvers, program-optimization
---


# Question
Title: The difference between dense graph and sparse one
How to decide whether the following statement is correct?

O(E log E) and O(E log V) are equivalent regardless whether graph is dense or sparse

# Answer
> 1 votes
You have to be careful with your definitions. For any graph, the number of nodes and the number of edges is a constant, so $O(V) = O(E) = (1)$. This is clearly not helpful.

*Sparse* and *dense* only make sense for a *family* of graphs $\\{G\_n\\}\_{n=1}^\infty$.

The edge density of a graph $G$ is the proportion of possible edges that a graph actually has:

$$ D = \frac{|E(G)|}{{|V(G)|}\choose{2}}. $$

The edge density of a family of graphs is

$$ D = \lim\_{n \to \infty} \frac{|E(G\_n)|}{{|V(G\_n)|}\choose{2}}. $$

The family is *sparse* if $D = 0$ and *dense* if $D \> 0$. You must analyze the performance of your algorithm under either type of family as inputs.

This definition is from Diestel's *Graph Theory*.

# Answer
> -1 votes
> In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph.

A **sparse graph** is a graph $G=(V,E)$ in which $|E|=O(|V|)$.

For example, consider a graph $G=(V,E)$ with n nodes. Suppose that the out-degree of each vertex in $G$ is some fixed constant k. Graph $G$ is a sparse graph because $|E|=k|V|=O(|V|)$.

**\[UPDATE\]** If $N$ and $E$ are the number of nodes and edges in a network respectively. $N^2$ possible edges in a fully connected network.

Sparseness $P = \frac{E} {N^2} $

If $P \<\< 1$, then the network is sparse.

Source: MIT OpenCourseWare

A **dense graph** is a graph $G=(V,E)$ in which $|E|=O(|V|^2)$.

For example, consider a graph $G=(V,E)$ with n nodes. $|E|=f|V|^2=O(|V|^2)$.

> How to decide whether the following statement is correct?
>
> O(E log E) and O(E log V) are equivalent regardless whether graph is dense or sparse

In the case of $O(E log E)$ and $O(E log V)$,

asymptotically $log E \approx log V$ and only $E$ contributes to the result regardless the graph is dense or sparse.

Thus, $O(E log E) \approx O(E log V)$ for any dense or sparse graph.

---
Tags: graphs, terminology, landau-notation
---


# Question
Title: Big O notation question for set insertion with sequential scan?
A friend and I are asking some questions on Big O Notation.

1. We have an operation that requires a sequential scan on insertion of an element O(n).
2. The insertion itself of an element is O(1).
3. We are inserting a whole set of *n* items.

We both agree the time for insertion is *O(n+1)* or simply O(n) reduced. But, we have two questions..

1. Does Big O Notation ever refer to the time for a set operation such as insertion of a whole set, or only to an individual elements operation on the set?
2. Can we ever say the time for an "insertion of a whole set of n size is O(n\**2)" per the above?

# Answer
> 2 votes
First of all, let's get some things straight. Big-Oh notation is just a notation for describing the asymptotic behavior of *any* mathematical function (well, at least those defined on the real numbers). It is *not* tied to algorithm analysis.

Performing algorithmic analysis on a program $p$ that takes input $x$, you want to find a function $f(n)$ so that, for every input $x$ of size $n$, one has $T(p(x)) \leq f(n)$, where $T(p(x))$ denotes the run-time of a program. That is, we are finding the *worst-case* bound on the run-time of $p$.

Now, it may very well be the case that

$$T(p(x)) \leq e\times n^{3/2} + 2.73 \log\_{\pi} \sqrt n \times + .23432342 $$

However, this is not very useful. It's difficult to conceptualize the growth of this function. That is one reason we use asymptotic bounds (the other being it is often easier to determine the asymptotic behavior than the exact behavior). It is much more approachable to write

$$ T(p(x)) = O(n^{3/2}) $$

Anyway, to answer your question: you'll note here that $p$ is an arbitrary program. You can take that program to be whatever you like, including "insert $n$ elements into the set". No one can tell you what to analyze.

---
Tags: landau-notation
---


# Question
Title: Draw a Directed Acyclic Graph from a makefile
I am completely new to Analysis of Algorithms and I have to draw a Directed Acyclic Graph from the makefile below. (I know what a DAG is). My question is simple: should I do it just by watching the makefile or is there an algorithm I can use? All I want is to be oriented so I have a way to start.

An additional question about this problem is: How many valid orderings exist for processing the makefile? I will very much appreciate your feedback for this second question.

```
project: main.o utils.o command.o
    cc -o project main.o utils.o command.o
main.o: main.c defs.h
    cc -c main.c
utils.o: utils.c defs.h command.h
    cc -cutils.c
command.o: command.c defs.h command.h
    cc -c command . c

```

# Answer
> 1 votes
Although it is not entirely clear from the exercise, it looks like you should make a dependency graph. A dependency graph has *nodes* for the *objects* that can depend on each other, and an edge from $x$ to $y$ when $x$ depends on $y$ (or the other way around, depending on the definition).

In a Makefile, the objects are the targets and files. Dependencies can be directly read from the Makefile in the target lines: the targets depend on that what comes after the colon.

---
Tags: graphs, algorithm-analysis
---


# Question
Title: Is it possible to solve the Mountain Car reinforcement learning task with linear Q-Learning using the state as direct input?
I'm trying to solve the Mountain Car task on OpenAI Gym (reach the top in 110 steps or less, having a maximum of 200 steps per episode) using linear Q-learning (the algorithm in figure 11.16, except using maxQ at s' instead of the actual a', as required by Q-learning; I've solved it with other methods easily, the question is about linear Q-learning). Also, I'm using 1 output for each action, so I can select an action in a single forward pass. Important: my input features are the identity function of the state, i.e., the state variables themselves. I know it can be solved with other features, I want to know about this one specifically.

Here is a description of the algorithm I'm using: https://youtu.be/vVDKzIxzkzQ

Unfortunately, this method never solves the task. Actually, it rarely reaches the top. I'm aware that vanilla Q-learning has no convergence guarantees, so I tried some variants which reduce or even solve this issue: I've tried experience replay, double q-learning, GTD and advantage learning. Nothing helped.

I know that this task can be solved linearly on the state inputs directly, since I've done it by manually tuning the weights so the car always apply the force in the same direction as its velocity, so the representation is not an issue. But it seems that the learning algorithm is.

So the question is: **is linear Q-learning able to learn the mountain car task directly from the state variables?** A paper where the author solves this task with Q-learning in a single-layer network (and shows the algorithm or code) with features = state variables would be enough.

# Answer
> 3 votes
I just found out the answer and it's actually pretty simple: while there is a good linear policy for the mountain car task, the value function itself is non-linear.

The state space of this task is like a spiral, and there is no linear approximation possible even for a mediocre value function. If you increase the value for going right and reaching the top, going left will have the lowest values. This is why the car never reaches the top.

By applying a simple random projection and transforming the input space, it is possible to show that the task becomes linearly solvable (with a value-based method).

---
Tags: reference-request, reinforcement-learning, gradient-descent
---


# Question
Title: Why complement of most negative number in octal does not turn out to be itself
I know the range of the $n$ digit numbers in $r$'s complement system is given as

> $r^{n-1}-1$ to 0 to $-r^{n-1}$.

So for 3 bit 2's complement, its:

> $(2^2-1)$ to $0$ to $-(2^2)$
> that is
> $3$ to $0$ to $-4$
> that is
> $(011)\_{\text{2's comp}}$ to $(0)\_{\text{2's comp}}$ to $(100)\_{\text{2's comp}}$

And for 3 digit 8's complement, its

> $(8^2-1)$ to $0$ to $-(8^2)$
> that is
> $63$ to $0$ to $-64$
> that is
> $(077)\_{\text{8's comp}}$ to $(0)\_{\text{8's comp}}$ to $(700)\_{\text{8's comp}}$

Now I came to know that

> the $r$'s complement of the smallest / most $-$ve number in the range will be the same number.

For example, taking 2's complement of most $-$ve / smallest number possible with 3 bit 2's complement system, $(100)\_{\text{2's comp}}$ is itself:

```
1 0 0
0 1 1 (1's complement)
1 0 0 (add 1 to get 2's complement)

```

But taking 8's complement of most $-$ve / smallest number possible with 3 digit 8's complement system, $(700)\_{\text{8's comp}}$ does not seem to be itself:

```
7 0 0
0 7 7 (7's complement)
1 0 0 (add 1 to get 8's complement)

```

So 8's complement of 700 does not seem to be 700 itself but is in fact 100. So what I am missing? Or I am doing it all wrong?

# Answer
First of all, if you are considering the $n$th digit of the number as being a *sign digit*, you can think of it as being either 0 or 1, no matter the value of $r$. In other words, it is always a **bit** (a binary digit), and that's how you would represent it in hardware, should that be the case.

> $\[1\]73\_{\text{8's comp}} = -5$
>
> $\[1\]73\_{\text{8's comp}} + \[0\]06\_{\text{8's comp}} = \[0\]01\_{\text{8's comp}}$

The complement of a negative number represented in $r$'s complement will obviously produce the positive version of that same number. The most negative number doesn't have a positive of the same magnitude that fits into the given number of digits (a weakness of this form of representation).

The number is still there, though, only unsigned:

> $\[1\]00\_{\text{8's comp}} = -64\_{10}$
>
> $100\_8 = 64\_{10}$
> 0 votes

# Answer
The smallest 3-digit 8's complement number is not 700, but 400.

Indeed, the assertion at the start of the question is already wrong: as long as $r$ is even, the actual range is from $-\tfrac r2r^{n-1}$ to $\tfrac r2r^{n-1}-1$.
> -1 votes

---
Tags: arithmetic, number-formats
---


# Question
Title: Compute equality comparison without comparison operators
Is there a possibility to compute the result of an integer equality comparison by only using arithmetic or bitwise operations? Negative values use the two-complement representation.

I am looking for a generic algorithm, which results in two possible values for equality and inequality but not using comparison operations.

# Answer
> 5 votes
Let $W$ be the number of bits, $A, B$ integers to compare.

$Result = (NOT((A - B) \text{ OR } (B - A))) \>\> (W - 1)$.

Here NOT negates bits. $A - B$ and $B - A$ is zero iff numbers are equal otherwise they are of different signs which ORed together will give a negative number.
The result is $1$ if numbers are equal and $0$ otherwise.

# Answer
> 1 votes
Iff they're unequal their xor will have at least one bit set. You can test the resulting word for zero in various ways, for instance by or'ing all the bits together, or known bit hacks. Specifically, (Z-1)&(~Z & 1\<\<(wordsize-1)) to check if Z is zero, by seeing if subtracting 1 carries all the way to the high bit.

# Answer
> 0 votes
Since all arithmetic operations return an integer, and the result of an equality comparison must be a boolean, this is clearly impossible.

Edit for updated question:

This should do the trick in C:

```
int cmp(int a, int b) {
  return !!(a-b)

```

This function returns 0 if the argument are equal, and 1 otherwise.

If $a = b$, then $a-b=0$. The first bang (the logical *not* operator) will transform the 0 into a 1, and the second will transform it back into a 0.

If $a \neq b$, then $a - b \neq 0$. The first bang will then transform the result into 0, and the second to 1.

---
Tags: algorithms, arithmetic
---


# Question
Title: Big-O comparison different arrangements of similar code
The following code should have a run time of $O(N)$,

```
int min = INTEGER.MAX_VALUE;
int max = INTEGER.MIN_VALUE;

for (int x : array) {
    if (x < min) min = x;
    if (x > min) max = x;
}

```

but what about the following code?

```
int min = INTEGER.MAX_VALUE;
int max = INTEGER.MIN_VALUE;

for (int x : array) {
    if (x < min) min = x;
}
for (int x : array) {
    if (x > min) max = x;
}

```

# Answer
Its **O(N)**. When there are consecutive loops, we calculate time complexity as sum of time complexities of individual loops.

```
for (int i = 1; i <=m; i += c)
{
        // some O(1) expressions
}
for (int i = 1; i <=n; i += c)
{
        // some O(1) expressions
}

```

Time complexity of above code is `O(m) + O(n)` which is `O(m+n)` If `m == n`, the time complexity becomes `O(2n)` which is `O(n)`.
> 1 votes

---
Tags: algorithms, runtime-analysis, loops
---


# Question
Title: Any algorithm better that O(N*logN) for a problem of finding student with largest average score in a list of N scores of the form StudentID, score
Question: Suppose you are a given a csv with N lines of the form StudentID, score. Multiple lines can have same student-ID. Find the student with maximum average score

I can't think of any way to make it faster than O(N\*logN).

1. Maintain a hash-table that keeps track of STudentID = Key and Value being an object with sum of scores and number of scores seen with that studentID --\> O(N)
2. Create an array with values in hash table, maybe convert each entry into average while doing so
3. Sort it worst-case N(logN), all entries belong to same student

Is there any way to do it faster?

# Answer
You are on a good path, but seem to be confused for no reason. After step 2 you have created an array with average scores. This is a worst case O(N) size array. What is the complexity of finding the highest average score now? Do you need to sort the array?
> 5 votes

# Answer
@megas has the right approach. All I want to add is another, yet more involved solution:

* you can calculate averages **online**, instead of computing it at the end. You need to maintain the count and average. For every score update and before updating the count, `new_avg = (old_avg*count + score)/(count + 1)`. Then update the count.
* now that you have all student averages at any point in time, you can take advantage of order-maintenance solutions to keep your set of student scores ordered at all times.

Note that by doing this, you're paying the time tax on keeping all student scores sorted. That's why @megas has the better solution because you're interested in the max score.
> 0 votes

---
Tags: algorithms, arrays, algorithm-design
---


# Question
Title: Context Free Grammar for Try-Catch-Finally Statement and Throw
I am currently working on a problem that is asking me to write the grammar productions for the try-catch-finally and throw C# statements. It states that "you can assume that there are nonterminals "Type", "Expression", and "Statement", as well as a terminal "Ident". I do not understand how this is possible using so few nonterminals and only one terminal

# Answer
> 3 votes
You need more terminals, for the reserved words `try`, `catch`, `finally`, and `throw`, and possibly for braces and for semicolon (depending on the interpretation of *Statement*).

Here is an example to help you get started. It gives the syntax of a simple if statement, assuming that *Statement* also includes compound statements (i.e. `{ ... }`), and that statements do not end in a semicolon.

IfStatement → **if** **(** Expression **)** Statement

---
Tags: formal-grammars, parsers
---


# Question
Title: Can we have a poly time reduction from 2-SAT to 2-Coloring problem?
I know that given a 2-Coloring instance we can easily convert it into a 2-Sat instance in polynomial time . Is the reverse possible? i.e given a 2-sat instance can we convert it into an 2-Coloring instance in poly time?

# Answer
As rotia mentions in their comment, to make the question meaningful we must restrict the power of the allowable reductions. The two most obvious choices are to allow only logspace reductions or only AC0 reductions.

Since 2SAT is NL-complete (with respect to logspace reductions) whereas 2COL (2-colorability) is in L (this is a non-trivial result which follows from Reingold's theorem), if there is a logspace reduction from 2SAT to 2COL then L=NL, which is considered unlikely. Hence we do not expect such a reduction to exist; a fortiori we do not expect an AC0 reduction to exist.
> 9 votes

---
Tags: reductions, satisfiability
---


# Question
Title: Reference request for coding Knight's Tour
Could someone give an easily accessible reference containing an algorithm that could be conveniently implemented into a code for computing Knight's Tour (preferably also with fairly good efficiency)?

# Answer
The idea is that we have a board of size $n \times n$, where $n$ is say 8 for your usual chessboard. We start from one of the corners (typically), and place a knight chess piece to this corner cell. The question is, can we move the knight through the board such that we visit each cell exactly once?

In graph theoretic terms, this is the Hamiltonian path problem, which *in general* is NP-complete. The Warnsdorff's rule you describe in the comments is a way to solve the problem pretty efficiently in practice. More generally, the Warnsdorff's rule is a *fail first heuristic*. This means that by running into dead-ends quickly, we prune the search tree aggressively, and thus succeed quickly.

For a programming exercise (and for the easiness of presentation), it is convenient to represent the graph as an implicit graph: you will have no explicit graph stored, but instead you can just store the coordinates visited, and compute the edges "on the fly".

* At every step, your knight is in position $v$ on the board. The set of possible next moves is given by the successor function ("what unvisited cells I can move to from my position $v$?"), let us denote the possible next cells by $N(v)$.
* When considering what cell $u \in N(v)$ to pick, we look at the degree of the vertices in $N(v)$. In this case, the degree of a vertex $u \in N(v)$ is given by the *number of possible moves the knight can take from $u$*.
* Let $N^\delta(v)$ denote the set of neighbors of a vertex $v$ with the smallest degree. Our goal is to choose the vertex with the smallest degree; this is really easy if there is only one choice, i.e. if $|N^\delta(v)| = 1$. If this is not the case, we can employ some *tie breaking strategy*.
* A simple and a pretty effective tie breaking strategy is to pick the next vertex $u \in N^\delta(v)$ uniformly at random -- this is simple to implement as well.

For a programming exercise, I definitely recommend using implicit graphs, and also not fixing the chess piece as a knight. Instead, build say an array of moves your piece can take -- it's pretty fun to try to see how the set of possible moves affect path finding. It's also fun to experiment with vertex choosing heuristics other than Warndorff's, and similarly with tie-breaking strategies.
> 2 votes

# Answer
For accessibility, implement the board as a 12x12 grid. The squares in the outer 2 rows/columns are initialized to 'have been visited.' Now you don't have to bother checking x and y coordinates for boundary conditions. Your knight can't go to those squares and thus can't leap off the board into hyperspace. An old version of Sargon used this technique.

Then you'll need a 2x8 array for the offsets to move the knight:

```
a[0][0] = 2, a[0][1] = 1
a[1][0] = 2, a[1][1] = -1
a[2][0] = 2, a[2][1] = 1
a[3][0] = -2, a[3][1] = -1
(etc)

```

The first row means you'd move your knight up-2-and-one-to-the-right. The last row means you'd move the knight back-2-and-one-to-the-left.

Initialize the board to all -1's. Each time you make a move, stamp the move number onto the board. You can't move to a square that has a number greater than -1.

Preparation:

```
1. create a 12x12 board.
2. initialize the outer 2 rows and columns to 0 so the knight can never visit them. only squares with a value of -1 can be visited.
3. initialize the 8x8 center to -1.
4. Create the 2x8 knight array as described above.

```

To start the tour, jump! Note the 0, which is the first move. The x and y coordinates of 6 are wholly arbitrary.

```
IF (Jump(0, 6, 6)) output the board
ELSE print "There was no solution";

function Jump(moveNumber, x, y) BEGIN
    if (board[x, y] has been visited) return FALSE;
    board[x, y] = moveNumber;
    IF (moveNumber == 63) THEN return TRUE -- Success!

    FOR(i=0; i<8;i++) BEGIN
        IF (Jump(moveNumber+1, x+x_offset[i], y+x_offset[i])) return TRUE
    END

    -- If we get here, we fail. There is no solution going forward, we must backtrack.
   board[x, y] = -1  // Don't forget to restore the board!
   return FALSE
END FUNCTION

```

This is your garden variety brute-force algorithm. It is not speedy. The wiki page shows some optimizations. They can be generalized as 'fail early, fail often.' For example, after every successful leap, if you can find a isolated square, you can safely fail.

Also, it is possible to nitpick the algorithm I present. No amount of tweaking will make it run appreciably faster. The run time in the problem is in its fundamental difficulty, not where we do a few checks or variable assignments. For example, it would be possible to move to the FOR loop the check to see if a square has already been visited. You would save a few seconds, maybe. That is, this pokey algorithm might run in an hour instead of 3,602 seconds.

An interesting thing about this problem is that the starting position of the knight greatly influences how long it takes to find a solution. And because the knight-offset array is independent of the starting position, the board is not really symmetric. That is, starting in the upper left column might yield a solution much sooner than starting in the lower right.
> 1 votes

# Answer
A computer program that solves the knight's Tour is published in 'Century/Acorn User Book of Computer Puzzles' edited by Simon Dally https://openlibrary.org/books/OL15157004M/Book\_of\_computer\_puzzles
> 1 votes

---
Tags: algorithms, graphs, reference-request
---


# Question
Title: How to simulate systems' unavailability?
I am simulating a system where the clients' unavailability is one big issue to the systems behavior.

I gathered the real system logs to analyze the unavailability of the clients in the deployment environments and I computed the values for **Mean Time Between Failure (MTBF)** and **Mean Time To Repair (MTTR)**.

Now I want to simulate such a system failure in my simulator. Currently what I am doing is as follows:

```
1. Every client rolls the dice every 1 minute (Uniform random in [0, 1])
2. If the number if larger than a specified probability (P_unavail),
   the client becomes unavailable for the next (T_unavail) minutes (i.e. (T_unavail) = 10min).

```

The simulation does not need to capture the whole details of the real world. Showing the trends (how often the failure occurs? how long does the repair take?) is indeed enough. However, the simulation method and parameters should not be arbitrary.

If any one who has some knowledge on it.

* Is the method that I am using appropriate?
* If yes, what values for P\_unavail and T\_unavail would be appropriate? Can I compute them MTBF and MTTR from the log analysis?
* If no, could you give me any idea?

Thanks,

# Answer
Fix some probability distribution for failures and failure duration and sample from there. Maybe a Poisson distribution for failures and a normal distribution for repair times would make sense. Compare the results from your sampling with the real data to see whether things match.
> 1 votes

---
Tags: simulation, modelling
---