# Question
Title: Are there NP problems, not in P and not NP Complete?
Are there any known problems in $\mathsf{NP}$ (and not in $\mathsf{P}$) that aren't $\mathsf{NP}$ Complete? My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility.

If there is a problem that is $\mathsf{NP}$ (and not $\mathsf{P}$) but not $\mathsf{NP\text{-}complete}$, would this be a result of no existing isomorphism between instances of that problem and the $\mathsf{NP\text{-}complete}$ set? If this case, how would we know that the $\mathsf{NP}$ problem isn't 'harder' than what we currently identify as the $\mathsf{NP\text{-}complete}$ set?

# Answer
> 28 votes
> Are there any known problems in NP (and not in P) that aren't NP Complete? My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility.

No, this is unknown (with the exception of the trivial languages $\emptyset$ and $\Sigma^\*$, these two are not complete because of the definition of many-one reductions, typically these two are ignored when considering many-one reductions). Existence of an $\mathsf{NP}$ problem which is not complete for $\mathsf{NP}$ w.r.t. many-one polynomial time reductions would imply that $\mathsf{P}\neq\mathsf{NP}$ which is not known (although widely believed). If the two classes are different then we know that there are problems in $\mathsf{NP}$ which are not complete for it, take any problem in $\mathsf{P}$.

> If there is a problem that is NP (and not P) but not NP Complete, would this be a result of no existing isomorphism between instances of that problem and the NP Complete set?

If the two complexity classes are different then by Ladner's theorem there are problems which are $\mathsf{NP}$-intermediate, i.e. they are between $\mathsf{P}$ and $\mathsf{NP\text{-}complete}$.

> If this case, how would we know that the NP problem isn't 'harder' than what we currently identify as the NP Complete set?

They are still polynomial time reducible to $\mathsf{NP\text{-}complete}$ problems so they cannot be harder than $\mathsf{NP\text{-}complete}$ problems.

# Answer
> 12 votes
As @Kaveh stated, this question is only interesting if we assume $P \neq NP$; the rest of my answer takes this as an assumption, and mostly provides links to further wet your appetite. Under that assumption, by Ladner's theorem we know that there are problems that are neither in $P$ nor $NPC$; these problems are called $NP$-intermediate or $NPI$. Interestingly enough, Ladner's theorem can be generalized to many other complexity classes to produce similar intermediate problems. Further, the theorem also implies, that there is an infinite hierarchy of intermediate problems that are not poly-time reducible to each other in $NPI$.

Unfortunately, even with the assumption $P \neq NP$ it is very difficult to find natural problems that would be provably $NPI$ (of course you have the artificial problems coming from the proof of Ladner's theorem). Thus, even assuming $P \neq NP$ at this time we can only believe some problems to be $NPI$ but not prove it. We come to such beliefs when we have reasonable evidence to believe that an $NP$ problem is not in $NPC$ and/or not in $P$; or just when it has been studied for a long time and avoided fitting into either class. There is a pretty comprehensive list of such problems in this answer. It includes such all-time favorites as factoring, discrete log, and graph-isomorphism.

Interestingly, some of these problems (notable: factoring and discrete log) have polynomial time solutions on quantum computers (i.e. they are in $BQP$). Some other problems (such as graph-isomorphism) are not known to be in $BQP$, and there is ongoing research to resolve the question. On the other hand, it is suspected that $NPC \not\subseteq BQP$, thus people don't believe we will have an efficient quantum algorithm for SAT (although we can get a quadratic speed up); it is an interesting question to worry about what sort of structure $NPI$ problems need in order to be in $BQP$.

# Answer
> 7 votes
No **NP**-complete problems are known to be in **P**. If there is a polynomial-time algorithm for any **NP**-complete problem, then **P** = **NP**, because any problem in **NP** has a polynomial-time reduction to each **NP**-complete problem. (That's actually how "**NP**-complete" is defined.) And obviously, if every **NP**-complete problem lies outside of **P**, this means that **P****NP**. We're not really sure why it's hard to show it one way or the other; if we knew the answer to that question, we'd probably know a lot more about **P** and **NP**. We have a few proof techniques that we know don't work (relativization and natural proofs, for example), but don't have a principled explanation as to why this problem is hard.

If there are problems in **NP** which are not in **P**, then there is actually an infinite hierarchy of problems in **NP** between those in **P** and those which are **NP** complete: this is a result called *Ladner's theorem*.

Hope this helps!

# Answer
> 6 votes
There are some problems which are NP, but no one knows they are NP-Complete or $P$, like graph isomorphism1. But as I know there isn't special complexity class for such a problems, may be I'm wrong, though.

May be it's $P$, e.g before AKS algorithm no one knows primality testing is $P$ or NPC.

Also there are some problems which are NPC but not in strong sense or weakly NP-Complete, like 2-Partition problem, means, if the input numbers are in polynomial order of input size, this problems can be solved in $P$ (or there is a pseudo polynomial time algorithm for them).

---

1 Similar problem: sub graph isomorphism is NP-Complete in strong sense.

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


# Question
Title: How to make NFA remember its first step?
I have to design an NFA that will take the strings `"token"` and `token`.

I can use $\lambda$ or `"` to the first state, but then how do I know on the final state if it should have end quotes or not?

# Answer
NFAs have finite "memory", and you need to store one bit of information: whether the first symbol was `"`.

> Copy the automaton for tokens. If your string starts with `"`, move to one copy; if not, to the other. The first copy then requires a trailing `"` to accept, the second one does not.
> In general, you can implement any finitely-bounded counter like this: just copy all states as many times as you need.
> 2 votes

# Answer
What you can do is the following. Suppose you NEA $N$ that accepts all `token` is the tuple $(Q,\Sigma,\delta,q\_0,F)$. You build a new NEA $N'$ where you introduce for every state $q\in Q$ a copy. This can be encoded by defining as new state space as $Q':=Q\times\\{\text{orig},\text{copy}\\}$.

We interpret the new states as follow. If you are in some state $(q,\text{orig})$ then the text started, without `"` otherwise, if you are in some state $(q,\text{copy})$, the text started with `"`. Now you have to add the transitions. The start state of $N'$ is $(q\_0,\text{orig})$ and you can go with an `"` from that state to $(q\_0,\text{copy})$. Otherwise it is not possible to traverse between the copied states and the original states. I think from here on you can figure out how to wire the rest of the NEA. One final remark you need $|F|$ additional states that ensure that the last character in the `"`-part ends with a `"`.
> 2 votes

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


# Question
Title: How to convert process / cpu core based upon MIPS?
I want to know how can i find number of cpu cores/processor supported given i have the MIPS value?

For e.g I want to know the number of matching cores/processor to process speed of 18 triilion instructions / sec.

# Answer
For a modern CPU there is no exact MIPS rating since it depends on the specific instruction stream, power saving mode, and other factors. As a reference number you may look at the BogoMIPS rating that is calculated by the Linux kernel.

A desktop CPU core at 3GHz can process about 2 instructions per clock cycle *on average* resulting in a rating close to 6000 MIPS (or 6 billion instructions per second), therefore 18 trillion instructions would require about 3000 cores.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: How to show that f(x) is primitive recursive?
> Let
>
> $$f(x)=\begin{cases} x \quad \text{if Goldbach's conjecture is true }\\ 0 \quad \text{otherwise}\end{cases}$$
>
> Show that f(x) is primitive recursive.

I know a primitive recursive function is obtained by composition or recursion, but I don't know what should I do about this problem.

# Answer
> 7 votes
Goldbach's conjecture is either true or false. Do a case analysis on the two possibilities. In one case, $f(x)=x$, which is primitive recursive. In the other case, $f(x)=0$, which is also primitive recursive. Therefore $f$ is primitive recursive.

---
Tags: computability, recursion
---


# Question
Title: Asymptotic time complexity of a two-loop program
I have two pieces of code in a function which I'm trying to calculate the asymptotic running time for:

```
for (int x = 0; x < y; x++) {
    total  +=  total;
    total  +=  x;
}

```

and:

```
while (y > 0) {
    total  -=  y;
    y  =  y/2;
}

```

Combining those two pieces of code, what is the run time of that function and how do I calculate it?

# Answer
> 2 votes
The first loop has $y$ iterations, each iteration takes constant time ($O(1)$), so all together we have $O(y)$. The second loop has $\log\_2(y)$ iterations of constant time, giving a complexity of $O(\log\_2(y))$. Both loops together we have: $O(y + \log\_2(y)) = O(y)$ because $y$ dominates $\log\_2(y)$.

---
Tags: time-complexity, imperative-programming, loops
---


# Question
Title: Superpolynomial time set such that SP=NSP is known?
Are there any superpolynomial time set $\mathsf{SP}$ in between $\mathsf{P}$ and $\mathsf{EXPTIME}$ such that the problem $\mathsf{SP}=\mathsf{NSP}$ has a known answer?

**UPDATE**: It must be defined by time and strictly between $\mathsf{P}$ and $\mathsf{EXPTIME}$. I was wondering, what if Cobham's thesis is wrong and we are fighting with $\mathsf{P=NP}$ because of that thesis when the really useful question is another one? Maybe one that's even already answered?

# Answer
> 1 votes
Take any time complexity class and its corresponding nondeterministic counterpart: $\mathsf{DTime(F)}$ and $\mathsf{NTime}(F)$ where $F$ is a family of nice functions containing polynomials and bounded by exponential functions. You are asking if we know these two classes are equal. We don't know!

Take $SAT$ as an example. A certificate can be verified in linear time so it is in $\mathsf{NTime}(n)$. However there is no algorithm that solves even very simple instances of $SAT$ (e.g. decide if the propositional statement that n+1 pigeons can be mapped into n holes is false) significantly faster than brute-force, i.e. exponential time. In other words, we don't even know if $\mathsf{NTime}(n) \subseteq \mathsf{DTime}(f)$ where $f$ is a little bit smaller than exponential function $2^n$. IF what you are asking was true then the lhs would be subset of your $\mathsf{NTime}(F)$ and therefore by your assumption a subset of $\mathsf{DTime}(F)$ where $F$ is smaller than exponential functions.

The question about $\mathsf{P}$ and $\mathsf{NP}$ is not *only* important because of Cobham's thesis that efficient computations are captured by $\mathsf{P}$, we don't know any simulation of nondeterminisitic time bounded machines by deterministic ones which doesn't use brute force search for the certificate. So the essential question about $\mathsf{P}$ vs. $\mathsf{NP}$ is can we find a certificate in a space exponentially faster than brute-force search of the space?

In fact, the question was known in Russian literature as the *perebor* problem (the brute-force search problem).

If you don't accept Cobham's thesis then you can think of $\mathsf{P}$ vs. $\mathsf{NP}$ question as the flagship of questions about the relation between verifying and constructing answers, or as I said above, as the question about existence of deterministic search algorithms which are exponentially faster than brute-force search.

---
Tags: complexity-theory, nondeterminism
---


title: Complement of HAMPATH

text:
# Question
Title: Complement of HAMPATH
Is the complement of the Hamiltonian Path problem known to be in $\mathsf{NP}$? I could not find explanations saying that it is, but then neither were there any claims saying that it is **not** in $\mathsf{NP}$.

# Answer
The HAMPATH complement ("G does not contain an Hamiltonian path from s to t") is in co-NP; to be more precise it is co-NP complete (it is easy to prove that $L$ is NP-complete if and only if its complement $\bar{L}$ is co-NP-complete).

The question if it is in NP is open.

But since HAMPATH is NP-complete, if its complement is in $\mathsf{NP}$ then $\mathsf{NP} = \mathsf{co\mbox{-}NP}$
> 9 votes

---
Tags: complexity-theory, decision-problem
---


# Question
Title: Are there are problems in NP that have been shown to be not NP-complete but it is still not known if they are in P or not?
I am not talking about NP-indeterminate class because those problems have to be shown to not exist either in P or NP-complete class and existence of such problems proves P!=NP. I am interested to know if we are half-way there i.e. problems that have been proven to be not NP-complete but are in NP but we don't know if they are in P as well.

What about such problems whose deterministic polynomial solution was found only recently? Was primality testing such a problem?

I would appreciate if the answers are given for someone like me who only has a high level understanding of computational complexity theory.

# Answer
> 9 votes
Any problem that is provably not $\mathsf{NP}$ complete (w.r.t. polynomial time reductions) would mean that the class of problems reducible to it are distinct from $\mathsf{NP}$. In other words if you show some problem is in $\mathsf{NP}$ but is not $\mathsf{NP}$ complete would imply that $\mathsf{P}$ is not equal to $\mathsf{NP}$.

In short, there is no problem in $\mathsf{NP}$ that we know it is not $\mathsf{NP}$-complete.

---

Regarding primality and AKS algorithm for it:

Note that the according to the current state of knowledge, it is possible that primality is NP-complete. Existence of a deterministic polynomial time algorithm for a problem does not rule out the possibility of the problem being $\mathsf{NP}$-complete.

You are probably interested in the list of problems that are conjectured to be between $\mathsf{P}$ and $\mathsf{NP}$ (known as $\mathsf{NP}$-intermediate) in which case you can check the answers to Problems Between P and NPC.

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


title: Universality of NOT and CNOT

text:
# Question
Title: Universality of NOT and CNOT
I'm trying to figure out why NOT and CNOT gates are not sufficient to create all bijective functions in classical circuits. I have been struggling on this for hours, and just can't make sense of it.

I feel it has something to do with the Toffoli gate, as it contains an (implicit) AND operation, and I feel that's what missing in the NOT and CNOT gates. However I can't find a proper way to actually 'show' this.

# Answer
Edit: This is a proof for the non-quantum version.

Suppose we want to compute $x \land y$ from $x,y,0,1$ using the operations NOT and CNOT (=XOR). Prove by induction that any such expression is equal to one of the following forms: $$ 0,1,x,y,\lnot x, \lnot y, x\oplus y, \lnot(x\oplus y). $$ It is more helpful to write it in the form $ \alpha \oplus (\beta \land x) \oplus (\gamma \land y)$, where $\alpha,\beta,\gamma \in \\{0,1\\}$. Yet more helpful is to switch notation so that this expression is written $\alpha + \beta x + \gamma y$; this should be suggestive enough.
> 4 votes

---
Tags: logic, circuits
---


# Question
Title: Rigorous proof against pseudo random function
I have the following problem:

Deﬁne the keyed function F as follows: On input k ∈ {0, 1}$^n$ and x ∈ {0, 1}$^n$ , Fk(x) = k ⊕ x.Rigorously prove that F is not a pseudorandom function.

How do I approach a proof against pseudorandomness for a keyed function? I don't know where to start with this one.

# Answer
How to approach it? It's always the same answer - **go back to the definitions**.

the definition of PRF, talks about a *family* of functions $\\{f\_k\\}$. The key $k$ just selects one specific function out of this big family.

Next, for $\\{f\_k\\}$ to be a PRF family,the definition requires that any PPT algorithm $A$ will not be able to distinguish a member of the that family, from a really-random function (that is, a function sample randomly from all-the-possible-functions).

Since all the functions in your family have a very specific structure, you can easily built an algorithm $A$ that will always answer '1' if it's input function has the structure $f\_k(x)=k\oplus x$, or otherwise, it outputs '0' (I let you complete the details). This $A$ is a distinguisher for that family-- for functions from this family it always answers `1`, and for a random-function, it will answer '0' most of the times (say, it will answer '0' for at least half of those functions). Since such a distinguisher exists, the given family of functions is not pseudo-random.
> 7 votes

---
Tags: proof-techniques, cryptography
---


# Question
Title: Designing context free grammar for a language with range restriction on repetition of alphabets
I am having issue with designing contex free grammar for the following language:

$L = \\{0^n 1^m \\, | \\, 2n \leq m \leq 3n \\}$

I can design for the individual cases i.e. for $m \geq 2n$ and $m \leq 3n$ but don't know how should i combine both. Or is it a different approach altogether?

# Answer
> 3 votes
It has been a while, since I have done context-free grammars, but I think this should be the answer:

$\qquad \displaystyle A \to 0A11 \mid 0A111 \mid \varepsilon$

I am assuming that empty string is in $L$.

The idea behind is, that you are working your way from outside. Since you need at least 2 times more of $1$'s, than you need $0$'s, you need the first rule. The upper limit is handled with the second rule. All cases inbetween are also covered. $-$ is needed for termination.

---
Tags: context-free
---


# Question
Title: Problem with implementing Brzozowski's algorithm
I've been trying to implement Brzozowski's algorithm but I've just discovered that it creates suboptimal automata for a certain class of inputs, having one more state than what is really needed in the result. I can show it on a trivial automaton:

```
   a b           a   b           a b            a     b            a b
>0 0 1  rev  *0 0,2  -   det  >0 - 1  rev  *0   -     -    det  >0 1 2
 1 1 2  -->   1  1   0   -->   1 2 5  -->   1   -    0,4   -->   1 1 2
*2 0 2       >2  -  1,2        2 2 3        2  1,2    -          2 2 3
                              *3 4 -        3   -     2         *3 1 3
                              *4 4 1        4  3,4    -
                              *5 5 5        5   5    1,5
                                           >6 3,4,5 1,2,5

```

Here *rev* is the edge reversal part, where I'd already removed the transitions on epsilon, and *det* is determinization through powerset construction, creating new states as soon as it discovers them, recursively.

The problem here is this: once I add the extra state to make up for the three different start states after the first edge reversal and powerset construction, nothing ever returns to that state and thus I can't get rid of it later for being equivalent to the original start state.

Is there something wrong with the way I'm doing it? Am I missing something?

# Answer
> 6 votes
This is an excellent question!

The reverting step in Brzozowski's Algorithm does not introduce a new virtual starting state that leads to the old accepting states via $\varepsilon$-transitions. Instead it allows multiple starting states, which is no big problem, if you construct the product-automaton anyway right after the reversion.

Conceptually, it is the easiest to consider reverting and determinization as one single step. If your DEA is $M=(Q,\Sigma,\delta,q\_0,F)$, then define as the reverted DEA $ M^R=(Q^R,\Sigma,\delta^R,q\_0^R,F^R)$ as follows:

* $Q^R=\mathcal{P}(Q)$,
* $q\_0^R=F$,
* $F^R=\\{ P\subseteq Q \mid q\_0\in P\\}$,
* $\delta^R(P,a):=\\{ p\in Q \mid \delta(p,a)\in P\\}$.

(You might want to ignore states that are not reachable.)

Brzozowski's Theorem states that $(M^R)^R$ is a minimal DEA accepting $L(M)$.

For further reading I suggest Elements of Automata Theory by Sakarovitch pages 116-117.

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


# Question
Title: Providing Tight Example in Approximation Algorithm Analysis
Let's say I found a 2-approximation algorithm for a certain problem and I want to show that the analysis is tight.

Do I now need to come up with an example of generic size $n$ or does it suffice to show that I have an example of size $10$ for which the algorithm yields $2OPT$?

# Answer
> 6 votes
That depends on your definition of approximation ratio. Normally the approximation ratio is defined as the worst ratio between optimal solution and the one produced by your algorithm. If this is the case, all you need to show that the ratio is tight is come up with one bad example.

Sometimes, however, you prove something like $ALG \leq 2OPT + 1$. This means that your approximation ratio is really $2 + o(1)$. To show that this is tight, you will need an example for infinitely many sizes (but not necessarily for a *generic* size; perhaps all your examples have even size).

# Answer
> 3 votes
If your algorithm achieves a 1.5 approximation on all but a finite set $S$ of instances, on which your algorithm achieves a 2-approximation, then you could "improve" your algorithm by "hardwiring" the optimal solutions for the instances in $S$ into your algorithm. In short, for theoretical purposes, an algorithm that succeeds on all but a finite set of instances is just as good as an algorithm that always succeeds. Therefore, a *theoretically meaningful* tight example is actually an infinite family of tight examples. As Yuval says, any infinite family of examples will do, you don't need an example for every instance size.

That being said, most problems allow you to "scale up" a small example into a larger one.

---
Tags: algorithms, proof-techniques, approximation
---


# Question
Title: What is the depth of a complete binary tree with $N$ nodes?
This question uses the following definition of a complete binary tree:

> A binary tree $T$ with $N$ levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.

The following is an excerpt from *Algorithms*:

> It ($\log N$) is also the depth of a complete binary tree with $N$ nodes. (More precisely: $⌊\log N⌋$.)

Why is the above excerpt true?

Originally defined here

# Answer
Consider how a complete binary tree of height $h$ is constructed, one vertex at the root level, two at the first level below the root, four at the second level below, and so on, until the $h^{th}$ level, which has at least one vertex, but at most twice as many as the previous level. Note that the number of vertices at each level is a power of two (excluding the last, which is a special case). Then we have: $$ 1+\sum\_{i=0}^{h-1}2^{i} \leq n \leq \sum\_{i=0}^{h}2^{i} $$ Using the identity that the sum of the first $k$ powers of two is $2^{k+1}-1$ we get: $$ 1+2^{h}-1 \leq n \leq 2^{h+1}-1\\ 2^{h} \leq n \leq 2^{h+1}-1 $$ and hence $$ 2^{h} \leq n \< 2^{h+1} $$

Taking the base 2 logarithm: $$ h \leq \log n \< h+1 $$ So we can conclude $$h = \lfloor\log n\rfloor$$ As $\log n$ is bigger than $h$, but less than the next integer $h+1$.
> 9 votes

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


# Question
Title: Given the phrase "Where NONE of the following are TRUE" and two statements how should a boolean logic be composed?
Let's have two statements

1. **(value \> 10)**
2. **(value \< 25)**

And a list of items with the following values

* 10
* 20
* 30

This is what a truth table would give

```
Item  Value  (value > 10)  (value < 25)
----  -----  ------------  ------------
1     10     FALSE         TRUE
2     20     TRUE          TRUE
3     30     TRUE          FALSE

```

## Example 1

```
Where ALL of the following are TRUE
   value > 10
   value < 25

```

This one is easy and we get the following

```
Where (value > 10) AND (value < 25)

```

The result is then a single value of 20

## Example 2

```
Where NONE of the following are TRUE
   value > 10
   value < 25

```

This is where I am not sure of what to generate.

This would be "simple" as it is only a NOT of the whole expression

```
Where NOT ((value > 10) AND (value < 25))

```

However, the result is then two values (10 and 30)

From what someone would think of NONE of the two statements would be something like:

```
Where NOT ((value > 10) OR (value < 25))

```

And the result would be that no items are produced.

What is the correct meaning of NONE here?

# Answer
> 4 votes
The correct meaning is:

`"Where (NOT (value > 10)) AND (NOT (value < 25))"`.

Applying one of the De Morgan's laws:

1) `P AND Q <=> NOT( (NOT P) OR (NOT Q) )`
2) `P OR Q <=> NOT( (NOT P) AND (NOT Q) )`

we get:

`"Where NOT ( (NOT(NOT(value > 10))) OR (NOT(NOT(value < 25))) )"`

and the equivalent final result is

`"Where NOT ((value > 10) OR (value < 25))"` :-)

---
Tags: logic
---


# Question
Title: If a Language is Non-Recognizable then what about its complement?
Is the complement of a Non-Recognizable language

1. Recognizable
2. Non-Recognizable
3. May be Recognizable, May be Non-recognizable. I.e cant comment.

A mathematical proof would be of great help since im unable to think of any way to prove this.

I did some research on this and found below examples. Im specifying complement using a "!"

1. !A(TM) is a non-recognizable language while A(TM) is a recognizable language.
2. EQ(TM) is a non-recognizable language and !EQ(TM) is also non-recognizable language

The above two would mean that we simply cant comment on the Recognizability of the complement of non-recognizable language. But I feel that there should be some way to prove (or disprove) this.

# Answer
> 1 votes
Assuming that you can prove statement 1 and 2 above, you have just presented a proof. You're trying to show that there exists a language which is non-recognizable such that its complement is recognizable. You then prove that $!A(TM)$ has this property. Then you want to show that there exists a non-recognizable language whose complement is also non-recognizable and then you show that $EQ(TM)$ has this property.

The point is that to prove that you can't comment, you need only to show that both possibilities are possible ie. that examples of each exist.

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


# Question
Title: How to do Fairy Chess problem in O(N^3)?
https://www.interviewstreet.com/challenges/dashboard/#problem/4f1c88e0dec8a

> Fairy Chess (35 Points)
>
> You have a $N \times N$ chess board. An $S$-leaper is a chess piece which can move from square $(x\_1,y\_1)$ on the board to any other square $(x\_2,y\_2)$ if $|x\_1 - x\_2| + |y\_1 - y\_2| \le S$. The chess board may also contain some pawns. The leaper cannot land on the same square as a pawn. In how many ways can a leaper move $M$ times on the board?
>
> Input: The first line contains the number of test cases $T$. $T$ cases follow. Each case contains integers $N$, $M$ and $S$ on the first line. The next $N$ lines contains $N$ characters each. The $i$th character on the $j$th line is a `.` if the corresponding chess square is empty, `P` if there is a pawn, or `L` if the leaper is situated on that square.
>
> Output: For each case, output the number of ways the leaper can make $M$ moves. Output each answer modulo 1000000007.
>
> Constraints: $$\begin{gather} 1 \le T \le 10 \\ 1 \le S \le N \le 200 \\ 1 \le M \le 200 \\ \end{gather}$$ There will be exactly one `L` character on the board.
>
> Sample Input:
>
> ```
> 3
> 4 1 1
> ....
> .L..
> .P..
> ....
> 3 2 1
> ...
> ...
> ..L
> 4 3 2
> ....
> ...L
> ..P.
> P...
>
> ```
>
> Sample Output:
>
> ```
> 4
> 11
> 385
>
> ```

I wrote a DP solution but with O(N^5).

> Psuedocode for ways function:

```
Memoize[Xmax][Ymax][Nmax];

ways(int X, int Y, int M) // (X,Y) current co-ordinates and M is number of moves to make
{
    if(Memoize[X][Y][M] != -1) // != -1 means we already have the result
        return Memoize[X][Y][M];
    sum=0;
    for all (u,v) such that |X-u| + |Y-v| <= S
        sum += ways(u, v, M-1);

    Memoize[X][Y][M] = sum;
    return sum;

}

```

> Code:

```
/* Enter your code here. Read input from STDIN. Print output to STDOUT */

#include <stdio.h>
#include <stdlib.h>

long ways(long ***DP, char **Chess, int X, int Y, int S, int N, int M);

int main()
{
    int T;
    scanf("%d", &T);
    while(T>0)
    {
        int N, M, S;
        scanf("%d", &N);
        scanf("%d", &M);
    scanf("%d", &S);
        long ***DP = (long ***) malloc(sizeof(long **) * N);
        int i,j,k;
        char **Chess = (char **)malloc(sizeof(char *) *N);
        int Xstart;
        int Ystart; //printf("N=%dM=%dS=%d\n", N, M, S);
        for(i=0;i<N;i++)
        {
        Chess[i] = (char *)malloc(sizeof(char) *N);
        DP[i] = (long **)malloc(sizeof(long *) * N);
            for(j=0;j<N;j++)
            {   //printf("i=%dj=%d\n", i, j);
        DP[i][j] = (long *)malloc(sizeof(long) *(M+1));
                char a;
                scanf(" %c", &a);
                if(a=='L')
                {
                    Xstart = i;
                    Ystart = j;
                }
                Chess[i][j] = a;
        //printf("jf=%d\n", j);
        }
        }

        for(i=0;i<N;i++)
        {
            for(j=0;j<N;j++)
            {
                for(k=1;k<M+1;k++)
                {
                    DP[i][j][k] = -1;
                }
                DP[i][j][0] = 1;
            }
        }

       printf("%ld\n", ways(DP, Chess, Xstart, Ystart, S, N, M));
       T--;
    }
}

long ways(long ***DP, char **Chess, int X, int Y, int s, int N, int M)
{
    if(DP[X][Y][M] !=-1)
    {
    //printf("X=%d Y=%d M=%d Val=%ld\n", X, Y, M, DP[X][Y][M]);
    return DP[X][Y][M];
    }
    else
    {
        long sum1 = 0;

        int S,k;
    sum1 += ways(DP, Chess, X, Y, s, N, M-1);

        for(S=1;S<=s;S++)
    {
        for(k=0;k<=S;k++)
            {
                if(k!=0 && (S-k)!=0)
                {
                    if(X+k<N && Y+(S-k) <N && Chess[X+k][Y+(S-k)] != 'P')
                    {
                        Chess[X+k][Y+(S-k)] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X+k, Y+(S-k), s, N, M-1);
                Chess[X+k][Y+(S-k)] = '.';
                        Chess[X][Y] = 'L';
                    }
                    if(X+k<N && Y-(S-k)>=0 && Chess[X+k][Y-(S-k)] != 'P')
                    {
                        Chess[X+k][Y-(S-k)] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X+k, Y-(S-k), s, N, M-1);
                Chess[X+k][Y-(S-k)] = '.';
                        Chess[X][Y] = 'L';
                    }
                    if(X-k>=0 && Y+(S-k) <N && Chess[X-k][Y+(S-k)] != 'P')
                    {
                        Chess[X-k][Y+(S-k)] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X-k, Y+(S-k), s, N, M-1);
                Chess[X-k][Y+(S-k)] = '.';
                        Chess[X][Y] = 'L';
                    }
                    if(X-k>=0 && Y-(S-k) >=0 && Chess[X-k][Y-(S-k)] != 'P')
                    {
                        Chess[X-k][Y-(S-k)] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X-k, Y-(S-k), s, N, M-1);
                            Chess[X-k][Y-(S-k)] = '.';
                        Chess[X][Y] = 'L';
                    }

                }
                else if(k==0 && (S-k)!=0)
                {
                    if(Y+(S-k)<N && Chess[X][Y+(S-k)] != 'P')
                    {
                        Chess[X][Y+(S-k)] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X, Y+(S-k), s, N, M-1);
                Chess[X][Y+(S-k)] = '.';
                        Chess[X][Y] = 'L';
                    }
                    if(Y-(S-k)>=0 && Chess[X][Y-(S-k)] != 'P')
                    {
                        Chess[X][Y-(S-k)] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X, Y-(S-k), s, N, M-1);
                Chess[X][Y-(S-k)] = '.';
                        Chess[X][Y] = 'L';
                    }

                }
                else if(k!=0 && (S-k)==0)
                {
                    if(X+k<N && Chess[X+k][Y] != 'P')
                    {
                        Chess[X+k][Y] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X+k, Y, s, N, M-1);
                Chess[X+k][Y] = '.';
                        Chess[X][Y] = 'L';
                    }
                    if(X-k>=0 && Chess[X-k][Y] != 'P')
                    {
                        Chess[X-k][Y] = 'L';
                        Chess[X][Y] = '.';
                        sum1 += ways(DP, Chess, X-k, Y, s, N, M-1);
                Chess[X-k][Y] = '.';
                        Chess[X][Y] = 'L';
                    }

                }
            }
    }
    //printf("X=%d Y=%d M=%d Val=%ld\n", X, Y, M, sum);
    DP[X][Y][M] = sum1;
        return sum1;
    }
}

```

# Answer
> 5 votes
A big hint, since this is 'homework' of a sort: this (obviously?) isn't actually anything resembling a chess problem; instead, it's a *graph theory* problem in disguise. Consider the graph with $n^2-P$ nodes, one for each cell of the board, and an edge between two nodes if they're a leaper-distance away; then the question is asking for the number of paths of length $M$ on this graph starting from a given point. Now, think about a representation that uses an $n\times n$ array representing the number of paths (of a specific length) from the starting point to the given point. Because the degree of the graph is small (there are roughly $2S^2$ individual moves from any given point), a single iteration (going from the length-$b$ paths to the length-$(b+1)$ paths) should take $O(n^2S^2)$ time and the full algorithm should run in time $O(n^2S^2M)$.

Note that the current algorithm as given by the code is *much* worse than this: each call to the `ways()` function is a *recursive* call, meaning that some values are being recomputed many, many times; its running time is, at first glance, roughly $O(S^{2M})$ (since a call to ways($M$) makes $S^2$ calls to ways($M-1$) and thus the running time $w(M) = S^2\cdot w(M-1)$). Replacing that with an iterative approach where one loops $m$ from $1\ldots M$ and stores the number of paths of length $m$ to each cell, then uses the previous iteration's results to find all the paths of length $m+1$, should make a huge difference.

---
Tags: algorithms, data-structures, dynamic-programming
---


# Question
Title: Finding big O notation of function with two parameters
I'm looking to work out the big-O notation for the following:

$$\frac{n^{s + 1} - 1}{n - 1} - 1$$

I have a feeling the result is $O\left( n^s \right)$ but I'm not sure how to prove it.

Any help greatly appreciated! :)

# Answer
Some of modifications of *O* described in Concrete Mathematics: Foundation for Computer Science says:

$ \qquad O(f(n)) + O(g(n)) = O(\mid f(n)\mid + \mid g(n) \mid) \qquad (9.22)\\ \qquad O(f(n))O(g(n)) = O(f(n)g(n)) \qquad \qquad \qquad (9.26) $

And using some basic knowledge of *O* notation and functions:

$ \qquad O(f(n) +c) = O(f(n)) \\ \qquad \forall\_{n\in \mathbf N} \forall\_{k\>0} n^k \> 0 $

Use those transformation you can came up with something like this:

$$\frac{n^{s+1}-1}{n-1}-1 = O\left(\frac{n^{s+1}-1}{n-1}-1\right) = O\left(\frac{n^{s+1}-1}{n-1}\right) = O\left(\frac{1}{n-1}\right)O\left(n^{s+1}-1\right) = $$ $$ O\left(\frac{1}{n}\right)O\left(n^{s+1}\right) = O\left(\frac{n^{s+1}}{n}\right) = O(n^s) $$

So your intuition was right.
> 7 votes

---
Tags: time-complexity
---


# Question
Title: Given many partial orders, check them for consistency and report any that are not consistent
**Inputs.** I am given a finite set $S$ of symbols. I know there should exist some total order $\<$ on $S$, but I'm not given this ordering and it could be anything.

I am also given a collection of assertions. Each assertion takes the form $s\_1\<s\_2\<\cdots\<s\_m$, where $s\_1,\dots,s\_m$ form a subset of the symbols of $S$. The assertion probably won't mention all of the symbols of $S$, just a subset. Each assertion will probably cover a different subset.

**Warmup problem.** The starter problem is: Given $n$ assertions, identify whether they are all internally self-consistent, i.e., whether there exists a total order on $S$ that is consistent with all of the assertions, and if so, output an example of such a total order.

**The real problem.** In practice, a few assertions might be faulty. Almost all of them should be correct, though. So, the real problem is: if the assertions are not all internally self-consistent, find a minimal subset of assertions to label as "probably-erroneous", such that if you remove the probably-erroneous assertions, the remainder are all self-consistent.

**What I know.** I know how to solve the warmup problem (just compute the transitive closure of the union of the partial orders given by each assertion, and check that the result is antisymmetric; or, in other words, create a graph with $S$ as vertex set and an edge $s\to t$ if $s\<t$ appears in any assertion, then check for cycles). However, I don't know how to solve the real problem. Any ideas?

**Real-world parameters.** In the application domain where I've run into this, $S$ might have up to a few hundred symbols, and I might have up to a few thousand assertions, with each assertion typically mentioning dozens of symbols.

# Answer
This sounds like weighted FAS (Feedback Arc Set). Find a minimal (weight) feedback arc set in a directed graph and report the assertions that contributed to the wrongly directed arcs.

For each pair of symbols s and t, there is an arc saying how many assertions have s \< t and how many assertions have t \< s.

This is a known NP-complete problem.

On a different note, your problem is a classic social choice problem where each of the "assertions" are votes.
> 3 votes

# Answer
I thought I'd jot down the two approaches that have occurred to me, but maybe you can do better.

**Approach 1.** Here's a randomized procedure that, given an ordering of the assertions, will emit a candidate set of assertions labelled as "probably-erroneous" such that the remainder are all self-consistent. We can repeat the procedure many times, and keep the best output (the one with the smallest number of assertions labelled as "probably-erroneous").

The procedure:

* Step 1. Randomly permute the assertions. Create an empty graph $G$ with vertex set $S$ and with no edges
* Step 2. For each assertion, in the order chosen in step 1, do the following:

+ Suppose the assertion is $s\_1\<s\_2\<\cdots\<s\_m$. Test whether adding the edges $s\_1\to s\_2, \dots, s\_{m-1} \to s\_m$ would create a cycle in $G$.
    + If this would create a cycle, label this assertion as "probably-erroneous", and don't add the edges to $G$.
    + If this would not create a cycle, add the edges to $G$.

**Approach 2.** Create a $|S|\times|S|$ matrix $V\[\cdot,\cdot\]$, where $V\[s,t\]$ counts the number of "votes" for the claim $s\<t$. Initialize all counts in the matrix to zero.

Treat the assertion $s\_1\<s\_2\<\cdots\<s\_m$ as a collection of $m(m-1)/2$ votes for the claims $s\_1\<s\_2$, $s\_1\<s\_3$, $s\_2\<s\_3$, etc. Process each assertion, incrementing the counts in $V$ appropriately. This gives you the full matrix $V$.

Now look through $V$ to check for symbols $s,t$ such that $V\[s,t\]\>0$ and $V\[t,s\]\>0$ and such that the quantity $V\[t,s\]/(V\[s,t\]+V\[t,s\])$ is minimized. Conclude that $s\<t$ is correct, and label all assertions which contradict this (which voted for $t\<s$) as "probably-erroneous". Remove these assertions from the set of assertions, and re-start the entire procedure, until the assertions that remain are all self-consistent.

This procedure is not guaranteed to terminate with a correct answer (e.g., consider the five assertions $A\<P$, $P\<Z$, $A\<Q$, $Q\<Z$, $Z\<A$), but it's a heuristic that might be worth trying.
> 2 votes

---
Tags: algorithms, graphs, approximation, finite-sets, partial-order
---


# Question
Title: Radon transform for advanced 3d graphics and games?
The Radon transform is used to take 2d projections of an object and create a 3d representation.

It seems like it would be possible to apply such a transform in 3d graphics in games (although possibly too slow to be practical).

For example, a very simple way to display an object is to use a 3d rectangle and texture map each side. This is relatively fast but the 3d detail is limited. When a side is parallel with the visual plane it will represent the detail 100% (so the visual detail would be limited to that of the texture map). Of course it won't represent external 3d effects properly, like lighting.

But by using the Radon transform one could gain a true 3d approximation of the object from the six textures/projections used. By increasing the number of textures/projections the approximation is better.

I'm curious if the idea has potential. Possibly for high-quality 3d models it might pay off in performance and size. Of course 3d models can be optimized to limit their size which also increases speed but visually doesn't change much.

# Answer
I've been studying the use of OpenGL and DirectX and even though I am at an intermediate level, I believe this is where the use of bump maps, light maps etc comes into play. These are encapsulated in the idea of a Shader. The hardest part about the shader and lighting to work correctly with the 3D object with respect to the angle of the camera view directly depends if your normals are defined correctly. As for what you are describing it does make sense using 3D approximation, however my linear algebra is a little rusty, I am not sure if the conventional 4x4 matrices will work, and when it comes to motion with rotations you might have to redefine your quaternions too.
> -1 votes

---
Tags: algorithms, computational-geometry, efficiency, graphics
---


title: Represent string as concatenations

text:
# Question
Title: Represent string as concatenations
If $S\_1,S\_2$ are set of strings, then $S\_1S\_2 = \\{s\_1s\_2|s\_1\in S\_1, s\_2\in S\_2\\}$. $S^0=\\{\epsilon\\}$, $\epsilon$ is the empty string. $S^n = S^{n-1}S$.

Two related problems about represent string as concatenation of other strings.

1. Given a finite set $S$ of strings, how to decide if there exist a string can be written as concatenations of elements in $S$ in two different ways?
2. Given a finite set $S$ of strings and $n$, how can one compute the smallest set of strings $T$, such that $S\subset T^n$?

(Bonus: what about infinite $S$, at least when it's regular? For the second problem when $S$ is infinite, we might ask to find a minimal $T$ under set inclusion.)

# Answer
> 5 votes
I will try (1) and go for infinite (the bonus).

The finite case is called the *code problem*: finding possible decompositions is like decoding. Its classical algorithm is called *Sardinas–Patterson*. It is not immediately clear it is a finite search space. The lengths of the decomposition might be long. Still it is not Post Correspondence as that has additional restrictions.

The finite case has a simple regular language solution: for every pair of distinct $s,t \in S$ test whether the regular set $s S^\* \cap t S^\*$ is empty. (The Sardinas-Patterson tries that "in parallel".) This does not work in the infinite case as there would be infinitely many $s,t$ to test.

In the infinite (but regular) case I would build a new finite state automaton based on an automaton for $S$. It simulates in parallel the two different decompositions by keeping track of a *pair of states*, one for each decomposition. On a letter both pairs make a step on the same letter. In a final state each component may either restart (it has seen an element in $S$) or proceed (trying to find a longer word in $S$). Now we need one additional boolean addition to the state-pair as we need to check whether the two components made different choices in at least one point. Accept if both simulations end in a final state (*and* we have seen a point where the two decompositions differed). Now again there are no two different decompositions for the same string iff the language of the automaton is empty.

And indeed, for context-free the problem must be undicidable, but I do not have a reference at hand now.

---
Tags: algorithms, formal-languages, strings
---


title: Program compilation and execution flow

text:
# Question
Title: Program compilation and execution flow
I was studying operating system concepts from Silberschatz, Galvin and Gagne's book (sixth edition) and I have some questions about the flow of execution of a program. A figure explains the processing of the user program:

We get an executable binary file when we reach the **linkage editor** point. As the book says,

> The program must be brought into memory and placed within a process for it to be executed.

I have several questions about this flow:

1. Before the program is loaded into the memory, the binary executable file generated by the linkage editor is stored in the hard disk. The address where the binary executable file is stored in the hard disk is the logical address as generated by the CPU ?
2. If the previous answer is yes, Why CPU has to generate the logical address ? I mean the executable file is stored somewhere in the hard disk which pertains to an address, why does CPU has to separately do the stuff ? CPU's main aim is processing after all!
3. Why does the executable file needs to be in the physical memory i.e ram and can not be executed in the hard disk? Is it due to speed issues ?

# Answer
First of all, you are fundamentally confusing the purpose of RAM and hard disk. RAM is the only part of memory that CPU can access. Hard disk exists to expand the capacity of RAM as well as store the data permanently (data on RAM is transient).

How it works -

1. The computer generates an executable and stores it in the hard disk. It is just a passive program right now.
2. Another process (already in memory and currently running) calls the program you just created using the access path (full psth + name) in the filesystem. This is a system call; an interrupt is issued and control is transferred to OS.
3. OS decodes the path to get the actual location(s) on hard disk where the program data blocks are stored. Hard disk is treated as any other I/O device; it vouches for CPU time like any other I/O device. Here, OS has two choices:
    * either it needs to fetch data from hard disk each time hard disk has some to give (hard disk announces it by issuing interrupts) and store it in RAM. But with ever faster hard disk speeds nowadays, frequency of interrupts can be high enough to be inefficient for CPU.
    * second option is that CPU, while issuing the read command for program data blocks, also specifies the RAM memory addresses to which hard disk should directly copy its data (Direct Memory Access). Since CPU, I/O devices (including hard disk) and memory all share common bus, data can be transferred one at a time. Moreover, CPU meanwhile also has other processes (in RAM) to run while data is being copied by hard disk to RAM. Thus, both CPU and hard disk take turns when copying data to RAM. Here, DMA would be faster if CPU is idle or requires less memory accesses. When hard disk has completed writing data to RAM as specified by CPU, it issues interrupt to CPU to tell it that it has completed its task.
4. Take note above that CPU has never accessed the data of hard disk directly. The hard disk works the same way as any other device like keyboard or modem would work (via interrupts etc). Now after hard disk has copied data and interrupt generated, OS assigns stack memory and other resources for this newly created process and inserts it into the queue of active processes.

That is why when creating small beginner programs, we can never save the state of programs. We create some variables while the process is running and modify them, but never explicitly store them on the hard disk (unless engaging with the file handling aspect). When we destroy the program all the memory is lost. and all the read, write operations of a language are merely wrappers around the system calls provided by the OS so as to make the code portable across several operating systems (since system calls of each are different). These read/write/open/close system calls are requests for OS to let us access a file on hard disk, different from the RAM.

As to your question about logical addresses, it is a little ambiguous as to what you want to say. Logical addresses are used in reference to RAM by programs, and usually refer to the program's view of its memory. For a program, its logical addresses may start from 0, but that doesn't translate into the fact that all programs start at physical address 0 of RAM! You are right that CPU has to process data, but it needs some data at all to process, with is stored in RAM. The addresses provided by program code are logical (say, get data stored in location '7 + start of program') and CPU has to calculate its actual physical address to work upon (i.e. replace 'start of program' with the base address of process code blocks in RAM).

Thus, logical addresses have nothing to do with hard disks.
> 4 votes

---
Tags: compilers, operating-systems, memory-management, virtual-memory
---


# Question
Title: Size of the universe for van Emde Boas Trees
In order to achieve the time complexity of $O(\log \log u)$ for van Emde Boas trees I read in this lecture that the the universe size $u$ is chosen as $u = 2^{2^k}$ for some integer $k$ for van Emde Boas trees. Why choose $u$ to be of this specific form ?

# Answer
This assumption makes the analysis easier. If the universe $\mathcal{U}$ is of size $2^{2^k}$ then every element in $\mathcal{U}$ can be represented by $2^k$ bits. Roughly speaking, when executing one of the vEB-tree operations you halve the "relevant bits" in every level of the recursion. So when you start with $2^k$ bits, then the recursion depth is $k$.

If your universe has a size not of the form $2^{2^k}$, then you have to use floor/ceiling in the analysis.
> 6 votes

---
Tags: algorithms, data-structures, algorithm-analysis, binary-trees, trees
---


# Question
Title: Dynamic Programming Solution for Optimal Matrix Chain Multiplication Order
I have been thinking about why the dynamic programming approach to finding the optimal matrix chain order is better than a brute force approach that finds the optimal order by exploring all nested orders. The more I think about it, the more I feel strongly that the dynamic programming solution considers all possible chain orders, thus contradicting the justification of choosing a dynamic programming approach to solving this problem.

For Eg. Lets consider a product of 4 matrices. There are 5 possible matrix chain orders (in the brute force method)

(A1 (A2 (A3 A4)))

(A1 ((A2 A3) A4))

((A1 A2) (A3 A4))

((A1 (A2 A3)) A4)

(((A1 A2) A3) A4)

Now, if we consider the dynamic programming approach all the sub matrix products included in each of the orders above will be computed. How then is the dynamic programming approach more efficient than the brute force approach?

EDIT: The answers and the comments have been really useful in helping me understand the DP solution better. But I am not able to visualise a brute force approach in my head. As soon as I start writing a brute force method to compute all possible matrix multiplication orders, the DP solution manifests itself naturally in my attempt. This may be because I know the optimized DP solution and I am not able to think of a rudimentary brute force solution. If someone can mention the pseudo code for generating all possible matrix multiplication orders , it will make it clearer as to what sub-problems the DP solution avoids and hence is more efficient.

EDIT (again): Let us disregard memoization. Will the DP solution still generate lesser number of computations?

# Answer
The dynamic programming solution computes a table that for each $i\le j$ has the optimal solution for $Ai$, ... $Aj$. The computation is done bottom-up, and (as one of the comments notes) many values are reused. Total complexity order $n^3$ as there is a quadratic number of $i,j$ each taking linear time to compute.

A real brute force takes exponential time, the number of binary trees, which is equal to the number of nested expressions. See Catalan numbers.
> 5 votes

# Answer
Your example may be too small. Consider the dynamic programming algorithm on 6 terms. Let's say that (A2 (A3 A4)) is better than ((A2 A3) A4). The dynamic programming algorithm is not going to compute any of the orders:

> (A1 (((A2 A3) A4) A5)) A6
> ((A1 ((A2 A3) A4)) A5) A6
> (A1 ((A2 A3) A4)) (A5 A6)
> A1 ((((A2 A3) A4) A5) A6)
> A1 (((A2 A3) A4) (A5 A6)).
> 3 votes

---
Tags: dynamic-programming, matrices
---


# Question
Title: Explanation of recursive structure of Van Emde Boas Tree
From Van Emde Boas trees lecture:

> We will use the idea of superimposing a tree of degree ${u^{1/2}}$ on top of a bit vector, but **shrink the universe size recursively** by a square root at each tree level. The ${u^{1/2}}$ items on the ﬁrst level each hold structures of ${u^{1/4}}$ items, which hold structures of ${u^{1/8}}$ items, and so on, down to size 2. I have a question regarding van Emde Boas trees :

1. How is the universe size getting reduced ? Aren't we just spreading the universe keys which is always constant at $u$ to different levels ? I can not understand the idea of "**shriniking**" the universe size . I find similar language is used in defining the recursive structure for Van Emde Boas tree in Introduction to Algorithms by CLRS also .

# Answer
> 8 votes
Well the crucial idea about vEB trees is the following: You store all the elements as a 0/1 bitvector of size $s$. For example the vector $(0,1,1,0)$ denotes that in your universe of size $s=4$, the third and second elements are present. Now you subdivide the vectors in blocks of size $\sqrt{s}$ and for every block you also store a flag, if there is at least one $1$ in the block. This gives you a set of $\sqrt{s}$ flag bits. If you store also the $\min$ and $\max$ for every block, then you can determine in which block you have to continue your search for the successor after **either** perform a successor query in the block of your query element **or** in the flag bit vector.

This implies that the sup-problem you are requesting has size $\sqrt{s}$. But this is the same statement as saying that you go from a $k$-bit universe to a $k/2$-bit universe.

And this is meant by **shrinking** the universe.

---
Tags: algorithms, data-structures, algorithm-analysis, search-trees, trees
---


# Question
Title: Using Amdahl's law how do you determine execution time after an improvement?
Speeding up a new floating-point unit by 2 slows down data cache accesses by a factor of 2/3 (or a 1.5 slowdown for data caches). If old FP unit took 20% of program's execution time and data cache accesses took 10% of program's execution time, what is the overall speed up?

I solved this problem using amdahl's law:

FeFP = floating point enhanced fraction = .2

FeDC = data cache access enhanced fraction = .1

SeFP = floating point enhanced speedup = 2

SeDC = data cache access enhanced speedup = 2/3

Speedup overall = 1 / ( (1 - FeFP - FeDC) + FeFP/SeFP + FeDC * SeDC )

= 1 / ( ( 1 - .2 - .1 ) + .2/2 + (.1) * (2/3) ) = 1.154.

I hope I did this correctly, but I'm confused about the next part asking what percentage of execution time is spent on floating point operations after implementing the new FP unit?

I know that T\[improved \] = T\[affected\] / improvement factor + T\[unaffected\]

But I'm unclear how to use it in the context of this problem. Would appreciate all / any advice.

# Answer
Since the FP speedup  *slows down*  the cache by a factor of $2/3$, the cache is "sped up" by $3/2$. Hence the overall speedup is

$ S = \frac{1}{0.7 + 0.2/2 + 0.1 \times \frac {3}{2}} = 1.05 \equiv 5\\%$

The execution times now have the ratio: $0.7:0.1:0.15$ for remaining operations:FP:cache. The percentage time spent on FP now is $\frac{0.1}{0.7+0.1+0.15} = 0.105 \equiv 10.5\\%$.
> 3 votes

---
Tags: computer-architecture, program-optimization
---


# Question
Title: How to prove transitivity in small-o of asymptotic analysis?
Here is my proof, but I am not sure whether it is correct.

We know:

$\qquad \begin{array}{l} \forall {c\_1},\exists {n\_1},0 \le f\left( n \right) \le {c\_1}g\left( n \right),\forall n \ge {n\_1} \\ \forall {c\_1},\exists {n\_2},0 \le g\left( n \right) \le {c\_1}h\left( n \right),\forall n \ge {n\_2} \\ \end{array}$

Hope to prove:

$\qquad \begin{array}{l} \forall c,\exists {n\_0},0 \le f\left( n \right) \le ch\left( n \right),\forall n \ge {n\_0} \\ \Rightarrow 0 \le f\left( n \right) \le {c\_1}g\left( n \right) \le {c\_1}\left( {{c\_1}h\left( n \right)} \right),\forall n \ge \max \left\\{ {{n\_1},{n\_2}} \right\\} \\ \end{array}$

Let $c = {c\_1}^2$. Then,

$\qquad 0 \le f\left( n \right) \le {c^2}h\left( n \right),\forall n \ge {n\_0} = \max \left\\{ {{n\_1},{n\_2}} \right\\}$

Is there any mistake?

# Answer
> 3 votes
**Comment on your proof**: You write "Let $c = {c\_1}^2$." Strictly speaking, this doesn't make sense, since you haven't set $c\_1$ to any value yet at this point. To be formally correct, you need to start with some given $c$, and then set $c\_1$ to $\sqrt{c}$ and proceed from there (which is what I've done below where $\epsilon = c$).

---

To show that $f(n) \in o(h(n))$, you need to show that $\lim\_{n\rightarrow\infty}\frac{f(n)}{h(n)}=0$. Or, in other words, for any constant $\epsilon$, there exists $N\>0$ such that $$ \forall n \geq N\colon |f(n)| \leq \epsilon|h(n)|. \qquad \text{(A)} $$ Before proving (A), let's write out our assumptions explicitly: Since we have assumed $f(n) \in o(g(n))$, we know that for any $\epsilon$, there exists an $N\_f$ such that $$\forall n \geq N\_f\colon |f(n)| \leq \epsilon |g(n)|. \qquad\text{(1)}$$ Analogously, by $g(n) \in o(h(n))$, we know that there is $N\_g$ such that $$ \forall n \geq N\_g\colon |g(n)| \leq \epsilon |h(n)|, \quad\text{(2)} $$ for any given $\epsilon$.

**Proof of (A):** Suppose we are given some $\epsilon$. Let $$N = \max\left(N\_f(\sqrt{\epsilon}),N\_g(\sqrt{\epsilon})\right),$$ where $N\_f(\sqrt{\epsilon})$ and $N\_g(\sqrt{\epsilon})$ are constants that make (1) and (2) true for $\sqrt{\epsilon}$. It follows that $$ \sqrt{\epsilon} \> \frac{|g(n)|}{|h(n)|} \> \frac{(1/\sqrt{\epsilon})|f(n)|}{|h(n)|}, $$ and therefore $|f(n)| \leq \epsilon |h(n)|$, as required.

---
Tags: asymptotics, check-my-proof
---


title: A variant of the Assignment Problem

text:
# Question
Title: A variant of the Assignment Problem
In my variant of the assignment problem I have a set $A$ of agents and a set (of possibly different cardinality) $T$ of tasks. Each agent needs to be assigned exactly $n$ or $n+1$ tasks, and each task needs to be assigned to exactly $m$ or $m+1$ agents.

It is guaranteed this this is possible: the segment $\left\[ |A|n, |A|(n+1) \right\]$ intersects the segment $\left\[ |B|m, |B|(m+1) \right\]$.

Each agent-task combination yields a profit, and I want to maximize the profit.

Is this a special case of one of the known problems? How can this be solved? If not practical for n=100,000, what are good approximations and what is their complexity?

<sub> Not a comp.scientist, but have done the basic research. Please excuse me if I've overlooked anything obvious. </sub>

# Answer
This can be formulated as an instance of min-cost (or in this case, max-profit) flow.

Set up a network as follows. There will be four layers.

The first layer is a single node we call the source. The next layer consists of a node for each agent. The next layer has a node for each task. The final layer is one node we call the sink. For each edge, we give a capacity and a profit. The min-cost flow algorithm can be used to find the flow through this graph that produces the greatest profit.

For each agent, we create two edges connecting the source to that agent, one having capacity $n$ and large profit; the other having capacity 1 and profit 0.

We connect each task to the sink with two edges, one having capacity $m$ and large profit; the other having capacity 1 and profit 0.

We connect every agent to every task, with an edge having capacity 1 and profit given by the agent-task combination.

We now use a min-cost flow algorithm to find the optimum flow. Because the min-cost flow problem has an integrality property, the flow on each agent-task edge will either be 0 or 1. This gives the assignment of the agents to their tasks.

Because the profit on the source-agent edges with capacity $n$ is large, the optimal solution will always use these, ensuring that every agent has at least $n$ tasks. Because the other source-agent edge has capacity 1 (and profit 0), each agent can have at most $n+1$ tasks. Similarly, each task is assigned to either $m$ or $m+1$ agents.

The min-cost flow algorithm won't be practical if each agent needs $100,000$ tasks, though. Is that really what you meant by $n=100,000$? How many tasks and how many agents?
> 6 votes

# Answer
(Partial answer/Too long for comment) Note that if $|T| \neq |A|$, we can introduce dummy tasks or agents carrying zero profit, and make the cardinalities equal. Let $t\_d,a\_d$ be respectively the number of dummy tasks and agents. Suppose now that the tasks are $T\_1,\ldots T\_s$ and the agents are $A\_1,\ldots,A\_s$. Let $\mathtt{assign}(T\_i,A\_j)$ be a boolean function which outputs $1$ iff $T\_i$ is assigned to $A\_j$ (and conversely). We need to maximize the profit:

$P = \sum\_{i,j} \mathtt{assign}(T\_i,A\_j) \cdot \mathtt{profit}(T\_i,A\_j)$

where the $\mathtt{profit}$ matrix is known. The constraints on the agents and tasks imply:

$$ \forall j:\sum\_{1\leq i \leq s} \mathtt{assign}(T\_i,A\_j) \in \\{n+a\_d,n+1+a\_d\\}; \\ \forall i:\sum\_{1\leq j \leq s} \mathtt{assign} (T\_i,A\_j) \in \\{m+t\_d,m+1+t\_d\\} $$

This is equivalent to constraining the $\mathtt{assign}$ matrix to have row and column sums within those ranges. I take it that $m,n$ are arbitrary integers.

Clearly the problem is an integer programming problem , somewhat like the Matching or Job Assignment problem. My guess is that the constraints make the problem NP-hard. Approximations would involve replacing the above constraints with something like: $ \forall j: \sum\_{1\leq i \leq s} \mathtt{assign}(T\_i,A\_j) \leq n+1+a\_d$

and similarly for the $i$'s. HTH.
> 1 votes

---
Tags: optimization, linear-programming, assignment-problem
---


# Question
Title: What does 'computable in the limit from above' mean?
$H(x)$ is the program size complexity of $x$ for some universal Turing machine $U$. $H$ is not computable, however $H$ is "*computable in the limit from above*".

From my notes:

> i.e the set $\\{(x,n) \mid x \in B^\*,n \geq 0, H(x) \leq n\\}$ is computably enumerable.

Can someone tell me what this means? I understand the incomputability of $H$ but the term "limit from above" is confusing me.

# Answer
To quote Wikipedia/Scholarpedia,

> A partial function $f$ from the rational numbers to the real numbers is **upper semicomputable** if it is defined by a rational-valued partial computable function $\phi(x,k)$ with $x$ a rational number and $k$ a nonnegative integer such that $\phi(x,k+1)≤ϕ(x,k)$ for every $k$ and $\lim\_{k \to \infty}\phi(x,k)=f(x)$. This means that $f$ can be computably approximated from above.

Further, using the squeeze theorem, we could conclude:

> If a function $f$ is both upper semicomputable and lower semicomputable on its domain, then we call $f$ **computable**
> 2 votes

---
Tags: computability, terminology
---


title: Assignment problem for multiple days

text:
# Question
Title: Assignment problem for multiple days
I have a problem that can be reduced to an assignment problem. (In a previous question i found out how to do that.)

Which means we have a set $A$ of agents and a set $T$ of tasks as well as a cost function $c(i,j)$. We need to find an assignment so that the total cost is minimal.

The hungarian algorithm can find an optimal solution in at least $O(n^4)$. Which sounds good to me.

My new Problem is: There is a given number of days. I have to solve the assignment problem for each day so that **every task is done every day** and **no agent does the same task twice**.

What I have tried: We could run the hungarian algorithm separately for each day and limit the number of possible combinations based on the result of the previous day. But this would get us into trouble at some of the later days, where most likely it will be impossible to find a feasibly solution.

Another idea is to somehow integrate local search to change decisions made at a previous day. But I think we can't rely on this.

The problem instances I have to face will be somewhere around $|A| = |T| = 500$. The cost matrix $C(i,j)$ will have lots of same values (E.g. mostly 1 or infinity, only some 2 or 3). So during the hungarian algorithm there is a lot of space to create different optimal solutions for a single day.

I'd be glad to hear some ideas or advises how to find a good solution for the problem. Thanks in advance.

# Answer
There's a way to this in polynomial time. I'll sketch the algorithm (in reverse order ... do step 2 first and step 1 second).

1. if we can find a set of $nk$ agent-task pairs $(i,j)$ such that each task is in exactly $k$ pairs, each agent is in exactly $k$ pairs, and no pair appears more than once, then we can find $k$ assignments that together cover these $nk$ agent-task pairs. We do this by repeatedly using a maximum bipartite matching algorithm to find a perfect matching in the corresponding bipartite graph, and removing that assignment from the graph. Hall's marriage theorem guarantees we can do this.
2. We can find the minimum-cost set of $nk$ agent-task pairs as in step 1 by using min-cost flow. Consider a network with a source $s$, a sink $t$, and nodes for each of the agents and each of the tasks. Connect the source to each agent with an edge of capacity $k$ and cost $0$. Connect each task to the sink with an edge of capacity $k$ and cost $0$. Now, connect agent $i$ to task $j$ with an edge of capacity $1$ and cost $c(i,j)$. The minimum-cost flow in this network is guaranteed to be integral (because all capacities are integral, and there is a theorem saying that this implies that there is an optimal integral min-cost flow), so the flow on each agent-task edge is $0$ or $1$. The edges $(i,j)$ with flow $1$ form the set of pairs in step 1.

There are lots of algorithms that can solve min-cost flow; it's a special case of linear programming. For your size problem, the algorithm I sketch should not just be polynomial-time, but also practical.
> 6 votes

---
Tags: algorithms, graphs, assignment-problem
---


title: Does Subset Sum allow multisets?

text:
# Question
Title: Does Subset Sum allow multisets?
In the Subset Sum problem can some of the given numbers $a\_1,a\_2,a\_3,\dots,a\_n$ be the same? For example, we might have $\[1,1,1,2,3,4\]$ and the target is $5$? Can I assume that I have a specific solution with numbers $2$ and $3$ and $1,1,1$ and $2$ is not?

# Answer
One question we could ask is "Can we reduce this back to the subset sum problem?" In this case, the answer is **yes**: for each duplicate $z$ we replace it with two numbers $x$ and $y$ such that $x+y=z$. $$\[-1,-1,2,3\]\to \[-7,-1,2,3,6\]$$

However, we need to be careful that we don't introduce additional solutions (those using just $x$ without $y$), which we can do by making $x\>\lvert \Sigma(a\_i)\rvert$ for $a\_i\<0\in A$, and $y\<-\lvert\Sigma(a\_i)\rvert$ for $a\_i\>0 \in A$. Specifically, this precludes the use of $x$ without $y$ (and vice versa) by making the sum of $x$ and all negative numbers strictly above zero (and thus doesn't satisfy the traditional subset sum problem).
> 10 votes

---
Tags: complexity-theory, terminology
---


title: Mixed-strategy Nash equilibria

text:
# Question
Title: Mixed-strategy Nash equilibria
Is the following statement always true:

> if there is a mixed-strategy Nash equilibria then it is unique.

I know that there can be several pure strategy Nash equilibrias.

# Answer
> **Shameless Advertisement:** Game Theory proposal on Area 51 that you should totally follow!

**No**. The easiest way to prove this is by counterexample. Expanding matching pennies, we can create a game with two mixed strategies (players either mix between A and B or between C and D):

What *might* be true about that statement is for a mix of particular pure strategies for two players, there is a unique mixed strategy equilibrium. This presumes that there is a threshold after which you switch from using strategy $0$ to strategy $1$. At this threshold, your opponent is ambivalent between her strategies. As depicted below, the intersection (and hence mix) will be unique.
> 4 votes

---
Tags: game-theory
---


# Question
Title: Proving following problem NP Hard using known NP Hard partition problem
Least cost travel by intermixing different airline routes having linear discount functions:

Lowest air fare route chosen by mixing different routes provided by different airline having different discount functions (like some airline can give 25% discount if fare crosses $5k) so that total cost of travel is minimized after intermixing of different airline routes

This is a graph problem. Let $E(k)$ be the set of edges/routes flown by $k$-th airline, also given cost of travel associated with each edge.

For $n$ airlines we have $n$ sets of edges i.e $E(k)=\\{\mbox{some edges}\\}$ for all $k=1.. n$. We need to find the route from given source $s$ to given destination $t$ such that we end up paying least fare among all possible routes. There is no restriction on number of edges in a route.

This is an NP-hard problem. How can I prove it?

# Answer
Assuming that an "airport" cannot be visited more than once, you can reduce HAMILTONIAN PATH to your problem: given a graph $G = (V,E)$, $|V|=n$; suppose that there are two airlines such that $E(1)=E(2)=E$ (i.e. both airlines cover all edges). Then set the price of each edge = $1$. One of the two companies gives no discount, the other gives a (big) discount $d$% (such that $n - \frac{n * d}{100} \< 1$) if the cost of the travel is $\geq n$.

Then $G$ has an Hamiltonian path from $s$ to $t$ if and only if the minimum cost of the travel is $\< 1$ (i.e. the airline which gives the discount is more convenient).

Note: if an airport can be visited more than once I think that the problem is no more NP-hard (but I didn't think of it too much). In this case a modified version of a shortest path algorithm should work: just augment the shortest path traversing multiple times an edge of each airline and check if the total cost decreases after reaching the discount treshold.
> 3 votes

---
Tags: complexity-theory, graphs
---


# Question
Title: Average number of full nodes in a binary search tree
> Let $f(N)$ be the average number of full nodes (nodes with two children) in an $N$-node binary search tree.
>
> 1. Determine the values of $f(0)$ and $f(1)$.
> 2. Given that for $N \> 1$,
>
> $\qquad \displaystyle f(N) = \frac{N-2}{N} + \frac{1}{N} \sum\_{i=0}^{N-1} \[f(i) + f(N - i - 1)\]$,
>
> show that $f(N) = \frac{N - 2}{3}$.
> 3. Using this information, show that the average number of nodes with one child in a binary search tree is $\frac{N + 1}{3}$.

I know that for (1) both values are $0$. I mainly need help proving (2). I also found some hints for (2) and (3) but I can't figure it out:

(2) The root contributes $\frac{N − 2}{N}$ full nodes on average, because the root is full as long as it does not contain the largest or smallest item. The remainder of the equation is the expected contribution of the subtrees.

(3) The average number of leaves is $\frac{N + 1}{3}$.

Any help would be appreciated, even just pointing me in the right direction. Thanks!

# Answer
As the both the formula itself is given $f(n) = \frac{n-2}{3}$ as well as the inductive structure $f(n) = \frac{n-2}{n} + \frac1n \sum\_{i=0}^{n-1}{\dots}$, it seems you are requested to show the formula by (mathematical) induction. Hint (2) only explains the formula.

Inductively you apply the formula for $f(k), k\<n$ in the recursive expression and conclude that it also holds for $f(n)$. I can do that, but run into trouble. The formulas do not match.

Summing $f(i) + f(n-i-1)$ is easy, as it is equal to $\frac{i-2}3 + \frac{n-i-1-2}3 = \frac{n-5}3$, so the $i$'s cancel. Plugging it into the recursion yields $\frac{n-2}{n} + \frac nn \frac{n-5}3$ which is *not* the expected $\frac{n-2}{3}$.

**edit:** The first values of $f$ however are special. $f(0) = f(1) = 0$, where the formule $\frac {n-2}3$ predicts $\frac {-2}3$ and $\frac {-1}3$ respectively. Thus we have to *correct* this within the summation, twice as it occurs in both $i=0,1$ and $i=n-1,n$, and add $\frac 2n$. Amazingly, that works.

Part (3) just expects you to know what is the relation between the numbers of full nodes and leaves in a binary tree.
> 2 votes

---
Tags: data-structures, combinatorics, recurrence-relation, binary-trees
---


# Question
Title: How can we reduce variables when converting from 3-SAT to 4-SAT?
If we suppose that we'd like to convert an instance of 3-SAT to an instance of 4-SAT, by how much can we reduce the amount of variables?

**CONVERSION METHODS FOR PRODUCTS OF SUMS**

If we are given a 3-SAT clause $(A \lor B \lor C)$, we can readily convert this to 4-SAT by rewriting it as $(A \lor B \lor C \lor x) \land (A \lor B \lor C \lor \overline{x})$, where $x$ is a free variable. In other words, $x$ can be any one of the existing variables, or a completely new variable. This entails that we can gaurantee that 3-SAT can be converted to 4-SAT without adding any new variables.

Additionally, we can convert 3-SAT into 4-SAT and eliminate one variable, given a special set of clauses. The 3-SAT clauses

$$(x \lor B \lor D) \land (\overline{A} \lor \overline{C} \lor x) \land (A \lor C \lor \overline{x}) \land (A \lor \overline{C} \lor x) \land (\overline{A} \lor C \lor x)$$

readily "reduce" to $(A \lor B \lor C \lor D)$. This eliminates the free variable $x$, assuming it only appears in these clauses, and also greatly reduces the number of clauses. The significance of this is that we may be able to eliminate some variables using this technique.

**THE MAIN QUESTION**

What are some other techniques for reducing the number of variables when converting from 3-SAT to 4-SAT?

Note that converting from product-of-sums to sum-of-products form may also be useful.

# Answer
> 2 votes
The paper Effective Preprocessing in SAT through Variable and Clause Elimination covers the variable elimination techniques used in Minisat. Broadly, variables can be eliminated by

1. Substitution, in which a variable to be removed is defined in terms of other variables in the formula and the definition is substituted everywhere in place of the variable. Automatic Extraction of Functional Dependencies describes how to efficiently find (some of) these variable definitions.
2. Distribution, in which all clauses containing a negated literal of $x$ are resolved against all clauses containing a positive literal of $x$. The produced resolvents are kept (minus any tautological clauses) and the original clauses containing $x$ are discarded. The resulting formula is satisfiable iff the original formula was satisfiable.

The overall goal of the techniques described in the Minisat paper is to optimize the formula for exploration by a CDCL solver by reducing the total number of clauses and strengthening (decreasing the length of) the clauses that remain. You could of course (with exponential effort) eliminate all the variables, eliminating all the clauses as well if the formula was satifiable or leaving one or more empty clauses if formula was unsatisfiable.

---
Tags: satisfiability, 3-sat
---


# Question
Title: What units should Shannon entropy be measured in?
The only examples I've seen use bits as a measurement of entropy, but all these examples happen to use binary code alphabets. If we wanted to see how well a coding with a code alphabet of length n works, would we measure entropy in units of n?

Or would it make sense to stay using bits if we're comparing codings with binary and n-length code alphabets?

# Answer
Generally bit was introduced by Shannon in 1948. Using bit instead of any other information measurement unit it's because of convenience any information can be represented by single bit or by set of bits.

I bet you already ran into most popular example which is coin tossing. You can represent head as *1* and tails as *0*. You can also use stream of bits as representing more complex information as integer.

> **Simple example**
>
> Consider *W* as information about current week day you might use 7bit length stream as representation of week. Eg Monday would be represented as 1000000 and Wednesday as 0010000. So each bit in stream represents one day.

You should always consider domain for your problem and use bit encoding which fits best. Using code alphabet of length n shows universality of that particular encoding (like ASCII or Unicode).

Another thing is that bit can be efficently represented in low powered (5v) circuits. There exists interference detection and fixing functions for such circuits.

Consider domain different then bit, eg real numbers, and let them represent information using some relation R. Now because real numbers are dense even minimal interference will have impact on end result.
> 1 votes

---
Tags: information-theory, entropy
---


# Question
Title: Minimum space needed to sort a stream of integers
This question has gotten a lot of attention on SO:
Sorting 1 million 8-digit numbers in 1MB of RAM

The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $\[0,\\: 99\mathord{,}999\mathord{,}999\]$) using only 1 MB of memory ($2^{20}$ bytes = $2^{23}$ bits) and no external storage. The program must read values from an input stream and write the sorted result to an output stream.

Obviously the entire input can't fit into memory, but clearly the result can be represented in under 1 MB since $2^{23} \geq \log\_2 \binom{10^8}{10^6} \approx 8079302$ (it's a tight fit).

So, what is the minimum amount of space needed to sort n integers with duplicates in this streaming manner, and is there an algorithm to accomplish the specified task?

# Answer
Ok, it's way past my bedtime, but this won't let me go, so here's a second try (deleted my first)...

Before going into the specifics of how to sort the numbers, I will start by representing them not as a sequence of integers $i\_1, i\_2, \dots , i\_n$, but as a sequence of their differences, i.e. $\delta\_k = i\_k - i\_{k-1}$ where, by convention, $i\_0 = 0$.

Then, in order to represent these values, I will first group them into buckets depending on the number of bits needed for their representation, with the assumption that I need one bit to represent `0`. Since the numbers are between 0 and 99'999'999, I will need 27 buckets.

For each bucket, I will choose a prefix from the set `1`, `01`, `001`, `0001`, etc... Up to `000000000000000000000000001`. Obviously, I will choose the shortest prefix for the largest bucket, the second-shortest for the second largest, etc...

The sequence of $\delta\_k$ can then be written as pairs of prefixes and values, whereby for the values $\>1$, the leading bit can be omitted.

For any random set of numbers, then, how many bits do I need to represent the sequence of $\delta\_k$?

For a constant sequence, e.g. $0, 0, 0, 0, \dots , 0$, I only have to store one million representations of the number $0$, or with the above encoding, `10`, hence 2 million bits. For any other constant, it would be 2 million bits plus the number of bits of that value for the initial $\delta\_1$.

The same computation goes for an increasing sequence, e.g. $0, 1, 2, 3, \dots , n$, where $\delta\_k=1$ and the sequence is represented as a million copies of `11`.

Now what is the worst-case, i.e. what sequence of $\delta\_k$ will give the longest sequence of bits? The worst we can do is make sure that each bucket has one entry less than the previous one, choosing the smallest $\delta\_k$ possible, thus assigning the largest prefix to the longest sequences. For simplicity, I'll assume that $K$ buckets have the same amount of entries, with the shortest prefix assigned to the shortest sequence. This means that we have $n$ ones, $n$ twos, $n$ fours, etc... To represent the $j$th bucket, we need $2j-1$ bits, except for the first bucket, that needs $2$ bits.

So if we put $m$ $\delta\_k$s into each of the $K$ buckets, we need $m\left(2 + \sum\_{j=2}^{K}2j-1\right) = m(K^2 + 1)$ bits. However, the sum of all the $\delta\_k$ must not exceed 99'999'999. This sum, assuming we've kept the $\delta\_k$ as small as possible, is $m\sum\_{j=2}^{K}2^{j-1} = m(2^K-2)$.

So here's the question: is there a combination of $K$ and $m$ such that

* $m(2^K-2) \< 100'000'000$, e.g. the largest value is $\<100\\,000\\,000$,
* $Km \< 1'000'000$, e.g. there are at most a million values, and
* $m(K^2+1) \> 8'000'000$, e.g. we use more than $8\\,000\\,000$ bits?

Unfortunately, this does happen. Here's a plot of the number of bits as computed in Maple with `plot( min( 100000000/(2^K-2) , 1000000/K ) * (K^2 + 1) , K=2..27 )`:

So we can represent any sequence of up to one million numbers in $\[0,99\\,999\\,999\]$ using roughly 10 million bits. This is, unfortunately, still above the specification.

But how can we sort numbers like this? Well, remember that the numbers come in one by one, so as each number comes in, we update its bucket count ($\mathcal O(1)$) and compute the new optimal prefixes for each bucket ($\mathcal O(\log\log(i\_\mathsf{max}))$ if the buckets are indexed in a heap). We then run through our encoded $\delta\_k$, reading each entry, computing the respective $i\_k$ from the cumulative sum, and comparing it to the new value. If the computed $i\_k$ exceeds the new value, we encode the new value and write it back, along with the adjusted $\delta\_k$, using the new encoding. Otherwise, we just write back the $\delta\_k$ with the new encoding.

But write-back where? Well, if we treat our eight million bits as one large ring buffer, we can append the new, re-coded sequence of $\delta\_k$ to the old sequence, re-writing the old values as we go along. We've got almost 1 million extra bits from the worse-case scenario, and I don't think the re-coding can cause that amount of stretching to make this not work.

All in all, this leaves us with a $\mathcal O(n)$ cost for inserting the $n$th number, which gives us an average-case cost of $\mathcal O(N^2)$ for a total of $N$ elements. This isn't really good, but speed did not seem to be a criteria.
> 5 votes

---
Tags: algorithms, sorting, space-complexity, data-compression, streaming-algorithm
---


# Question
Title: Rényi entropy at infinity or min-entropy
I'm reading a paper that refers to the limit as n goes to infinity of Rényi entropy. It defines it as ${{H}\_{n}}\left( X \right)=\dfrac{1}{1-n} \log\_2 \left( \sum\limits\_{i=1}^{N}{p\_{i}^{n}} \right)$. It then says that the limit as $n\to \infty $ is $-\log\_2 \left( p\_1 \right)$. I saw another article that uses the maximum of the ${{p}\_{i}}'s$ instead of ${{p}\_{1}}$. I think that this works out fairly easily if all of the ${{p}\_{i}}'s$ are equal (a uniform distribution). I have no idea how to prove this for anything other than a uniform distribution. Can anyone show me how it's done?

# Answer
> 8 votes
Suppose $p\_1 = \max\_i p\_i$. We have $$ p\_1^n \leq \sum\_{i=1}^N p\_i^n \leq N p\_1^n. $$ Therefore $$ \frac{n \log p\_1 + \log N}{1-n} \leq H\_n(X) \leq \frac{n \log p\_1}{1-n}. $$ As $n \rightarrow \infty$, $\log N/(1-n) \rightarrow 0$ while $n/(1-n) \rightarrow -1$.

---
Tags: information-theory, entropy
---


# Question
Title: In the Miller-Rabin primality test, for a composite number, why are at least $\frac{3}{4}$ of the bases witnesses of compositeness?
The following is an excerpt from the Wikipedia article on the Miller-Rabin primality test:

> It can be shown that for any odd composite $n$, at least $\frac{3}{4}$ of the bases $a$ are witnesses for the compositeness of $n$.

In the Fermat primality test, if $n$ is not a Carmichael number, at least half of the bases $a$ are Fermat witnesses. Testing for non-trivial roots in the Miller-Rabin primality test however increases the minimum number of witnesses to $\frac{3}{4}$.

# Answer
> 12 votes
Here are the three tests you're (implicitly) considering:

* Fermat: test whether $a^{n-1} \equiv 1 \pmod{n}$
* Solovay-Strassen: test whether $a^{(n-1)/2} \equiv \left( \dfrac{a}{n} \right) \pmod{n}$ (where $\left( \dfrac{a}{n} \right)$ is a Jacobi symbol, which can be calculated using quadratic reciprocity via a GCD-like algorithm)
* Miller-Rabin: suppose $n-1 = 2^k m$. Test whether the list $a^m,a^{2m},\ldots,a^{2^km} \pmod{n}$ consists of a (possibly empty) string of $-1$s followed by a string of $1$s

Each test is stronger than the previous one: if $a$ passes Fermat's test, it will satisfy Solovay-Strassen, and if it passes Solovay-Strassen then it passes Miller-Rabin. In the first two tests, the set of $a$ which pass the test form a group. Therefore, unless all $a$s pass the test, at most half of them do. For Solovay-Strassen, one can show that if $n$ is composite, then *some* $a$ (which can be constructed explicitly) doesn't pass the test.

For Miller-Rabin, the argument is more complicated. The most difficult case turns out to be $n = pq$, where $p,q$ are different primes. The argument uses the Chinese Remainder Theorem to consider what happens modulo $p$ and modulo $q$ separately. For $a$ to pass the test, it must behave in exactly the same way under both primes, and that's the intuitive reason that makes it harder to pass the test. For a proof, check Schoof's paper, for example.

---
Tags: cryptography, number-theory
---


# Question
Title: Source entropy and other questions related to information theory
Kolmogorov-Sinai entropy (KS) explains the mathematical concept behind KS entropy.

$$h ( T ) =\sup\limits\_{\xi} \\, h ( T , \xi )$$

defines the formula for KS where the left-hand side is nothing but the Shannon's entropy. In many papers I have seen that KS is defined as the supremum over source entropy. These conflicting views raises the following questions

1. What is the difference between Shannon's entropy and source entropy (source entropy given by $\lim \frac{1}{n}\cdot h(T)$ where $n$ is the length of the word or sequence,unsure though).
2. Would source entropy be the entropy of the raw signal before it has been quantized or should it be that of the quantized?
3. Is 'n' the length of the data series or the number of quantization levels\>
4. Topological entropy (TS) explains topological entropy whose formula looks exactly as KS. So, what is the difference since KS is also known as metric entropy and not known as Topological entropy?

# Answer
If you look at wikipedia you see that *topological entropy* is modeled after *Kolmogorov-Sinai (KS)* entropy, but it is defined without reference to a probability measure $\mu$ on the space.

For KS entropy, you need to use Shannon entropy: $-\sum\_i\mu(X\_i) \log \mu(X\_i)$ for some partition of the space $\\{X\_i\\}$, which can only be defined if you have some probability measure $\mu$ on your space, while topological entropy is defined without reference to a probability measure.

Since putting different probability measures on the space will give different KS entropies, while not affecting the topological entropy, these entropies are different. However, they are related by the theorem that the topological entropy is the supremum of the Kolmogorov-Sinai entropy over all probability measures $\mu$.
> 6 votes

---
Tags: reference-request, information-theory, entropy
---


# Question
Title: Constructing a tree from disjoint graphs
I will preface my question with the definition of a simple tree that applies to my question:

> A simple tree is an undirected and connected graph with no cycles.

I am having difficulty coming up with a compelling argument that a tree of the above definition can be constructed by taking a set of disjoint valid graphs and adding a vertex between each of them. The practice problem states:

> Prove that some graph $G$ is a tree if and only if it can be constructed from a set $X\_1, X\_2, \dots, X\_i$ of disjoint valid graphs by adding a new node adjacent to one node from each of $X\_1,\dots, X\_i$. A single node is a valid graph.

I'm confused whether this question is asking me to prove that two graphs, or trees ("valid"), can be made into one tree by adding a node and adding edges from one preexisting node from each of the trees. If that is how the question should be interpreted, then is it enough to prove that the new tree (or "graph," I guess) has no cycles, and is connected?

I'm new to graph theory and I'm wondering if you can help me understand it.

# Answer
The reverse direction is relatively straight forward, as we start with disjoint vertices, and at each step only add edges to a *new* vertex, we cannot introduce a cycle, furthermore at each step we connect the "graph so far", so we finish with a connected graph.

For the forward direction, we just need to consider how we could construct a tree in such a manner. The key observation being that a subtree is also a tree. Thus we can recursively break down a tree (the construction is then a series of applications of adding a new node and some edges) by picking a vertex in the tree, and taking each of its subtrees as the sets $X\_{1},X\_{2},\ldots$. Each of these is a tree (and hence "valid"), so we can construct them in the same manner. Eventually we reach a set of leaves (individual vertices) which are by definition "valid".

The diagram gives a little sketch of this, with the "valid" components $X\_{1}$, $X\_{2}$ and $X\_{3}$ all representing trees, with a new vertex added, and a single edge from each component to this new vertex.
> 3 votes

---
Tags: graphs, trees
---


# Question
Title: Constructing deterministic PDA for not regular language
Let the input alphabet be $\Sigma = \\{a,b,c\\}$ and *L* be the language of all words in which all of the *a*’s come before all of the *b*’s and there are the same number of *a*’s as *b*'s and arbitrarily many *c*’s that can be in front, behind or among the *a*’s and *b*’s. Some words in *L* are: *abc ccacaabcccbccbc*

I know that the language is not regular but how can I find a deterministic PDA (in a drawing fashion) that accepts *L*?

Edit: So far I've ended up with this which takes care of having the same number of a's as b's and all a's come before all b's. However I cannot figure out how to account for the arbitrary amount of c's in-between b's. Any ideas?

Sorry for the horrible drawing in advance.

# Answer
Recipe in shorthand. Ignore $c$'s. Use a bottom fo stack symbol $Z$ that stays there. Keep the surplus of $a$'s on the stack. So $ZAAA$ (top of stack right) means three $a$'s more than $b$'s. If we read another $a$ push $A$, if we read another $b$ pop an $A$ (and move to another state to indicate we have now seen $b$).
> 2 votes

# Answer
Your diagram looks like you have the correct answer. Just for comparison:

Somewhat overannotated, but I don't think I've missed anything. As best I can tell, your diagram expresses the same idea.
> 2 votes

# Answer
Perhaps this diagram will explain in a clear manner

Simply put,

```
When you start, put a $ symbol as starting marker. Now, if you see c dont do anything.

If you see a put a symbol into your stack. Go on doing this till you see b.

Once you see b pop out the a symbol from the stack. (just like before if you see c dont do anything).

Once you reach the end of input, see if the stack is empty (by checking our $ marker). If yes, accept the string. Else reject.

```
> 1 votes

---
Tags: automata, pushdown-automata
---


# Question
Title: Ray Tracing versus object-based rendering?
Intro graphics courses usually have a project that asks you to build a ray tracer to render a scene. Many graphics students entering grad school say that they want to work on ray tracing. And yet it seems that ray tracing is a dead field in venues like SIGGRAPH etc.

Is ray tracing really the *best* way to render a scene accurately with all desired illumination etc, and is it just the slow (read non-interactive) performance of ray tracers that makes them uninteresting, or is there something else ?

# Answer
Raytracing is a very nice and intuitive algorithm, and it is a more physically realistic way of describing the illumination of a scene than rasterization, but:

* Raytracing is slow, specially if you want to implement the more realistic effects that distinguish it from rasterization (e.g. refraction, reflection, motion blur, soft shadows) because this implies creating a lot more rays per pixel.
* Most people can't tell the difference between real and fake effects, which I think is the key point. The goal of a practical rendering algorithm is to create a photorealistic representation of a scene in the most efficient way, and right now Rasterization, although uses a lot of hacks, accomplishes this very well.
* There are many other practical limitations of Raytracing compared to a Rasterization renderer: poor anti-aliasing and displacement mapping, limited instancing, etc.

Even in non-interactive applications, such as movies, Raytracing is used very little becasue of its limitations. Pixar only started using Raytracing in Cars, and only for some specific reflection effects (Ray Tracing for the Movie ‘Cars’).

Here is an excellent article that describes in more detail the current state of Raytracing and its advantages and disadvantages: State of Ray Tracing (in games).
> 12 votes

# Answer
Basic ray tracing has a major problem related to ambient light. Most illumination models treat ambient light as a constant factor pervading the ether. While ray tracing is great for computing reflections, it suffers from numerical instability and complicated surface intersection tests. Ray tracing may not play nicely with hardware accelerated rendering since recursion plays a major roll in determining the illumination for any particular pixel. Basic ray tracing is computationally very expensive.

Radiosity handles ambient light better in that it treats all objects in the environment as light sources, producing a lighting model that is in some way more realistic than ray tracing. With a radiosity solution there are a fixed number of polygons in a scene, and the computation is amenable to hardware acceleration.

Ultimately ray trancing is not best way to render a scene, but it is a component of a good rendering strategy. The high cost computational cost and poor ambient lighting are major strikes against ray tracing. As a research topic work is ongoing, but seems to be focussed on hardware acceleration.
> 8 votes

# Answer
I wouldn't say that ray-tracing/path-tracing is dead ... if anything, there's been quite a resurgence of popular interest in the field due to the inherent parallelism of the many associated algorithms in this area combined with the speed of GPU-based systems that are allowing for millions of rays to be calculated per-second. Added to that is the flexibility in the rendering pipeline that more generic languages such as CUDA and OpenCL are enabling that allow developers to leverage the parallel functionality of the GPU without having to explicitly use the OpenGL graphics pipeline like initial GPGPU techniques. Some notable main-stream examples of continued path-tracing research include:

* The research of Daniel Pohl and others in the Intel Advanced Render group
* Nvidia's Optix engine
* SIGGRAPH this past year included a couple courses on Monte Carlo image synthesis as well as discussion on the latest in photon density estimation techniques.

Finally, you have a lot of researching going into optimization techniques for the global illumination problem, including point-based global illumination, Photon Mapping and related optimizations, advanced appearance modeling (including data-driven methods), irradiance caching, etc., etc.
> 4 votes

---
Tags: graphics
---


# Question
Title: How to prove or disprove that f is computable?
If $f(x\_1,\dots, x\_n)$ is a total function that for some constant $K$, $f(x\_1,\dots, x\_n) \leq K$ for all $x\_1,\dots, x\_n$ then $f$ is computable.

I want some hints on how to prove/disprove the above claim. This an exercise from the book Computability, Complexity, and Languages. As I didn't find the solutions to the exercises online, I want to see a formal solution of such problems, if possible.

# Answer
Define the function $f: \mathbb{N} \to \\{0,1\\}$ as follows. Let $f(x) = 1$ if turing machine $x$ halts on itself as input and $f(x) = 0$ otherwise. Then for all $x$, we have that $f(x) \leq 1$. Yet, if $f$ is computable, then the Halting problem should be decidable.
> 4 votes

---
Tags: computability, proof-techniques
---