# Question
Title: $L = \{x\#x^R \mid x\in\{0,1\}^* \} $ not accepted by a queue automaton?
It can be proven that class of languages accepted by queue automata is equal to class of languages accepted by Turing machines. It was mentioned somewhere that the language $$L = \\{x\\#x^R \mid x\in\\{0,1\\}^\* \\} $$ can not be accepted by a queue automaton. But the language is accepted by a TM. Can somebody explain this apparent contradiction?

# Answer
If a queue automaton is Turing-Complete, then it can compute (decide) any function (language) that a Turing machine can. And we know that TM can decide both $L = \\{x\\#x^R \mid x\in\\{0,1\\}^\* \\}$ and $L = \\{x\\#x \mid x\in\\{0,1\\}^\* \\}$, thus both can be decided by a queue-automaton.

"How?" you ask? For this you need to understand how a queue-automaton works. It starts with the input already in the queue (where the end of the input is marked by a special character $\\$$), and then at every move it reads the letter at the head of the queue and can insert one **or more** characters to the end of the queue.

Let $M$ be a TM. The way to simulate $M$ over the queue automaton is to keep reading content out of the queue and then putting it back into the end of the queue. This allows us to make multiple passes over the "tape" of the TM. For instance, assume the queue holds "abc$". A "Cycle" (a pass on the queue) will look like (plotting the queue content):

```
 abc$ -> bc$a -> c$ab -> $abc -> abc$

```

and we are back to square one, allowing the machine now to take another pass on the input.

It is then trivial to simulate the TM moves as long the head moves to the right, or stays in place: we can denote the heads place by a special symbol ($\to$) that points on where the TM head looks at. E.g., at the very first move we do:

```
abc& -> bc$→a -> c&→ab -> ... -> →abc$

```

Then moving the head to the right is elementary:

```
→abc& -> abc$ -> bc&a→ -> ... -> a→bc$

```

It is a bit more tricky to simulate a move of the TM head to the left, because seemingly, we need to put the head even before we see the next letter that causes the move back.

The trick here is to use the current state in order to "keep one letter in the memory". So when we see a letter, we don't immediately put it back to the queue, but we "remember" it using a state (e.g. if the states of the TM are $q\_1,q\_2,..$ etc, we will move to $q\_1^a$ if we see an `a` or to $q\_1^c$ if we see a `c`, etc.) Before putting the letter back to the queue we first we check the next letter, and if it is not the head, we put it back, If it is the head, we may move the head as needed.

The cycle of moving the head left will look something like the following:

```
a→bc$ ->(remember a using states)-> →bc$a -> bc& -> (*)

```

at this point the machine knows it needs to move the head to the left. It remembers `a` and so it put it back in the queue, now remembering `b` using the current state

```
-> c$→a -> $→ab -> ... -> →abc$

```
> 1 votes

---
Tags: formal-languages, automata
---


title: Why aren't tries generally used?

text:
# Question
Title: Why aren't tries generally used?
To store say integers (positive), we prefer to use red black BSTs. I have never seen a explicit use of a trie anywhere to store numbers. I believe we can convert numbers to string and store them in tries for fast retrieval. Is it a bad idea to use tries? We don't use them because they are hard to code and there are libraries for BSTs or is there some other reason?

# Answer
This is an interesting question. Certainly worth asking.

The choice of a data structure is very much dependent on what you want to do with it. A more costly sophisticated structure, no matter how smart, is a bad choice if you can meet your need with something cheaper in space or time.

As I was writing this answer, I discovered that the wikipedia article on tries does discuss to a significant extent comparison of tries with other data structures.

One advantage of binary search trees (BST) is that they keep ordered lists, for some arbitrary order that can be tested. Actually the order is often used only to help organization and retrieval, but there are applications where you want to actually access the elements of your ordered subset following the order of elements. BST will provide you with such an order.

I do not see any obvious way of doing it with tries for an arbitrary order (but I did not try hard). However, tries do work with lexicographic order, and can be used for lexicographic enumeration of the keys, using simply a preorder traversal of the tree implementing it.

Similarly, asking for the current rank of an element in the set represented by a BST , or accessing an element by its current rank is fairly easy to implement in $\log n$ time (by keeping track of the weight of subtrees). It seems not so tractable on a trie, except again if one is interested in lexicographic order, in which case the solution is similar to that used for BST.

Another point to consider is cost of basic operations (insertions, deletions, search). With a balanced BST it is done in $\log n$ time, where $n$ is the number of elements. For a trie, the cost is linear in the size of the element representation. It is hard to compare the two kinds of cost, and one would think the choice is very much problem dependent. This also applies to such operation as access by rank, or rank retrieval.

The cost of number representation in a BST or in a trie may also be an issue, as a trie will represent each digit separately (up to some optimizations). It is possible that, for very large numbers, expressed with a large base, the trie representation would be a better choice. I am not sure.

There is probably more to say. The conclusion is that it is probably worth thinking whether tries can be used, but it may be actually limited.
> 6 votes

---
Tags: data-structures, search-algorithms, binary-trees, search-trees, balanced-search-trees
---


# Question
Title: Why is my proof wrong for $L = H_{TM} \cap \overline{A_{TM}} $
$A\_{TM} = \\{\<M,w\> | $ M is a TM and M accepts w $\\}$

$H\_{TM} = \\{\<M,w\> | $ M is a TM and M halts on w $\\}$

I thought that $L = H\_{TM} \cap \overline{A\_{TM}} \in R$

But I saw the proof for why $L \in RE \setminus R$

But I don't understand why this is wrong:

$H\_{TM} \in RE$ and $\overline{A\_{TM}} \in Co-RE $

We know that $RE \cap Co-RE = R$

So why is this wrong $L = H\_{TM} \cap \overline{A\_{TM}} \in RE \cap Co-RE = R$ ?

# Answer
$RE$ and $co-RE$ are sets of sets of strings. $H\_{TM}$ and $\overline{A\_{TM}}$ are sets of strings. You correctly have that $H\_{TM}\in RE$ and $\overline{A\_{TM}}\in co-RE$. However, you cannot then conclude that $$ H\_{TM}\cap\overline{A\_{TM}}\in RE\cap co-RE $$ For a simple example, let $$ A=\\{\\{1\\},\\{2\\}, \\{1, 3\\}, \\{2, 3\\}\\}\text{ and }B=\\{\\{1\\},\\{3\\}, \\{1, 2\\}, \\{2, 3\\}\\} $$ So $A$ will serve as $RE$ and $B$ will serve as $co-RE$. Then we have $A\cap B=\\{\\{1\\},\\{2,3\\}\\}$. Now let $x=\\{1,3\\}\in A$ and $y=\\{2,3\\}\in B$ (here $x$ serves as $H\_{TM}$ and $y$ serves as $\overline{A\_{TM}}$). Then $x\cap y=\\{3\\}\notin A\cap B$.
> 2 votes

---
Tags: turing-machines, undecidability
---


# Question
Title: How to apply a 1-qubit gate to a single qubit from an entangled pair?
Reading about superdense coding I came upon a calculation I can not understand.

We have an EPR entangled pair of qubits $\frac{1}{\sqrt2}(|00\rangle + |11\rangle)$ and we want to apply a Pauli X gate to the first of the entangled qubits. On wikipedia, there is an example showing that such an operation would lead to the state $\frac{1}{\sqrt2}(|10\rangle + |01\rangle)$. I can't see an intuition behind it. I know that the Pauli X gate operates as a quantum NOT, but at the same time I do not know how to write it algebraically.

**How can a single qubit from an entangled pair be represented?** Is it $\frac{1}{\sqrt2}(|0\rangle + |1\rangle)$ for the pair above? And if so, why does the Pauli X gate change it at all (if we wrote the operation using matrices, the qubit would be represented as $\left\[\frac{1}{\sqrt2} \frac{1}{\sqrt2}\right\]$, which multiplied by the Pauli X gate matrix would not change at all...)

# Answer
I came to a conclusion that we do not actually take away a single qubit from an entangled pair and operate it, but **operate on both qubits with Identity operator on the one we do not want to change.**

So basically to apply Pauli X gate to the first qubit from an entangled pair, we apply X tensored with $I$ to the entangled pair to get the result. That is, to operate a not on the first qubit, we evolve the system by $$ \sigma\_x \otimes I = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \otimes \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0& 0 \end{pmatrix} $$

Intuitively it is like applying a single operation to the first qubit and identity to the second one (effectively not changing its state).

Thus if we start with the entangled state $|\psi\rangle \frac{1}{\sqrt2}(|00\rangle + |11\rangle)$ we end up with $$ (\sigma\_x \otimes I)|\psi\rangle = \begin{pmatrix} 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0& 0 \end{pmatrix} \cdot \frac1{\sqrt{2}} \begin{pmatrix}1 \\0 \\0 \\1 \end{pmatrix} = \frac1{\sqrt{2}} \begin{pmatrix}0 \\1 \\1 \\0 \end{pmatrix} = \frac1{\sqrt{2}}(|01\rangle+|10\rangle) $$
> 9 votes

# Answer
@3yakuya

I think you made a mistake writing the multiplication between Pauli Matrix X tensor product with Identity matrix, you wrote

$$ \sigma\_x \otimes I = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \otimes \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1& 0 \end{pmatrix} $$

the correct one is

$$ \sigma\_x \otimes I = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \otimes \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0& 0 \end{pmatrix} $$

Claim: Why I say this is true; because according to the definition of Tensor Product, they apply as following, and Tensor product doesn't follow the commutative rule; so for example $ A \otimes B =! B \otimes A $; if that were true, then both the above products are correct..

so the answer would be the same (this is not always true)

$|\psi\rangle = \frac{1}{\sqrt2}(|00\rangle + |11\rangle)$ $$ (\sigma\_x \otimes I)|\psi\rangle = \begin{pmatrix} 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0& 0 \end{pmatrix} \cdot \frac1{\sqrt{2}} \begin{pmatrix}1 \\0 \\0 \\1 \end{pmatrix} = \frac1{\sqrt{2}} \begin{pmatrix}0 \\1 \\1 \\0 \end{pmatrix} = \frac1{\sqrt{2}}(|10\rangle+|01\rangle) $$

---

Note: 1 - I would like to comment in the "comment box" but I couldn't so this is why I write this in "Answer box" ..

2 - I would see how @3yakuya will respond because may be he has an argument.
> 4 votes

# Answer
While you have found the answer to your main question yourself, let me answer the sub-question you asked as part of the main question:

> How can a single qubit from an entangled pair be represented?

A single qubit from an entangled pair cannot be represented by a state vector, but has to be represented by a density matrix. More exactly, it is represented by the partial trace over the other qubit of the entangled state's density matrix.

For example, for the state $$\left|\phi^+\right\rangle = \frac{1}{\sqrt{2}}\left(\left|00\right\rangle + \left|11\right\rangle\right)$$ the corresponding two-qubit density matrix is the projector onto that state: $$\rho\_{\phi^+}=\begin{pmatrix} \color{green}{\tfrac{1}{2}} & \color{green}{0} & \color{red}{0} & \color{red}{\tfrac{1}{2}}\\ \color{green}{0} & \color{green}{0} & \color{red}{0} & \color{red}{0}\\ \color{blue}{0} & \color{blue}{0} & 0 & 0\\ \color{blue}{\tfrac{1}{2}} & \color{blue}{0} & 0 & \tfrac{1}{2} \end{pmatrix}$$ Here I've marked with the same colour the elements which belong to the same indices for the first qubit; for example, the $\color{green}{\text{green}}$ numbers are those matrix elements where both indices of the first qubit are $\color{green}{0}$.

Now the partial trace over the second subsystem just means the trace over those submatrices: $$\operatorname{tr}\_B \rho\_{\phi^+} = \begin{pmatrix} \color{green}{\tfrac{1}{2}} & \color{red}{0}\\ \color{blue}{0} & \tfrac{1}{2} \end{pmatrix}$$ Note that this is the completely mixed one-qubit state. That is, the single qubit has a completely undetermined state.

Note that also the state of the second qubit is completely mixed. Which shows that the information about the entangled state is not in the individual qubits. This can also be seen in the fact that the information in half of the density matrix elements is completely ignored by the partial trace (this includes in particular the upper-right and lower-left $\frac{1}{2}$ elements, which are exactly what distinguish that entangled state from a separable equal mixture of the states $\left|00\right\rangle$ and $\left|11\right\rangle$).
> 3 votes

---
Tags: quantum-computing
---


title: NP hard relation with NP complete

text:
# Question
Title: NP hard relation with NP complete
If any problem P is NP complete then if there is a polynomial time reduction of P to another problem R then what can we say about R.Is it NP-hard or NP complete ?
From Theory of computation of Hopcroft,Ullman theorem 10.4 it says it would be NP complete but there some times when i see that it is NP-Hard in some other reference . is there any condition when it is NP Hard or NP Complete .Or i misunderstood the theorem .

# Answer
NP-hard means that all the problems *in* NP reduces to this. NP-complete means that it is *in* NP as well.

Sometimes we say a problem is NP-hard when it is obviously NP-complete. But this is because we want to stress the hardness of the problem, and also that it should be trivial that the problem is *in* NP.
> 4 votes

# Answer
A problem L is NP-complete when:-

1. L $\epsilon$ NP
2. Every problem L' $\epsilon$ NP, L' is polynomial time reducible to L

> For at least property 2 satisfied but do not know if 1st property (or not necessarily property 1) is satisfied by a problem L, then L $\epsilon$ NP-Hard.

For proving a problem satisfies property 1, best we can do is check if for any given input an algorithm can verify the solution in polynomial time, i.e., problem is polynomial time verifiable given a certificate of a solution as input.

For proving a problem satisfies property 2, it is difficult to prove all L' individually are polynomial- time reducible to L. Hence we make use of transitivity property of the polynomial reductions.

> If we are able to show that a problem L'' already known to be in NP-complete to be polynomial-time reducible to the problem L, then L satisfies property 2 by transitivity.

**Transitivity - If L1 is polynomial-time reducible to L2 and L2 is polynomial-time reducible to L3, then L1 is polynomial-time reducible to L3 by transitivity.**

So, every L' is polynomial-time reducible to L'' (already NP-complete) and we prove L'' is polynomial-time reducible to L implies every L' is polynomial-time reducible to L.

In the case in the question, P (= L'') is already known to be in NP-complete. So, P is polynomial-time reducible to R(= L) implies R satisfies property 2. Hence, **R $\epsilon$ NP-Hard** for sure. For R $\epsilon$ NP-complete it requires to be NP too.
> 1 votes

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


# Question
Title: Learning a small disjunction using an input distribution of our choice
I have a boolean function $f: \\{0,1\\}^n \to \\{0,1\\}$ that I know takes the form

$$f(x\_1,\dots,x\_n) = x\_{i\_1} \lor x\_{i\_2} \lor \dots \lor x\_{i\_k}.$$

I don't know the values of $i\_1,\dots,i\_k$, but I do know $k,n$. My goal is to recover $i\_1,\dots,i\_k$ from the value of $f$ on randomly chosen inputs, using as few evaluations of $f$ as possible.

There's a twist. I can choose any efficiently sampleable distribution $D$ on $\\{0,1\\}^n$ that I want, depending on $k,n$. A referee will pick $f$, randomly sample many values of $x$ from $D$ (iid), and then give me $(x,f(x))$ for each such $x$. Then, my ultimate task is to infer $i\_1,\dots,i\_k$.

I'm looking for an efficient algorithm to select $D$ and then recover $i\_1,\dots,i\_k$, given the pairs $(x,f(x))$. How efficiently can this be done? What distribution $D$ is optimal? The most relevant complexity measure is probably the number of pairs needed. Randomized algorithms are OK. I'm particularly interested in the regime where $k \ll n$.

This is a generalization of a prior question of mine, where I showed that if we take $D$ to be the uniform distribution on $\\{0,1\\}^n$ then $\Theta(2^k \lg n)$ pairs are necessary and sufficient. However, it seems likely that the uniform distribution is not optimal. I suspect we can do better by choosing a distribution $D$ that is biased towards values of $x$ with lower Hamming weight.

On first glance, it feels like maybe we can restrict attention to distributions $D$ that is symmetric (i.e., $x$ and $\pi(x)$ have the same probability, for all permutations $\pi$ on the $n$ bits). For instance, we could consider a distribution $D$ where the bits of $x$ are iid Bernoulli(p), for some parameter $p$. Is this right, and if so, what is the optimal distribution $D$ and how many pairs does this mean we will need?

This is motivated by an application in inferring input-output relationships in programs (black-box taint analysis).

# Answer
> 1 votes
$\Theta((k+1) \lg n)$ pairs are sufficient. I think this is the best that's achievable.

Here's the distribution $D$ that achieves this result. Let $p = 1/(k+1)$ and choose each bit of $x$ from Bernoulli(p) (i.i.d.), i.e., each bit of $x$ is $1$ with probability $p$ and $0$ otherwise.

Call $x$ *good* if $f(x)=0$. Note that if $x$ is chosen according to $D$, it has probability $(1-p)^k$ of being good. This is $(1-1/(k+1))^k$, which is approximately $e^{-1}$ (using the standard approximation $(1-y)^z = e^{-yz}$). So, $\Pr\[f(x)=0\] \approx 1/e$, and about a constant fraction of pairs are good.

Now we can take all of the good pairs we have, and look for bit positions that are consistently zero in every good pair. If we have enough good pairs, only correct positions $i\_1,\dots,i\_k$ should remain. Fix a particular incorrect bit position; it has a probability $p$ of being eliminated by each good pair, so the probability that it survives all the good pairs is $(1-p)^g$, where $g$ is the number of good pairs. Taking $g = -2\lg(n)/\lg(1-p) \approx 2 \lg(n)/p$, we find that the probability of survival for a single incorrect bit position after all $g$ good pairs is $1/n^2$. By a union bound, this means the probability that any of the incorrect bit positions survive is about $1/n$. In other words, if we have $2\lg(n)/p$ good pairs, with overwhelming probability this procedure will succeed in correctly inferring $i\_1,\dots,i\_k$.

Putting these two together, we need about $2e \lg(n)/p$ pairs. Since $1/p=(k+1)$, this is $\Theta((k+1)\lg n)$.

It's possible to show that this is the best possible value of $p$. Define $f(p) = p (1-p)^k$. Then $$f'(p) = (1-p)^{k-1} (1-(k+1)p),$$ since $f'$ is zero at $p=1/(k+1)$, and one can verify that the maximum value of $f(p)$ on the interval $\[0,1\]$ is attained at $p=1/(k+1)$. Now the total number of pairs needed by the above procedure is $2 \lg(n)/f(p)$, which is minimal for $p=1/(k+1)$. This justifies the choice of $p$ suggested above.

I'd conjecture that you can't do better than this class of distributions $D$ (where each bit of $x$ is chosen iid Bernoulli). If that is right, then it follows that the result given above is the best possible: $\Theta((k+1)\lg n)$ pairs are necessary and sufficient to solve this problem.

---
Tags: algorithms, machine-learning, boolean-algebra, learning-theory
---


title: Pipelining and Preemption

text:
# Question
Title: Pipelining and Preemption
According to the concepts of ***Pipelining***,

> In a single cycle different stages of different instructions are executed.

Now I have a bit of confusion here, that *if a single processing element is there and can perform one processing at a time* , **then -**

Do the preemption occurs multiple times in a single cycle in order to complete the different stages of different instructions inside the pipeline ?

If so, then does this mean that clock cycle duration is larger than the time quanta assigned to execute each stage of an instruction ?

For Example -

**In Cycle 2** \- below given stages of different instructions is to be executed -

> IF of instruction5, ID of instruction4, EX of instruction3, MEM of instruction2,
>
> WB of instruction1

OR the pipelining works only when there are multiple processing elements ? If I am missing something ?

Please explain or provide some helpful links for me to clear my doubts.

Thanks in Advance !

# Answer
Your question reminds me of an old joke:

If the Atlantic can be crossed in 7 days with one boat, you can cross it in one day, if you have seven boats available. (there are actually many variants)

Your problem is the problem of **assembly lines** in general, and that is the technical model of a pipelined processor.

On the assembly line for making car (I am of course simplifying), you will have one fellow placing the doors, another one placing the bumpers, one placing the wheels, another painting the car. They all work at the same time, doing their job in the duration of a single *car making cycle*, fixed by the big clock on the factory wall.

Every cycle, the last worker of the line finishes one car, while the first does the initial steps of making a new one. So there is exactly one car produced for each cycle. There is a single assmbly line (read: **a single processor**), producing one car with each cycle.

But it does not mean that it takes only one cycle to produce a car. It takes as many as there are stages in the assembly line. The rate of production (read processing rate) of one car per cycle is only a average over time.

The idea that that it is more efficient to have *specialized* workers working independently. But you do not want to keep them idle, when it is not their turn on a given car.

And, it may not be necessary that each car is built identically to the previous one. All you need is that each worker gets his part of the instruction(s), such as the diameter of the wheels to be placed, or the color of the paint. So the instructions may change, while going through the same assembly line to produce cars.

No one ever preempts the line to get something done. But all contributing workers are synchronized.
> 2 votes

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


# Question
Title: Is an infinite language of halting TM is in $RE$? in $RE \setminus R$?
> Let an **infinite** language, $L$, which contains only TM which halt for every input (meaning, decides some language). Is $L$ in $R$ ? in $RE \setminus R$ ?

I've understood that the answer is: **it depends on what exactly $L$ is**.

So basically I'm trying to think of two scenarios for $L$ - one which $L\in R$ and one which $L\in RE \setminus R$, but haven't come up with something useful so far.

I'd be glad for help.

# Answer
The empty set $\emptyset$ satisfies trivially the constraint as all the TM it contains (actually none) halt for all input. But the emptys set is also in $R$ since it is very easy to decide whether a TM is in it: the answer is always NO. But unfortunately, this example cannot be used, because we hav a requirement that the set $L$ of TM be infinite (Thanks to @FrançoisG for reminding me).

So we choose another simple counter example, the set $L\_{\emptyset,0}$ of TM recognizing the empty language that halt and reject after 0 steps, but may have a lot of useless states and transitions. There is also an infinite number of such machines, and it is easy to see by inspection of its transitions whether a TM is in $L\_{\emptyset,0}$. Thus $L\_{\emptyset,0}$ is infinite and recursive.

Since the set $L\_{\emptyset,0}$ is recursive, there is a computable bijection $\phi: \mathbb N\to L\_{\emptyset,0}$

Then given any subset $S$ of $\mathbb N$, we can get get with the bijection $\phi$ a subset $\phi(S)\subset L\_{\emptyset,0}$ which has the same level of computability.

Thus if we take any non-recursive RE subset $S\_{RE\setminus R}\in\mathbb N$, we have $\phi(S\_{RE\setminus R})\subset L\_{\emptyset,0}$ which is RE but not recursive. And it contains only (Gödel indexes of) TM machines that always halt.

Of course, other levels of computability can be obtained in the same way.
> 4 votes

# Answer
$L$ can indeed be "everything".

* Let $L$ the set of Turing machines that

+ always move right,
    + never write to the tape, and
    + halt when they read the blank symbol.

Clearly, we can decide these critera from inspecting the transition matrix.

Note that this is *not* the set of all TMs that decide regular languages, since that set is not recursive (by Rice's theorem).
* Let $L$ the set of all TMs of primitive recursive functions. This set is known to be recursively enumerable, but it is by Rice's theorem of course not recursive. Hence, $L \in RE \setminus R$.
* Let $L$ the set of all TMs that always halt, i.e. the set of all TMs that accept languages from $R$. We know that this set is not recursively enumerable, so $L \not\in RE$.

Note how all three languages are infinite and contain only (descriptions of) TMs that always halt.
> 3 votes

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


# Question
Title: Do problems in P only reduce to NP and coNP problems?
Consider the languages $B,C,D$, such that $B\le\_p C$ and $B\le\_p D$.
**Statement**: $B\in P, D\in NP, C\in coNP$.

> Is the statement true for every $B,C,D$?

I know that the answer is no and I have tried to come up with a conunter-example. I thought about taking $D\in NPC$ or $C \in coNPC$ but that didn't yield anything good.

# Answer
> 3 votes
One short answer, take $B$ be to be any problem in $\mathsf{P}$. The reduction is then powerful enough to simply solve the problem as part of the reduction, and consequently produce a trivial yes or no instance at the other end as appropriate. Then we can take $C$ and $D$ to be anything, they don't even have to be computable.

A more interesting, but conditional answer, is to take $B$, $C$ and $D$ to be any three $\mathsf{NP}$-complete problems (they don't even need to be different ones). Every $\mathsf{NP}$-complete problem is polynomial-time many-one reducible to every other $\mathsf{NP}$-complete problem, so the two reducibility conditions hold trivially. If $\mathsf{P} \neq \mathsf{NP}$, then $B$ can't be in $\mathsf{P}$, and if $\mathsf{NP} \neq co\mathsf{NP}$, then $C$ can't be in $co\mathsf{NP}$. You can do essentially the same thing by taking them all to be $co\mathsf{NP}$-complete. Taking it further, you can do this for any class in the polynomial hierarchy, and the statement being true would imply a collapse to whatever level you chose, another thing that is viewed as unlikely to happen. You could also choose a selection of $\mathsf{PSPACE}$-complete problems, and the statement would imply $\mathsf{P} = \mathsf{PSPACE}$, which also seems unlikely to be true.

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


# Question
Title: Why do Shaefer's and Mahaney's Theorems not imply P = NP?
I'm sure someone has thought about this before or immediately dismissed it, but why does Schaefer's dichotomy theory along with Mahaney's theorem on sparse sets not imply P = NP ?

Here's my reasoning: Create a language $L$ which is equal to SAT intersected by an infinite decidable sparse set. Then $L$ must also be sparse. Since $L$ it is not trivial, affine, 2-sat, or Horn-sat, by Shaefer's theorem it must be NP-complete. But then we have a sparse NP-complete set so by Mahaney's theorem, P=NP.

Where am I going wrong here? I suspect that I am misunderstanding/misapplying Shaefer's theorem but I don't see why.

# Answer
Schaefer's theorem applies only to a specific type of languages, those of the form $\mathrm{SAT}(S)$ for a finite set of relations over the Boolean domain or $\mathrm{CSP}(\Gamma)$ for a finite constraint language over the Boolean domain (the two notations are equivalent; see the Wikipedia page for a description). Any other language is not covered by the theorem, and the theorem has nothing to say about it. In particular, Schaefer's theorem doesn't say anything about your language $L$.
> 14 votes

---
Tags: complexity-theory, np-complete, satisfiability, p-vs-np
---


# Question
Title: Find all the paths from node A to node B
You are given a bunch of nodes evenly spaced in a rectangular grid. The rectangle is M nodes long and N nodes wide. Node A is in the upper left hand (northwest) corner and node B is at the bottom right hand corner (southeast). From each node you can only move east, south, or diagonally southeast to the next adjacent node (assuming there is an adjacent node that permits moving in that direction). How many different paths are there from A to B?

I only found a brute-force method using a depth first search with a stack. Is there a more efficient algorithm to solve this puzzle? Specifically, I am looking for an algorithm (preferably efficient) that can determine the total number of paths you can take from node A to node B in a grid of evenly spaced nodes of size M x N.

# Answer
> 4 votes
Let $P(i, j)$ be the number of paths from the start node, $(0,0)$, to the destination node, $(i, j)$. Then it's easy to see that $$\begin{align} P(i, 0) &= 1\\ P(0, j) &= 1\\ P(i, j) &= P(i-1,j)+P(i-1,j-1)+P(i, j-1), \text{ if }i,j\>0 \end{align}$$ Applying this recursion directly isn't particularly efficient, since you'll wind up making a lot of redundant calls. You could improve this by memoizing the intermediate values: at step $k$, compute and save the values $P(0, k), P(1, k), \dotsc P(k,k)$ and the values $P(k, 0), P(k, 1), \dotsc P(k,k)$. Note that this last series actually doesn't need to be saved at all, since $P(a,b)=P(b,a)$.

---

For another way (which turns out to be conceptually the same as Yuval's answer), you could observe that a path consists of a collection of steps:

1. An eastward move, $E$, from node $(i,j)$ to node $(i+1, j)$.
2. A southward move, $S$, from node $(i,j)$ to node $(i, j+1)$.
3. A diagonal move, $D$, from node $(i,j)$ to node $(i+1, j+1)$.

So to get from $(0,0)$ to $(i,j)$ we will need to make $i$ moves east and $j$ moves south. Note that each diagonal move will contribute 1 to the eastward moves and 1 to the southward moves. Thus, every path from the origin to node $(i,j)$ can be uniquely described as a sequence of $E, S, D$ where the number of $E$s plus the number of $D$s equals $i$ and the number of $S$s plus the number of $D$s equals $j$. For example, $P(2,2)$ is the number of paths

1. Using no $D$s: $EESS, ESES, ESSE, SEES, SESE, SSEE$.
2. Using one $D$: $DES, DSE, EDS, SED, ESD, SED$.
3. Using two $D$s: $DD$

So we see that $P(2,2)=6+6+1=13$.

Now the number of sequences of three symbols $D,E,S$, in order, with $a$ of the $D$s, $b$ of the $E$s, $c$ of the $S$s, is given by the multinomial coefficient $$ \binom{a+b+c}{a,\ b,\ c}=\frac{(a+b+c)!}{a!\\;b!\\;c!} $$ and from this and the observations we just made, we'll have, for $i\le j$, $$ P(i, j)=\sum\_{k=0}^i\binom{i+j-k}{k,\ i-k,\ j-k}=\sum\_{k=0}^i\frac{(i+j-k)!}{k!\\;(i-k)!\\;\ (j-k)!} $$ where $k$ is the number of $D$ moves, $i$ is the number of $E$ moves and $j$ is the number of $S$ moves. This sum of factorials is also somewhat computationally expensive, but by recognizing that there are some relations among the terms, you can slightly simplify the number of multiplications and divisions involved. Unfortunately, there doesn't appear to be any nice closed form for this sum, unlike the situation where we don't allow diagonal moves, in which case $P(i,j)=\binom{i+j}{i}$.

# Answer
> 3 votes
The answer is the coefficient of $x^N y^M$ in the generating function $$ \frac{1}{1-x-y-xy}. $$ This is because $$ \frac{1}{1-x-y-xy} = \sum\_{\ell=0}^\infty (x+y+xy)^\ell, $$ and every term in the expansion of $(x+y+xy)^\ell$ corresponds to a walk of length $\ell$.

We can also obtain an explicit formula for it: $$ \sum\_{t=0}^{\min(N,M)} \frac{(N+M-t)!}{t!(N-t)!(M-t)!}. $$ Here $t$ is the number of diagonal steps.

---
Tags: algorithms, graphs, shortest-path, enumeration
---


# Question
Title: Why does Kadane's algorithm solve the maximum sub-array problem?
I've tried to solve a exercise 4.1-5 in algorithm book "Introduction to algorithms".

it is about Maximum sub-array problem, which is an algorithm that determines the greatest sum of sub-array A\[i\], A\[i+1\] , ... , A\[j\] in given array A\[1\] , ... , A\[n\].

The exercise is about developing linear-time algorithm to solve this using a following idea, (f.y.i. A\[1 ,... , j\] means A\[1\] , A\[2\] , ... , A\[j\] )

> Knowing a maximum **sub-array of A\[1, ... , j\]**, extend the answer to find a maximum sub-array ending at index j+1 by using the following observation: a maximum sub-array of A\[1, ... , j+1\] is either a maximum sub-array of A\[1,...,j\] or a sub-array A\[i,...,j+1\], for some 1 \<= i \<= j+1. Determine a maximum sub- array of the form A\[i,...,j+1\] in constant time based on knowing a maximum sub- array ending at index j." .

People said that this solution is actually Kadane's algorithm, which is relatively a simple algorithm stated on Wikipedia (I'm really sorry that you have to move to another site. but it explains better than I do.)

However, Kadane's Algorithm deals with only a sub-array that ends at exactly j. but above idea says I should use maximum sub-array of A\[1, ... , j\] and we can't guaranteed that this sub-array should end with j. Because I think this two algorithm is quite different.

# Answer
Suppose $A\[1..N\]$ is your array for which you want to find maximum sum sub-array. Construct $B\[1..N\]$ such that $B\[j\]=max (\sum A\[k\] \mid k \le j,k \ge i)$ ($i$ is some starting index for which B\[j\] is maximum). So it boils down to $B\[j\]=max(B\[j-1\]+A\[j\],A\[j\])$ (here I am assuming that empty sub-array isn't allowed in answer). And then find the maximum $B\[j\]$ for all $j \in \[1..N\]$. Now this can be done in constant space since we only need result of the previous iteration( for $j$ we need only $B\[j-1\]$) and the maximum sub-array sum which has occurred till now. Now compare these two ideas and you will get you answer.
> 5 votes

---
Tags: algorithms, optimization, arrays
---


# Question
Title: Operator precedence in propositional logic
there is some kind of priorities for the elements in propositional logic ?

for example : p ∧¬q → r , given this ,we there may be two options

(p ∧¬q) → r OR p ∧ (¬q → r) , which one is the correct ?

# Answer
> 8 votes
If you look at formal definitions of the syntax of propositional logic, you will find that

$\qquad p \land \lnot q \to r$

is not a proper sentence; parentheses are needed to avoid exactly the ambiguity you mention.

Operator *precedences* can be used for implicit parenthesisation. You seem to be asking if there are agreed-upon operator precedences in logic.

I don't think *formal* logics contains this concept; formal grammars just do not lend themselves to model precedences (or any ambiguity) very well. In practice (by which I mean both blackboard writing and implemented logic parsers), we *do* use precedences; usual conventions include

1. $\lnot$,
2. $\land$,
3. $\lor$,
4. $\implies$,
5. $\iff$

in decreasing order of precedence. Using these, your example is equivalent to

$\qquad (p \land (\lnot q)) \to r$.

David's warning is apt, though: if you want to be clear, don't rely on implicit precedences. Typesetting can help -- you can e.g. group terms with spacings -- but in case of doubt, just put the parentheses. In a larger body of work, you can also state your convention once and safe symbols afterwards, provided you stick to your own rules.

# Answer
> 3 votes
It seems to be conventional that $\neg$ binds to the object immediately following it, so $\neg A \land B$ means $(\neg A) \land B$, rather than $\neg(A \land B)$.

Beyond that, the safest option is to treat all other operators as having equal precedence and use enough parentheses to force the reading you intend. In the past, authors frequently asserted or assumed precedence rules because syntax was seen as being more interesting in and of itself. However, such rules are rather arbitrary. For example, one might assert that $\land$ is multiplication modulo 2 and $\lor$ is addition modulo 2 so $\land$ should have higher precedence. But this doesn't help much because $\land$ and $\lor$ have different distributivity properties to $\times$ and $+$, at least in the non-modular setting that we're used to.

Nowadays, except for negation, it seems more common to just disambiguate by bracketing. If you see a modern author asserting or, worse, assuming precedence rules, I suggest poking them with a stick until they stop.

---
Tags: logic, notation, propositional-logic
---


# Question
Title: When did polynomial-time algorithm become of interest?
I would like to understand why and when polynomial algorithms became of interest.

When did people realize the role and importance of efficient versus non-efficient algorithms? Did that happen when the concept of an algorithm was discovered, or the the term algorithm used.

For instance, I've looked at some textbook of Algorithms such as the one by Cover, Leiserson, Rivest, and Stein "Introduction to Algorithms" 3rd ed. they states in the Preface "Before there were computers, there were algorithms. But now that there are computers, there are even more algorithms, and algorithms lie at the heart of computing".

Would it be the case that, before computers were invented, we were more interested in finding new ideas for solving problems, and were not so concerned with the time it took.

So I am interested in knowing when people became conscious of the importance of efficiency, started to study it more systematically.

Are there some reference papers on the subject, on the history of algorithms and their motivations, and on the concern with efficiency.

\[note from the translator\] The topic of the question may seem a bit wide, as I tried to keep the meaning without betraying the author. But it seems a good and useful general question that can be adressed with a few general remarks and some facts and examples

# Answer
*Since this question was reopened and made more explicit, I would like to convert my comment into an answer. Now the OP wants to understand*

> why and when polynomial algorithms became of interest.

I especially focus on the sub-question:

> When did people realize the role and importance of efficient versus non-efficient algorithms?

---

Because algorithms, in its general terms, have existed since ancient times, it is hard to identify the person who is the first to highly praise the polynomial algorithms(, and when and why). However, there is a famous person who has explicitly advocated the polynomial algorithms. It is Jack Edmonds, in the paper Paths, Trees, and Flowers; 1965.

In Introduction, the author claims

> We describe an ***efficient algorithm*** for finding in a given graph a matching of maximum cardinality.

Then in the second section titled "Digression", the author

> An explanation is due on the use of the words ***"efficient algorithm"***.

Then come the explanations:

> There is an obvious finite algorithm, but that algorithm increases in difficulty ***exponentially*** with the size of the graph. It is by no means obvious whether or not there exists an algorithm whose difficulty increases only ***algebraically*** with the size of the graph.
>
> When the measure of problem-size is reasonable and when the sizes assume values arbitrarily large, an asymptotic estimate of $\ldots$ the order of difficulty of an algorithm is theoretically important.
>
> For practical purposes ***the difference between algebraic and exponential order is often more crucial than the difference between finite and non-finite***.
>
> However, if only to motivate the search for good, practical algorithms, ***it is important to realize that it is mathematically sensible even to question their existence***. For one thing the task can then be described in terms of concrete conjectures.

---

***ADDED:*** I have just happened to found a third-party confirmation that it was Jack Edmonds who originally advocated the polynomial algorithms.

The following is quoted from Section 2.18.1 of the book "Applied Combinatorics (second edition)" by Fred Roberts and Barry Tesman.

> A generally accepted principle is that an algorithm is *good* if it is polynomial. This idea is originally due to Edmonds \[1965\].
> 11 votes

# Answer
in addition to the other standard credits eg to Edmonds (1965); some obscure CS history that few are aware of and is not written in many (any?) textbook accounts so far, and is rarely cited, (maybe not even much on stackexchange CS sites): Gödel is given credit as being one of the 1st mathematicians/ "scientists" (from the modern CS pov) who 1st considered the idea of efficiency of algorithms, and polynomial growth, and Landau notation applied to algorithmic complexity, in a 1956 letter to Von Neumann. in a sense it is one of the first written/ posthumously published musings on complexity theory. the letter was not rediscovered for its significance to CS until decades later, apparently noted by Sipser in 1992. contents/ translation/ some more details in comments on following. (it would be nice for a complexity theorist expert to write a detailed analysis/ interpretation esp from historical pov, but have not seen one. cannot locate further analysis in RJ Liptons blog.)

The Gödel Letter (RJ Lipton blog)

The letter was originally written in German. Mike Sipser’s translation can be found in “The History and the Status of the P versus NP Question”, in the 24th STOC proceedings, 1992, pp. 603-618.
> 7 votes

# Answer
People have been conducting calulations for centuries, and calculations in general follow some algorithms. It does not matter who or what calculates - computing takes time (and time is one of the resources you can never get back, once lost.) And to save more time you need to have better algorithms.

Can you imagine building atomic reactors without even simplest calulators to help? People did it (and many more amazing things), and they often spent literally *months* just calculating. With some better algorithms for their problems they could cut that to weeks, days or even hours.

Did it matter before computers? Yes, a lot! Even more than today as they actually needed *people* to compute, which is much more costly than having your PC do that. Faster algorithms are faster for humans, computers or anything else able of conducting them.

Also note that algorithms are not only related to computing. An algorithm is basically a recipe of "How to do something step-by-step" with a desired level of detail. So if people tried to make something easier/faster - they often tried to improve their algorithms of doing it (even if they did not look at it this way.)
> 4 votes

---
Tags: algorithms, reference-request, efficiency, polynomial-time, history
---


# Question
Title: What is the relation between differential-privacy mechanism and entropy?
Why do differential-privacy people care whether or not the noise function saturates the lower bound of Shannon entropy?

For example : Laplace distribution that is used to model the noise function happens to saturate the lower bound of Shannon entropy under epsilon differential privacy constraints. See Theorem 8 in Yu Wang, Zhenqi Huang, Sayan Mitra and Geir E. Dullerud, Entropy-minimizing Mechanism for Differential Privacy of Discrete-time Linear Feedback Systems for an example.

But what is the significance of this saturation?

# Answer
> 1 votes
In general, if you're not sure about the significance of mathematical results in a published paper, often a good first place to look is the paper's introduction and/or conclusion. The authors often try to provide some explanation why you should care about their results in the introduction and conclusion.

In this case, the following two quotes from the introduction of the paper you cited provide a pretty clear explanation for why the authors care:

> we first study an $\epsilon$-differentially private noise-adding mechanism for one-shot queries that provides the best output accuracy, which is measured by the Shannon entropy. \[...\]
>
> In Section III, we prove that, for a one-shot $n$-dimensional input, there is a lower bound $n + n \ln(2\epsilon)$ on the entropy of the output for an $\epsilon$-differentially private noise-adding mechanism, and the lower bound is achieved by Laplacian noise with parameter $\epsilon$.

In other words, the Shannon entropy measures the accuracy of the output after adding the noise (lower is better); Theorem 8 proves that Laplace noise achieves the lowest possible Shannon entropy, in a particular situation; therefore, we can conclude that Laplace noise is optimal in the sense that it achieves the highest possible output accuracy, in that situation.

---
Tags: complexity-theory, cryptography, information-theory
---


# Question
Title: Tag, index and offset of associative cache
My main issue of a homework problem is trying to figure out the different parts of the chart. I have a 3 way set associative cache with 2 word blocks, total size of 24 words. I am given $3, 180, 43, 2, 191, 88, 190, 14, 181, 44, 186, 253$ to try to map.

What I have so far and where I am stuck:

My main problem is trying to figure out how to find the index and offset of associative (3-way set) cache. Since I have 3 sets, is it: $3 \bmod 3 = 0$, so $0$ is the index? $180 \bmod 3 = 0$ index as well? And would it looks like the following:

$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline \text{Block} & \text{Ix} & \text{Hit/Miss} & \text{Set 0} & \text{Set 0} & \text{Set 1} & \text{Set 1} & \text{Set 2} & \text{Set 2} \\\hline 3 & 0 & \text{miss} & \mathit{mem}\[3\] \\ 180 & 0 & \text{miss} & \mathit{mem}\[3\] & \mathit{mem}\[180\] \\ 43 & 1 & \text{miss} & \mathit{mem}\[3\] & \mathit{mem}\[180\] & \mathit{mem}\[43\] \\ 2 & 2 & \text{miss} & \mathit{mem}\[3\] & \mathit{mem}\[180\] & \mathit{mem}\[43\] && \mathit{mem}\[2\] \\ 191 & 2 & \text{miss} & \mathit{mem}\[3\] & \mathit{mem}\[180\] & \mathit{mem}\[43\] && \mathit{mem}\[2\] & \mathit{mem}\[191\] \\\hline \end{array} $$ etc...

Somehow I feel like this is all wrong, because of some sample problems I have seen. But in class, this is how I remember it being explained. Helping me understand the fundamentals of this problem would be so helpful and I appreciate all the help I can get. Sorry if it doesn't seem like I have put a lot of work into this, but I am familiar with only directly mapped cache and the sample problems I have seen aren't very explanatory.

# Answer
Before getting to your question, let's recall what set-associativity means, and how one can figure out how to split the address into tag, index and offset. If you prefer to learn by examples, jump to after the fold.

### Cache

A cache is just a faster, yet smaller, memory. It might take a long time to access data in the main memory, but it is very fast to access the cache. So we better save data in our small and fast cache rather than in our big and slow main memory. However, the cache is small, so it cannot hold the *entire* data of the main memory. Instead, it will hold some part of the data stored in the main memory.

Which part of the data? We don’t know in advance - this would depend on the actual usage of the data (i.e., it depends on the software we run). In general we would like to be able to put in the cache **any** part of the main memory, and we would need to figure out **where** to put each memory-address in the cache, and **how** to identify which memory-address lies in each cache-cell. The index and tag bits will do just that (see below for a better explanation). But before we get there, let’s make things a bit more complex: we stop discussing addresses of the main memory and start discussing memory *blocks*.

### Blocks and offsets

Many times, when we access the memory, we access consecutive addresses. That is, many times if we access address 0, then shortly after we will access address 1 (and 2, and 3....). So maybe when we first access address 0, and put it in the cache, it will be smart to bring along addresses 1 and 2 and 3 \[...\] and put them in the cache as well. This "chunk" of information that we bring into the cache is called **a block**. The cache always hold blocks of consecutive memory addresses. It is possible that each block in the cache contains the data of only 1 memory-address. It is possible that a block contains the data of 2 (consecutive) addresses. Maybe it contains 128 consecutive addresses... Each cache has its own parameters.

Since the cache "knows" only blocks rather than specific addresses, we need a way to distinguish different addresses within a specific block. For this we have *offset bits*. If a block contains $x$ addresses of the memory, then any $x$ consecutive addresses constitute a single block. Given a specific address in the memory, we can look at its bits representation: the MSB will be the "block number" and the LSB would be the offset inside the block. That is, to get the block number out of a specific address we can simply ignore the last $\log\_2 x$ bits (LSB), and the rest will indicate the number of the block associated with these $x$ addresses. The lower $\log\_2 x$ bits are called *offset bits* and they are used to tell the cache which address *within the block* we wish to access.

### Set Associativity

Now to the more interesting part of caching. Where does each block go within the cache? This seems like a stupid question: why don't any block go anywhere in the cache. The answer is that if any block can be anywhere, then it may be very difficult to locate that block when we need it -- we will have to search through the entire cache for that block, and this search may be slow/expensive.

The solution is that the cache is split into “sets”. Each memory block is assigned to one specific set. **This assignment never changes.** Whenever you access that memory block: if it is in the cache it will be in that assigned set; if it is not in that assigned set, it is not in the cache and you need to bring it from the memory.

> Example: let's say the cache have a place for only 2 blocks (Place A, and Place B), and the memory contains 10 blocks (block0 to block9). We can decide that in the first “set” (Place A) we put only even blocks, and in the second set (Place B) only odd blocks. Now if we access block 5 (say), then we only need to check the second set (Place B), because it can only be there. This may save us HALF the search time (or half the cost of searching a block).

In the above example, each “set” could hold only one block, but in general, each set can hold $n$ blocks at the same time: this kind of cache is called $n$-associative.

In other words, an $n$-associative cache is split into sets, where each set holds $n$ memory blocks. This allows us to determine the amount of different sets: it is the size of the cache (in blocks) divided by $n$.

Let’s have two examples:

* 1-associative: each set can hold only one block. As always, each address is assigned to a unique set (this assignment better be balanced, or all the addresses will compete on the same place in the cache). Such a setting is called **direct mapping**
* fully-associative: here each set is of the size of the entire cache. That is, if the cache is of size $t$ blocks, a fully associative cache is in fact a $t$-associative cache. How many sets are there? one! and all the blocks are assigned to this single set. Therefore, each blocks can be saved “anywhere” at the cache, because all the cells of the cache belong to the same set.

### index and tag

We said that each block gets an assignment to one of the $k=size/n$ sets. To make things simple, this assignment is determined by looking at lowest $\log\_2 k$ bits of the block number. These are called the “index” bits: they index to which set the block will go into.

> Pop Quiz 1: How many index bits are there in a fully associative cache?

Answer (think about it for a second before looking at the answer):

> In a fully associative cache there is only one set. So we don’t need an index to choose a set, there is only one! Formally, $k=1$ and we need $\log\_2 k=\log\_2 1=0$ index bits.

next,

> Pop Quiz 2: How many index bits are there in a direct mapping cache?

Answer

> In a direct mapping cache, we have $k=size/1$ different sets. Thus we need $\log\_2 k$ index bits.

Next, there are the “tag” bits. To explain these, let’s think on a fully-associative cache. To make things simple, let’s assume the cache is of size 2 blocks. Assume this two cache-cells are full with information from the main memory: the first cell holds block 0 and the second one holds block 190. Now we access an address in block 220. But it is not in the cache, so we need to bring it from the memory and replace one of the blocks that are currently in the cache. But wait! How do we actually know that the cache doesn’t hold block 220? Right. The cache must “remember” that the first cell holds block 0, and that the second one holds block 190. No other choice. This information (0 or 190) is called the *tag*: to each cell of the cache we add a little tag with that indicates what block is currently there. Simple, right?

But saving information in the cache is expensive, and we don’t want to save information we never use. In the above example every address could be placed anywhere in the cache, but this is not the case for other associativity levels: Each address can go only to its assigned set as determined by the “index” bits. So if there are two sets, where the first can hold only blocks 0,2,4,6,8, and the second set can hold only blocks 1,3,5,7,9, then we don’t need to save the entire block number in the cache-- block 4 can never appear in the second set, and block 7 can never appear in the first set. This means we don’t need to save the last bit (the one that determines the parity), but we need to save the rest. Indeed, the last bit serves as the *index*, and the rest serve as *tag*, thus, by knowing the set+the tag we know exactly which block is currently kept in each cache-cell.

---

Now back to your question, which exemplifies the above ideas:

The 3-way associativity means that the cache is split into sets, and each set can hold up to 3 blocks. The question gives us that each block is 2 words.

So instead of having 3 sets, where each can hold 2 different addresses/block (as you had in the table you drew), the cache has a large number of sets, and each set has a room for 3 blocks.

How many sets exactly? well, the cache has 24 words, that is 12 blocks, that is 4sets (of 3 blocks each!). This gives us the size of the `index` field: 2 bits. \[The index decides which set we go into, and there are only 4 sets, so the index needs to be only 2 bits..\].

This was the first part of the story. The other part is that a block is two words. Therefore, e.g., when the address 0 is accessed, the cache (set 0) will hold the first two memory words. Thus, if the address 1 is later access, it will be a hit. Since both addressed 0 and 1 are in the same block, we need a way to distinguish them. This will be the "offset" bit.

The above suggests that the 8bit address is to be parsed as

```
tttttiio

```

where `o`=offset (distinguishes between the 2 words in each block), `i` is the index (specifies the set) and `t` is the tag (tells us which block is occupying each cache cell..

So, unless I'm being too careless in thinking it over, the mapping will look like this (building on your table).

```
Block   Add      Index     Hit/Miss   Set 0         Set 0      Set 0     Set 1      Set 1      Set 1     Set 2      Set 2      Set 2     Set 3      Set 3      Set 3
3   =00000011    01        miss      mem[00000]
180 =10110100    10        miss      mem[00000]                                                                     mem[10110]
43  =00101011    01        miss      mem[00000]     mem[00101]                                                      mem[10110]
2   =00000010    01        hit       mem[00000]     mem[00101]                                                      mem[10110]

```

etc... Note that by `mem[ttttt]` I denote the specific block by writing its 5-bit tag value.

---

**tl;dr** A nice illustration to all this "set-associativity" thingy can be found here.
> 22 votes

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


# Question
Title: Greedy algorithm correctness proof for "Elegant Permuted Sum" (UVa 11158)
Given a sequence of $2 \leq n \leq 50$ numbers $s = (s\_1,s\_2,...,s\_n)$, find a permutation $a = (a\_1,a\_2,...,a\_n)$ of $s$ such that $$\sum\_{i=1}^{n-1} |a\_i - a\_{i+1}|$$ is maximized.

I found many codes that get "Accepted" in the online judge with the following greedy algorithm.

> If $n = 2$, then $a = s$. Stop the algorithm.
>
> Let $s' = (s'\_1,s'\_2,...,s'\_n)$ be $s$ in the non decreasing order. Start the optimal sequence with $a = (s'\_1,s'\_n)$ and remove these two elements from $s'$.
>
> $\text{loop}$: Let $s' = (s'\_1,s'\_2,...,s'\_k)$ be the remaining sorted sequence. If $k = 0$, stop the algorithm. If $k \> 0$, from the following choices, choose the one that yields the greatest absolute difference.
>
> 1. Remove $s'\_1$ from $s'$ and push it to the front of $a$.
> 2. Remove $s'\_1$ from $s'$ and push it to the back of $a$.
> 3. Remove $s'\_k$ from $s'$ and push it to the front of $a$.
> 4. Remove $s'\_k$ from $s'$ and push it to the back of $a$.
>
> Go to $\text{loop}$.

I'm having trouble to formally prove the correctness of this algorithm.

For example, to prove the optimal substructure property. Let $b = (b\_1,b\_2,...,b\_n)$ be an optimal solution. How can I argue that $(b\_1,b\_2,...,b\_{n-1})$ is also optimal? What if it's not???

And for proving the greedy-choice property. Let $a = (a\_1,a\_2,...,a\_m)$ be a partial, yet still optimal, solution. The algorithm relies on the fact that only adding $s'\_1$ or $s'\_k$ to $a$ can yield another optimal solution. Why is this true? And more, why we don't need to test inner positions for inserting the new element, but only the ends?

Any help with these proofs? Or, perhaps, this algorithm is not correct? But I can't find a counterexample...

# Answer
> 2 votes
This algorithm appears and is analyzed in Curtis, Darts and hoopla board design. Curtis actually considers two problems:

1. Dartboard design: Given a sequence of numbers, find a circular arrangement $a\_1,\ldots,a\_n$ maximizing $\sum\_{i=1}^n |a\_i-a\_{i+1}|^q$ for some $q \geq 1$ (where $a\_{n+1} = a\_1$).
2. Hoopla board design: Given a sequence of numbers, find a permutation $a\_1,\ldots,a\_n$ maximizing $\sum\_{i=1}^{n-1} |a\_i-a\_{i+1}|^q$ for some $q \geq 1$.

Your problem is the hoopla board design with $q = 1$. You can find a complete proof of the greedy algorithm in Curtis' paper. It's not trivial, though also not too complicated.

---
Tags: correctness-proof, greedy-algorithms
---


title: pipeline execution time

text:
# Question
Title: pipeline execution time
Lets suppose that 20 percent of the instructions in a program are branch instructions.The static prediction of the jumps supposes that the jumps don't happen.

I should find the execution time in two cases : When 30 percent of the branches happen and when 70 percent of the branches happen I also should find the speedup of one case compared to the other and express it in percentage.

Thing is,how do I find the execution time here ? I usually find the execution time where the pipeline is separated in different phases and there is given the time for each phase ....

Edit : This is NOT homework.I found this in my computer architecture textbook and its not a familiar exercise.

# Answer
> 2 votes
With a static prediction of not-taken, when the branch is not taken (correct prediction) there is no penalty. When the branch is taken ("happens"), all the instructions that were fetched after the branch instruction are flushed from the pipeline (except for any branch delay slot instructions) when the branch instruction is evaluated. Instruction fetch restarts at the correct address.

With a simple five-stage pipeline (instruction fetch, decode, execute, memory, writeback) where branch direction and target are determined in the third (execute) stage and no branch delay slots are used, a taken branch will take three cycles (i.e., the instructions in the fetch and decode stages are flushed). If all other instructions have a cycles per instruction of one, then the total CPI would be the fraction of instructions that are taken branches times three cycles plus one minus that fraction (all other instructions including not taken branches) times one cycle (for 30% taken branches: 0.20\*0.30\*3 cycles + (1-(0.20\*0.30))\*1 cycle; for 70% taken branches: 0.20\*0.70\*3 cycles + (1-(0.20\*0.70))\*1 cycle). (This is simply the sum of the products for each instruction type of the number of cycles for that instruction type times the fraction of instructions of that type. For this case, the instruction types are taken branches (three cycles, 30% of 20%) and all other instructions (1 cycle, 100% - taken branch percentage).

The execution time (in cycles) is simply the CPI times the instruction count. The speedup *factor* would be the execution time for one case divided by the execution time of the other case. Subtracting one from the speedup factor and multiplying by 100 gives the speedup percentage. (If the factor is less than one, the speedup percentage will be negative. Negating this would provide the slowdown percentage.)

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


# Question
Title: How would you implement truly random hash functions in practice?
Suppose that $\[U\] = \[0,...,U-1\]$ is the universe from which all elements will be taken, and $A$ a hash table of size $m$.

A hash function $h:\[U\]\rightarrow\[m\]$ is truly random if

For any set of distincts elements $\\{x\_{1},...,x\_{k}\\} \subseteq \[U\]$ and any set of values $u\_{1},...,u\_{k} \subseteq \[m\]$ we have $Pr\_{h}\[h(x\_{1}) = u\_{1} \wedge ... \wedge h(x\_{k}) = u\_{k}\] = \frac{1}{m^{k}}$. This of course implies that $h(x\_{i})$ is uniform random and independent of $h(x\_{1}),...,h(x\_{i-1}),h(x\_{i+1}),...,h(x\_{k})$.

I was trying to understand why this is not possible to implement efficiently in practice, and found this paper where at some point they write in the abstract:

> Hashing is fundamental to many algorithms and data structures widely used in practice. For theoretical analysis of hashing, there have been two main approaches. First, one can assume that the hash function is truly random, mapping each data item independently and uniformly to the range. This idealized model is unrealistic because a truly random hash function **requires an exponential number of bits to describe.**

I do not see how using exponential number of bits can help us come up with a truly random hash function when the universe is $\[U\]$ and the hash table can store at most $m$ elements.

How would you use an exponential number of bits to come up with a function that can guarantee the probabilities described above?

# Answer
> 0 votes
The number of bits required to describe a function from $\[U\]$ to $\[m\]$ is $m \times 2^U$. This is exponential in $U$.

---
Tags: algorithms, probability-theory, randomized-algorithms, hash, hash-tables
---


# Question
Title: Show that the set of all TMs that move only to the right and loop for some input is decidable
I am trying to prove that

$\qquad L=\\{\langle M\rangle \mid M \text{ is a TM }, \exists w. \text{ in } M(w) \text{ the head moves only right and } M(w)\\!\uparrow \\}$

is decidable.

I thought about the following solution:
Lets build $\hat{M}$, a TM that will decide L:
M on input $\langle N \rangle$:
1. $\Sigma^{Q+1} $ is decidable so it has an enumerator f.
2. for every word $ w\in\Sigma^{Q+1} $ simulate parallel N on w for |Q|+1 steps:
$\space \space \space$ - if N got to a blank then N moved only right and is stuck in a loop.
3. if all of those words stopped the simulation at a blank accept. else reject.

I am quite sure I am missing something here. Can you help please?

# Answer
> 2 votes
Your approach is on the right track. It should follow the next ideas:

1. If there exists such $w$, then, when $M$ reaches the first "blank" after reading $w$ it will be in a state $\tilde q$ that goes right (and then keep going right, no matter the state changes). Finding this $\tilde q$ that satisfied this property (if such exists) can easily be verified for by checking all the states in $Q$ (of the given $M$).
2. If such $\tilde q$ exists, we need to see if it is reachable after reading some input $w \in \Sigma^\*$. The idea you already noticed is that if this happen, then $\tilde q$ will be reachable after processing the end of some word in $\Sigma^{Q+1}$ (or the like). This is simply a pigeonhole argument..

Therefore it is enough to only examine all the words in $\Sigma^{Q+1}$ and check if $M$ on any of them goes only right, and reaches $\tilde q$ when hitting the first blank. Since the number of words in $\Sigma^{Q+1}$ is finite, this is doable in a finite time.

You just need to properly formalize the above ideas as a decider $\hat M$.

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


# Question
Title: Constructing languages in NPI other than through Ladner's Theorem
I have seen proofs of Ladner's theorem which detail the construction of languages in NPI assuming P $\neq$ NP. However, I was wondering if there are any other constructions using the fact that sparse sets cannot be NP-complete assuming P $\neq$ NP (Mahaney's Theorem). Specifically, is it definite (assuming P $\neq$ NP) that the intersection of an infinite decidable sparse set and an NP-complete language lies in NPI? It seems to me that it cannot be in P, but I don't know how to prove it. (Note: I am asking about taking a given NP-complete language and its intersection with a sparse set, not about $\textsf{NPC} \cap \textsf{SPARSE}$ which must be empty, again by Mahaney's Theorem.)

# Answer
> 5 votes
It is perfectly possible that the intersection of an infinite decidable sparse set and an NP-complete set lies in P. Take your favorite NP-complete set $L$, and consider $L' = 0L \cup 1^\*$, which is still NP-complete. The intersection of $L'$ with the infinite decidable sparse set $1^\*$ is $1^\*$, which is certainly in P.

Mahaney's theorem shows that sparse sets cannot be NP-complete, but to construct an NPI language you will need to show that your sparse set is not in P, which will probably require diagonalization. Your diagonalization will somehow have to ensure that the resulting language is sparse, while still being in NP and outside of P. Perhaps this can be done, but I'm not aware of any such proof. (That said, my knowledge of the relevant literature is sparse.)

---
Tags: complexity-theory, p-vs-np, np-intermediate
---


# Question
Title: Proving that a set of grammars for a given finite language is decidable
Let the language $$L = \left\\{ \langle G \rangle \ |\ L(G) = \\{1,\ldots , 1000\\}, \text{ G is a CFG }\right\\}$$

> Prove that $L \in R$.

Well, I think that for a start we need to check whether or not $L(G)$ is infinite, so we only need to check if there's a word $w\in L(G)$ such that $n \le \left|w\right|\le 2n$

Suppose $L(G)$ is finite. How can I validate that $L(G) = \\{1,\ldots ,1000\\}$?

# Answer
> 2 votes
Hint: Combine the following two properties of context-free grammars:

1. Given a context-free grammar $G$ and a regular language $L$ (given by a DFA, say), there is an algorithm that constructs a context-free grammar $G'$ satisfying $L(G') = L(G) \cap L$.
2. Given a context-free grammar $G$, there is an algorithm deciding whether $L(G) = \emptyset$.

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


# Question
Title: If one-way functions exist are we definitely using them?
I know that if one-way functions exist then there are certain universal one-way functions that exist, but to my knowledge they are too impractical to implement (which is the main reason why they are not being used in modern cryptographic protocols). However, if one-way functions exist are the modern implementations (like RSA and its computational equivalents) definitely one-way? Conversely, if it can be shown that these cryptosystems are insecure, do one-way functions definitely not exist?

# Answer
> 6 votes
One-way functions are an asymptotic concept. A function such as modular exponentiation *with specific parameters* doesn't qualify for being a one-way function since it only exists for a specific size. The same can be said about hash functions such as SHA1. In order to ask the question, you will need to specify an infinite family of functions of the type you're interested in.

Once you've specified your infinite family of functions, the answer to both of your questions is negative: even conditional on the existence of one-way functions, we don't know whether these particular families are one-way, and conversely, it could well be that one-way functions exist, but these families are not one-way.

Should we care? Probably not. Even if a family of functions is one-way, that doesn't mean that using one of these functions is secure. One-way functions is an asymptotic concept, and a family of one-way functions can have significant weaknesses unless the key length is $10^{100}$, and still be one-way. What we need is more concrete guarantees.

In practice, functions we use are deemed secure since generations of researchers have tried to break them and failed (or at least failed to let us know that they succeeded). There is no relation to theoretical cryptography.

---
Tags: complexity-theory, cryptography, one-way-functions
---


title: Recurrence relation complexity

text:
# Question
Title: Recurrence relation complexity
I just learned about recurrences and I just can't solve this problem. I have this recurrence relation:

$$ T(n) = \begin{cases} k\cdot T(\frac{n}{k}) & n \> 0\\ 1 & n = 0\\ \end{cases} $$

where $k$ is a constant number.

I tried drawing a recurrence tree or replacing for lower $n$s but no success. I hope you can help me with an idea!

# Answer
Suppose that $n$ is a power of $k$, say $n = k^t$. Then $$ T(k^t) = kT(k^{t-1}) = k^2T(k^{t-2}) = \cdots = k^tT(1) = k^t, $$ assuming a base case of $T(1) = 1$. So for powers of $k$, we have $T(n) = n$. You can also prove that by induction: if $T(n/k) = n/k$ then $T(n) = kT(n/k) = k(n/k) = n$.
> 2 votes

---
Tags: recurrence-relation
---


# Question
Title: What are the criticisms regarding the performance of HTM?
I just recently learned about the existence of this *hierarchical temporal memory (HTM)*. I already read the document *Hierarchical Temporal Memory: Concepts, Theory and Terminology* (by Jeff Hawkins and Dileep George), which seems rather easy to understand, but one red flag is that the document is neither peer-reviewed nor attempting to explain why it should work in details.

I tried to look around for some independent sources. I found a few papers that compare its performance against others, but none explain why it performs well (or not). I noticed some comments claiming that it was looked down by mainstream expert, but I was unable to find any actual criticisms.

**What are the criticisms regarding the performance of HTM?** Since HTM is meant to be generic, any domain-specific criticism should be related to a more fundamental problem.

Furthermore, there are a huge amount of training data to use, enough even for multiple months training session. Basically, any criticisms regarding size or length of training is not relevant.

# Answer
Criticisms against Jeff Hawkins are well summarized in the following essay taken from http://www.theregister.co.uk/2014/03/29/hawkins\_ai\_feature/

I myself believe that the HTM theory has a huge potential and will be a foundation of true machine intelligence. IBM recently announced to back up the HTM theory and started the Cortical Learning Center including some hundred members.

http://www.technologyreview.com/news/536326/ibm-tests-mobile-computing-pioneers-controversial-brain-algorithms/

As is pointed out in the essay, Dillep George, a cofounder of Numenta, made the startup Vicarious, which attracted a huge amount of fund, of which fact suggests a potential of the HTM theory.

> Source: Criticisms against Jeff Hawkins, The Register
>
> His media-savvy, confident approach appears to have stirred up some ill feeling among other academics who point out, correctly, that Hawkins hasn't published widely, nor has he invented many ideas on his own.
>
> Numenta has also had troubles, partly due to Hawkins' idiosyncratic view on how the brain works.
>
> In 2010, for example, Numenta cofounder Dileep George left to found his own company, Vicarious, to pick some of the more low-hanging fruit in the promising field of AI. From what we understand, this amicable separation stemmed from a difference of opinion between George and Hawkins, as George tended towards a more mathematical approach, and Hawkins to a more biological one.
>
> Hawkins has also come in for a bit of a drubbing from the intelligentsia, with NYU psychology professor Gary Marcus dismissing Numenta's approach in a New Yorker article headlined Steamrolled by Big Data.
>
> Other academics El Reg interviewed for this article did not want to be quoted, as they felt Hawkins' lack of peer-reviewed papers combined with his entrepreneurial persona reduced the credibility of his entire approach.
>
> Hawkins brushes off these criticisms and believes they come down to a difference of opinion between him and the AI intelligentsia.
>
> "These are complex biological systems that were not designed by mathematical principles \[that are\] very difficult to formalize completely," he told us.
> 6 votes

# Answer
I've been studying HTM for a while. It's kinda cool. The default behavior of an HTM is to analyze temporal data. On the other hand, nowadays, you need a "fancy" neural network (e.g. a recurrent neural network) to model a sequence-to-sequence problem (e.g. a chatbot). But HTM can be naturally applied to this type of problems!

I'm planning on making some kind of interactive TV with it, with control data sent up with the visual data, then constrain the visual data to the control data (that is possible, but don't expect it to suddenly dream new video, that doesn't happen). But, I must say, the coolest thing about it is the video you teach it with won't come out on playback, rather it'll show the most typical version of it, which is its form of understanding, and actually making it really cool. So that's kinda like the dream you get out of it.

If you're using HTM with text,

1. it stores letters,
2. then it produces syllables.
3. then it takes these syllables and produces commonness out of these,
4. then it forms words out of the common syllables,
5. then it takes these words and determines what they have in common,
6. then it forms possibly larger words,
7. then it forms groups of words,
8. then it forms groups of sentences

So, each time, it goes up a level, it "forgets" a little more, just to maybe ingrain the groups together more firmly. These more closely ingrained groups will playback a little differently than the record playing into it. And this playback hasn't been seen by a lot of people.

I wonder if it comes up with its own sentences completely.

It makes the sentence grow a little slower, much better. It's much harder work than not forgetting anything and simply having a flat playback of the record. I'd say the slower your sentence grows, the better you did it, so if there is some more way to find typicality, you should do it.
> 3 votes

---
Tags: neural-networks, hierarchical-temporal-memory
---


# Question
Title: Selecting k "special" nodes in a graph such that the min distance is maximized?
Lets say we have a graph $G$ with $|V|$ nodes. We wish to select $k$ such nodes while optimizing the following attribute:

maximize: for each $i$ and $j$, where $i \neq j$, $min(distance(v\_i, v\_j))$

Hope that makes sense. We'd like to pick $k$ nodes such that the distance between the closest pair of distinct nodes is maximal.

Currently, my plan is to pick a node in random, find the node furthest away from it $v\_0$ and the one furthest away from that node $v\_1$. Now recursively look for nodes such that maximize the minimal distance from the selected node set. Meaning, nodes that have the greatest distance possible from the any selected node and specifically the member closest to them of the previously selected set of nodes.

The issue with this is that it's greedy and therefore possibly very inaccurate.

# Answer
Assuming $k$ is part of the input, the problem is NP-hard (by reduction from Independent Set; there's an independent set of size $k$ if and only if there's a way to solve your problem and achieve a minimum distance of 2 or greater).

Your current plan is known as the furthest-point heuristic. It's a heuristic, because it won't necessarily give the optimal solution, though often it gives a solution that's reasonably good. The furthest-point heuristic has been used, among other things, as a technique to select the initial values for $k$-means clustering.

If you want to find an exact solution, you could express this as an instance of of ILP or SAT. Suppose we want to test whether min-distance $t$ is achievable. For each variable $v$, you have a boolean variable $x\_v$ that's 1 if $v$ is selected or 0 otherwise. Now for each pair of nodes $u,v$ such that $d(u,v)\<t$, you add a constraint saying that you cannot choose both $u$ and $v$ (e.g., the constraint $x\_u+x\_v \le 1$ or $(\neg x\_u \lor \neg x\_v)$). Finally, you add a constraint that exactly $k$ nodes much be selected, and then you test whether these constraints are satisfiable. If they are, min-distance $t$ is achievable. Now repeat using binary search to find the largest $t$ such that the instance is satisfiable.
> 4 votes

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Algorithm to find sequence of minimum moves to sort 13 card hand
Just for fun I am trying to write a program to sort the 13 cards (from a standard pack of 52) in a Bridge hand by performing human-like moves on the hand.

A sorted bridge hand is arranged by suit, with alternating colors of suit (if possible), and the cards are sorted by decreasing rank within each suit. For example

* ♣QJ3♥K4♠AQ974♦K76 is a sorted hand
* ♥K4♣QJ3♠AQ974♦K76 is not a sorted hand because the two black suits are touching
* ♣QJ♥K4♠AQ974♦K76♣3 is not a sorted hand because the clubs are not together
* ♣3JQ♥K4♠AQ974♦K76 is not a sorted and because the clubs are not sorted in decreasing rank.

The goal is to sort the 13 randomly dealt cards using the least number of the following human-like moves:

* A card can be temporarily removed from the hand and inserted back somewhere else. For example the ♣3 in ♣QJ♥K4♠AQ974♦K76♣3 can be inserted after the second card to sort the hand.
* Any number of consecutive cards can similarly be removed from the hand and inserted back somewhere else. For example the ♣QJ3 in ♥K4♣QJ3♠AQ974♦K76 can be moved to the front. This is considered one move.

What is an efficient algorithm to find the sequence of the minimum number of such moves to sort the hand?

# Answer
> 3 votes
This problem is harder than you might think. Your operation of removing a block of adjacent cards and re-inserting the block somewhere else is known as a *transposition*. Sorting by transpositions has been studied in the context of bioinformatics and is known to be hard. Of course, if you limit the length to 13 cards, then efficiency becomes much less of a concern--even an exponential algorithm is likely to be fast enough.

I recommend breaking the problem into two related parts. The first, lower level, is to write an algorithm for sorting by transposition on an array of integers, more specifically, on an array that is a permutation of the numbers 1..N. This may be inefficient, but for small N, should be fast enough.

The second, higher level part, is to consider the possible arrangements of suits (clubs-hearts-spades-diamonds, ...). There are at most 8 legal arrangements of suits, and fewer if one or more suits are missing. For each arrangement of suits, it is easy to calculate, for each of the 13 cards, what position it should end up at, giving you an array of the numbers 1..13. Then you can call the first part above as a subroutine.

# Answer
> 1 votes
I ended up implementing this with a brute force method while pruning the moves I chose next. From any given hand, I calculated the next possible moves that I should make, and searched the move space like a BFS algorithm. I followed the following rules to weed out candidates for the next moves, which make the algorithm run, even for 26 cards, within a few seconds:

1. Only consider moves in the forward direction (left to right). This works because if you want to move a card or range backwards, you can move a range of cards forwards to achieve the same state.
2. Cards that must appear in consecutive order in the sorted hand must be moved together. I used a list of list data structure to model this, and only considered moving groups of cards, with the cards in each group being consecutive in the sorted hand. For example in ♦K♠Q9♦7♠A74(...hearts and clubs), the consecutive groups in the first half of the hand are the following 5: ♦K, ♠Q9, ♦7, ♠A, ♠74.
3. No moves can cause cards of any suit to get unsorted. For example in ♦K♠Q9♦7♠A74 moving ♦K♠Q9 after ♠A is not considered as a next move since the ♦K was moved passed the ♦7, and is now unsorted. My reasoning is that moving everything except the unsorted cards (i.e. 2 ranges on either side of that card) requires at most the same number of moves as moving the entire range and then moving the unsorted cards back. However, I have not proved this.
4. Only take moves that minimize the number of previously mentioned consecutive card groups. Only the move ♠Q9 after ♠A in the above hands will be considered in the above hand to minimize the number of groups to 2: ♦K♦7, ♠AQ974. My reasoning was that since no cards are being unsorted (rule 3), the most greedy approach should win every time. However I have not proved this.
5. If a move consisting of a single suit is moved next to other cards with the same suit, do not consider any similar moves in that suit. For example in ♠23456789TJQKA, only ♠2 after ♠3 will be considered as a next move. ♠2 after ♠4 will not be considered due to rule 4. ♠3 after ♠4 will not be considered since all cards moved are in ♠, end up next to other cards in ♠, and another move like this in ♠ had already been considered. My reasoning is that these moves within the suit will have to be made anyway, and there is no point in considering all permutations at every iteration. However I have not proved this. There are also more optimizations in this class of rule (find equivalently good next hands), but I can't think of one that would have a big impact.

Full Java implementation: http://pastebin.com/4eRX2a1w

Here is a run with 13 random cards (also below): http://pastebin.com/fLz4xRAf

```
level 0, bfs queue size 0
D H D S C D H S D D C S C
J 5 5 Q J 8 2 J K A Q 8 3
level 1, bfs queue size 1
D H D SS D D CC D H S C
J 5 5 QJ K A QJ 8 2 8 3
level 2, bfs queue size 23
SS DD H D D CC D H S C
QJ KJ 5 5 A QJ 8 2 8 3
level 3, bfs queue size 181
DD H D D CC D H SSS C
KJ 5 5 A QJ 8 2 QJ8 3
level 4, bfs queue size 336
DDD H D CC D H SSS C
AKJ 5 5 QJ 8 2 QJ8 3
level 5, bfs queue size 687
DDD D CC D HH SSS C
AKJ 5 QJ 8 52 QJ8 3
level 6, bfs queue size 632
DDDDD CC HH SSS C
AKJ85 QJ 52 QJ8 3

original hand
D H D S C D H S D D C S C
J 5 5 Q J 8 2 J K A Q 8 3
move groups 5 to 7 after group 11
D H D SS D D CC D H S C
J 5 5 QJ K A QJ 8 2 8 3
move groups 1 to 4 after group 5
DD H D SS D CC D H S C
KJ 5 5 QJ A QJ 8 2 8 3
move groups 1 to 4 after group 5
DDD H D SS CC D H S C
AKJ 5 5 QJ QJ 8 2 8 3
move groups 3 to 4 after group 6
DDD H CC DD SS H S C
AKJ 5 QJ 85 QJ 2 8 3
move groups 3 to 5 after group 6
DDD HH CC DD SSS C
AKJ 52 QJ 85 QJ8 3
move groups 2 to 3 after group 5
DDDDD SSS HH CCC
AKJ85 QJ8 52 QJ3
sorted in 6 moves
level 6, bfs queue size 595

```

Here is a run with 26 random cards: http://pastebin.com/Bw8kzfgU

Here is the run with spades in the reverse order: http://pastebin.com/NwAXavxE

---
Tags: algorithms, sorting, lower-bounds
---


# Question
Title: Traversals from the root in AVL trees and Red Black Trees
We all know that for insertion() operation in AVL tree following can happen:

We traverse down the tree from root to appropriate node and there insert the key and then for maintaining height balance we have to check heights of the ancestors of the newly inserted node and in doing so, we could end up traversing up to the root.

I completely agree with this.

But according to me the same can happen in Red Black tree because first we would traverse down the tree to appropriate node and then insert the key.Then there is a possibility that a series of rotation and flip color operations could make us traverse the path up to the root.

Now my question is : why following statement is right?

> In AVL tree insert() operation, we first traverse from root to newly inserted node and then from newly inserted node to root. While in Red Black tree insert(), we only traverse once from root to newly inserted node.

It came as a question, which of the following statements is right about AVL and Red Black trees and the option with given statement was marked correct in the answer key. I am trying to figure out mistake in my second observation?

# Answer
For virtually all kinds of binary search trees, including AVL trees and red-black trees, you can implement insertion in what is called a *bottom-up* fashion. This involves two passes through the tree: the first pass starting at the root and moving down the tree to find the right place to do the insertion, and the second pass starting at the insertion point and moving upward toward the root fixing the tree as necessary. Frequently, these two passes are implemented as one recursive function, where the first pass is going down the recursion, and the second pass is coming back out of the recursion.

For some kinds of binary search trees, including red-black trees but not AVL trees, the "fixes" to the tree can fairly easily be predicted on the way down and performed during a single *top-down* pass, making the second pass unnecessary. Such insertion algorithms are typically implemented with a loop rather than recursion, and often run slightly faster in practice than their two-pass counterparts.

Note that, for trees like red-black trees, where you can implement insertion either way, the two different approaches (bottom-up/two-pass vs top-down/one-pass) do not necessarily yield *exactly* the same tree, but will yield trees that are equivalent. For example, the exact pattern of red and black nodes may vary slightly, but will still obey all the expected invariants of a red-black tree.
> 5 votes

---
Tags: data-structures, search-trees, balanced-search-trees
---


# Question
Title: How to find a basis which is guaranteed to need 9 or less characters to represent a 12 digits number?
I'm trying to map a 12 digit number into a fixed width file. For a number of reasons, it must be compressed in such a way that it is guaranteed to be less than or equal to 9 characters (alpha numeric is fine). My first thought was a change of base, but I can't find an equation which gives an upper bound the number of characters needed for a given base.

For example, transforming into base 32

123456789101 -\> 3IV9I6JD

Which is 8 digits. How to find a basis which is guaranteed to need 9 or less characters to represent a 12 digits number?

# Answer
The largest 12 digit number in base 10 is $10^{12} - 1$. In general the largest $n$ position number in a base $b$ is $b^{n} - 1$. So in your case you need a base large enough that $b^{9} - 1 \> 999,999,999,999$ $(10^{12} - 1).$ Solving for $b$:

$$b^{9} - 1 \> 10^{12} - 1$$ $$b^{9} \> 10^{12}$$ $$b^{9/9} \> 10^{12/9}$$ $$b \> 10^{12/9}$$ $$b \> \sqrt\[9\]{10^{12}}$$ $$b \> 21.54$$

So make your base 22 and your numeric data will fit in 9 positions.
> 11 votes

---
Tags: databases, encoding-scheme, base-conversion
---


title: Shannon Entropy for Binary Numbers

text:
# Question
Title: Shannon Entropy for Binary Numbers
First of all, I have to mention that I am very new in the field of information theory. I have a question regarding the Shannon Entropy calculation for binary values. As far as I understood, the main assumption in the Shannon Entropy formula is that all the bits have the same weights. However, I am looking for a formula/techniques to calculate the entropy based on the weight of each bit of a binary string. Let me elaborate on this.

Suppose we have a 3-bits binary number (b2, b1, b0) and let us assume that the probability of being 0 or 1 is 0.5. Based on the Shannon's theorem the entropy considers all these bits with the same weight. If I give tell you that (b1, b0) = (00) then you can guess that the final value is either 0 or 4. But if I give you (b2,b1) = (00) you can guess that the final value is either 0 or 1. To me it means b2, b1 provides more information than knowing b1,b0. Because, you can guess the final value with less error. Is it really related to information or it is something else?

It would be good if you could provide me some links to get more information about this topic.

This is the link to my related question: Hamming Error Correction

Thanks

# Answer
Take a look at rate-distortion theory, which studies information transmission in settings where a certain distortion is allowed (such as audio, image, or video compression).
> 3 votes

# Answer
I may be misunderstanding your question but I think you may be misinterpreting error. Measuring error should not be based upon the distance between the values, rather the number of possible discrete values given a particular state. That is, the fact that the distance between messages (4) and (0) is greater than (1) and (0) is inconsequential.

For either of your scenarios, a given partial message (ie. x00 or 00x) has at most 2 possible messages. Given that all bits have the same state probabilities, the probability of guessing wrong final value is the same in either scenario. So, knowing a particular two bit states does not provide more (or less) information about the third.

All bits of an encoded message do not have to have the same probability. I do not see the immediate use case for associating a weight with each bit. Could you elaborate on what you are trying to accomplish? To me it sounds like you want to artificially bias the entropy based upon the state of each bit, but I can't see why that couldn't be accomplished by simply changing the probability associated with each bit state and using the standard entropy equations found at: https://en.wikipedia.org/?title=Information\_theory
> 0 votes

---
Tags: information-theory
---


# Question
Title: Complexity calculation using a recurrence relation
I just can't solve this problem, I'm new to reccurences. I have this recurrence

$T(n)=n\*T(n-1)$
$T(1)=1$

The second term will be:

$T(n-1)=(n-1)\*T(n-2)$

And so on.

It's complexity is **O(n!)** but i don't know how to solve it.

I hope you can help me with an idea!

# Answer
> 0 votes
Hint: Prove by induction on $n$ that $T(n) = n!$.

Note that a recurrence relation doesn't have a *complexity*. Rather, it defines a function. In many cases, this function is the running time of some algorithm, and then the time complexity of the *algorithm* is the solution to the recurrence.

---
Tags: complexity-theory, recurrence-relation, induction, factorial
---


title: Constructible enumerable set

text:
# Question
Title: Constructible enumerable set
We suppose that the sets $S\_1$ and $S\_2$ are constructible enumerable, that means that there is an algorithm that enumerates them. Show that the sets $S\_1 \cup S\_2$ and $S\_1 \times S\_2$ are also constructible enumerable.

To show this do we have to construct a Turing machine for the union and one for the cartesian product?

# Answer
Hints:

1. For $S\_1 \cup S\_2$, use the same idea in the proof that the natural numbers and the integers have the same cardinality. The proof goes by listing the integers in sequence: $$ 0,1,-1,2,-2,3,-3,\ldots $$ You can think of $S\_1$ as $0,1,2,3,\ldots$ and of $S\_2$ as $-1,-2,-3,\ldots$.
2. For $S\_1 \times S\_2$, use the same idea in the proof that the natural numbers and the positive rationals have the same cardinality. The proof uses the "diagonal method", and consists of listing the rationals sorted by the maximum of the numerator and the denominator: $$ \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{2}{2}, \frac{1}{3}, \frac{2}{3}, \frac{3}{1}, \frac{3}{2}, \frac{3}{3}, \ldots $$ In this case $S\_1=S\_2$ are both $1,2,3,\ldots$.
> 1 votes

# Answer
One way to show that a set is enumerable, is to provide a TM that enumerates all the words in that set. (that what the comments are trying to say, and probably what you are asking)

A second way is to show a bijection to another enumerable set of the same cardinality (like the natural numbers or like $S\_1$ or $S\_2$ themselves, in case they are infinite.) This is what Yuval was trying to hint.

Choose your way, both are correct.
> 1 votes

---
Tags: algorithms, computability, turing-machines, enumeration
---


title: Can a computer count to infinity?

text:
# Question
Title: Can a computer count to infinity?
So, could a computer count to infinity assuming it was a super computer and had near unlimited amounts of ram and hard drive/solid state drive storage? I am being serious when I ask this.
\[This is what I am asking\]: Wouldn't Infinity mean endless counting, and wouldn't *that* be infinity?

# Answer
It depends on what you mean by "count to infinity". Specifically, how does the computer give output?

consider the following quesitons:

* Can a computer show, on its screen, all the number from 1 till (infinity): increasing the number on screen by 1 every second?
* Can a computer send on the network line, a package that contains a number starting with 1, and increasing the number by 1 every second (splitting large numbers into multiple packages, assuming computation is very fast, and "every second" can be "every minute", etc, as necessary)

then, the answer for the above is **YES**.

However,

* can a computer hold (in his memory/RAM/HD/whatever finite storage unit it connects to) a number, so that it starts with 1 and increase this number every x seconds?

then the answer is **NO**. At some point, the computer will be out of storage. This is because the storage is finite, and "counting to infinite" requires an infinite amount of information.
> 3 votes

---
Tags: counting, mathematical-programming
---


# Question
Title: Why a language specified by a regular expression is not a complement of a given language?
I am taking a compiler MOOC online on my own time. The class is self paced. There is a question with an answer but I can't understand why the answer is correct.

Here is the question.

> For any language $L$, the complement of the language (usually written $L′$) is defined as the language that consists of all the strings that are NOT in $L$. That is,
>
> $L′=Σ^\*−L$
>
> It turns out that the complement of any regular language is also a regular language. Which of the following regular expressions define a language that is the complement of the language defined by the regular expression: $1(01)^\*$?
>
> 1. $(10)^\*+\big((10)^\*0(0+1)^\*\big)+\big(1(01)^\*1(0+1)^\*\big)$
> 2. $\epsilon + (0(0 + 1)^\*) + ((0 + 1)^\*0) + \big((0 + 1)^\*(00 + 11)(0 + 1)^\*\big)$
> 3. $(0 + \epsilon)\big((1 + \epsilon)(0 + \epsilon)\big)^\*$
> 4. $(10)^\*$

Correct answers are 1 and 2. I can't understand why 3 and 4 are not correct as well since the strings generated by these languages are also not in $L$.

Any explanation is greatly appreciated.

# Answer
The complement of a language $L$ should contain *all* strings not in $L$. Your language $L$ doesn't contain the word $0$, which the language $(10)^\*$ also doesn't contain – so $(10)^\*$ can't be the complement of $L$.
> 4 votes

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