title: Halting problem without self-reference

text:
# Question
Title: Halting problem without self-reference
In the halting problem, we are interested if there is a Turing machine $T$ that can tell whether a given Turing machine $M$ halts or not on a given input $i$. Usually, the proof starts assuming such a $T$ exists. Then, we consider a case where we restrict $i$ to $M$ itself, and then derive a contradiction by using an instance of a diagonal argument. I am interested how would the proof go if we are given a promise that $i \not = M$? What about promise $i \not = M^\prime$, where $M^\prime$ is functionally equivalent to $M$?

# Answer
Suppose HALTS is a TM that reads its input as a pair $M$ and $x$, where $M$ is a TM encoding and $x$ is any input to that TM.

Your question is if what would happen if we assumed HALTS solved the halting problem for all inputs $\langle M,x \rangle$ such that $x$ is not an encoding of a TM that is functionally equivalent to $M$.

I claim this implies a contradiction. I came up with this on the spot, so I welcome any and all criticism of my proof. The idea of the proof is that rather than diagonalizing something on itself, we make two mutually recursive TMs that behave differently on some input (thus are not functionally equivalent), but otherwise cause contradictions.

Let $D\_1$ and $D\_2$ be two mutually recursive TMs (which is to say we can simulate, print, etc, the description of $D\_2$ inside the program of $D\_1$ and vice versa). Note that we can make mutually recursive TMs from the recursion theorem.

Define $D\_1$ and $D\_2$ as follows: on input $x$, if $|x| \< 10$ (10 chosen arbitrarily), then $D\_1$ accepts and $D\_2$ loops. (Thus, they are not functionally equivalent).

Given input $x$ with $|x| \ge 10$, define $D\_1$ to simulate HALTS on $\langle D\_2, x \rangle$ and halt if $D\_2$ halts or loop if $D\_2$ loops.

Given input $x$ with $|x| \ge 10$, define $D\_2$ to simulate HALTS on $\langle D\_1, x \rangle$ and loop if $D\_1$ halts or halt if $D\_1$ loops.

Then note that for any $x$ with $|x| \ge 10$, $D\_1$(x) either halts or loops. If $D\_1$ halts on input x, then we know HALTS($D\_2$, x) determined that $D\_2$ halts on input x. However, $D\_2$ halting on input x implies that HALTS($D\_1$, x) loops.

If $D\_1$ on input $x$ loops, the contradiction follows similarly.

This is a contradiction unless $x$ is an encoding for a turing machine functionally equivalent to $D\_1$ or $D\_2$, in which case HALTS has undefined behavior. However, $x$ was chosen at arbitrary from all strings of size greater than $10$. Thus, it remains to show there exists a turing machine with an encoding of size greater than 10 that behaves differently than $D\_1$ and $D\_2$. We can construct such a machine trivially. QED.

Thoughts?
> 7 votes

# Answer
You're still not out of the woods. You run into the same problem, only now you give it a different TM, $M'$ as input, where you've chosen $M'$ to be functionally equivalent to $M$ (say you add a new rule to $M$ so that $M'$s opening moves are one step right, one step left and otherwise you make no changes). You'll still run into a contradiction. You might try eliminating all the TMs that are equivalent to $M$, but that's an undecidable set.

---

**Update**. Fix an encoding scheme where $\langle\\,M\\,\rangle$ denotes the description under that scheme of a TM $M$ and suppose you had a TM, $H$ where

* $H(\langle\\,M\\,\rangle, x)$ is undefined when $x$ is the encoding of a TM which computes the same partial function as $H$ (i.e., $x$ and $H$ are functionally equivalent).
* For all other inputs, $H(\langle\\,M\\,\rangle, x)$ returns true if and only if $M(x)$ halts.

Now the usual diagonalization construction still results in a contradiction. Define a TM $Q$ by

```
Q(x)=
  if H(<Q>, x) = false
    return true
  else
    loop forever

```

Clearly $Q$ and $H$ are functionally inequivalent, so we can let $x=\langle\\,Q\\,\rangle$ and find that $Q(\langle\\,Q\\,\rangle)$ halts if and only if it doesn't halt, so there can be no such TM $H$.
> 2 votes

---
Tags: computability, undecidability, halting-problem
---


title: How is data written to RAM

text:
# Question
Title: How is data written to RAM
From my understanding(correct me if I am wrong) when I read data from RAM memory it is copied into processor cache and than it is copied into register to be used by the processor. When I create data (like variable) is it first created in register and than copied to cache and from cache to RAM or is it directly created in RAM?

Additional question:Does stack and heap exist only in RAM or do they exist in processor cache as well?

# Answer
> 8 votes
When you read data from a given memory address, the memory manager checks if there is a copy in the cache. If yes (cache hit), the copy is read into the register. If no (cache miss), the cache is first updated with a row of memory from RAM; then the data can be read into the register.

Conversely, when you write to a memory address, the data is just written to the cache, making room if required. Later, when the cache line must be freed or is explicitly flushed, the row of memory is copied to RAM.

If you perform successive reads and writes to the same address, it can very well arise that all changes are made in the cache and the RAM left untouched. From the processor's point of view, the presence of the cache is transparent. It just reads from and writes to memory addresses, and the memory manager optimizes the transfers.

Note that you don't "create" data in memory. When a program is loaded, some RAM space is assigned to it and reserved (possibly also initialized), and the addresses of the variables are "mapped" onto that space. Then the program is allowed to write to or read from these addresses.

In modern, multicore CPUs, cache management is much more complicated because several concurrent reads/writes to the same memory addresses can occur. The MMU must ensure that all caches and RAM remain coherent and "synchronize" their content.

The stack and the heap have a range of memory addresses allocated, and they are handled through the cache like ordinary program space. The stack is an essential resource during program execution and it is extremely frequently accessed. It is important that it be cached as well.

# Answer
> 4 votes
> From my understanding(correct me if I am wrong) when I read data from RAM memory it is copied into processor cache and than it is copied into register to be used by the processor.

That is generally correct. Just be sure you understand that we're talking about reading data that happens to be in RAM. We're not talking about issuing an instruction to read data from an address because that data may, or may not, be in RAM. (It may be in this core's cache, it may be in some other core's cache, it may be on a peripheral, and so on.)

> When I create data (like variable) is it first created in register and than copied to cache and from cache to RAM or is it directly created in RAM?

Yes (though the register can by bypassed on most processors), but again, let's be clear. We're talking about what happens if, for some reason, the data does in fact need to go to RAM. Writing to an address may or may not wind up writing data to RAM.

> Additional question:Does stack and heap exist only in RAM or do they exist in processor cache as well?

Forcing stack and heap operations to go to RAM would make performance horrible. Stacks and heaps are used constantly, and we want to avoid using RAM wherever possible. The point of the cache is to avoid RAM operations as much as we possibly can. Not improving the most common operations would be a non-starter.

Basically, the distinction between stack and heap is primarily in how the address space is used by the instructions. As far as the cache and memory hardware is concerned, they're both just address space that is ultimately backed by RAM.

The primary purpose of all of these caches is essentially to minimize the number of reads and writes that have to go to RAM. Even if a core isn't waiting for the reads and writes to complete, memory bandwidth is typically a very limited resource compared to the rate at which CPUs can process information.

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: How to write all $r$-tuples with a certain property in a list
I have the following question:

Let $a,b,c,d$ be four natural numbers with $a \leq b$ and $c\leq d$.

I have written a program that produces a list, which has as entries all 2-tuples $(x,y)$ with $x\in \[a..b\]$ and $y \in \[c..d\]$.

Now, I have a new list, let's call it list\_1. It consists of elements indexed by the $(x,y)$.

For example, let a=3, b=4, c=7, d=8.

Then my programm produces list=\[\[3,7\],\[3,8\],\[4,7\],\[4,8\]\].

Now, my list\_1 is \[M\_{3,7},M\_{3,8},M\_{4,7},M\_{4,8}\].

> I would like to have a new list, call it list\_2, which has exactly the following entries.
>
> list\_2 shall contain all $r$-tuples (for $r\in\\{1,...,m\\}$; $m$ is the size of list\_1) with the form
>
> $(M\_{i\_1},...,M\_{i\_r})$, such that $i\_j$ is an entry of list, that comes before $i\_k$ for all $j\<k$.
>
> For example, $i\_j=\[3,8\]$ comes before $i\_k=\[4,7\]$.

In our example, list\_2 looks like this:

$(M\_{3,7}),(M\_{3,8}),(M\_{4,7}),(M\_{4,8}), (M\_{3,7},M\_{3,8}),(M\_{3,7},M\_{4,7}),(M\_{3,7},M\_{4,8}),(M\_{3,8},M\_{4,7}),(M\_{3,8},M\_{4,8}),(M\_{4,7},M\_{4,8}), (M\_{3,7},M\_{3,8},M\_{4,7}),(M\_{3,7},M\_{3,8},M\_{4,8}),(M\_{3,7},M\_{4,7},M\_{4,8}),(M\_{3,8},M\_{4,7},M\_{4,8}),(M\_{3,7},M\_{3,8},M\_{4,7},M\_{4,8})$.

I would like to have this in general for arbitrary natural numbers $a,b,c,d$ with $a \leq b$ and $c\leq d$.

I would be very grateful, if somebody was able to send me a pseudo-code.

Thanks for the help!

# Answer
There are many ways to compute all $k$-tuples of elements in a given list $L$. One way is to use recursion and the analogue of Pascal's identity $$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}. $$ We can interpret this identity as follows. Write $L=x, L'$, where $x$ is the first element and $L'$ is the rest of the list. A $k$-tuple of $L$ is either a $k$-tuple of $L'$, or $x$ along with a $k-1$-tuple of $L'$. I'll let you figure out how to turn this into a solution for your problem.

Using the same idea, you can also write a function that given $m$ outputs the $m$th $k$-tuple of $L$, in lexicographic order. You can even decode such a tuple back to its index in this order.

If you don't like recursion, you can also try an iterative approach. The idea is to start with the tuple $0,1,\ldots, k-1$, and keep *incrementing* the tuple. To increment the tuple, start by incrementing the last position. If it's now $n$, we backtrack and increment the previous position. If that one is now $n-1$, we backtrack once more, and so on. Eventually, unless we were at the last tuple, we well have incremented some position successfully, say to the value $m$. The following position (if any) we set to $m+1$, the one after it (if any) to $m+2$, and so on. I'll let you figure out how to implement this idea.

Both approaches can be implemented so that they produce the same, lexicographic, order. There are probably other, trickier approaches, that rely on applying an intricate sequence of transpositions on the list $0,1,\ldots, n-1$, but the ones I described are general approaches applicable in many other situations. For the more magical ones, check Knuth's new volumes-in-preparation of TAOCP.
> 1 votes

---
Tags: algorithms, combinatorics, sorting, lists
---


# Question
Title: A graph in descriptive complexity - is $x$ already a vertex?
So suppose that there is an undirected graph with edge connections known. Now in first-order logic there is quantifier $\forall x$. Then does this automatically refer to vertexes, or can we use relation like $v(x)$ to say that $x$ is a vertex?

# Answer
> 1 votes
(First-order logic) formulae are independent of structures; you just have variables, predicates and possibly functions (in addition to the syntactical symbols). To decide whether a formula $\varphi$ is true in a given structure $S$ (consisting of a universe of individuals $U$ and an interpretation of predicates $I$), i.e. whether $S$ is a model of $\varphi$, you apply the semantic rules of first order logic.

Concerning your specific question: if you have $\varphi = \forall x: F$ where $F$ is some formula, then $x$ denotes exactly all vertices iff you defined your structure $S = (U,I)$ such that $U$ contains exactly all vertices. Note that if you do that and want access to the edges, then you'll need to define some predicate $e(x,y)$ such that $e(x,y) \Leftrightarrow \text{there is an edge between } x \text{ and } y$.

More generally: the quantifiers do not differentiate between elements of your universe, the predicates will have to do that. If you want to check $F$ only for all vertices but your universe contains elements that are not vertices, then you do what you suggested: introduce a predicate $v(x)$ and use $\varphi' = \forall x: (v(x) \rightarrow F)$

# Answer
> 1 votes
Let me quote from Immerman's survey on descriptive complexity: In Descriptive Complexity we view the input as a finite logical structure. A graph is a logical structure whose universe is the set of vertices and $E\_G$ is the binary edge relation.

So when describing graph properties, qualifiers quantify over all vertices, and edges are encoded by a binary relation. This is the convention in descriptive complexity. If you follow some other convention then you might get different behavior.

# Answer
> 0 votes
Typically, when referring to vertices in a graph, one does by the following. Let $G=(V,E)$ be a graph such that $V$ is the set of vertices and $E$ is the set of edges. Then you would proceed $\forall x \in V$ etcetera.

---
Tags: complexity-theory, logic, first-order-logic, descriptive-complexity
---


# Question
Title: Satisfying all the conditions of case 3 of the Master Method except the regularity condition
The regularity condition of case 3 of Master Method says that $af(n/b) \< cf(n)$, for $c \< 1$.

How to devise a recurrence relation that satisfies all other conditions of case 3 except the regularity condition?

# Answer
> 3 votes
For a run-time recurrence to satisfy all conditions of **case 3** and not satisfy the **regularity condition**, we have to think of such $f(n)$ that grows or shrinks by a factor of $a$ when $n$ is decreased to $n/b$. Consider the following function:

> $T(n) = T(n/2) + n(\sin(n - \pi/2) + 2)$

Let's take a look at $f(n)$

We can choose x such that $f(x/2) \> f(x)$ even though $f(x) \geq x$ throughout. Let's check the regularity condition for $T(n) = T(n/2) + n(\sin(n - \pi/2) + 2)$

$(n/2)(\sin(n/2 - \pi/2) + 2) \leq cn(\sin(n - \pi/2) + 2)$

Thus $c \geq (1/2)\left(\frac{\sin(n/2 - \pi/2) + 2}{\sin(n - \pi/2) + 2}\right)$

Let $n = 2\pi k$, where k is odd

Then, $\sin(n/2 - \pi/2) + 2 = \sin(\pi/2) = 1$

$\sin(n - \pi/2) + 2 = \sin(-\pi/2) = -1$

And we get,

$c \geq (1/2)\left(\frac{1 + 2}{-1 + 2}\right)$

$\implies c \geq 3/2$ Thus we cannot choose c \< 1 to satisfy the regularity condition.

---
Tags: recurrence-relation, master-theorem
---


title: Interleaving algorithm for 2 stacks

text:
# Question
Title: Interleaving algorithm for 2 stacks
Suppose I have two stacks $\<a\_1,a\_2,...a\_m\>$ and $\<b\_1, b\_2,...b\_n\>$ and a third stack of size $m+n$. I want to have the third stack in the following manner, $$\<a\_1,b\_1,a\_2,b\_2,...a\_n,b\_n...a\_m-1,a\_m\>$$ for $$m\>n$$ This was easy to do if the two initial stacks were not size constrained. But if the two stacks are size constrained, I am in a fix.

Is it even possible to interleave the elements of the two stacks into a third stack in constant space? Also what would be the minimum number of moves to do this? I know using recursion this can be reduced to Tower of Hanoi variant, but what about a non-recursive algorithm?

# Answer
> 2 votes
Here's an algorithm that works without using recursion. I might say it's even easier to do without recursion.

I'll be working off the underlying assumption that you don't have access to temporary variables, and that the only available operation to you is $pop(s, d)$ which pop the top element of s(source) and places it on top of d(destination). E.g.: we have the stacks $A=\<a\_1,a\_2,a\_3\>$ and $B=\<\>$. After calling $pop(A,B)$ we have $A=\<a\_1,a\_2\>$ and $B=\<a\_3\>$.

First, I'll define a new function $popm(s,d,c)$. It's role is to iterate $pop(s,d)$ c times. E.g.: $A=\<a\_1,a\_2,a\_3\>$ and $B=\<\>$. After calling $popm(A,B,3)$, $A=\<\>$ and $B=\<a\_3,a\_2,a\_\>$.

Here is the proposed algorithm.

1. Start with $A=\<a\_1,a\_2,\dots,a\_m\>$, $B=\<b\_1,b\_2,\dots,b\_n\>$ and $C=\<\>$
2. $pop(B,C,n)$. $A=\<a\_1,a\_2,\dots,a\_m\>$, $B=\<b\_1,b\_2,\dots,b\_n-1\>$ and $C=\<b\_n\>$ The goal is free a spot in $B$
3. $popm(A,C,m)$. $A=\<\>$, $B=\<b\_1,\dots,b\_n-1\>$ and $C=\<b\_n,a\_m,\dots,a\_2,a\_1\>$ You've exposed $a\_1$ on top of $C$
4. $pop(C,B)$. $A=\<\>$, $B=\<b\_1,\dots,b\_n-1,a\_1\>$ and $C=\<b\_n,a\_m,\dots,a\_2\>$ Have $B$ hold the value $a\_1$ on top
5. $popm(C,A,m-1)$. $A=\<a\_2,a\_3,\dots,a\_m\>$, $B=\<b\_1,\dots,b\_n-1,a\_1\>$ and $C=\<b\_n\>$ Restore $A$ (excluding $a\_1$) to it's original order. Also, have $A$ hold $b\_n$ for now.
6. $pop(C,A)$. $A=\<a\_2,a\_3,\dots,a\_m,b\_n\>$, $B=\<b\_1,\dots,b\_n-1,a\_1\>$and $C=\<\>$ Have $A$ hold $b\_n$ for now.
7. $pop(B,C)$. $A=\<a\_2,a\_3,\dots,a\_m,b\_n\>$, $B=\<b\_1,\dots,b\_n-1\>$ and $C=\<a\_1\>$ Put $a\_1$ at the bottom of $C$, it's desired place.
8. $pop(A,B)$. $A=\<a\_2,a\_3,\dots,a\_m\>$, $B=\<b\_1,\dots,b\_n-1,b\_n\>$ and $C=\<a\_1\>$. Restore $b\_n$ to the top of B
9. Interchange $A$ and $B$ and repeat from step 1, adjusting for the new state of $A$, $B$ and $C$. You can ignore steps 2, 6 and 8 since you now will have a free spot on top of B from now on.
10. When $B$ has been emptied, $popm(A,B,m-n)$ then $popm(B,C,m-n)$ to have your remaining stack $A$ do a "double back flip" off $B$ onto $C$.

Let me say why this isn't related to tower of Hanoi. In the Hanoi problem, you cannot inverse the tower. Moreover, you have the middle peg as a temporary holder, which we don't have. Finally, in this example, you can reverse the order on the elements.

# Answer
> 3 votes
**Note**: *I found a better technique which I give in a separate answer, which is more general, faster and simpler, though the complexity results remain somewhat similar. I chose to leave this answer rather than replace it, as it may be interesting to compare, and both solutions were too long for a single answer.*

Let A, B and C be the three stacks. I assume that the top of A and B are on the small index side.

I note `(X,Y,p)` the transfer of p elements from the top of X to the top of Y. This has of course the effect of inverting the order of these p elements, and has a cost p.

Let q and r the quotient and remainder of the integer division of m by n. Thus m=q\*n+r.

## Pseudocode for the interleaving

```
% transfer of the m-n unmatched tail by chunk of n elements
For i from 1 by 1 to q-1 do
  % transfer the bottom n elements remaining in A
  (B,C,n)
  (A,C,m-i*n)
  (A,B,n)      % bottom n
  (C,A,m-i*n)
  (B,C,n)      % bottom n
  (C,A,n)      % bottom n
  (C,B,n)
  (A,C,n)      % bottom n
  end loop
if r≠0 then
  % transfer the remaining r elements of the umatched tail
  (B,C,n)
  (A,C,n)
  (A,B,r)      % bottom r
  (C,A,n)
  (B,C,r)      % bottom r
  (C,A,r)      % bottom r
  (C,B,n)
  (A,C,r)      % bottom r
  end if

% Now we have transferred the extra elements of A at the bottom of C.
% We have only 2n slots available in C, for intertwining A and B.
% But we have m-n free slots in A.

(A,C,n)   % rest of A inverted in C
(B,A,n)   % B inverted in A
k=n       % number of remaining elements of each stack still to be transferred
t=m-k     % available space in A to do the transfer
while k>0 do
  t=min(k,t)
  (C,A,t)   % last t of A in direct order in A
  (C,B,k-t) % top rest of A in B in direct order
  (A,B,t)   % last t of A inverted in B
  For i from 1 by 1 to t do    % intertwin in C last t elements of remainder
    (A,C,1)
    (B,C,1)
    end loop
  (B,C,k-t) % top rest of A inverted in C
  k=k-t
  t=2t
  end  loop

```

## Complexity

I am only counting the number of moves. It actually gives the complexity since the control statements introduce only a constant factor on the moves and the number of moves is polynomial.

For one iteration of the first loop : $6n+2(m-i\times n)$

Hence the cost of the loop is $\sum\_{i=1}^{q-1}6n+2(m-i\times n)$ = $(q-1)(6n+2m)-2nq(q-1)/2$ = $(q-1)(6n+2m-nq)$ = $(q-1)(6n+2m-(m-r))$ = $(q-1)(6n+m+r)$

The cost of the following conditional is at worst $4(n+r)$

So the total cost for the last $m-n$ elements of stack A is majored by $q(6n+m+r) \leq q(7n+mn/n) \leq 7m+m^2/n$

The cost of transferring the tail of A is quadratic in $m$ when $n$ is constant, as B becomes too small with increasing values of $m$ to do the tranfer in a fixed number of passes over the whole stack. The linear decrease of the remaining part to be transferred does not help enough.

Things are however better with the parts of the two stacks that must be intertwined.

There is a first cost of $2n$.

The cost of one iteration of the loop is $2t+2(k-t)+2t$, the cost of the inner loop being $2t$. So this makes a total of $2(k+t)$.

If $m\geq 2n$ then the loop is executed only once, with $k=t=n$, hence the cost is $4n$. Note that $4n\leq 2m$ in this case.

Otherwise we start the loop with $k=n$ and $t=m-n$, so that we have $k+t=m$. But the update `k=k-t; t=2t` at the end of the loop preserve this property as an invariant. So each iteration actually costs $2(k+t)=2m$, except possibly the last one, since $t$ may be reduced by the statement `t=min(k,t)`, thus lowering the cost of that last iteration. Note that, in this case, $2m\leq 4n$.

Since $t$ doubles at each iteration, but will not be greater than $n$, the number of iterations is at worse $1+\log\_2 n$, when $t$ starts with value 1. Note that there must be at least one iteration when $n=1$ (though it could be simplified), in which case $\log\_2 n=0$.

But the initial value of $t$ is actually $min(n, m-n)$. Since it would take $\log\_2 min(n, m-n)$ iterations to reach that value, starting from 1, the actual number of iterations is $1+\log\_2 n - \log\_2 min(n, m-n) = $1+log\_2 \frac{n}{min(n, m-n)}$

Hence the total cost for this part is less than $2n+4n(1+\log\_2 \frac{n}{min(n, m-n)})$

So, the **overall complexity** in stack moves is $O(m^2/n+n(1+\log \frac{n}{min(n, m-n))})$

In particular the **complexity is linear in $n$ or $m$ when the ratio $h=m/n$ remains constant**.

This is obvious for the first term $m^2/n=h^2n$.

For the second term, we have $min(n,m-n)=min(n,n(h-1))=n min(1, h-1)$. Hence $n(1+\log \frac{n}{min(n, m-n))})= n(1+\log\frac{1}{min(1, h-1))})$

# Answer
> 1 votes
It can certainly be done, at least in something like $O(m^2)$ steps. This is without consideration to given order of the stacks or intended result. An arbitrary element $a\_i$ of either given stack can be moved to the bottom of the last stack in the following steps.

* Given is $\<a\_1, \dots, a\_i, \dots a\_n\>$; $\<b\_1, \dots, b\_m\>$; $\<\>$.
* First move $b\_1$ and $a\_1 \dots a\_{i-1}$ to last stack: $\<a\_i, \dots a\_n\>$; $\<b\_2, \dots, b\_m\>$; $\<a\_{i-1}, \dots, a\_1, b\_1\>$.
* Then move $a\_1$ to second stack and move contents of last stack to first stack: $\<b\_1, a\_1, \dots, a\_{i-1}, a\_{i+1}, \dots a\_n\>$; $\<a\_i, b\_2, \dots, b\_m\>$; $\<\>$.
* Finally move $a\_i$ to last stack.

The resulting configuration allows for these steps to be repeated until last stack is filled in any order.

# Answer
> 1 votes
# A simpler and more general answer

## Introduction

Since we do not know for sure from the OP where is the top of the stack, I am proposing a solution that is insensitive to it, and can actually answer his question for any type of interleaving, as long as it preserve for the elements coming from a given stack the order that they had in that stack.

The general idea is quite simple: we transfer elements from A or B to C in any order corresponding to the desired interleaving. This will produce the reverse order of the desired result in C. It has a cost of exactly $m+n$ moves.

Then we are left with the problem of reversing the content of the stack C, using A and B. This is the problem I will now address.

The algorithms proposed have complexity $\Theta(m^2/n)$, which is quadratic in $m$ when $n$ is constant, and linear in $m$ when the ratio $m/n$ is constant. A simple twist in the second algorithm can double the speed.

These solutions do not require $m\>n$, wich is a hypothesis of the question. It also works when $m=n$.

*A somewhat more complexe version of this solution, now edited out and replaced by those given below, was initially inspired in part by the answers of ZeroUltimax and Karolis Juodelė, which are both based on the idea of moving a single element of the top of A or B to the bottom of C.*

*I am leaving posted my previous answer, which shows how complex a problem can become, when starting on the wrong path. Separating issues can make things much simpler.*

## The problem of stack reversal

We have two empty stacks A and B, respetively of size $m$ and $n$. We assume, without loss of generality, that $m\geq n$. We also have a stack C of size $m+n$. Note that there is no requirement that $m\neq n$.

Using only stack operations, and no extra memory for stack elements other than A and B, we want to reverse the order of the content of C, i.e. to end up with the same content in C in reverse order.

**Notations used for the algorithms**:

We note (X,Y,p) the transfer of a segment of p elements from the top of stack X to the top of stack Y. This has of course the effect of reversing the order of these p elements, and has a cost p.

For each segment we transfer in a stack X, we call it direct if it is in its original order in C, and reverse when it is in reverse order. We comment each application of a transfer by specifying whether the transferred segment is in direct or reverse order after the transfer is performed.

## A very simple stack reversal algorithm

The idea is to operate with segments of size n, taking care to inverse their order, and to inverse the order of the elements they contain.

The comments indicate the order of the elements of the segment transferred, just after tranfer. Initially all element are in C, in direct order, which we want to reverse.

**Pseudocode for the simple algorithm**

```
r = m modulo n
if r==0 then r=n
q = (m-r)/n             % not actually used; number of iterations is q+1
For i from m by -n do
  (C,A,n)      % reverse
  (A,B,n)      % direct
  (C,A,i)      % reverse
  (B,C,n)      % reverse  - final position
  if i≤n then
     (A,B,r)   % direct
     (B,C,r)   % reverse  - final position
     exit loop
  (A,C,i)      % direct
  end loop

```

**Complexity**

We measure the complexity in number of moves of one element.

Each iteration costs $3n+2i$ moves, and there is an extra $r$ moves at the last iteration.

There are $q+1$ iteration with $i=m-j\times n$ for $j\in\[0,q-1\]$.

So the total cost, i.e., number of moves, is:
$\begin{align\*} \mathcal{C} &= r+\sum\_{j=0}^q 3n+2(m-jn) \\ &= r+(q+1)(3n+2m)-2n\sum\_{j=0}^qj \\ &= r+(q+1)(3n+2m)-2nq(q+1)/2 \\ &= r+(q+1)(3n+2m-nq) \\ &= r+(q+1)(3n+2m-(m-r)) \\ &= r+(q+1)(3n+m+r) \\ &= 3nq+qm+qr+3n+m+2r \\ &= 3(m-r)+qm+qr+3n+m+2r \\ &= qm+qr+4m+3n-r \\ &= qm+(q-1)r+4m+3n \\ &= m(m-r)/n + r(m-r)/n +4m+3n-r \\ &= m^2/n-mr/n + mr/n-r^2/n +4m+3n-r \\ &= m^2/n - r^2/n +4m+3n-r \\ &= m^2/n - (r^2/n+r) +4m+3n \end{align\*}$

Since $r\in\[1,n\]$, the **asymptotic complexity** is $\Theta(m^2/n)$.

The algorithm is linear in $m$ when the ratio $m/n$ is constant. It is quadratic in $m$ if $n$ is constant. Note also the number of moves increases with the ratio $m/n$, in particular when $n$ gets smaller for constant $m$, and the algorithm no longer works for $n=0$.

The coefficient of the main term is $1/n$ when the algorithm is quadratic because $n$ is constant.

The result is of course the **same for the initial interleaving problem**, as it take only a linear amount of extra moves.

---

## An stack reversal algorithm that is twice as fast

The analysis of the previous algorithm shows there seem to be no way of escaping the back and forth transfer of the bulk of the stack. But the algorithm would be faster if we could do more work, whenever the stack is thus moved between C and A. The limiting factor is the size $n$ of the smaller stack B, which is the maximum that may be moved together from one end of the stack content to the other end. But the weakness of the previous algorithm is that it works on only one end, building the final reversed stack at the bottom of C. We now propose to use the same strategy, but working on both end at the same time, building the lower half of the final reversed stack at the bottom of C and the upper half in direct order at the bottom of A. This allows to process $2n$ elements for each back and forth movement of the stack, and will thus double the speed, at least when $m/n$ is large, which is precisely what makes the algorithm otherwise slower.

The stacks C and A have then a symmetrical role for most of the algorithm.

**The faster algorithm in pseudocode**

```
s = m+n modulo 2n
if s==0 then s=2n
t = (m+n-s)/2n        % number of iterations, not actually used
For i from m by -2n while i>n do
  (C,A,n)      % reverse
  (A,B,n)      % direct
  (C,A,i)      % reverse
  (B,C,n)      % reverse  - final position in C
  (A,B,n)      % direct
  (A,C,i-n)    % direct
  (B,C,n)      % reverse
  (C,A,n)      % direct   - final position in A
  end loop
if s≥n then
  (C,A,n)      % reverse
  (A,B,n)      % direct
  (C,A,s-n)    % reverse
  (B,C,n)      % reverse  - final position in C
  (A,B,s-n)    % direct
  (B,C,s-n)    % reverse  - final position in C
else
  (C,A,s)      % reverse
  (A,B,s)      % direct
  (B,C,s)      % reverse  - final position in C
  end if
(A,C,t*n)    % reverse  - push back into C the part of the work accumulated in A

```

**Complexity** The cost of one iteration is $5n+2i$ where $i=m-2nj$ for $j\in\[0,t-1\]$

So the cost of the loop is
$\begin{align\*} \mathcal{C}\_{loop} &= \sum\_{i=0}^{t-1} 5n+2(m-2nj) \\ &= t(2m+5n) -4n(t(t-1)/2)) \\ &= t(2m+5n-2n(t-1)) \\ &= t(2m+7n-2nt) \end{align\*}$

Since $2nt=(m+n-s)$ we have
$\begin{align\*} \mathcal{C}\_{loop} &= t(2m+7n-(m+n-s) \\ &= t(m+6n+s) \end{align\*}$

The cost of the conditional is $\mathcal{C}\_{if}$ = $3s$ in both branches

And the final transfer of about half the stack from A to C costs $nt$, since there were $t$ iteration storing $n$ element each in A.

So the total cost is
$\begin{align\*} \mathcal{C} &= t(m+6n+s)+3s+nt \\ &= t(m+s)+3s+7nt \\ &= t(m+s)+3s+7(m+n-s)/2 \\ &= t(m+s)+(7m+7n-s)/2 \\ &= tm+(t-1/2)s+7(m+n)/2 \\ &= m(m+n-s)/2n + ((m+n-s)/2n-1/2)s +7(m+n)/2 \\ &= m^2/2n+m/2+ms/2n + ms/2n+s/2-s^2/2n-s/2 +7m/2+7n/2 \\ &= m^2/2n+4m +ms/n - s^2/2n +7n/2 \\ &= m^2/2n+ (4+s/n)m - s^2/2n +7n/2 \end{align\*}$

Since $r\in\[1,2n\]$, the **asymptotic complexity** is $\Theta(m^2/n)$.

The algorithm is linear in $m$ when the ratio $m/n$ is constant. It is quadratic in $m$ if $n$ is constant. Note also the number of moves increases with the ratio $m/n$, in particular when $n$ gets smaller for constant $m$, and the algorithm no longer works for $n=0$.

**Comparison with the simpler algorithm**

Note however that the term of the cost that determine this complexity when quadratic, which is the worse situation, is $m^2/2n$. It coefficient $1/2n$ is half the coefficient for the previous algorithm, so that **this algorithm is asymptotically faster than the previous one by 50%** when it is quadratic.

The result is of course the **same for the initial interleaving problem**, as it take only a linear amount of extra moves, actually $m+n$ moves.

---
Tags: algorithms, data-structures, stacks
---


# Question
Title: Applications in Computer Sciences of Partition Functions
A partition function computes the number of ways an integer $n$ can be represented as the sum of $m$ other integers. For some value $n$, we have a partition function $p(n)$.

These were studied extensively in mathematics by MacMahon, Hardy, Littlewood and Ramanujan. Rademacher provided a way to approximating $p(n)$, improving on a formula by hardy and Littlewood. More recently, K. Ono and A. Wiles have come up with new interesting results.

Are there applications of partition functions in Computer Sciences, perhaps in the theory of elliptic curve cryptography or complexity?

# Answer
> 2 votes

---
Tags: discrete-mathematics, mathematical-foundations, integer-partitions
---


title: How do locks work?

text:
# Question
Title: How do locks work?
Suppose I have an application with two threads, which both use the same resource. Normally, a synchronized block keeps these threads from messing with the resource in a way the user doesn't expect. I understand why you do this, but I need an explanation how it is done, especially on the following part.

How come acquiring the lock never results in a race condition? For Example: Let t1,t2 be threads that are synchronized on some object obj.

```
t1 checks if obj has a lock
it doesn't.

                         t2 checks if obj has a lock.
                         it still doesn't.
t1 locks obj.

                         t2 locks obj (which it should not be able to)

```

How is this prevented?

# Answer
Almost every modern processor has special memory instructions built in specifically to deal with this problem.

For example, many processors have a `swap` instruction. This *atomically* swaps a value between a local variable in a thread and a global variable that is shared between threads. (Under the covers the "local variable" will be stored in a machine register and the "global variable" will be stored in memory.)

Suppose the "lock" is stored in the global variable `global_lock_var` and a value of `0` means "unlocked" and a value of `1` means "locked. Then you do a critical section by:

```
do:
  local_var = 1
  swap global_lock_var <-> local_var
while local_var == 1
# Critical Section
#   (you only get here if the value of global_lock_var was originally 0, so you have
#    acquired the lock)
global_lock_var = 0  # release the lock

```

It is also possible to solve the locking problem even on a machine that doesn't have atomic instructions, just `load` and `store` instructions, but it is a little bit more complicated. One well known way to do it is by using something called Peterson's algorithm. This requires 3 variables, `flagA` (used to indicate thread `A` is trying to acquire the lock), `flagB` (used to indicate thread B is trying to acquire the lock), and `turn` (used to indicate who has priority if both are trying to acquire the lock).

```
# initialization:
flagA = false
flagB = false
turn = 'A'

# thread A:                    # thread B:
flagA = true                   flagB = true     # "I want the lock"
turn  = 'B'                    turn  = 'A'      # "But I'll be polite and give you priority"
while ((flagB == true) &&      while ((flagA == true) &&
       (turn  == 'B')):               (turn  == 'A')):
  # busy wait (do nothing)       # busy wait (do nothing)
# critical section             # critical section
flagA = false                  flagB = false    # "I'm done"

```

Even though there are "races" all over the place, the algorithm is accounting for the possibilities. If only one of the threads wants to get into the critical section, then the other thread's `flag` variable will be false (so the `turn` variable doesn't even get checked.) But if both threads try to acquire the critical section simultaneously then whichever one sets the `turn` variable *last* will lose.
> 4 votes

---
Tags: concurrency, threads, synchronization, deadlocks
---


# Question
Title: from when do we have the field of computer vision?
when was the field of computer vision created and what are the disciplines that gave birth to it? I would appreciate it if you could give some web references that have the answer.

# Answer
> 2 votes
Here are pointers to popular initiatives and breakthroughs in Computer Vision.

This paper starts the history of computer vision with Larry Roberts' thesis (around 1960):

http://cds.cern.ch/record/400313/files/p21.pdf

David Marr is also a huge name in the field and is mentioned in the paper.

The related field of computer geometry is rooted in such names as M. Minsky (Perceptrons, 1969 - although about neural networks explicitly, the book is highly related to the initial steps of computer vision and geometry). Bentley and his quadtree data structure is pervasively used in computer vision:

http:/www-ma2.upc.es/~geoc/mat2q1011/presentacioGeoC-2.ppt

I guess that the moment digital imaging started existing, researchers have started thinking about those topics. Most of the works quoted here date back to the 60's and 70's, which makes sense. Back then, you had the Voyager project at NASA.

Legacy machinery that do things similar to what robotics accomplishes with computer vision today can be found here:

http://cyberneticzoo.com/cyberneticanimals/1962-5-hopkins-beast-autonomous-robot-mod-ii-sonarvision-jhu-apl-american/

In the proto-computer vision era, you could then have the school of cybernetics founded by McCullogh. The school was started slightly after WW2 from work done during the war.

---
Tags: reference-request, history, computer-vision
---


# Question
Title: Does modern type theory include specifications and implementations?
Good programming practice distinguishes between specification (at the API level) and implementation. I would have thought that this same distinction would be found in type theory. Perhaps I just don't understand what I'm reading, but I don't see it.

Apologies if I'm completely off (and corrections appreciated), but it seems that in type theory one adds new computation/rewrite rules, which in effect are at the implementation level, i.e., they compute something. (They may be "declarative," but they are used for computation.) I don't see how one adds anything like a specification.

# Answer
A type $T$ is a specification. A term $t$ of type $T$ is an implementation *together* with a proof of correctness.

Dependent types are more expressive than simple types found in programming languages. Via the propositions-as-types correspondence they allow us to express logical statements which comprise a specification, rather than just "bare" typing information.

For instance, the type $$\prod\_{k : \mathbb{N}} \sum\_{m : \mathbb{N}} \mathsf{prime}(m) \times (k \< m)$$ can be read in any of the following ways:

1. As a proposition: for every natural number $k$ there is a prime $m$ larger than $k$.
2. As a type: the type of functions which take as input a number $k$ and output a triple $(m, p, q)$ where $m$ is a number, $p$ is a proof that $m$ is prime, and $q$ is a proof that $k \< m$.
3. As a specification: implement a function which takes a number and returns a prime larger than it.

Fancier specifications can be expressed just as well. For instance, we can express the specification for a dictionary as a dependent sum (or a record type if it's available) $$\sum\_{D : \mathsf{Type}} \sum\_{K : \mathsf{Type}} \sum\_{V : \mathsf{Type}} \sum\_{\mathsf{empty} : D} \sum\_{\mathsf{add} : K \to V \to D \to D} \sum\_{\mathsf{lookup} : K \to D \to 1 + V} \cdots $$ which is read as follows: we need to specify the type of dictionaries $D$, the type of keys $K$, the type of values $V$, the empty dictionary, and the addition and lookup functions. The $\cdots$ would express the required properties of dictionaries, i.e., logical statements governing the behavior of a dictionary.
> 3 votes

---
Tags: terminology, type-theory
---


# Question
Title: How to figure out the minimal number of colors needed to color specific given graphs?
I found this question on the net and I'm wondering what is the process for answering such questions? I assume there is some formula that works for all graphs?

**1.a.** Consider the undirected graph with vertices $A$, $B$, $C$, $D$, $E$, $F$ and edges $AB$, $AC$, $BD$, $CE$, $DF$ and $EF$ (i.e., the graph is the 6-cyle $ABDFECA$). What is the minimal number of colours needed to colour this graph?

**1.b.** Show how when considering the ordering $A$, $B$, $C$, $D$, $E$, $F$ of the vertices in the above graph, a greedy algorithm will find this minimal number, and find one other ordering where it will not.

# Answer
I'm not sure what you mean by a "formula that works for all graphs" – what would the variables of such a formula represent? Since it's **NP**-hard to determine the chromatic number of a graph (the minimum number of colours required), there's unlikely to be any simple way of doing it in general.

For the specific graph in the question, the easiest way is to find a colouring with some number of colours and then prove that no smaller number of colours can work. In this case, it's easy to find a 2-colouring of the graph and there's clearly no 1-colouring, since every vertex is adjacent to at least one other vertex.

For part b, are you familiar with greedy colouring algorithms? In particular, if the next vertex to be considered has no neighbours that have already been coloured, that vertex will receive colour $1$. So, one way to produce an ordering that makes the greedy algorithm use a suboptimal number of colours is to find two non-adjacent vertices $X$ and $Y$ that must always have different colours in an optimal colouring, and begin your ordering $X,Y, \dots\\;$. Doing this requires understanding what optimal colourings look like, which is fairly simple for the given graph but, as I stated above, is hard in general.
> 2 votes

---
Tags: graphs, greedy-algorithms, colorings
---


# Question
Title: Why is a program with only atomics in SC-DRF but not in HRF-direct?
In the paper "Heterogeneous-Race-Free Memory Models" \[1\], the authors state that a program consisting only of atomic is race free in SC-DRF but it is not in HRF-direct. I am not able to understand why this is. Can anyone explain how this can happen?

\[1\] Derek R. Hower *et al.*, "Heterogeneous-Race-Free Memory Models". In *Proceedings of ASPLOS '14*, ACM, 2014. (PDF)

# Answer
Hopefully they didn't say explicitly say exactly "a program consisting only of atomics is race free in SC-DRF." That's incorrect.

They do say that "\[in\] scoped synchronization ... it is possible to write a racey program that is composed entirely of atomics if those atomics do not use scopes correctly," \[top of page 2\], which is slightly different (and uses the word "racey" ambiguously, perhaps leading you to believe they meant the incorrect statement.) They perhaps should have instead said said that in scoped synchronization it is possible to write a *non sequentially consistent* program that is composed entirely of atomics if those atomics do not use scopes correctly.

SC-DRF (roughly: the memory semantics for C++ and Java) divide memory locations into two classes, *synchronization* objects, (sometimes called `atomics`), and *data* objects. For the most part all operations on synchronization objects are guaranteed to be *sequentially consistent*.\[1\] (*Not* race free.) This is a constraint on the compiler, not the programmer. It says that if the programmer says that one thread writes atomic object `a` then writes atomic object `b`, *all* the threads will see the writes occur in this order. (The compiler is not allowed to reorder the accesses, and is required to insert the appropriate memory barriers and fences on machines that aren't sequentially consistent.)

*Sequentially consistent* means that all threads on all processors agree on a total order of all memory operations. If one thread thinks that operation $x$ *happened before* operation $y$, *all* the threads think that operation $x$ *happened before* operation $y$. Sequentially consistent does not mean *not racey* and it does not mean *deterministic*. For example, two different threads could try to write the same synchronization variable at approximately the same time. These accesses will be racey. A sequentially consistent system will just guarantee that if one thread thinks that write $x$ happened before write $y$, *all* the threads will agree that write $x$ happened before write $y$. Sequential consistency is useful because you can use it to construct and reason about useful non-deterministic synchronization objects like mutexes and condition variables.

SC-DRF then says that *if* your program is *data* race free, the operations on *data* objects will *appear* to be *sequentially consistent*. The compiler *is* permitted to reorder (or even sometimes eliminate) operations on data objects, and if the underlying machine is not sequentially consistent, the compiler is not required to insert memory barriers or fences. *But* the compiler is *not* allowed to reorder operations on data objects with respect to operations on synchronization objects.

*Data* race free is not the same as *race free*. And *sequentially consistent* is not the same as *race free*. A particular program execution schedule is *data* race free if for any pair of data object accesses, $x$ and $y$, by two different threads (at least one of which is a write operation) we can use the (sequentially consistent) order of atomic object accesses to prove that either $x$ *happened before* $y$ or $y$ *happened before* $x$. If we can not do the proof then that execution schedule is *data racey*.

A *program* is *data race free* if all possible execution schedules are data race free. A program is *data racey* if there is an execution schedule that is data racey.

Being *data race free* is a constraint on the programmer, not the compiler. It says that if your program is data racey, then your program has no semantics. The compiler is allowed to do anything it wants, including halting the program, going into an infinite loop, or blowing up the computer.

Oh dear. **TL; DR!** I haven't even mentioned SC-for-HRC yet!

In SC-for-HRC the atomics need to specify what *scope* they belong to. Atomic accesses are guaranteed (by the compiler) to be sequentially consistent only within their own scope. All threads within the scope will agree about the order in which the atomic accesses occur, but threads in a different scope may *not* agree (and may not even be able to see the accesses at all, let alone their order.)

For example it might be the case that all the GPU threads agree that thread 19 acquired mutex A then acquired mutex B, but all the CPU threads do *not* agree (or know) that thread 19 acquired mutex A or mutex B at all. SC-DRF does not have "scopes" so doesn't suffer this problem.

\[1\] The exceptions to the sequentially consistent atomics have to do with explicitly using `std::memory_order_relaxed`. So don't do that. (And I'll ignore the exceptions in the rest of what I'm saying.)
> 14 votes

---
Tags: concurrency
---


# Question
Title: Proving the (in)tractability of this Nth prime recurrence
As follows from my previous question, I've been playing with the Riemann hypothesis as a matter of recreational mathematics. In the process, I've come to a rather interesting recurrence, and I'm curious as to its name, its reductions, and its tractability towards the solvability of the gap between prime numbers.

Tersely speaking, we can define the *gap* between each prime number as a recurrence of preceding *candidate* primes. For example, for our base of $p\_0 = 2$, the next prime would be:

$\qquad \displaystyle p\_1 = \min \\{ x \> p\_0 \mid -\cos(2\pi(x+1)/p\_0) + 1 = 0) \\}$

Or, as we see by plotting this out: $p\_1 = 3$.

We can repeat the process for $n$ primes by evaluating each candidate prime recurring forward. Suppose we want to get the next prime, $p\_2$. Our candidate function becomes:

$\qquad \displaystyle \begin{align} p\_2 = \min\\{ x \> p\_1 \mid f\_{p\_1}(x) + (&(-\cos(2\pi(x+1)/p\_1) + 1) \\ \cdot &(-\cos(2\pi(x+2)/p\_1) + 1)) = 0\\} \end{align}$

Where:

$\qquad \displaystyle f\_{p\_1}(x) = -\cos(2\pi(x+1)/p\_0) + 1$, as above.

It's easy to see that each component function only becomes zero on integer values, and it's equally easy to show how this captures our AND- and XOR-shaped relationships cleverly, by exploiting the properties of addition and multiplication in the context of a system of trigonometric equations.

The recurrence becomes:

$\qquad f\_{p\_0} = 0\\ \qquad p\_0 = 2\\ \qquad \displaystyle f\_{p\_n}(x) = f\_{p\_{n-1}}(x) + \prod\_{k=2}^{p\_{n-1}} (-\cos(2\pi(x+k-1)/p\_{n-1}) + 1)\\ \qquad \displaystyle p\_n = \min\left\\{ x \> p\_{n-1} \mid f\_{p\_n}(x) = 0\right\\}$

... where the entire problem hinges on whether we can evaluate the $\min$ operator over this function in polynomial time. This is, in effect, a generalization of the Sieve of Eratosthenes.

Working Python code to demonstrate the recurrence:

```
from math import cos,pi

def cosProduct(x,p):
    """ Handles the cosine product in a handy single function """
    ret = 1.0
    for k in xrange(2,p+1):
        ret *= -cos(2*pi*(x+k-1)/p)+1.0
    return ret

def nthPrime(n):
    """ Generates the nth prime, where n is a zero-based integer """

    # Preconditions: n must be an integer greater than -1
    if not isinstance(n,int) or n < 0:
        raise ValueError("n must be an integer greater than -1")

    # Base case: the 0th prime is 2, 0th function vacuous
    if n == 0:
        return 2,lambda x: 0

    # Get the preceding evaluation
    p_nMinusOne,fn_nMinusOne = nthPrime(n-1)

    # Define the function for the Nth prime
    fn_n = lambda x: fn_nMinusOne(x) + cosProduct(x,p_nMinusOne)

    # Evaluate it (I need a solver here if it's tractable!)
    for k in xrange(p_nMinusOne+1,int(p_nMinusOne**2.718281828)):
        if fn_n(k) == 0:
            p_n = k
            break

    # Return the Nth prime and its function
    return p_n,fn_n

```

A quick example:

```
>>> [nthPrime(i)[0] for i in range(20)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

```

The trouble is, I'm now in way over my head, both mathematically and as a computer scientist. Specifically, I am not competent with Fourier analysis, with defining uniform covers, or with the complex plane in general, and I'm worried that this approach is either flat-out *wrong* or hides a lurking horror of a 3SAT problem that elevates it to NP-completeness.

Thus, I have three questions here:

> 1. Given my terse recurrence above, is it possible to deterministically compute or estimate the location of the zeroes in polynomial time and space?
> 2. If so or if not, is it hiding *any other* subproblems that would make a polytime or polyspace solution intractable?
> 3. And if by some miracle (1) and (2) hold up, what dynamic programming improvements would you make in satisfying this recurrence, from a high level? Clearly, iteration over the same integers through multiple functions is inelegant and quite wasteful.

# Answer
The following paper shows that PRIMES is in P (it also won a Gödel award in 2006):

http://www.cse.iitk.ac.in/users/manindra/algebra/primality\_v6.pdf

By setting the solution of the Nth prime minimization procedure to the AKS PRIMES algorithm (modulo a subtraction), we may effectively get a tractable solution to the recurrence relation (if you can prove that the prime gap is given by the recurrence relation).

Source codes can be found on the internet. I am not pointing to them here because I did not check them personally.

As is however, we may still have the upper bound of $\sqrt{n}$ for checking all numbers...
> 1 votes

---
Tags: complexity-theory, reference-request, recurrence-relation, mathematical-analysis
---


# Question
Title: Origins of the Segment tree data structure
I'm interested in the first appearance in the CS literature of the data structure described here which is used to answer Range Queries. Although I have come across the same data structure many times with the name *segment tree* (mostly in algorithmic competition sites), it seems that the same name is also used for this data structure which is quite different from the first one and has application in computational geometry.

I'd like to know who introduced the data structure described in the TopCoder tutorial and if another name was initially used as there seems to be a confusion between the two data structures that go by the same name.

# Answer
It seems to me that the Segment tree in the Wikipedia article is exactly the same as the segment tree you're used to hear about.

Segment trees as used in programming competitions can be generalized as working over any data type which forms a Semigroup (that is, any data type over which some binary associative operation can be defined on). As a reference, I've been implementing them in Haskell, the source code can be found here.

In this particular case, you'd have to notice that the power set of a set forms a commutative monoid with union, and monoids are, in particular, semigroups. Hence, the particular case described in Wikipedia is a segment tree where the data type is an Interval, and the associative operation is the union operation!.
> 1 votes

# Answer
Segment trees are a form of binary trees. So to clarify your question, the data structures in both links are the same. They might be used in different ways or for different operations but they are in fact the same. I do not know who introduced the "segment tree" use of binary trees, but I hope this helps.
> -1 votes

---
Tags: reference-request, data-structures, trees
---


# Question
Title: Can we construct a binary tree with width and height Θ(n)?
we know this definition:

Given a binary tree, Width of a tree is maximum of widths of all levels.

Let us consider the below example tree.

```
     1
    /  \
   2    3
 /  \     \
4    5     8
          /  \
         6    7

```

For the above tree, width of level 1 is 1, width of level 2 is 2, width of level 3 is 3 width of level 4 is 2.

So the maximum width of the tree is 3.

can we have a binary tree with Height $\Theta(n)$ and Width $\Theta(n)$

My solution: is YES. for example a binary tree with one-node:

```
     1

```

am i right?

# Answer
Statements about $\Theta$-classes are statements about the behaviour of an algorithm/data structure, as (in this case) $n$ gets large. Thus, a single example can never prove such a statement. You'd have to provide a set that contains examples that become arbitrarily large and behave as desired. (The set, however, doesn't have to contain an example for every value of $n$.)

So you should try to construct such a set of examples. (And if you fail constantly, try to find out why. This might lead to a proof that no such set exists, i.e. the claim is false.)
> 3 votes

# Answer
First, FrankW is right about you having to provide what he calls a set of examples (way of constructing a tree with those properties for most $n$ / a generic recipe)

However, while this set doesn't have to contain an example for every value on $n$, it should contain an example for every value above a certain $n\_0$, which would also be a part of your solution (check the definition of $\Theta$, google "Big Oh"). In other words, for each $n$ above a certain $n\_0$ (that you need to figure out), you need to able able to construct a tree with your desired properties for that $n$.

I also think you would have to clarify what exactly you mean by Width being $\Theta(n)$. Does that mean the Width of every level is in class $\Theta(n)$, or that the final (bottom) level is? Does it matter?

As for constructing the tree, here's a couple of guides that are hopefully not mistaken and leave a bit work for you to do yourself

1. What's the minimal tree of height $n$ that you can come up with? What is its width at the bottom level?
2. Is there a way of increasing the width of the minimal tree of height $n$ by one while keeping its height?
3. Can you apply 2. until you get to width $n$?
> 0 votes

---
Tags: graphs, asymptotics, trees, binary-trees
---


# Question
Title: Connection of "modern" runtimes and number of steps on a Turing machine
Why an evaluation of Turing machine efficiency is equal to the algorithm which is implemented by this machine and vise versa? For example, we can say that efficiency of merge sorting algorithm is O(nlog(n)) and therefore Turing machine which implements this algorithm will do O(nlog(n)) steps. Why is this conclusion correct? And vise versa: if there's no deterministic Turing machine which takes less than exponential number of steps to solve some problem, we aren't able to find efficient algorithm solving this problem.

# Answer
Your premise that turing machines can implement algorithms with the same efficiency as a modern computer is not correct.

Turing machines can simulate 'enhanced' turing machines that have the properties of modern computers (e.g. random access into memory, multiple memory spaces, etc) with only polynomial slowdown.

However, not all problems can be solved exactly as fast on a turing machine. For example, consider the problem PALINDROME to determine if the input is a palindrome. On a modern computer there is an obvious $O(n)$ algorithm, where you just read the front and back character, and if they match recurse on the inner substring. This problem is known to require $\Omega(n^2)$ time for a classical turing machine to solve. This means turing machines are decidedly "weaker" by some amount compared to an ideal modern computer.
> 5 votes

---
Tags: algorithms, complexity-theory, turing-machines, runtime-analysis, simulation
---


title: Bit distance and disruption

text:
# Question
Title: Bit distance and disruption
Earlier, I asked a question defining disruption in Genetic Algorithms. Given that definition, I'm still confused on how to answer the following question.

> True or false? For 1-point and 2-point crossover, the schemata which have bits that are close together on the string encoding are more likely to be disrupted by crossover.

From my understanding of cross-over disruption should only be dependant on the number of matching bits strings between parents. So `1001` would be more likely to be disrupted by `0110` then by `1000`. So I answered false, but their justification was that bits closer together encourage disruption, which I don't totally understand.

I'm assuming that "bit distance" can be defined as the number of zeros between sequential bits, but based on my proof above, I really don't see how this could affect disruption. Alternatively, I could consider "bit distance" as being the number of bits to flip to reach from one number to another, but based on my proof above, the greater the distance, the greater the chances of disruption.

Where is the mis-understanding between the official answer and my own?

# Answer
> 3 votes
Disruption refers to the phenomenon in which a schema represented by a particular parent is not passed down into its offspring.

That bit about schemata is important -- disruption isn't really defined except for in terms of schemata. Briefly, a schema is a **ternary** string containing 0s, 1s, and \*s (don't-cares), whereas individuals are only binary (no \*s). Each individual is a representative of $2^n$ schemata. For example,

```
10010011

```

is an instance of all of the following schemata:

```
1*******
*00**01*
1******1
...

```

The idea Holland had was that, for example, if good solutions tended to have a 1 in the leading bit, then the proportion of the population that is an instance of the schema

```
1*******

```

would increase over time according to a certain inequality. That's the schema theorem. Now, what if instead of that simple schema being more fit than average, we had a more complicated one, like

```
1*****0*

```

That is, suppose that individuals matching that pattern are above average in fitness. According to Holland, the GA should work by increasing the proportion of the population that conforms to that pattern over time.

But look at what happens with one-point crossover. It's going to pick a crossover point somewhere along the string and split it around that point. If both parents are instances of the schema, then both children will be as well. But if either parent is not an instance of the schema, then we have a probability that the children won't inherit that pattern. That failure to inherit the pattern is called disruption. Holland would have said that this was very bad. The presence of that schema in the population is evidence that it's good, and crossover is wrecking it. The modern understanding is much more nuanced than that, but that's the rationale behind considering disruption as a concept at least.

So you question asks whether schemata that have bits that are close together are more or less likely to be disrupted. We should really be more precise -- it's not whether any old bits are close together that matters. It's the distance between the first and last non-\* bit that matters (called the defining length). The greater that distance, the more likely we'll put a crossover point in between them, and therefore the more likely we are to disrupt the schema.

---
Tags: algorithms, genetic-algorithms
---


# Question
Title: Generating hard puzzles for a backtracking snake
Let $M$ be a matrix of height $h$ and width $w$. Each entry of $M$ is an integer.

There is a snake that starts from the "left side" of $M$, and its goal is to reach the "right side" of $M$. To get from one side to the other, i.e. to move from column $c$ to column $c+1$, the snake must choose an integer from both. Whatever the snake picks from column $c$, it can never pick the same integer again in $c+1$, nor from any column that appears later.

For example, suppose each entry in column 1 has integer 1, each entry in column 2 has integer 2, and so on. Now the snake can move very freely: in fact, we have $h$ choices in each of the $w$ columns. Even a blind snake gets through the matrix easily.

The goal is to generate matrices that are difficult for a snake that performs some kind of exhaustive backtracking search. The matrices can be tall, but preferably not wide. Can we assign the integers to $M$ such that there is exactly one (i.e. a unique) path through it? The hope is matrices with unique valid paths through them are difficult for a backtracking snake.

# Answer
Here's an idea for generating instances with a non-unique solution that will be difficult to solve by backtracking but actually are quite easy to solve:

Let $M$ be $h$ tall and $2w$ wide. Take the integers ${1, 2, ... w}$ and fill $M$ with them randomly. For $i = 1$ to $w$, replace column $w + i$ to be the column with only the value $i$.

We know that $M$ has no solution, because it requires $2w$ unique integers to bring the snake across the matrix.

Now, for the first $w$ columns of $M$, replace a random element of column $i$ with the number $w + i$.

Then, it follows that the sequence of integers corresponding to any solution is $w + 1, w + 2 .... 2w, 1, 2, ...... w$. This is very easy to find, unless you are searching by backtracking. In particular, the first $w$ columns have a unique correct choice.

Here's an example of a matrix made by this algorithm:

$$ \begin{array}{ccc} 1 & 5 & 2 & 1 & 2 & 3 \\ 3 & 3 & 2 & 1 & 2 & 3 \\ 4 & 1 & 1 & 1 & 2 & 3 \\ 2 & 2 & 2 & 1 & 2 & 3 \\ 2 & 3 & 6 & 1 & 2 & 3 \\ 3 & 1 & 3 & 1 & 2 & 3 \\ 1 & 1 & 1 & 1 & 2 & 3 \\ \end{array} $$

To make a given instance harder, just make the matrix arbitrarily taller.
> 3 votes

---
Tags: artificial-intelligence, search-problem, backtracking
---


title: Language of a grammar

text:
# Question
Title: Language of a grammar
What's the language of following grammar?

$G: S \to S\_1B$

$S\_1 \to aS\_1b$

$bB \to bbbB$

$aS\_1b \to aa$

$B \to \lambda$

any hint or solution?

# Answer
Hint: Starting with $S\rightarrow S\_1B$, do the $S\_1$ derivation and then the $B$ part. Invoke $S\_1\rightarrow aS\_1b$ a certain number, $n$, times. What do you get? Then eliminate $S\_1$ by using $aS\_1b\rightarrow aa$. Now what do you have? Finally, use $bB\rightarrow bbbB$ some number, $m$ times (getting two more $b$s each time) and eventually erase the $B$. What's your final result? It should be fairly obvious, except for one special case.
> 1 votes

---
Tags: formal-languages, automata, formal-grammars, finite-automata
---


# Question
Title: Strictly speaking do the Hoare and Lomuto partitioning algorithms work on the same algorithm: quicksort?
For Hoare's partitioning algorithm quicksort is implemented as such

```
 quickSort(array, first, last)
    if(last > first)
        pivot = partition(array, first, last);
        quickSort(array, first, pivot);
        quickSort(array, pivot+1, last);

```

but Lomuto is

```
 quickSort(array, first, last)
    if(last > first)
        pivot = partition(array, first, last);
        quickSort(array, first, pivot-1);
        quickSort(array, pivot+1, last);

```

Notice the first one doesn't have pivot-1. Is it correct to call these two the same implementations of the quicksort algorithm? I'm having trouble rapping my head around the difference, I thought quicksort worked on the premise that after one call to it the pivot is in it's final place (so do +1 and -1 for the rest of the array) but Hoare's method doesn't seem to work like this.

# Answer
The term "Quicksort" stands for this abstract algorithmic idea:

1. Pick a value $x$.
2. Partition the input into $\\{y\mid y \leq x\\}$ and $\\{y \mid y \> x\\}$.
3. Recurse on the partitions (if they are non-trivial) and append the results.

You may want to generalise to multiple pivots, or create a third partition for elements equal the pivot, but mostly that's it.

There are many, many implementations. All of them are called "Quicksort", but many modify the name. See here for a discussion about the differences of these particular two variants.
> 5 votes

---
Tags: algorithms, quicksort
---


# Question
Title: Why is the language of even-length non-palindromes context-free?
We know $L\_1=\\{w\_1 w\_2 \in (a+b)^\*\mid |w\_1|=|w\_2|, w\_2 \neq w\_1^{\\;\mathrm{R}}\\}$ is a context-free language.

Can anyone help me produce a PDA or give me any hint how I can quickly understand why this is context-free?

# Answer
The language of even-length non-palindromes is given by the following context-free grammar:

$$S \rightarrow 0S0 \mid 1S1 \mid D$$ $$D \rightarrow 1A0 \mid 0A1$$ $$A \rightarrow \lambda \mid 00A \mid 01A \mid 10A \mid 11A$$
> 4 votes

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


# Question
Title: Does #$P$-Completeness imply approximation hardness?
Let $\Pi$ be some counting problem which is known to be #$P$-Complete.

Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?

# Answer
No. Counting independent sets in graph is **#P**-hard, even for 4-regular graphs but Dror Weitz gave a PTAS for counting independent sets of $d$-regular graphs for any $d\leq5$ \[3\]. (In the model he writes about, counting independent sets corresponds to taking $\lambda=1$.)

Computing the permanent of a 0-1 matrix is also **#P**-hard (this is in Valiant's original **#P** paper \[2\]) but, relaxing your requirement a little, there's an FPRAS due to Jerrum and Sinclair \[1\]. This corresponds to counting perfect matchings in bipartite graphs.

**References**

\[1\] Mark Jerrum and Alistair Sinclair, "Approximating the permanent." *SIAM Journal on Computing*, 18(6):1149–1178, 1989. (PDF)

\[2\] Leslie Valiant, "The complexity of computing the permanent." *Theoretical Computer Science*, 8:189–201, 1979. (PDF)

\[3\] Dror Weitz, "Counting independent sets up to the tree threshold." STOC 2006. (Unpublished full version: PDF.)
> 9 votes

# Answer
Adding another example I came across, with an even stronger result:

A (deterministic) FPTAS exists for the problem of counting the number of matchings in a bounded-degree bipartite graph, while this is a $\\#P$-complete problem.
> 3 votes

---
Tags: complexity-theory, complexity-classes, approximation, counting
---


# Question
Title: Fast checking Matrix multiplication in mod 10
I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In other words, return the result of expression `(A x B) mod 10 == C`.

For example:

$\qquad A = \begin{bmatrix} 0 & 5 & 8 \\ 1 & 4 & 9 \\ 2 & 3 & 3 \end{bmatrix}\qquad B = \begin{bmatrix} 3 & 5 & 0 \\ 1 & 2 & 6 \\ 3 & 7 & 0 \end{bmatrix}\qquad C = \begin{bmatrix} 9 & 6 & 0 \\ 4 & 6 & 4 \\ 8 & 7 & 8 \end{bmatrix}$

return: TRUE

If

$\qquad C = \begin{bmatrix} 1 & 6 & 0 \\ 4 & 6 & 4 \\ 8 & 7 & 8 \end{bmatrix}$

return: FALSE, since the element C(1, 1) must be 9.

Time limit is 1s, pretty strict. Please gives me some idea how to solve the problem efficiently; is it possible time $O(N^2)$?

# Answer
I got Accepted by using Freivald's algorithm as suggested by @David Richerby. Thank you very much !

I have not tested the brute-force solution using Coppersmith-Winograd algorithm yet. Will report in a couple of days, by the way I think it might not get Accepted but possibly will gain a fairly amount of points.

For those who want to check your implementation, submit your code on http://vn.spoj.com/problems/VMATRIX/. The problem statement is in Vietnamese, so here is the short description of input format:

> * First line is number of testcase (the example gives 2 testcases)
> * For each testcase:
> * the first line is size of 3 matrices, N. In 20% testcase N \<= 100.
> * next N * N lines: matrix A
> * next N * N lines: matrix B
> * next N * N lines: matrix C

Output: YES or NO for the result.
> 0 votes

---
Tags: algorithms, number-theory, matrices, modular-arithmetic
---


# Question
Title: What's the difference between Clock and Second Chance Page-Replacement Algorithm?
I know that they both have reference bit, but I only understand the Second Chance but not the Clock Page-Replacement algorithm.

could anyone help me understand?

# Answer
> 4 votes
Clock *is* second chance. Given the same input they will both produce the same replacements at the same points in time. The only difference is the details of implementation. Second chance is usually described in terms of a "fifo" which is assumed to be a linked list where there is a pointer to the `head` and `tail` and every node contains a pointer to `next`. Then when you remove a page from the head of the fifo you do it by setting `head = head->next`. When you insert a page on the tail of the fifo you do it by setting `tail->next = new_node`, `tail = new_node`, `new_node->next = NULL`.

Clock is just a simpler (and slightly faster) implementation of a fifo where you keep a *circular* linked list. `tail->next` points to what was the head in our old structure. We only need one pointer, the pointer to `tail.` Now removing a node from head is simply `tail->next=tail->next->next` and inserting a node on the tail is `new_node->next = tail->next`, `tail->next = new_node`, `tail = new_node`. This is all about the same as the non-circular version. The efficiency comes when you need to move a node from the head to the tail. That's just `tail = tail->next` with the circular list.

## Two-handed clock

By adding a second clock hand to the clock algorithm you get an extremely low-cost approximation of not-recently-used (which is an approximation of least-recently-used.)

In the two-handed clock algorithm you have two clock hands. One of the hands is just like before, it points at the next page being considered for replacement. When a replacement is required we just keep moving this clock hand (clearing reference bits) until we find a page with the reference bit cleared, and that's the page that gets replaced. (So this clock hand is just doing the clock implementation of second chance.)

The second clock hand is another pointer into the circularly linked list. The purpose of the second hand is to clear reference bits. Every once in a while you clear the reference bit on the linked-list node that the second hand is pointing to, and set `second_hand = second_hand->next`. This eliminates one of the problems with second chance, which is that when a page is only used a small amount right after it is first fetched then second-chance will require two cycles through the fifo before that page gets replaced. In the two-handed clock algorithm those "short-term usage" pages get replaced after just one cycle through the fifo.

Another replacement algorithm you might look at is WSClock of Carr and Hennessy. It is a combination of the two-handed clock with a bunch of heuristics that are helpful in practice.

---
Tags: algorithms, operating-systems, memory-management, paging
---


# Question
Title: How to reconstruct the image from a neural network output?
I am trying to use the genetic algorithm to optimise a multi-layered neural network for image classification (i am using a subset of the MNIST handwritten digit data set as my initial dataset, but eventually would like to make it more general).

my neural network is represented by connection weight matrices with inputs as the rows an outputs as the columns (so element (3, 4) is the weight of the connection between input 3 and output 4, etc) and have an extra column and row for the biases of the inputs/outputs

the system seems to work well, it takes an input vector, multiplies it by the first layer matrix, uses the sigmoid function to determine whether that neuron will fire or not, then uses the output vector of that as the input to multiply by the 2nd layer and so on to the final layer, and i am getting the results that i expect with test data that i know the expected output for.

i have an idea of how i will implement the genetic algorithm to search for the best solutions, but my problem is that im having a little bit of trouble understanding how neural networks can be used to reconstruct images so i can test for the error between the input image and the reconstruction to test each solution for fitness.

i understand that i need to first encode the image into a vector of pixels, and that that input needs to be passed through the network to the end layer, but i am not sure what that end data is supposed to represent..

the dataset i am using are images of 28\*28 pixels, so the structure of my network is as follows (inspired by the Hinton paper here):

484 -\> 1000 -\> 500 -\> 250 -\> 30

so the output of the whole thing will be a vector 31 (30 neurons +1 for the bias column/row) elements long

how should i use this vector to reconstruct the image?

i read somewhere that to decode information from a neural network you need to multiply the output by the transpose of the transformation matrix, but that doesnt really make sense as (for example):

```
T = [ 1  2 ;
      3  4 ]

A = [ 5  6 ]

A * T = [ 23  34 ] = B

B * T' = [ 91  205 ] != A

```

clearly this is not a very good reconstruction of the original data..

can someone give an explanation as to how neural nets can be used to reconstruct data, and if possible, point me to some good resources on the subject?

# Answer
> 3 votes
You can't necessarily use the output of a neural network to reconstruct the image, like you want. The output signals indicate how the neural network has classified the input image. Beyond that, they don't necessarily have any interpretation as a representation of the original image. There isn't necessarily any way to do what you want (to reconstruct the image given the output of the neural network), as this kind of neural network inherently throws away information.

Are you familiar with the notion of training "autoencoders"? One way to train multi-layer neural networks is by building a series of auto-encoders: e.g., to construct the weights for the first layer, you train a 2-layer autoencoder, then throw away the second layer of the autoencoder and use the first layer of the autoencoder as the first layer of your neural network. You repeatedly do this for each layer of your network. Autoencoders *do* reconstruct the original input, so if you're training each layer of the neural network in this way, then you automatically have a way to reconstruct (an approximation to) the original input from the signals at any layer -- if you saved the entire autoencoder at each stage. However, if your real end goal is to understand why an image was classified a certain way or debug your neural network, I expect this probably won't be helpful for that.

I'm not 100% sure what your real goal is. You mention "test each solution for fitness", but I'm not sure what you meant by that. However, my guess is that your best bet will be to figure out what your real goal is, and then ask about how to achieve that goal (which might not be by trying to reconstruct the original image).

---
Tags: machine-learning, neural-networks, computer-vision
---


# Question
Title: How the below program is taking O(n!) time?
The complexity of the below program is given to be O(n!)

```
double foo(int n){
int i;
double sum;
if(n==0){
    return 1.0;
}
else {
    sum=0.0;
    for(i=0;i<n;i++){
        sum+=foo(i);
    }
    return sum;
}

```

}

But I could determine its complexity as O(n!). Can anyone explain how is it coming to be O(n!)?

Is it Θ(n!) also or only O(n!)?

If it is not Θ(n!) .Can I get a sample of Θ(n!) code.

# Answer
Let's assume the time to calculate foo(n) is $T(n)$. In the case where $n\>0$, we can gather the time taken for an iteration will be: $$ T(n) = \left( \sum\_{i=0}^{n-1} T(i)\right) +n+c $$

Also, $T(1)=c$

First, a little justification. The summation in the parenthesis is the run time for all the calls to foo in the loop. The n accounts for the looping and the constant c accounts for things such as initialization, comparisons and such.

Now, with that in mid, let's calculate what the next step would be, and see if we can deduce the growth of the run time.

$$ T(n+1) = \left( \sum\_{i=0}^{n} T(i)\right) +(n+1)+c $$

Now, if from the present sum we extract $T(n)$, we get:

$$ T(n+1) = \left( \sum\_{i=0}^{n-1} T(i)\right) +T(n)+(n+1)+c $$

Now, if we rearrange the result in the following way, we have an opportunity for reducing the sum:

$$ T(n+1) =\left\[ \left( \sum\_{i=0}^{n-1} T(i)\right) + n+c \right\]+T(n)+1 $$

You see that in the brackets, that's exactly what we defined as $T(n)$ (1rst equation). In that case, we get that:

$$ T(n+1) =T(n)+T(n)+1 = 2T(n)+1 $$

From this, it also stands that $T(n)=2T(n-1)+1$. What happens if we replace $T(n-1)$ by it's value calculated with this very function? Well, let's iterate:

$$ \begin{array}{r l} T(n) & = 2T(n-1)+1 \\ & = 2 \left\[ 2 T(n-2) +1 \right\] +1 \\ & = 2 \left\[ 2 \left\[ 2 T(n-3) +1 \right\] +1 \right\] +1 \\ & \vdots \\ & = 2^kT(n-k)+k \end{array} $$

Almost there. Finally, let's write it in terms of $T(0)$, our known base case. First, for that we must have $T(n-k) = T(0)$ so it stands that $k=n$. In the end, we get:

$$ T(n) = 2^nT(0)+n=2^nc+n $$

With this in mind, we can conclude that $T(n) = \theta(2^n)$
> 3 votes

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Choosing error rates for probabilistic algorithms
Probabilistic algorithms often have a parameter that allows one to tune the error rate, typically by running the algorithm repeatedly. This often gives an error rate of something like $2^{-k}$ for $k$ iterations. This is a fine situation to be in, because $2^{-k}$ can be made as close to $1$ as you like without having to make $k$ very big at all. At this point, the theoretician sits back contentedly, his or her job done.

In practical terms, though, are there any guidelines as to which value of $k$ should one choose? Obviously, there's no universal answer, since the answer in any particular situation will be a trade-off depending on the importance of avoiding errors and the cost of doing more iterations.

For example, choosing $k=10$ gives an error rate of about one in a thousand, which seems rather high for most purposes; choosing $k=60$ means the expected number of errors would still be less than one even if you'd run the algorithm once a second since the big bang.

# Answer
As you say, this is application or situation dependant in general. However, a guideline I have encountered is "making the error probability smaller than the probability of a hardware failure". If I remember correctly, this is at least mentioned in the Mitzenmacher-Upfal book.

Say you wanted to replace a deterministic algorithm with a probabilistic algorithm, and still be confident (enough) it works. How often do hardware failures happen then?

Nightingale, Douceur, and Orgovan \[1\] analyzed hardware failure rates on a million consumer PCs. For instance, bus errors, microcode bugs, and parity errors in CPU caches issue a machine-check exception (MCE), indicating a detected violation of an internal invariant. Roughly, a CPU running for at least 5 days has a 1 in 330 chance of crashing due to an MCE (see Figure 2). They also observed laptops are more reliable than desktop machines, and underclocking helps as well.

In short, one guideline could be this: know the hardware you are running your algorithm on, and analyze how often the hardware makes critical mistakes (or take a good guess e.g. based on \[1\]).

---

\[1\] Nightingale, Edmund B., John R. Douceur, and Vince Orgovan. "Cycles, cells and platters: an empirical analysis of hardware failures on a million consumer PCs." Proceedings of the sixth conference on Computer systems. ACM, 2011.
> 6 votes

# Answer
This is the arithmetic for Juho's answer. (Run it for the length of time it takes to make the algorithm failure probability equal the hardware failure probability).

Suppose it takes time $t$ seconds to perform one computation, and thus time $kt$ to get the algorithm error probability down to $2^{-k}$.

Suppose that the hardware probability of failure per second is $p$. Then the probability of a hardware failure is approximately $ktp$ (see lemma below). So you want the $k$ that is the solution to

$$ \frac{1}{2^k} = ktp. $$

**Lemma**

Assume a memoryless failure process with a failure rate per time period of $p$. Let $P=1/p$ (makes the arithmetic easier). Then for very small $p$ (large $P$) the probability of success in $k$ time periods is

$$ 1 - (\frac{P-1}{P})^k = \frac{P^k - (P-1)^k}{P^k}.$$

By the binomial theorem this is

$$ \frac{P^k - P^k +kP^{k-1} + \frac{k(k-1)}{2}P^{k-2} + \cdots }{P^k} \approx \frac{k}{P} = kp.$$

**Value of $p$**

Also assuming memorylessness and independence and all that good stuff, the numbers in the paper that Juho provided give a failure rate (memory, disk and cpu) of about $1/180$ in 5 days, which is 432000 seconds, so the probability of failure in 1 second is something like $p = 1/77543800 \approx 2^{-26}$, but you want a *lower* probability than that, so you should probably use $2^{-27}.$

Thus you want k such that

$$ 2^{27-k} \lt kt$$ $$ 27-k \lt \log\_2 k + \log\_2 t $$ $$ 27 - \log\_2 k - \log\_2 t \lt k.$$

But for $k \> 1$, $\log\_2 k \> 0$ so choose

$$ k \> 27 - \log\_2 t. $$
> 8 votes

---
Tags: algorithm-analysis, randomized-algorithms, probabilistic-algorithms, applied-theory
---


title: Practical Page-Replacement Algorithms

text:
# Question
Title: Practical Page-Replacement Algorithms
Could anyone suggest other page replacement algorithms that are applicable to the real world aside from

* FIFO,
* Second Chance (Clock),
* Enhanced Second Chance and
* Random?

# Answer
> 4 votes
The Least-Recently Used (LRU) is a very common algorithm for page replacement, especially in system softwares that are exposed to data access of temporal locality.

---
Tags: reference-request, operating-systems, memory-management, paging
---


title: Smallest non-halting unlambda program

text:
# Question
Title: Smallest non-halting unlambda program
Is ````sii``sii` the smallest Unlambda program that doesn't halt?

In other words, what is the smallest non-terminating combinator term in SKI augmented with $C$ (call/cc) and $D$ (delay)? Is it $SII(SII)$?

# Answer
> 7 votes
Intuitively speaking, a non-terminating program needs either:

* a combinator such as $Y$ which, when applied, reduces to a larger expression containing itself;
* or two combinators such as $S$ which, when applied, replicate at least one of their arguments: one to do the initial replication and one to be replicated.

Unlambda lacks a combinator of the first type, but has two combinators of the second type: $S$ and $C$.

In the SKI-calculus, following the intuition above, a non-terminating term needs to somehow apply $S$ with the first argument being $S$. So it would have to be of the form $Swx(Syz)$, i.e. ````s*wx*``s*yz*` in Unlambda). This suggests that $SII(SII)$ is minimal. (Note that I've only given an intuition, I haven't proved it!)

However Unlambda also includes `c` (call/cc), and this is a very powerful operator in terms of replicating its argument. A term of the form $Cfx$ applies its own continuation $\phi$ to the function $f$; if $f \phi$ itself arranges not to destroy its context, then the term won't terminate. For example, $CI(CI)$ is non-terminating (exercise: work it out). ```ci`ci` is known as the Yin-Yang puzzle. To see it in action, make it print a trace of its execution: ```.@`ci`.*`ci`.

Because $S$ requires 3 arguments and $C$ requires 2, intuitively, there can't be a non-terminating 3-combinator term, so the 4-combinator term we found above is minimal.

Here's a quick-and-dirty bash script that enumerates all possible Unlambda terms of up to 4 combinators (i.e. 3 application nodes) and prints out the ones that take more than 1 second to terminate. I omitted the I/O primitives which reduce like `i`, as well as `e` (exit) which obviously wouldn't help to make a program non-terminating. This is an experimental way to list the non-terminating terms — the terms not printed here are guaranteed to be terminating (assuming a correct implementation), and the terms printed here are likely to be non-terminating.

```
for a in s k i c d v; do
  for b in s k i c d v; do
    for c in s k i c d v; do
      for d in s k i c d v; do
        for p in @$a$b @@$a$b$c @$a@$b$c @@@$a$b$c$d @@$a@$b$c$d @@$a$b@$c$d @$a@@$b$c$d @$a@$b@$c$d; do
          p=${p//\@/\`}
              timeout 1 unlambda <<<$p || echo $p
        done
      done
    done
  done
done

```

The result of the experiment is that only the following terms are potentially non-terminating:

```scc?
``c?`c?

where each `?` can be independently `i`, `c` or `d`. In other words, the non-terminating combinator terms are $SCCx$ and $Cx(Cy)$ (or so the experiment suggests, but it happens to be correct).

Exercises:

* Work out the reductions for these terms and check that they are indeed non-terminating. Do they loop or do they grow forever?
* Prove that all smaller terms terminate. (I don't think there's anything more interesting than a long case enumeration.)
* How does $SCCI$ relate with my intuition above concerning the minimum content of a non-terminating term — the $S$ replicates only $I$?
* Prove or disprove that there is no smaller non-terminating SKI term than $SII(SII)$. Are there others of the same size?

---
Tags: lambda-calculus, halting-problem, combinatory-logic
---


# Question
Title: Why is there still nondeterminism in my automaton?
I've been solving some exercises recently and it appears my answer was wrong for this particular example. The task is to convert this NFA into a DFA:

My attempt is this:

Now the tool I'm using (Exorciser) says that there is still nondeterminism in the automaton (even though it's equivalent to the original).

I don't see it; where is the mistake?

# Answer
The non-determinism comes from the state `{q0, q2}` because on input `b`, there are two transitions i.e. the self loop on `{q0, q2}` itself and second the transition to state `q2`. So when the NFA reaches the state `{q0, q2}` \- it has two options of taking a transition and has to **non-deterministically** decide which state to take a transition to.

Following this mini-method I told above, you can figure out where you are wrong.

However, for conversion of NFA's to DFA's, I recommend following a Powerset Construction algorithm by which mistakes are minimal.
> 3 votes

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


# Question
Title: Automatically generate meaningful queries for a data table
My field of research is not Database or AI. But I have some problems to solve, and would like to know which branch this kind of problems belong to, and what are the results.

The main question is: given a table of data, there are lots of possible queries that can be made. But some queries are meaningful, some are meaningless. Are there some algorithms to **automatically generate** a ranked set of **meaningful** queries, from the relationships inside the table?

Here is an example:

```
ArticleID   Price   Quantity    Sale
A01         10      3           30
A01         10      3           30
A02         20      4           80
A02         20      5           100
A03         15      3           45
A03         15      4           60
A03         15      5           75
A04         20      2           40
A04         20      3           60
A04         20      4           80

```

There are two relationships in this table, which may be given or inferred (the detection of the relationships is not an issue here): a) one `ArticleID` maps one `Price`; b) `Sale = Price * Quantity`.

Then, the first issue is, how to automatically generate some queries? For instance:

```
1) Sum of Quantity by ArticleID
2) Sum of Sale by ArticleID
3) Sum of Price by ArticleID

```

The second issue is, how to rank the meaningful queries? For example,
intuitively, we can say that `Query 1` and `Query 2` make more sense than `Query 3`. And this conclusion can be more or less inferred from the two given relationships.

Certainly, the problem becomes more complexe when there are relationships among several tables. The tables and the relationships that I study are not very complicated.

Could anyone tell me which field this problem belongs to? Are there some good results/proposals that are easy to understand?

# Answer
> 0 votes
I have no idea whether this has been addressed before. I have never seen it (but I am not in databases), and I would be surprised if no one had adressed it. Since there are no answers yet, I will attempt to give a view that may hopefully help. It is very elementary, and it would really require more study of how this kind of view may combine with the various types of queries one can make. What I write below was strongly influenced by your example and the queries that go with it. But there is more to a relational database.

As remarked by Raphael, generating queries is relatively easy. But that is not your problem. What you want is *meaningful* queries. It is a semantic issue that depends much on the semantics you attach to your columns.

I suspect that you may have a **typing problem**, which I tend to see also as a dimensional problem in the physics sense. It may not be easy or even meaningful to attempt to deal with it in a purely automated way. I am not thinking of elementary types as found in most programming languages, but of abstract types as found now in object oriented languages, and all languages with data abstraction.

Hence, first of all, **you should look whether there is something to be learned from object oriented databases.**

I also know that physicists use "databases" to store their experimental data before exploiting it with specialized software. If information can be found on these tools (usually very proprietary), there is a possibility that they may have addressed this typing issue, though a physicist told me that is not the case.

Also you should make clear what you intend to provide as input to your generator, so that your queries make sense. Short of providing some kind of semantic information, a column of numbers is just a column of numbers, and any idea you may have to fold, spindle or mutilate them with SQL queries is fair game. You have to say what data, what semantic information, you provide to your generator, if you hope for an answer (which is a variant of the GIGO principle).

I will attempt to illustrate a possible type vision with physics. Physics uses a lot of scalar quantities: weight, distance, speed, date, duration, temperature, heat.

You could have these quantities appear to qualify columns in the data base of a physicist. But not all operations between them make sense. Testing equality of weight and date probably does not. Actually, testing equality between to quantities that have different physical dimension is likely to be meaningless, unless there is some implicit relation that only the database creator can know about. The same goes for addition quantities with different dimensions.

Some dimensions have additive qualities, such as weight or volume, while others do not, such as temperature or density, though they can be averaged (some of them). Physicists distinguish them by talking of intensive or extensive properties. Extensive properties are proportional to the amount of material. They can be added.

I suspect that these concepts exists also for your store management database, but may have to be refined (I am not sure). The price per unit of a good is clearly an intensive property. Adding these prices makes no sense (whether its concerns the same article or different ones). But, for example, taking the average may have sense, if you do it for distinct articles.

Now such a classification can lead to more knowledge. For example. the ratio of two extensive properties is an intensive one. This is why the price per unit is intensive.

But *these concepts apply to properties of materials*, and I suspect things may be more complex than that in general. A ratio could be additive in a context where intensive/extensive does not apply. Still, though speeds can be added in physics, if you have a column of speeds in your database, it is very likely that adding them makes no sense, and that taking the average makes a lot of sense.

More generally, dimension equations may give you hints of what makes or does not make sense. Maybe there are other concepts such as intensive and extensive properties.

Then, in the same spirits as abstract typing in programming languages, with a specification that states the allowed primitive operations, you could have a specification of your database that give you information about columns (such as dimension, or allowed operations) from which you can infer whether a queries is meaningful.

But I do not believe this can be inferred from a simple knowledge of the database without any semantic knowledge provided by the designer. This knowledge should be part of the design process anyway.

Another point is about ranking. I am not sure that making sense can be rated on a subtler scale than (true, false). If things can make sense at all, they can be very important to some people and without interest to others. This can probably be measured by actual database use. But again, it also depends on what you want the ranking for, and on the kind of semantic information you can provide.

---
Tags: artificial-intelligence, data-mining, databases, database-theory, data-sets
---


title: Does the BIOS run on the CPU?

text:
# Question
Title: Does the BIOS run on the CPU?
I was just thinking about this: Does the BIOS execute on the CPU? If so, how does it handle multiple CPU architectures/instruction sets? If not, what does it execute on?

# Answer
> 6 votes
Yes, the processor itself runs the BIOS boot program. Each motherboard has to be equipped with appropriate BIOS that a processor of compatible chip set can use.

# Answer
> 2 votes
Yes.

The bios is just software stored on a chip. It has a special memory address, and the CPU is hardwired to execute the program in that address when it turns on.

---
Tags: computer-architecture
---


title: Inserting vertex in an adjacency matrix

text:
# Question
Title: Inserting vertex in an adjacency matrix
If a graph with $v$ vertices is represented in the form of adjacency matrix .

Then, adding a new vertex to the existing graph requires how much time ?

Is it $O(v^2)$ or $O(2v)$ .

We have the adjacency matrix of the graph with $v$ vertices , by adding a new vertex we have to enter a row (for edges leaving the new vertex) and a column(for incident edges of new vertex) and an entry for self loop . So ,there is a need to update $2v+1$ new entries. So i am in favor of $O(2v)$. Did i miss something ? Is there any need for creating new empty matrix of size $(v+1)^2$ and then copying $v^2$ existing elements and updating remaining $2v+1$ entries of new vertex , which takes $O(v^2)$ time.

Thanks in advance .

# Answer
> 7 votes
This is completely implementation-dependent. As you say, if you need to copy the existing matrix, you have $n^2$ entries to copy, which takes $\Theta(n^2)$ steps; if you only need to add the new entries (for example, if you've pre-allocated a large matrix but you're adding the vertices one at a time), you only need to write $O(n)$ entries each time.

If you did have to copy the matrix every time you grow it, a more time-efficient option would be to start with a small matrix (say, $10\times 10$) and double it every time it fills up. Doing it that way means you need fewer expensive copies but the potential down-side is that you could waste a lot of space. For example, if your graph ends up having 21 vertices, you'll have allocated a $40\times 40$ matrix, most of which is empty. You could mitigate that by not growing the array so aggressively (say, making it 25% bigger each time it grows, instead of 100%).

---
Tags: graphs, time-complexity, runtime-analysis
---