title: Survey of informed search algorithms?

text:
# Question
Title: Survey of informed search algorithms?
I'm looking for a list of informed search algorithms, also known as heuristic search algorithms.

I'm aware of:

1. best-first search

Are there more best-first algorithm or other informed searches that are not best-first?

# Answer
That list would be endless ... I will just try to provide a number of representative examples according to different criteria:

**Best-first search** (BFS): they are *complete*, i.e., they are guaranteed to find a solution provided that one exists and they are *admissible*, i.e., they are guaranteed to find the optimal solution provided, again, that one exists. However, they take memory exponentially in the depth of the search tree. Other than **Greedy best-first search** and **A$^\*$**, **pure heuristic search** ($f(n)=h(n)$) is often quoted as another BFS algorithm

**Depth-first search** (DFS): they are not *complete*, and thus they are not *admissible*. However, running a sequence of depth-first searches with a threshold that increases monotonically is guaranteed both to be complete and admissible while it takes memory just linear in the depth of the search tree. The most prominent member in this class would be **IDA$^\*$**. However, this is not the only way to guarantee both completeness and admissibility and **Depth-First Bround-and-Bound** (DFBnB) takes also memory which is linear in the depth of the search tree.

**Bidirectional Search** (BS): It has been observed that BS saves an exponential amount of time and memory in the case of blind (non-heuristic) search. Many efforts have been invested to reproduce the same result when using heuristic search but it is still an open question how to implement bidirectional search efficiently when using heuristics. James Kwa showed that **BS\*** does not always expand less nodes than a single A$^\*$ and Ariel Felner et al. have recently suggested **Single-Frontier Bidirectional Search** as a way to turn bidirectional search into a unidirectional search.

**Perimeter Search** (PS): while most people was considering that bidirectional search consists of two searches progressing simultaneously (either in front-to-front or front-to-end fashion), Giovanni Manzini and also Nelson and Dillemburg simultaneously and independently suggested to develop a perimeter around the target node $t$ and then to issue a unidirectional search from the start state $s$. The resulting algorithm is better known as Bidirectional Iterative-Deepening A\* BIDA$^\*$

**Real-Time Search** (RTS): in most cases the search is conducted off-line, i.e., the solution is seeked and as once it is found, it is executed. Korf (again) showed that this is not necessarily a limitation and was the first in introducing **Real-Time Search** for looking for the solution while the agent is moving. The same algorithm was improved and it is known as **Learning Real-Time Search**. This work started a branch of research which is continued even nowadays and you can find a myriad of algorithms to solve problems in Real-Time search. Very importantly also, this category of algorithms was devised taking minimax as a motif where decisions are taken without ever visiting a goal node. This is, these algorithms are also expected to solve problems which are unsolvable with the previous algorithms.

**Moving-Target Search**: somehow related to the previous case, but not exactly equal is the case of seeking a moving target while the agent is moving. Originally (as far as I know) Ishida and Korf (get in use to hear from Korf ;) ) suggested an algorithm called exactly like this Moving-Target Search. Ishida continued the work later and some work has been presented in recent years.

**Sub-optimal search**: most of the algorithms described above (all but RTS) are used to find optimal solutions. However, some algorithms are "extended" to find sub-optimal solutions with guarantees on the error margin. For example, Ira Pohl introduced weighted-A\* WA$^\*$ which is known to find solutions with a bounded error. There are also a lot of research in this category and one of my favourite algorithms (among others) is $A\_{\epsilon}$

But bear in mind that these are just only a number of prominent examles. The list of algorithms is huge and even the list of categories is quite large (though not impossible to get, of course).

Cheers,
> 7 votes

# Answer
**breadth-first search (BFS):** is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on
**Depth-first search (DFS)** is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking.

**Bidirectional search** is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph. It runs two simultaneous searches: one forward from the initial state, and one backward from the goal, stopping when the two meet in the middle. The reason for this approach is that in many cases it is faster: for instance, in a simplified model of search problem complexity in which both searches expand a tree with branching factor $b$, and the distance from start to goal is $d$, each of the two searches has complexity $O(bd/2)$ (in Big O notation), and the sum of these two search times is much less than the $O(bd)$ complexity that would result from a single search from the beginning to the goal.

As in A\* search, bi-directional search can be guided by a heuristic estimate of the remaining distance to the goal (in the forward tree) or from the start (in the backward tree).
> 3 votes

---
Tags: algorithms, reference-request, artificial-intelligence, search-algorithms
---


# Question
Title: Clarifications on polynomial reducibility for problems in P and NP-complete
**Can I always increase the complexity of a problem via polynomial reduction?** (in which case '*reduction*' is really a misnomer) For example, if I have a classic P problem (say, finding the smallest element in an array, by iterating through and making comparisons with the smallest value found thus far), what would be a corresponding problem in NP-complete (obtained via polynomial reduction)? Or, would it be possible to polynomially reduce a constant time (worst case) algorithm into a polynomial time algorithm (basically performing unnecessary executions for all n of the input for nothing)?

As a side request, I'm looking for a basic reference that deals with how one problem (in P or NP-complete) can be reduced (in polynomial time) to a problem in (P or NP-complete). Most of the things I found online are beyond scope or vague. I'm looking for an easy way to figure out whether a certain Problem A (in P or NP-complete) can be polynomially reduced to a Problem B (in P or NP-complete).

# Answer
> 7 votes
As pointed out by @Vor the point of polynomial-time reductions is to show that if have a reduction from A to B and an algorithm to solve a problem B then you can use it to efficiently (i.e. in polynomial time) solve the problem A. Note that efficiently does not mean optimally, when you reductions, your solutions will not be better than the class your use for reductions (i.e. if you use a polytime reduction to reduce to a constant time language, you still have just a polytime algorithm).

I think what you are getting confused about is that reductions can be used to show that a problem is easy or that it is hard. In this case, they are used in two different ways. Suppose you have some problem X, and

1. you think it is **easy** (i.e. doable in polynomial time). In that case you find your favorite polynomial time problem B (say linear programming) and reduce X to B. Now you have an efficient algorithm for X: run the reduction and then run a polytime LP-solver. On the other hand,
2. you think X is **hard** (i.e. probably not doable in polynomial time). In that case you find your favorite NP-complete problem A (say 3-SAT) and reduce A to X. Now if you had an efficient algorithm for X, you would be able to solve A in polynomial time (reduction, then X). Since we suspect that A *cannot* be solved in polynomial time, this means we have a contradiction, so you cannot have an efficient algorithm for X.

There is no general rule for deciding if a given problem is in P or NP-complete, but we have a list of rules of thumb to help you.

---
Tags: complexity-theory, time-complexity
---


title: Describing Strings

text:
# Question
Title: Describing Strings
Im trying to figure out how to describe fifty-six strings to test if a three state FA over the alphabet $\\{a,b\\}$ has a finite language.

The number fifty-six comes from a theorem that states if a machine has $N$ states and an alphabet has $m$ letters, then in total there are $m^N + m^{N + 1} + m^{N + 2} +\ldots+ m^{2N-1}$ different input strings in the range $N \leq \text{length of string} \< 2N$. Thus $2^3 2^4 2^5 = 56$ strings.

I know that we can test them all by running them on the machine and if any are accepted, the language is infinite, if none are accepted, the language is finite. I'm just not sure how to describe the strings.

# Answer
> 3 votes
The strings are just all strings of lengths $N$ to $2N-1$. In your case:

> 000 001 010 011 100 101 110 111
>
> 0000 0001 0010 0011 0100 0101 0110 0111
>
> 1000 1001 1010 1011 1100 1101 1110 1111
>
> 00000 00001 00010 00011 00100 00101 00110 00111
>
> 01000 01001 01010 01011 01100 01101 01110 01111
>
> 10000 10001 10010 10011 10100 10101 10110 10111
>
> 11000 11001 11010 11011 11100 11101 11110 11111

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


# Question
Title: Has anyone found polynomial algorithm on Hamiltonian cycle isomorphism?
As the title says, has anyone found a polynomial time algorithm for checking whether two graphs having a Hamiltonian cycle are isomorphic? Is this problem NP-complete?

# Answer
> 7 votes
*What follows is taken from Tsuyoshi Ito's comment.*

As rizwanhudda said, this problem is a special case of the graph isomorphism problem and therefore it is not known to be NP-complete. We cannot say “this problem can’t be NP-complete” because of that, because the graph isomorphism problem might be NP-complete. However, many complexity theorists believe that the graph isomorphism problem is not NP-complete (and therefore they will believe that your problem is not NP-complete, either) because the NP-completeness of the graph isomorphism problem would contradict the conjecture called “the polynomial hierarchy does not collapse.”

# Answer
> 4 votes
As suggested by Kaveh, perhaps this is a reduction that can prove that the class of graphs with an Hamiltonian cycle is GI-complete.

Given two graphs $G\_1 = (V\_1,E\_1)$ and $G\_2 = (V\_2,E\_2)$, $|V\_1| = |V\_2|=n$, expand $G\_1$ with a complete graph $K\_{2n}$ labeling its nodes in pairs $(a\_i, b\_i)$; then for each vertex $u\_i \in |V\_1|$ add two edges $(a\_i,u\_i)$ and $(u\_i,b\_i)$ that connect $G\_1$ to the $K\_{2n}$. Expand $G\_2$ in the same way.

By construction the two expanded graphs $G'\_1$ and $G'\_2$ have an Hamiltonian cycle $(a\_1 u\_1 b\_1 a\_2 u\_2 b\_2 ... a\_n u\_n b\_n a\_1)$ and the original graphs are isomorphic iff $G'\_1$ and $G'\_2$ are isomorphic. Informally: in $G'\_1$ and $G'\_2$ the added nodes cannot "interfere" with the original isomorphism because their degree is greater than $\max(\text{deg}(u\_i))$

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


# Question
Title: Does a weighted Breadth First search have "memory" when moving to the next vertex?
I'm in a programming course and one Problem given to us is to mark the order in which BFS visits nodes in a weighted graph.

My question is whether BFS adds the distance of the previous path while adding a new vertex, as that will definitely change the order in which the vertices are added?

# Answer
How about transforming your original graph to a graph with dummy nodes and just use regular BFS on it?

The idea is: if you have an edge with weight $k$ between $A$ and $B$, remove it. Then add a path between $A$ and $B$ with $k-1$ nodes in between, where all the edges have unit weight.

Now you can use regular BFS on your graph and it will reach the nodes in the same order as it would in the weighted version, without you having to transform the algorithm.

Ps. BFS always spreads out evenly, layer for layer like ripples in a pond. So if the next nodes to be added are A, B and C it will always add those nodes, but in which order does not matter- as long as the edges are unweighted.
> 5 votes

# Answer
The weighted version of BFS is called Dijkstra's algorithm. You can check the pseudocode in Wikipedia. Alternatively, Dijkstra's algorithm is supposed to find the shortest paths from the origin to all other vertices. If you've seen a proof in class, you should be able to match the algorithm to the proof. Only one implementation will result in the algorithm finding the shortest paths.
> 3 votes

---
Tags: graphs
---


# Question
Title: What's the difference between a rule based system and an artificial neural network?
I'm currently doing some reading into AI and up to this point couldn't find a satisfying answer to this question: what's the difference between a rule based system and an artificial neural network?

From my understanding both are trying to do inference based on a variety of different inputs.

# Answer
> 4 votes
The difference is vast, although as Dave wrote, the resulting black box might look the same from outside. Rule-based systems are examples of "old style" AI, which uses rules prepared by humans. Neural networks are examples of "new style" AI, whose mechanism is "learned" by the computer using sophisticated algorithms, and as a result, we humans don't really understand why it works. While in some cases rule-based systems could be effective, the general trend in AI has been to switch to machine-learning algorithms such as neural networks, due to their much better performance.

# Answer
> 1 votes
Just to give a slightly more general perspective than the other answers: "trying to do inference based on a variety of different inputs" is basically what much of the field is doing and it is a very general problem.

The idea is that you are looking for some simple, general way to explain how data observations are associated. This "explanation" is called the model. Of course there is an infinite number of types of models that you could check, and the "true" model underlying your data could be incredibly complex (for example, consider modelling the behavior of a live organism from its molecular components). From this you can see why the main challenge is to find efficient algorithms to identify different kinds of good predictive models.

Rule-based systems and Artificial Neural Networks are just some of the different algorithms/models that are being used. Other popular approaches are Support Vector Machines, decision trees, ensemble methods, probabilistic graphical models, and there are many others.

---
Tags: artificial-intelligence, neural-networks
---


# Question
Title: Problems showing the constraint of master theorem case three holds
Prove or disprove the following statements:

1. $T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \theta \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right) = \theta \left( {f\left( n \right)} \right) $ for all $ {\rm{ n = }}{{\rm{2}}^k}$
2. $T\left( n \right) = 2T\left( {\frac{n}{2}} \right) + f\left( n \right),f\left( n \right) = \Omega \left( {{n^2}} \right) $ then $ {\rm{ }}T\left( n \right) = O\left( {f\left( n \right)} \right)$ for all $ {\rm{ n = }}{{\rm{2}}^k}$

I think I should use the third case of the master theorem to check these equations.

But I have not been able to check this constraint for these inequations:

$\qquad af\left( {\frac{n}{b}} \right) \le cf\left( n \right)$

How do I do that?

# Answer
The following shows that the second statement is false.

Define $f$ as follows: $$ f(n) = \begin{cases} 4n^3 & n \text{ is a power of }4, \\ n^2 & \text{otherwise}. \end{cases} $$ Let $n = 2^{2k+1}$. Then $f(n) = n^2$ while $$ T(n) \geq 2T(n/2) \geq 2f(n/2) = n^3. $$
> 4 votes

# Answer
For 1., trouble is that you don't *know* $f$; it could be any one of the functions in $\Theta(n^2)$. Therefore, applying the master theorem directly is not (immediately) possible.

So let's unfold $\Theta$! Let $f \in \Theta(n^2)$ arbitrary. We know by definition of $\Theta$ that there are $d\_1, d\_2, n\_1, n\_2 \in \mathbb{N}$ such that

$\qquad \displaystyle d\_1n^2 \leq f(n) \leq d\_2n^2$,

for all $n \geq n\_0 := \max(n\_1,n\_2)$. We will ignore all $n \< n\_0$ in the sequel; consider the respective values of $T$ constants.

We can easily show with the master theorem (case 3) that for

$\qquad\begin{align} T\_1(n) &= 2T\_1(n/2) + d\_1n^2 \text{ and} \\ T\_2(n) &= 2T\_2(n/2) + d\_2n^2 \end{align}$

both $T\_1 \in \Theta(n^2)$ and $T\_2 \in \Theta(n^2)$. Since we have (asymptotically) that $T\_1(n) \leq T(n) \leq T\_2(n)$, we also get that $T \in \Theta(n^2) = \Theta(f)$ by squeeze theorem.

---

As you see, we needed *both* upper and lower bound to perform the proof. We don't have that in the second case where $f \in \Omega(n^2)$. That suggests the statement may be false (but does not prove it).

Once we suspect, we can choose a counter-example; see Yuval's answer for one.
> 2 votes

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


# Question
Title: Can an LL(k) parser parse any grammar without left recursion or common prefixes?
I'm being asked to create a "top down grammar" for a certain language (I'm pretty sure there's no such thing as a "top down grammar" but I think it means write a grammar that an LL(k) parser can parse).

I'm pretty sure the language is not LL(1), but I can remove left-recursion and common prefixes from it and still have an unambiguous grammar. But I'm a little confused about the significance of that. If I successfully removed left-recursion and common prefixes and the grammar is still unambiguous, is the language LL(k)? And does that mean it can be parsed by a top-down parser?

# Answer
> 1 votes
A 'top down parser' is usually understood to be a hand-written $LL(1)$ parser, or $LL(k)$ for some low $k$, which would explain the use of this terminology. These two concepts are therefore essentially the same.

I'm unsure what you mean exactly by 'common prefixes' - I guess you are talking about common lookaheads. If you ensure that you can always uniquely distinguish which production you need to expand by looking at the next letter, then your language is $LL(1)$ (and also contains no left recursion). Doing that usually means you change your grammar structure a bit so your parser is never confused by 'k letter prefixes' of the part of the input that you haven't looked at yet.

If you are really talking about common prefixes in the language-theoretic sense, then all your words would have to start with a unique letter, which means your language is finite and therefore $LL(1)$.

# Answer
> 0 votes
This grammar

```
<stmt> ::= <label> <unlabeled stmt>
<label> ::=
        ::= <name> ":"
<name>  ::= id <qual>
<qual>  ::=
        ::= "." id <qual>
<unlabeled stmt> ::= <name> "=" <exp>

```

is not $LL(k)$ for any $k$ (you need unbound look ahead to be able to decide if there is a label or not), has no left recursion and probably has no common prefixes if I correctly get what you mean. You can get a $LL(1)$ grammar for the same language, but with a generalization of left factoring but involving productions of several non terminals (AFAIK *left factoring* is usually taken as applying to the productions of one non terminal, an alternative view is that you apply left factoring after having inlined `<label>` and `<unlabeled stmt>` in `<stmt>`):

```
<stmt> ::= <name> <name suffix>
<name suffix> ::= ":" <unlabeled stmt>
              ::= "=" <exp>
<name>  ::= id <qual>
<qual>  ::=
        ::= "." id <qual>
<unlabeled stmt> ::= <name> "=" <exp>

```

---
Tags: formal-languages, compilers, parsers, ll-k
---


# Question
Title: Prove that the language of non-prime numbers written in unary is not regular
Im trying to prove that the following language is not regular. $$\text{Notprime} = \\{a^n \text{where \\(n\\) isn't prime}\\} = \\{\epsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots\\}$$

Heres what I have:

"If Notprime were regular, then its complement would be regular also. However, the complement of Notprime is the language Prime, hence Notprime is non-regular."

Is this the right way of proving it? Any help is appreciated!

# Answer
This proof is correct, the complement of a regular language is indeed a regular language (and dually the complement of a non-regular language is non-regular). Your proof relies on the assumption that Prime is not regular. If this was given as an exercise and there wasn't an earlier question about Prime, then the intent of the exercise was probably that you prove that Prime is not regular (or directly prove that Notprime is not regular, which is about as easy).

The usual method in elementary exercises to prove that a language is not regular is the pumping lemma. It works for this example. See How to prove that a language is not regular? for more methods, and questions tagged pumping-lemma for examples of using the pumping lemma.

For an with a single letter, there is a general form for all regular languages: they are the languages that, for sufficiently long words, consist of the union of several arithmetic progressions with the same coefficient: $\\{a^{ak+b} \mid k\in\mathbb{N}, b \in B\\}$ for some fixed $a$ and some finite set $b$. See What are the possible sets of word lengths in a regular language? for a more precise description and a proof. The set of primes, or the set of non-primes, does not have this structure since there are growingly large gaps between primes.
> 6 votes

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


# Question
Title: Program that generates a regular expression from an FA
> **Possible Duplicate:**
> How to convert finite automata to regular expressions?

Im curious if anyone knows if its possible to write a program to generate a regular expression given a finite automation.

To make things less complicated I want to limit the number of states to about 4, assume the FA is in minimal form and that the FA has only one FinalState and only one StartState.

Ive been thinking about it for a while now and I think the first obvious thing to do would be to create a transition table for the FA.

So an FA could look like this:

```
NumberOfStates 4
StartState   1
FinalState   4
StateNumber  NextStateA   NextStateB
1            2            4
2            3            2
3            4            4

```

And would generate the regular expression: b + (ab\*a(a + b))

Ive been racking my brain for hours but am stumped on how to go about this. Any ideas is greatly appreciated.

# Answer
Here's one resource on the matter: www.cs.dartmouth.edu/~ac/Teach/CS39.../lec09dfa2regexp.pdf

There's a commonly known Dynamic Programming algorithm which can do it. The link I send outlines the algorithm, though it doesn't convert to code. The DP algorithm is pretty common (I think it's usually used in the proof that DFA and RE are equivalent) so if you're looking for the code, it's probably out there somewhere.
> 0 votes

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


# Question
Title: Why does it take $O(f(n)^2)$ to simulate a 3-tape $O(f(n))$-time TM on a 1-tape  TM?
This looks like a fundamental result but I can't find a resource online that gives an intuitive interpretation of this complexity. Any basic explanation is appreciated.

# Answer
> 6 votes
Have a look in the book of Hopcroft and Ullman "Introduction to automata theory, languages and computation" (ISBN 0-201-02988-X). I have only the German version of this book, but there it is mentioned as Theorem 12.5.

However the basic idea behind the tape-reduction from $k$ tapes to 1 is quite easy. Assume the running time is bounded by $f(n)$. You boost you working alphabet $\Gamma$, such that every super-character represents $k$ original characters and $k$ Flags. The flags store the position of the head of the corresponding simulated tape. To simulate one step of the old machine, we have to scan through the whole tape. However, the tape contains at most $O(f(n))$ characters, hence the scan needs $O(f(n))$ time. Since we simulate $O(f(n))$ steps the 1-tape machine runs in $O(f(n)^2)$. I think from here you can work out the details on your own.

---
Tags: turing-machines, tape-complexity
---


# Question
Title: Which properties of context sensitive languages are decidable?
There are two context-sensitive languages, $L\_1$ and $L\_2$. Which of the following statements about them are decidable respectively undecidable?

1. $L\_1 = \emptyset$
2. $L\_1 = \Sigma^\*$
3. $L\_1 \cap L\_2 = \emptyset$
4. $\overline{L\_1}$ is also a context-sensitive language.
5. $L\_1 = L\_2$

# Answer
> 3 votes
When considering questions like this you need to make explicit what representation you are using for your languages. In the following I will assume you are using context-sensitive grammars as input for your problems.

1) is a well known undecidable property of context-sensitive grammars.

2) as well as 3) and 5) are obviously undecidable as they are undecidable for a proper subclass of context-sensitive grammars, namely the context-free grammars.

4) is trivially decidable as the answer is always yes because the complement of a context-sensitive language is itself context-sensitive.

---
Tags: formal-languages, undecidability, context-sensitive
---


# Question
Title: Is there a O(log n) algorithm for matrix exponentiation?
Is there an algorithm to raise a matrix to the $n$th power in $O(\log n)$ time?

I have been searching online, but have been unsuccessful thus far.

# Answer
Here is the pseudocode for an $O(\lg n)$ matrix exponentiation algorithm. Note that the * operator denotes ordinary matrix multiplication.

```
MATHPOWER (M, n)
if n == 1
    then return M
else
    P = MATHPOWER (M, floor(n/2))
    if n mod 2 == 0
        then return P * P
    else
        return P * P * M

```
> 13 votes

# Answer
There are two other algorithms which may or may not be relevant. The first algorithm diagonalizes your matrix (which is usually possible), writing it as $M = PDP^{-1}$, where $M,D$ in general may be complex-valued. You then compute $M=PD^nP^{-1}$. Note it's very easy to raise a diagonal matrix to the $n$th power. If $M$ is not diagonalizable, you find its Jordan form and proceed as before (now you also have to calculate some binomial coefficients). This algorithm is probably not numerically stable.

Another algorithm uses the fact that $M$ satisfies its characteristic polynomial (or even its minimal polynomial). Suppose $P(M) = 0$ for some $P$, say the characteristic polynomial. Then we can compute $M^n$ over $\mathbb{R}\[M\]/(P(M))$, and then substitute $M$. That means that we calculate $M^n$ as a polynomial, using the fact that $P(M) = 0$, and only at the end substitute the values of $M$. We could even precompute all the necessary powers of $M$ and all the values of $M^k \pmod{P(M)}$ for $k \< 2\deg P-1$, and then this algorithm could be faster than the algorithm is Massimo Cafaro's answer. It might be more numerically stable than the previous algorithm.
> 11 votes

---
Tags: algorithms, time-complexity, matrices
---


# Question
Title: How to go about working the average case run time of this trivial algorithm (and other algorithms)?
This is a similar algorithm to one I used in a previous question, but I'm trying to illustrate a different problem here.

```
for (int i = 0; i < numbers.length - 1; i++) {
    for (int j = i + 1; j < numbers.length; j++) {
        if (numbers[i] + numbers[j] == 10) {
            System.out.println(i+" and "+j+" add up to 10!");
            return;
        }
    }
}
System.out.println("None of these numbers add up to 10!");
return;

```

Basically, I realised, that I have a decent understanding of how to work out the best case run time here. I.e. the first two numbers which are fed in, add up to 10, and therefore our best-case runtime is constant time. Also, I understand that in the worst-case, none of the numbers we provide add up to 10, so we must then iterate through all loops, giving us a quadratic runtime. However, in the slides I was going through (for this particular course) I noticed that I had missed this:

Average case

• Presume that we've just randomly given integers between 1 and 9 as input in numbers to our previous example

• Exercise: Work out the average running time

I realise I don't have the first clue as to how to go about calculating average case run-time. I'm not asking for the answer to: "what is the average-case runtime for this algorithm?", what I need to know is, how do you work something like this out?

# Answer
> 5 votes
Here's an elaboration of The Unfun Cat's answer. For convenience, let the numbers be $v\_1,\ldots,v\_n$. Whatever the value of $v\_1$ is, for $i\>1$ we have $\Pr\[v\_i = 10-v\_1\] = 1/9$. Therefore, the number of iterations of the second loop is roughly distributed geometrically $G(1/9)$, so we expect it to run about $9$ times. A complication is that $n$ is not infinite, but this doesn't have a great effect on the running time.

Given $n$, the probability that the outer loop doesn't terminate on the first iteration is $(8/9)^{n-1}$. If it does, then the expected number of (inner-loop) iterations is less than $9$. Otherwise, it is at most $\binom{n}{2}$. Therefore the running time is $O(9 + \binom{n}{2}(8/9)^{n-1}) = O(1)$, using $n^2 = O((9/8)^n)$.

# Answer
> 4 votes
An insight here is that the probability of returning early does not depend on the length of the input (as long as numbers.length is of such a size that you would expect to find two numbers that add to ten).

You need to compute the probability $p$ that two integers between one and nine add to ten. Then solve $p\*x=1$ and $x$ is the number of iterations done on average. This is a constant $c$, so the running time on average is $O(1)$.

In general you would need to evaluate the running time of your algorithm on random inputs (for a specific probability distribution) and find the average. This can be tricky.

Wikipedia has a nice example for quicksort.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, average-case
---


# Question
Title: Length of the certificate in complexity classes
> A nondeterministic machine trying to decide membership in a language is presented with a hint (called a "witness" or "certificate") which proves membership (no such witness is provided for elements outside the language; the definition is asymmetric).

So, if a non-deterministic algorithm can solve a problem in O(f(n)) time, does this mean the length of the certificate is f(n) \[Since it could try all the possible combinations and the length of the shortest one will be f(n)\]? And the input size is n?

Also, if a deterministic algorithm A exists that can verify a certificate in O(f(n)) time, how does this imply the existence of a non-deterministic algorithm that can solve the problem in O(f(n)) time?

# Answer
> 3 votes
I'm a little confused by your quote.

There are two equivalent definitions of the NP complexity class in terms of Turing Machines:

1. The class of problems for which a deterministic verifier exists whose runtime is bounded by a polynomial in the size of the problem input.
2. The class of problems for which a nondeterminstic decider exists whose (nondeterministic) runtime is bounded by a polynomial in the size of the problem input.

So a nondeterministic machine trying to decide membership in a language *wouldn't* be presented with a certificate; that's not what it means to decide membership in a language. It's the deterministic verifier that gets a certificate - a verifier over language L is a decider over the language of pairs of an element of L and a certificate proving the element in L (that's why the definition is asymmetric and there's no certificates for non-membership; the verifier only answers "yes this is an element of L together with a certificate for this element", or "no this is either not an element of L or not a certificate for this element").

That aside, on to your questions.

If the running time of the verifier in O(f(n)), then the certificate (in general) is also in O(f(n)). It's possible the verifier needs to read the whole certificate and then do some trivial computation with it that doesn't increase the big-oh complexity over the time needed to simply read the certificate. *Particular* verifier algorithms for particular problems may well have much shorter certificates (implying that their runtime is occupied with much more computation than simply reading the certificate). But you can't say anything in general about an unknown verifier's certificate length just from knowing its runtime (well, anything more specific than that it's certificate length bound must be short enough to be read within its run time bound).

You also ask about how the existence of a deterministic verifier for a problem implies the existence of a nondeterministic decider for the same problem. The implication actually goes both ways (which is why the two definitions of the NP complexity class are equivalent).

Given a deterministic verifier you can construct a nondeterministic decider. The verifier is a decider over the language `<e, C(e)>` (where `e` is an element of L and `C` is a function that computes a certificate for `e`). The machine we're trying to construct will be given `e` as input. If it could come up with `C(e)` it could simply run the verifier on the pair and it would have its answer.

But our decider has the advantage of nondeterminism. It can simply guess a value for `C(e)` and run the verifier, and nondeterminism implies that if there is such a value that leads to acceptance then the machine will have picked the correct one. The "guessing" can be (almost) implemented by having a state that nondeterminsitically writes a symbol from the alphabet (any symbol) on the current cell, moves the tape head right, and then nondeterministically chooses to remain in the same state or to move on to the verifier stage.

Since the certificates must be within O(f(n)) length, and all we do before running the verifier is write down the certificate, the runtime of this machine on an `e` that **is** in L is O(f(n)) + O(f(n)), which is simply O(f(n)).

The only catch is that if `e` is **not** in L, then there is no such `C(e)` that will lead to the verifier accepting. But we can't let our machine keep trying longer and longer guesses for `C(e)`; our machine is a decider, so it is required to halt for all input. The machine needs to know when to give up; it must only be capable of generating a finite number of guesses for `C(e)`.

This means that machine must be able to calculate an upper bound to the length of `C(e)`, and only guess strings up to that length. This means that the upper bound has to be a total computable function of `e`. I'm not 100% certain if that's possible in general for verifiers with completely arbitrary runtime complexity O(f(n)), because f might not be a computable function, and the exact certificate length can be larger than f(n) because of the details big-oh notation abstracts away from (constants, lower-order terms, and the fact that the bound only has to apply for sufficiently large n; maybe someone who knows a bit more can add something here). But for verifiers with *polynomial* big-oh complexity, there always exists a polynomial in `n` which is strictly larger than the minimum certificate length for any `e` with length `n`.

So we can presume the existence of a nondeterminstic machine which for an element `e` of length `n`, calculates this upper bound, guesses any string whose length is within the bound, and runs the verifier on it. Since guessing a string within a polynomial bound takes at most polynomial time, and the verifier had a polynomial run time bound, and the sum of two polynomials is still a polynomial, the nondeterministic decider always halts within a polynomial bound.

The other direction (the existence of a polynomial nondeterminsitic decider implies the existence of a polynomial deterministic verifier) is much easier. Let the certificate for any `e` in L simply be a record of all the transitions used by the nondeterministic decider when processing `e`. All the verifier has to do is check that this record forms a valid path through the nondeterministic decider leading to an accept state. Since checking this doesn't require exploring all the nondeterministic possibilities, a deterministic verifier can do this with overhead of a constant multiplier over the nondeterministic decider's runtime (it only needs to check each transition against the decider's set of possible transitions, which is a constant).

I've answered a slightly weaker question than you asked, however. I've only shown that you can come up with a decider for verifiers with a polynomial runtime bound (although similar reasoning applies to exponential bounds, and most other functions that actually get used very often when talking about big-oh complexity). I also haven't shown that a verifier with runtime in O(f(n)) implies the existence of a decider with runtime in O(f(n)), even for polynomial f; all I've shown is that if the runtime bound of the verifier is a polynomial then the runtime bound of the decider is still a polynomial; it might be larger one. I don't actually know whether a verifier always implies a decider with the same runtime bound; I'd welcome an addition from someone who knows for sure either way.

# Answer
> 1 votes
Just a quick hint on how you can build the guess part of the non-deterministic solver, given a deterministic verifier (using *ASCII art* :)

```
         +----------------------+     +-----------------+
         |                      |     |                 |
         |               t1     V     V       t2        |
  [q2: write 0 on the ]<====[q1: START STATE]====>[q3: write 1 on the ]
  [certificate tape   ]           ||              [certificate tape   ]
                                  ||t3
                                  \/
                       [q4: first state of the]
                       [deterministic verifier]
                            ........

Where t1,t2,t3 transitions (====>) represent nondeterministic choices

```

Using another informal notation:

1. nondeterministically pick one of the following steps:
1.1. append a 0 to the certificate tape, and goto 1.
1.2. append a 1 to the certificate tape, and goto 1.
1.3. goto 2.
2. run the deterministic verifier using the input x and the certificate y as inputs

**EDIT:** (some clarifications)

1) for a Nondeterministic Turing machine (NDTM) there are infinite computations, one for each possible guessed string; some of them will halt on the accept state $q\_Y$, some will halt on the reject state $q\_N$, some will run forever;

2) a string $x$ is *accepted* by a Nondeterministic Turing machine if at least one of its computations halts on the accepting state $q\_Y$;

3) a language $L\_M$ recognized by a NDTM $M$ is the set of $x$ accepted by $M$;

4) the *definition* of time complexity for a Nondeterministic Turing Machine $M$ is slightly different from the definition of time complexity for a Deterministic Turing Machine:

$T\_M(n) = max ( \\{1\\} \cup \\{ m \\; : \\; $ there is an $x \in L\_M$ such that $|x|=n$ and $M$ accepts $x$ in $m$ steps $\\})$

The time complexity of a NDTM depends (by definition) only on the length of accepting computations.

See Garey&Johnson, "Computers and Intractability"

# Answer
> 0 votes
A non-deterministic Turing machine program $\mathcal{M}$ solves problems in two stages: (1) guess a candidate solution (certificate), (2) check that the guess is a solution. If it takes $\mathcal{O}(f(n))$ time to solve the problem, then the length of the certificate should be $\mathcal{O}(f(n))$ because you have to look at every bit of the certificate to validate it (if it's too long, just looking at it will take time that cannot be bounded by a function in $\mathcal{O}(f(n))$).

For the second part of your question, if a deterministic algorithm solves a problem in $\mathcal{O}(f(n))$ time, then you can use that same algorithm in the checking stage of the non-deterministic algorithm and ignore the guessing stage (don't look at the guessed solution).

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


# Question
Title: What's an intuitive distinction between semi-computable problems and noncomputable problems/functions?
The definitions I've found were highly technical and using terms I've never seen before.

Say, I have a certain irrational number *e* that I get get closer and closer to with a computer and I want to determine if there is a particular digit *d* appearing after a certain position. Or what about the halting problem (give a program and ask 'will the computer ever halt?')? Are these problems semi-computable problems or noncomputable?

# Answer
> 5 votes
Intuitively, a set of numbers is *computable* or *decidable* or *recursive* if there is an algorithm deciding membership for the set. A set of numbers is *semidecidable* or *recursively enumerable* (r.e.) if it has verifiable "proofs" of membership. For example, the set of programs which halt is semidecidable, since given a program $A$ and a time bound $t$, one can check that $A$ halts after at most $t$ steps. But this set is not computable, since without the time bound, we don't know how long to wait for. (That's an intuitive explanation; you can google for a proof that the halting problem is not decidable.)

There are several equivalent definitions of semidecidable sets:

* A set $S$ is semidecidable if there exists an algorithm $A$ which always terminates with either YES or NO as an answer, such that $x \in S$ iff there is a witness $w$ for which $A(x,w)$ answers YES.
* A set $S$ is semidecidable if there exists an algorithm $A$ such that $x \in S$ iff $A(x)$ halts.
* A set $S$ is semidecidable if there is an algorithm that enumerates all members of $S$.

See if you can show that all these definitions are equivalent. You might want to look up the technique of "dovetailing".

What about the digits of $e$? We need to phrase the problem of computing the digits of $e$ in our framework. The set of digits of $e$ is the set of pairs $(k,d)$, where $d$ is the $k$th decimal digit of $e=2.71828\ldots$, i.e. $\\{(0,2),(1,7),(2,1),(3,8),(4,2),(5,8),\ldots\\}$. Since there is an algorithm computing the $k$th digit of $e$ (e.g. using the Taylor series $e = \sum\_{k=0}^\infty 1/k!$), the set of digits of $e$ (under this encoding) is computable.

Edit: Following the OP's comment, suppose we're interested in the set of positions $n$ such that the decimal expansion of $e$ contains the digit $2$ somewhere past the $n$th digit. This set is decidable, for the following reason: either the digit $2$ appears infinitely often, or its last appearance is at digit $N$. In the first case, the set in question contains all natural numbers, in the second case it is $\\{0,\ldots,N-1\\}$.

The same trick works for any fixed real number. Consider, however, the set consisting of pairs $(A,n)$ such that $A$ is an algorithm that enumerates the decimal expansion of some real number, which contains the digit $2$ somewhere past the $n$th digit. This set is *not* computable, only semidecidable, since one can reduce the halting problem to it and vice versa (how?).

---
Tags: computability, terminology
---


# Question
Title: Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$
We know that $st\text{-}non\text{-}connectivity$ is in $\mathsf{NL}$ by Immerman–Szelepcsényi theorem theorem and since $st\text{-}connectivity$ is $\mathsf{NL\text{-}hard}$ therefore $st\text{-}non\text{-}connectivity$ is many-one log-space reducible to $st\text{-}connectivity$. But is there a direct/combinatorial reduction that doesn't go through the configuration graph of the Turing machines in $\mathsf{NL}$?

> $\mathsf{stConnectivity}$ (a.k.a. $stPATH$):
>
> Given directed graph $G$ and vertices $s$ and $t$,
>
> Is there a directed path from vertex $s$ to vertex $t$?

---

### Clarifications:

You can assume a graph is given by its adjacency matrix (however this is not essential since standard representations of graphs are log-space convertible to each other.)

It is possible to unpack the proof of $\mathsf{NL\text{-}hard}$ness of $st\text{-}connectivity$ and move it into the proof so the proof does not use it that theorem as a lemma. However this is still the same construction essentially. What I am looking for is *not* this, I want a conceptually direct reduction. Let me give an analogy with the $\mathsf{NP}$ case. We can reduce various $\mathsf{NP\text{-}complete}$ problems to each other by using the fact that they are in $\mathsf{NP}$ therefore reduce to $SAT$ and $SAT$ reduces to the other problem. And we can unpack and combine these two reductions to get a direct reduction. However it is often possible to give a conceptually much simpler reduction that doesn't go through this intermediate step (you can remove mentioning it, but it is still there conceptually). For example, to reduce $HamPath$ or $VertexCover$ or $3\text{-}Coloring$ to $SAT$ we don't say $HamPath$ is in $\mathsf{NP}$ and therefore reduces to $SA$ since $SAT$ is $\mathsf{NP\text{-}hard}$. We can give a simple intuitive formula that is satisfiable iff the graph has a Hamiltonian path. Another example, we have reductions from other problems in $\mathsf{NL}$ to $st\text{-}Connectivity$ which do not rely on $\mathsf{NL\text{-}complete}$ness of $st\text{-}Connectivity$, e.g. $Cycle$, $StronglyConnected$, etc, they involve modification on the input graph (and do not refer to any Turing machines that is solving them).

I still don't see any reason why this cannot be done for this one. I am looking for a reduction of this kind.

It might be the case that this is not possible and any reduction would conceptually go through the $\mathsf{NL\text{-}hard}$ness result. However I don't see why that should be the case, why the situation would be different from the $\mathsf{NP}$ case. Obviously to give a negative answer to my question we would need to be more formal about when does a proof *conceptually* include another proof (which is proof theory question that AFAIK not settle in a satisfactory way). However note that for a positive answer one does not need such a formal definition and I am hoping that is the case. (I will think about how to formalize what I am asking in a faithful way when I find more free time. Essentially I want a reduction that would work even if we didn't know that the problem is complete for $\mathsf{NL}$.)

Using the proof of Immerman–Szelepcsényi theorem is fine, using $\mathsf{NL\text{-}complete}$ness of $stPATH$ and configuration graph of an $\mathsf{NL}$ machine is what I want to avoid.

# Answer
It is possible, if messy, to convert the proof of the Immerman-Szelepcsényi theorem to the reduction you want. There is absolutely no need to use the NL-completeness of st-connectivity.

Given an instance $G=(V,E),s,t$, we construct a new graph $G'=(V',E'),s',t'$. The "major vertices" of $V'$ record the following information: the current distance $d$ from $s$, the number of vertices of distance at most $d-1$, the number of vertices of distance $d-1$ counted so far, the current vertex we're guessing if it has distance at most $d-1$, the number of vertices of distance at most $d$ counted so far, the current vertex we're determining whether it has distance at most $d$. The minor vertices handle the part where we guess a path of length at most $d-1$ to a vertex which we guess to be of distance at most $d-1$. Edges that involve showing the vertex $t$ is reachable from $s$ are dropped. For each vertex which we're testing at the current distance, we only move forward to the next vertex if we have accounted for all vertices of smaller distance. When moving from distance $d$ to distance $d+1$, we copy the requisite information. The starting vertex $s'$ accounts for the fact that $s$ is the only vertex of distance zero. The ending vertex $t'$ is pointed at by all vertices representing the fact that the process has finished up to (and including) distance $n-1$, where $n=|V|$.

As you can see, it will be quite messy to write everything in full and correctly, but definitely possible. No overt use of NL-completeness was made, in that we never use the configuration graph of any NL machine. That's not needed, since we have something better than the configuration graph - the input instance itself.
> 4 votes

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


# Question
Title: What is the relationship between NP/NP-Complete/NP-Hard to time complexity?
I'm familiar with a few problems of each class and even though the definitions are based on sets and polynomial reducibility, I see a pattern with time complexity. NP problems appear to be $O(2^n)$ (minus the P problems of course), and NP-hard problems seem to be worse: $n^n$ or $n!$ (Chess, TSP). Is this a misleading interpretation?

# Answer
See the definition of NP completeness. For a problem to be NP-complete, it

1. needs to be in NP and
2. all NP problems need to be reducible to it in polynomial time.

Condition 2 alone is what it means to be NP hard. Thus NP complete problems are the intersection of NP problems and NP hard problems.

NP $\subseteq$ EXPTIME, thus NP problems can be solved in $2^{O(p(n))}$, for some polynomial $p(n)$. But it is well know that if P $=$ NP, then NP problems can be solved in polynomial time.

NP hard problems are at least as hard as NP problems – you cite a few examples.
> 8 votes

# Answer
Your understanding is correct at a very high level. A problem being in NP means that the problem is “easy” (in a certain specific sense), whereas a problem being NP-hard means that the problem is “difficult” (in another specific sense), and I think that you understand this correctly.

However, your understanding is misled in several ways.

First, a problem being in NP and a problem being NP-hard are not mutually exclusive. When a problem is both in NP and NP-hard, we say that the problem is NP-complete, as Dave Clarke explained.

Second, it is not known (or believed) that all problems in NP can be solved deterministically in time O(2*n*), or in time 2O(*n*) for that matter. What is known is that all problems in NP can be solved deterministically in time 2poly(*n*) (= 2*n*O(1)). Time 2poly(*n*) is often called “exponential time” in complexity theory, but note that the same term “exponential time” can sometimes also refer to time 2O(*n*).

By the way, while you are right in that the traveling salesperson problem (TSP) is NP-hard, it seems that you are implying that TSP is not in NP. This point deserves some attention.

The TSP defined as a search problem (“Given a weighted directed graph, find a Hamiltonian circuit with the minimum total weight”) indeed cannot be in NP because by definition, NP is a class of decision problems. However, a natural decision version of TSP (“Given a weighted directed graph and a threshold *K*, decide whether the given graph has a Hamiltonian circuit with the total weight at most *K*”) is in NP, and this decision version is sometimes also called the traveling salesperson problem. This practice of calling the search version and the decision version by the same name is often convenient, but because of this, a strange thing happens—some people say “TSP is NP-complete” while others say “TSP is not in NP by definition,” and both are correct. See my post on math.stackexchange.com for more about this convention in general.
> 7 votes

# Answer
There are many exceptions to your running time summaries.

Probably most notably, TSP can be solved in $n^22^n$ time with dynamic programming (the Held-Karp Algorithm); you don't need all $n!$.

There are some NP-hard problems that can even be solved a bit faster than $2^n$. Subset sum can be solved in $O(2^{n/2})$ time, or about $O(1.4^n)$. There are many other NP-hard problems that can be solved in $c^n$ time with $c \< 2$.

Some NP-hard problems, like Partition, are only "weakly NP-hard", and have pseudopolynomial solutions. This means that there is running time that's polynomial in the value of the inputs (so if the largest item in the set has size $m$, the running time is proportional to $m$ as well as the size of the set $n$). Equivalently, these problems can be solved in polynomial time if the input is given in unary. Most problems similar to Partition (like Knapsack) fall into this category, as well as many--but not all--NP-hard scheduling problems. Depending on the problem instance, this may be better than $2^n$, or even polynomial.

Graph isomorphism is in NP but is likely not NP-hard and can be solved in $O(2^{\sqrt{n\log n}})$ time (not great but better than $2^n$). Some problems that are in NP but are not known to be NP-hard can be solved more quickly. For example, factoring, which can be solved in $e^{(64n/9)^{1/3}(\log n)^{2/3}}$ time for an n-digit number using the general number field sieve.

There are several other factors that may make an NP-hard problem considered to be more or less difficult compared to others, such as how closely they can be approximated in polynomial time.
> 5 votes

---
Tags: complexity-theory, terminology, time-complexity, np-hard
---


# Question
Title: Are $\log_{10}(x)$ and $\log_2(x)$ in the same big-O class of functions?
Are $\log\_{10}(x)$ and $\log\_{2}(x)$ in the same big-O class of functions? In other words, can one say that $\log\_{10}(x)=O(\log x)$ and $\log\_{2}(x)=O(\log x)$?

# Answer
Yes. Because they differ only by a constant factor. Remember high school math:

$\log\_2 x = \dfrac{\log\_{10} x}{\log\_{10}2}$.
> 13 votes

# Answer
Why?

$2^{\log\_2 x} = x$

$\log\_{10}(2^{\log\_2 x}) = \log\_{10} x$

$\log\_2 x(\log\_{10}2) = \log\_{10} x$ $(\*)$

$\log\_2 x = \dfrac{\log\_{10} x}{\log\_{10}2}$

QED.

$(\*) \log x^y = y\*\log x$
> 2 votes

---
Tags: landau-notation
---


# Question
Title: Finding the height of all nodes in a forest
I have a forest, i.e., nodes with directed edges and no cycles (directed or undirected). I define the height of a vertex $v$ as 0 if it does not have any incoming edges, or the maximum number of edges to traverse in reverse to reach a vertex of height 0.

I also know that the average degree of a node is a small constant, say 2 or so. To find the height of all vertices, I can think of two algorithms:

Walking Algorithm

1. Go through and mark $h=0$ for vertices with no incoming edges.
2. For each vertex with $h=0$, follow the outgoing edges, updating the height of each encountered vertex if it's previous height is smaller.

Frontier Algorithm

1. Go through and mark $h=0$ for vertices with no incoming edges, and mark these as the frontier.
2. For every frontier vertex, see if it's parent has children at or below the frontier, If it does, mark the parent as having $1$ plus the largest height among its children. Mark the parent as being on the frontier.
3. Repeat 2 until there is nothing beyond the frontier.

My questions:

1. Is there a name for this problem, and a well known fastest solution?
2. I tend to think simply walking up from all the $h=0$ vertices is the fastest solution. Am I right?

# Answer
First of all, it depends a bit how you can access your data to say which algorithms works best.

Anyway, I would suggest to determine the heights in a top-down fashion rather than bottom-up. I personally think that a top-down approach is conceptually nicer and easier to analyze. For any vertex $v$ in the forest it is true that

$$\text{height}(v)=\begin{cases} \left(\max\_{u\text{ child of }v}\text{height}(u)\right)+1 & \text{if $u$ is not a leaf} \\ \hskip4ex 0 & \text{otherwise} \end{cases}. $$

So you can scan for all roots, and then determine the heights by divide an conquer. You will touch every vertex at most twice (scanning for the roots + traversing). In the approach that you have suggested you might have to touch some vertices many times.

Btw, since you have a forest, you have less edges than vertices, so you **know** that you have average degree less than two (and therefore you can test for roots in linear time).
> 7 votes

# Answer
I don't know if this problem has an official name or not. Your title sums it up well enough. Walking up from the 0 height nodes will be fast, provided you take care to avoid duplicate work. Suppose you have a node with many children and a long path above this node to the root. Suppose also that the heights of each of the children are different. Each child may update the height of the node in question. That's ok. But you should avoid also updating the long path above that node until all its children have reported their heights.

The resulting algorithm will run in linear time, and the pseudo-code would look something like this:

```
initialize a queue Q
initialize all nodes to have a property: maxChildHeight = 0
initialize all nodes of in-degree 0 to have height = 0
Add all nodes of in-degree 0 to Q
while Q is non-empty:
  pop a node v from the front of Q
  subtract 1 from the indegree of the parent of v
  set parent.maxChildHeight = max(height(v), parent.maxChildHeight)
  if the indegree of the parent is 0:
      parent.height =  maxChildHeight + 1
      add the parent to Q

```
> 4 votes

# Answer
A problem so similar it might be of interest is *"Parallel Prefix on Rooted Directed Trees."* The algorithm finds the number of edges to the root from each node. So the roots ends up with a the value 0, while e.g. the bottom right node would end up with a value of two.

Note that the algorithm below solves the more general problem for weighted edges, but you can just initialize the W(i) to 1 for all i. And each node i's successor is given by P(i)=j.

```
for 1 ≤ i ≤ n do in parallel
    S(i) = P(i)
    while S(i) != S(S(i)) do
        W(i) = W(i) + W(S(i))
        S(i) = S(S(i))

```

The image below illustrates the "halving" of the path lengths and makes the logarithmic running time easy to understand. It does not show the node heights computed though.

(from "Introduction to Parallel Algorithms" by Joseph Jaja).

Using multiple processors, it is solvable in O(lg n) time, but uses O(n lg n) operations. There is a hack to get it down to linear work, but it is slightly involved.
> 3 votes

---
Tags: algorithms, trees, graph-traversal
---


# Question
Title: What is the difference between E-Science Infrastructures and Distributed Computing Infrastructures?
What is the difference between eScience infrastructures and grid computing or distributed computing infrastructures? And what are some of their examples.

I can not distinguish them clearly. Is it how a grid is used make it an e-science platform?

# Answer
Both eScience infrastructures and grid computing are based on distributed computing, which is related to loosely-coupled applications. There are several models including client-server, peer-to-peer etc. The issues arising in distributed computing, such as security, failures, network partition etc must be taken into account at design time, since in this context failures are the rule and not the exception. Many large-scale scientific endeavors rely on distributed computing, such as for instance SETI@HOME, the projects using the BOINC middleware etc. However, these projects are not examples of grid computing.

Grid computing refers to the coordinated sharing of resources installed at different administrative domains, usually HPC resources. Each domain is called a Virtual Organization. In contrast, the resources shared in projects such as SETI@HOME are usually common PC and laptops.

The grid computing paradigm emerged as a new field distinguished from traditional distributed computing because of its focus on large-scale resource sharing and innovative high-performance applications such as:

* distributed supercomputing;
* on demand computing;
* high throughput computing;
* data-intensive computing;

Distributed supercomputing applications require multiple supercomputers to solve problems otherwise too large or whose execution is divided on different components that can benefit from execution on different architectures. This class of applications present a number of challenges to be faced, like resource discovery and scheduling, coordinated startup, configuration at multiple sites, wide area message passing and fault tolerance. An example of such application is SF-Express, a distributed interactive simulation of a military battle. On demand computing refers to the possibility of dynamically acquiring online instruments (e.g. microscopes, satellite sensors and telescopes) connected by high-speed networks to gather and process the data generated. An experiment of microtomography at photon sources in 1999 demonstrated the feasibility of on demand computing. The aim of high throughput computing (HTC) is to schedule many independent jobs for parametric studies or data analysis; in this case a measure of efficiency is the number of jobs processed per unit of time. The two most important tools for HTC, namely Condor and Nimrod are now grid-aware. Data-intensive applications extract new knowledge from geographically distributed data archives or digital libraries; issues related to this class of applications include scheduling and configuration of multiple data flows through several hierarchy levels.

In the past, eScience infrastructures were almost always based on grid computing. Right now, cloud computing is also emerging as a viable alternative in some cases.
> 2 votes

---
Tags: distributed-systems
---


# Question
Title: Calculate storage requirements for a data set
I have a simple problem. I can't seem to even find the right search terms to get me pointed in the direction I need to be heading.

I'm writing a bunch of integers to disk. Lot's of them.

Starting with the integer 2, I add it to another integer, write the result to disk, and start the process again using the result as the seed.

This pattern is helping me generate data I need for other research, but I need to apply this pattern until I've reached integers with a length of 10,000 digits or more.

So, here is my simple question: given a set of data of a known data type, how do I calculate the storage space required to store that set?

At the moment, I'm doing this incredibly simple task in Python, recording longs to disk as binary in a single file. But, on my very small machine, I was only able to store the integers my process produced with values between 0 and 42 billion.

Short of my goal of recording a data set with values between 0 and 1e10000.

Given that I have no exposure to formulas for calculating hardware requirements for storing data like this, I have no idea if I'm using the most efficient language and data type for storing as many integers as possible in as little space as possible.

# Answer
There are two ways to interpret your dataset generating process. The first produces all even numbers between $2$ and your bound: $2$, $4$, $6$, $8$, …; the second produces all powers of $2$ between $2$ and your bound: $2$, $4$, $8$, $16$, … An integer $N$ requires roughly $\log\_{256} N$ bytes to store. Therefore, if your bound is $N$, the first interpretation will take about $$ \sum\_{k=1}^{N/2} \log\_{256} (2k) \approx \int\_1^{N/2} \log\_{256} (2x) \\, dx \approx (N/2) \log\_{256} N \text{ bytes}. $$ The second interpretation, assuming $N=2^m$, will take about $$ \sum\_{k=1}^m \log\_{256} 2^k = \sum\_{k=1}^m (k/8) \approx m^2/16 = 4(\log\_{256} N)^2 \text{ bytes}. $$
> 2 votes

---
Tags: integers, efficiency, storage
---


# Question
Title: What is a good resource to learn about oriented matroids in the context of digraphs and optimization?
I am interested in oriented matroids in the context of directed graphs and optimization. Unfortunately, I know very little of the topic. Is there a book, article or a resource that serves as a good introduction to oriented matroids, especially in the context of directed graphs? It's a bonus if the resource is suitable for an (under)graduate level course and is preferably even free.

# Answer
These notes written by Winfried Hochstättler for an MAA short course on matroids look like a good, short, introduction. They also contain references to several longer references on oriented matroids.
> 5 votes

---
Tags: optimization, reference-request, discrete-mathematics, matroids
---


# Question
Title: Compute relational composition in $O(|E||V|)$
Definitions: Let $G=(V,E)$ be a DAG without self-loops, and $X \subseteq G$ and $Y \subseteq G$ be graphs.

Input: $X,Y$. Output: The relational composition relational composition $X \circ Y$ in $\mathcal{O}(|E||V|)$.

* Case 1: $|E| \le |V|$. Two for loops over $E(X)$ and $E(Y)$: Runtime $ \le \mathcal{O}(|E|^2) \le \mathcal{O}(|E||V|)$.
* Case 2: $|V| \le |E|$
    1. Draw the graph $(V(G),E(X) \cup E(Y))$: $(O(|V|)+\mathcal{O}(|2E|)))$. We call edges from $E(X)$ black and from $E(Y)$ red.
    2. Topologically sort it (Kahn: $\mathcal{O}(|V|) + \mathcal{O}(|E|)$). Let the first level be $0$, and edges go from a level to a higher level.
    3. Draw this graph twice.
    4. In the first copy, remove every red edge beginning at even level, and every black edge beginning at odd level: $\mathcal{O}(E)$.
    5. In the second copy, remove every "black even" and "red odd": $\mathcal{O}(E)$.
    6. For the first copy:
        + for all nodes $u$ on level $2i$
        + for all nodes $v$ on level $2i+1$
        + report edge $(u,v)$ (Runtime $\mathcal{O}(V^2) \le \mathcal{O}(EV)$).
    7. For the second copy: The same for "$2i+1$".
    8. Union the reported nodes, throw out duplicates $\mathcal{O}(V^2) \<= \mathcal{O}(EV)$ (I hope the graph representation allows this).

Could some of you please look over my algorithm and check whether

* it is correct
* it is in $\mathcal{O}(|E||V|)$

If it's correct, does my algorithm already "exist"? If not, could you provide an alternative? I'll accept the first answer, but upvote if some more people are so kind to check.

EDIT: Step 6 Seems to be in $O(E^2)$ sometimes. I wish this would not be true. Has anyone a working algorithm?

# Answer
> 4 votes
The problem is in Step 6 (from my understanding).

Essentially, you idea is to check for sequences $(u,w)(w,v)$ whether $(u,w) \in E(X)$ and $(w,v) \in E(Y)$. The topological sorting is correct, since in such sequences the two edges must come after each other.

An edge $(u,w)$ is black if it belongs to $E(X)$. An edge $(w,v)$ is red if it belongs to $E(Y)$. An edge may have two colors in this case.

A node $u$ will check each neighbor $w$ \[s.t. $(u,w)$ is black\] if $w$ has a red edge $(w,v)$ for one of its neighbors. In this case: $\sum \_{u \in V} deg(u). \sum \_{w \in N(x)} deg(w) = O(E^2)$

From what I understood: you made some filtering of some unneeded edges (step 4,5)- however there may be a worst case that will lead to complexity higher than $O(E^2)$.

# Answer
> 6 votes
Theorem 2.29 on page 60 of Parsing Theory of Sippu and Soisalon-Soininen gives an algorithm for computing (among other operations on relations) the composition of two relations. The algorithm runs in $O(t(|V|+|E|))$ time, where $t$ is the time needed to perform union or assignment operations on sets of vertices. The result of this operation is a set of vertices per vertex representing its neighbors. This algorithm works on arbitrary graphs, not just acyclic ones.

---
Tags: algorithms, graphs, algorithm-analysis, check-my-algorithm
---


title: Convert table look-up into function

text:
# Question
Title: Convert table look-up into function
Two problems: Given a known table (boolean or int), convert it to a function that returns the same value using only simple operations (and, or, xor, sum...). For example:

`bool table1[] = {0,1}` converted to `fun (int index) {return index;}`

`bool table2[] = {0,1,1,0}` converted to `fun (int index) {return index ^ (index>>1);}`

`int table3[] = {4,5,7}` converted to `fun(int index) {return index+4+(index>>1);}`

# Answer
It seems that your tables are 1-dimensional. So basically for an integer $x$ you define some value $T\[x\]$ and you are looking for a function $f$ such that $f(x)=T\[x\]$.

There is a name for the problem that tries to find a function that runs through a given set of sample points, this is known as **interpolation**. Your problem is special, since your sample points are given by $(x,T\[x\])$ and the $x$s are the indices of your table.

The most classical approach is to use a polynomial as a function (but there is also theory about other classes of functions). It is a well known theorem that if you have $n$ samples, then you can find a polynomial $f(x)=\sum\_{i=0}^{n-1} a\_i x^i$ that coincides with your samples. There are different ways how determine the $n$ parameters $a\_i$ of the polynomial.

One way to determine the polynomial is the method of Lagrange, you define for every index $i$ of you table the coefficient $$L\_i(x):= \prod\_{j=1,j\neq i}^{n} \frac{x-j}{i-j}.$$ If you look how $L\_i(x)$ behaves on the samples, then you get $$L\_i(x)=\begin{cases} 1 & x=i \\ 0 & x= \text{table index}\not= i \end{cases}.$$

Now you can easily come up with the desired polynomial by setting $$f(x):=\sum\_{i=1}^n T\[i\]L\_i(x).$$ You can bring $f$ in the form $\sum\_{i=0}^{n-1} a\_i x^i$ if you like.

Concerning you example {4,5,7}, you get $$f(x)=4 ((x - 2)/-1\*(x - 3)/-2) + 5 ((x - 1)\*(x - 3)/-1) + 7 ((x - 1)/2\*(x - 2))),$$ which simplifies to $$f(x)=4-\frac{x}{2}+\frac{x^2}{2}.$$

For further reading visit the Wikipedia page on interpolation.

Here is a final remark. The table has in almost all cases the more compact representation, and it has the faster look-up time for sure.
> 2 votes

# Answer
It is unclear what is being asked here. If the table is of finite and known length, then you can do this using a polynomial regression, although that will not give you an optimal solution. If you simply want to have any arbitrary table turned into an optimal algorithm, then you can use genetic programming to find the answer, although that's more of a meta-algorithm than an algorithm itself.
> 1 votes

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


# Question
Title: How to prove that DFAs from NFAs can have exponential number of states?
All non-deterministic finite automata can be turned into equivalent deterministic finite automata. However, a deterministic finite automata only allows a single arrow per symbol pointing from a state. Therefore, its states should be members of the power set of states of the NFA. This seems to indicate that the number of states of the DFA could scale exponentially in terms of the number of states of the NFA. However, I was wondering how to actually prove this.

# Answer
One operation that transforms an NFA into another NFA but does not do so for a DFA is reversal (point all the arrows the other way round, and swap initial states with accepting states). The language recognized by the transformed automaton is the reversed language $L^R = \\{u\_{n-1}\ldots u\_0 \mid u\_0\ldots u\_{n-1} \in L\\}$.

Thus one idea is to look for a language that has an asymmetric construction. Going forward, this language should be recognized by inspecting the first $n$ symbols, requiring only $n + O(1)$ states. Going backwards, it should be necessary to keep a memory of the last $n$ states, which requires $A^n + O(1)$ states where $A$ is the alphabet size.

We're looking for a language of the form $M\_n S M'$ where $M\_n$ consists of words of length $n$, $S$ is a nontrivial subset of the alphabet, and $M'$ doesn't provide any further constraint. We might as well pick the simplest alphabet $\mathscr{A} = \\{a,b\\}$ (a singleton alphabet won't do, you don't get smaller NFAs there) and $M' = \mathscr{A}^\*$. A nontrivial $S$ means $S = \\{a\\}$. As for $M\_n$, we require that it does not correlate with $S$ (so that the DFA for the reversed language will need to keep the memory of $S$): take $M\_n = \mathscr{A}^n$.

Thus let $L\_n = (a|b)^n a (a|b)^\*$. It is recognized by a simple DFA with $n+2$ states.

Reversing it yields an NFA that recognizes $L\_n^R = (a|b)^\* a(a|b)^n$.

The minimal DFA that recognizes $L\_n^R$ has at least $2^{n+1}$ states. This is because all the words of length $2^{n+1}$ must reach distinct states in the DFA. (In other words, they belong to distinct Myhill-Nerode equivalence classes.) To prove this, take two distinct words $u,v \in \mathscr{A}^{n+1}$ and let $k$ be a position where they differ ($u\_k \ne v\_k$). Without loss of generality, let's assume $u\_k = a$ and $v\_k = b$. Then $u b^k \in L\_n^R$ and $v b^k \notin L\_n^R$ ($b^k$ is a distinguishing extension for $u$ and $v$). If $u$ and $v$ led to the same state in a DFA recognizing $L\_n^R$ then so would $u b^k$ and $v b^k$, which is impossible since one leads to an accepting state and the other one doesn't.

Acknowledgement: this example was cited in Wikipedia without explanations. The article gives a reference to an article that I haven't read which gives a tighter bound:
Leiss, Ernst (1981), "Succinct representation of regular languages by Boolean automata", *Theoretical Computer Science* 13 (3): 323–330, doi:10.1016/S0304-3975(81)80005-9.
> 17 votes

# Answer
Consider the following family of languages: $L\_n = \\{ x\_1, x\_2, \ldots, x\_k \\# x\_{k+1}: \exists i \in \\{1, \ldots, k\\} \text{ with } x\_i = x\_{k+1} \\}$

The alphabet of $L\_n$ is $\\{\\#, 1,\ldots, n \\}$.

There is an NFA with $O(n)$ states that recognizes the language $L\_n$. It has $n$ copies. In the $i$th copy we guess that the last letter will be $i$, and check our guess. It's simple to construct such a copy with $3$ states. The only non-determinism is in the initial state.

However, there is no DFA that recognizes $L\_n$ with less than $2^{O(n)}$ states because, intuitively, a DFA must *remember* subsets of $\\{1,\ldots, n\\}$.

I'm pretty sure Sipser's book has this example.
> 9 votes

# Answer
Another example is the language of all words which miss one symbol of the alphabet. If the alphabet is of size $n$, then a NFA can "guess" a starting state and so accept the language with $n$ states. On the other hand, using Nerode's theorem it is easy to see that the size of the minimal DFA for this language is $2^n$.

This example also shows that NFAs might incur an exponential blowup under complementation. Indeed, it is known that any NFA (or even context-free grammar) for the language of all words containing *all* symbols of the alphabet must have an exponential number of states.
> 8 votes

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


title: Sensor Cover Problem

text:
# Question
Title: Sensor Cover Problem
We are given an interval $I$ and several points $p\_1,p\_2,...,p\_n$. We are also given a set of sensors. Each sensor can be represented by an interval on the same line, which means all points lie within the interval can be monitored by the corresponding sensor. The sensors may not have the equal range.

Given the current positions of points and sensors, some (or maybe none) points in $I$ may not be monitored by any sensor. We would like to ask the following question:

> Given a distance $\delta$, is it possible to shift each sensor (to the left or to the right) by a distance at most $\delta$, such that every point in $I$ can be covered by some sensor?

PS: I tried to solve this by greedy algorithm. But there is always an exception to any greedy paradigm I came up with. If we want to cover the whole interval with the sensors, I am sure it can be solved by greedy algorithm. But if we only want to "monitor" finite discrete points, is there an efficient algorithm?

# Answer
> 1 votes
Just observations that do not fit on the comments:

I made a little research, and here are what I found + some of my observations: 1) You can use exhaustive search to find whether a solution exist. \[so it is decidable\] 2) In case $\delta$ is not restricted, all you need to check is the sum of all ranges and compare it to the distance between the farthest two points. If greater or equal, then there exist a solution. 3) In case $\delta$ is restricted, then you are trying to restrict the distance traveled by sensors to at most $n \delta$. In case the sensing ranges are not equal, then this problem is still open \[1\].

I would suggest you look in the same reference for a solution for the case of equal sensing ranges. So I think a greedy solution exist.

\[1\] On Minimizing the Maximum Sensor Movement for Barrier Coverage of a Line Segment. J. Czyzowicz , E. Kranakis , D. Krizanc , I. Lambadaris , L. Narayanan , J. Opatrny , L. Stacho , J. Urrutia, and M. Yazdani.

---
Tags: algorithms, computational-geometry
---


# Question
Title: How Does Populating Pastry's Routing Table Work?
I'm trying to implement the Pastry Distributed Hash Table, but some things are escaping my understanding. I was hoping someone could clarify.

**Disclaimer**: I'm not a computer science student. I've taken precisely two computer science courses in my life, and neither dealt with anything remotely complex. I've worked with software for years, so I feel I'm up to the implementation task, if I could just wrap my head around the ideas. So I may just be missing something obvious.

I've read the paper that the authors published \[1\], and I've made some good progress, but I keep getting hung up on this one particular point in how the routing table works:

The paper claims that

> A node’s routing table, $R$, is organized into $\lceil \log\_{2^b} N\rceil$ rows with $2^b - 1$ entries each. The $2^b - 1$ entries at row $n$ of the routing table each refer to a node whose nodeId shares the present node’s nodeId in the ﬁrst n digits, but whose $n + 1$th digit has one of the $2^b - 1$ possible values other than the $n + 1$th digit in the present node’s id.

The $b$ stands for an application-specific variable, usually $4$. Let's use $b=4$, for simplicity's sake. So the above is

> A node’s routing table, $R$, is organized into $\lceil \log\_{16} N\rceil$ rows with $15$ entries each. The $15$ entries at row $n$ of the routing table each refer to a node whose nodeId shares the present node’s nodeId in the ﬁrst n digits, but whose $n + 1$th digit has one of the $2^b - 1$ possible values other than the $n + 1$th digit in the present node’s id.

I understand that much. Further, $N$ is the number of servers in the cluster. I get that, too.

My question is, if the row an entry is placed into depends on the shared length of the key, why the seemingly random limit on the number of rows? Each nodeId has 32 digits, when $b=4$ (128 bit nodeIds divided into digits of b bits). So what happens when $N$ gets high enough that $\lceil\log\_{16} N\rceil \> 32$? I realise it would take 340,282,366,920,938,463,463,374,607,431,768,211,457 (if my math is right) servers to hit this scenario, but it just seems like an odd inclusion, and the correlation is never explained.

Furthermore, what happens if you have a small number of servers? If I have fewer than 16 servers, I only have one row in the table. Further, under no circumstances would every entry in the row have a corresponding server. Should entries be left empty? I realise that I'd be able to find the server in the leaf set no matter what, given that few servers, but the same quandary is raised for the second row--what if I don't have a server that has a nodeId such that I can fill every possible permutation of the nth digit? Finally, if I have, say, four servers, and I have two nodes that share, say, 20 of their 32 digits, by some random fluke... should I populate 20 rows of the table for that node, even though that is far more rows than I could even come close to filling?

Here's what I've come up with, trying to reason my way through this:

1. Entries are to be set to a null value if there is not a node that matches that prefix precisely.
2. Empty rows are to be added until enough rows exist to match the shared length of the nodeIds.
3. If, and only if, there is no matching entry for a desired message ID, fall back on a search of the routing table for a nodeId whose shared length is greater than or equal to the current nodeId's and whose entry is mathematically closer than the current nodeId's to the desired ID.
4. If no suitable node can be found in #3, assume this is the destination and deliver the message.

Do all four of these assumptions hold up? Is there somewhere else I should be looking for information on this?

---

1. Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems by A. Rowstrong and P. Druschel (2001) -- download here

# Answer
The idea of a routing table in Pastry (and all structured P2P networks) is to minimize its size, while guaranteeing a quicker routing.

The routing algorithm of Pastry goes as follows:

Step A. A node u searches for an object A by firstly looking it up in its leaf set. Step B. If it was not available, then the query is forwarded to a known node that shares "a number of prefixes with $A$ that is at least larger than what node u shares with A". Step C. If such a record is not found, then the query is forwarded to a node in the leaf set that is numerically closest to $A$.

This is why a node $u$ stores addresses of nodes organizes its table as follows:

1.Each record in row $i$ of the routing table of node $u$ is a node identifier that shares $i$ prefix bits with the identifier of $u$.

2.The $(i + 1)^{th}$ bit of the records of a row $i$ is unique and is taken from the set $\\{0, …, 2^{b} – 1\\}$.

Example in a typical scenario: if u address is 1111 and object $A$ has identifier 4324: then here is what will happen: (we assume that it is of the base of 4. (i.e. addresses are from \[1-4\]\[1-4\]\[1-4\]\[1-4\]).

Node $u$ shares 0 prefix with object $A$. Therefore, it looks in row 0. According to rule 2 above, node $u$ stores addresses of nodes 1XXX, 2XXX, 3XXX, 4XXX, where X is a "dont-care" value. The closest among these nodes to $A$ is 4XXX. - Let's say this 4XXX is actually 4013. Then $u$ forwards to $u \_1$ with address 4013. Now you are going to repeat the same thing again at node $u \_1$ with address 4013.

To make it simpler, here is again an example of how it will go in 4013. $u \_1$ will first look for the size common prefix between 4013 and 4324 which is 1. So it goes to row 1, which contain values such that 41XX, 42XX, 43XX, 44XX. The closes among them to $A$ is 43XX. - if this was 4331 then it will be forwards toward it.

The maximum number of hops here in is 4 hops (XXXX) ! in Pastry terms, it is $log\_{2^b}$. So it is reduced as $b$ increases. But the size of the rows which are $2^b$ will increases ! -- so the authors said that $b$ = 4 is a good balance !

Practical scenarios are usually not typical as that. There may be situations in which there are not many nodes in the network. this is why we follow step C above. - However, what you need to guarantee to make this algorithm correct is that each node be connected to the closest two nodes to it (in term of identifiers). This will form a ring of ordered nodes \[e.g. 1-\>3-\>4-\>9-\>10-\>11-\>1\]
> 5 votes

---
Tags: algorithms, data-structures, distributed-systems, hash-tables
---


title: Indirection in IAS computer

text:
# Question
Title: Indirection in IAS computer
From Computer Organisation and Architecture:

> The IAS operates by repetitively performing an instruction cycle. Each instruction cycle consists of two sub cycles. During a fetch cycle, the opcode of the next instruction is loaded into the IR and the address portion is loaded into MAR. This instruction may be taken from the IBR, or it can be obtained from memory by loading a word int he MBR, and then down to the IBR, IR, and MAR.

Now here, is there part I do not understand:

> **Why the indirection?** These operations are controlled by electronic circuitry and result in the use of data paths. To simplify the electronics, there is only register that is used to specify the address in memory for a read or write and only one register used for the source or destination.

Can anyone explain this to me more intuitively? Why is this indirection being used?

# Answer
the book is describing low level machine language architecture associated with the CPU & what is also known as "microcode". it would be possible to design opcodes that use multiple registers (that does occur in some mostly uncommon cases) but most opcodes generally refer to one register or a memory location, unless its a transfer between two registers. the register number is usually encoded into the opcode in binary. that is, registers serve as a sort of small intermediate "hub" or even a small "cache" between memory and the CPU.

if one had opcodes that refer to multiple registers it quickly leads to a combinatorial explosion where the opcodes become very numerous. even a 2-way register opcode scheme takes roughly $c \cdot r^2$ encodings where $r$ is the number of registers. a 3-way register operation would require $c \cdot r^3$ etc... another scheme is to limit multiway register operations to just a few "privileged" registers, not the full set.

a good case study or example might be the 6502 CPU that has an accumulator, an auxiliary X and Y register, and some limited operations to move between them. a full/general level of register interchange is then supported by stringing several/multiple register manipulation opcodes together.
> 1 votes

---
Tags: computer-architecture
---


title: How to prove $(n+1)! = O(2^{(2^n)})$

text:
# Question
Title: How to prove $(n+1)! = O(2^{(2^n)})$
I am trying to prove $(n+1)! = O(2^{(2^n)})$. I am trying to use L'Hospital rule but I am stuck with infinite derivatives.

Can anyone tell me how i can prove this?

# Answer
> 11 votes
You can compare ratios of adjacent values: $(n+1)!/n! = n+1$ versus $2^{2^n}/2^{2^{n-1}} = 2^{2^{n-1}}$. Since $n+1\leq 2^{2^{n-1}}$ for $n \geq 1$, you can prove using mathematical induction that $(n+1)! \leq 2^{2^n}$.

# Answer
> 12 votes
Well, since this upper bound is not nearly tight, you can just use basic transformations to get

$$(n+1)!\< (n+1)^{n}=2^{\log (n+1)^{n}}= 2^{n\log (n+1)}=O(2^{n\log n})\subset O(2^{(2^n)}). $$

# Answer
> 9 votes
Using de l'Hôpital's rule on discrete functions is meaningless; you would have to use continuous extension. For factorials, that would be the Gamma function. For discrete functions, there is Stolz–Cesàro.

In either case, considering difference or differential quotients does not make sense for (super)exponential functions: since growth is at least of the same order as the function value itself, application of such rules does not simplify the situation.

In order to deal with factorials in asymtotics, Stirling's approximation is often helpful:

$\qquad \displaystyle n! \sim \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n$

Therefore, $n! \in o(n^n)$. Furthermore, since

$\qquad\displaystyle \frac{n \log n}{2^n \log 2} \xrightarrow{n \to \infty} 0$

and $e^x$ is a non-decreasing and convex function¹, we have

$\qquad \displaystyle \lim\_{n \to \infty} \frac{n^n}{2^{2^n}} = \lim\_{n \to \infty} \frac{e^{n \log n}}{e^{2^n \log 2}} = \lim\_{n \to \infty} \frac{n \log n}{2^n \log 2} = 0$.

Therefore, $n^n \in o(2^{2^n})$. Together (since $o$ is transitive) we get the desired result.

For more general advice for comparing functions, see here.

---

1. There seems to be some folklore around this technique; statements like "apply a monotone function to numerator and denominator, the limit stays the same" are not valid in general.

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


# Question
Title: Why is Uniform cost search called "uniform" cost search?
By this possibly good attempt to explain this, the "uniformity" in the Uniform cost search *is actually the uniformity of the heuristic function*.

Is this explanation correct ? If yes, then don't all `un-informed` cost searches (like `BFS`, `DFS`, etc) have no heurstic and thus, be called as "`uniform cost` searches" ?

# Answer
Truth to be told, I am not completely sure about my answer, so take it with a grain of salt:

Uniform Cost Search is just a variant of Best-First Search. Among other variants, take Breadth-First Search where $f(n)$ equals $d(n)$, its depth. This actually means that nodes are not treated *uniformly* since different paths to the same node might result very easily in different depths ---with different costs *if the costs of the operators are different among them*. Much the same happens with Depth-First Search where nodes are distinguished by the path that led to them.

What makes Uniform-Cost Search a uniform search is that nodes are distinguished just by $g(n)$ so that all paths that lead to a particular node n are considered to be equivalent (and they are indeed when seeking the optimal solution), with the first one (the one with the optimal value) being expanded, and all the others being discarded. In this regard, I would consider a number of Best-First Search variants, uniform such as $A^\*$ where nodes are uniformly treated according to $f(n)=g(n)+h(n)$ with $h(n)$ being an admissible estimate.
> 1 votes

---
Tags: terminology, artificial-intelligence, search-algorithms, heuristics
---


# Question
Title: Dynamic programming table for finding similar substrings is too large
> **Substring Diff**
> Given two strings of length $n$, $P = p\_1\dots p\_n$ and $Q = q\_1 \dots q\_n$, we define $M(i, j, L)$ as the number of mismatches between $p\_i \dots p\_{i+L-1}$ and $q\_j \dots q\_{j+L-1}$. In set notation, $M(i, j, L)$ refers to the size of the set $\\{0 \leq x \< L \mid p\_{i + x} \neq q\_{j + x}\\}$.
>
> Given an integer $K$, your task is to find the maximum length $L$ such that there exists pair of indices $(i,j)$ for which we have $M(i, j, L) \leq K$. Of course, we should also have $i + L - 1 \leq n$ and $j + L - 1 \leq n$.
>
> **Constraints**
>
> * $0 \leq K \leq |P|$
> * Both $P$ & $Q$ would have the same length
> * The size of each of the string would be at the max **1500**
> * All characters in $P$ and $Q$ are lower-case English letters.

The recursive function will have the form:

```
longest(string1, string2, allowed_mismatches) =
    {
        ... (something :P )
    }

```

The state space then has size $K^3$. With an upper bound on $K$ of 1500, the running time and space usage will be terrible... So direct dynamic programming will not work without some additional property to reduce the state space.

Ideas?

**UPDATE**

Using the ideas suggested by both Yuval and Vor, I came up with the following solution that works like a charm, running in $O(K^2)$ time and using $K$ space.

```
def longest_range_min_sum(str1, str2, start1, start2, slice_size, max_sum):
    longest = 0
    i = 0
    running_sum = 0
    while i + longest < slice_size:
        if str1[start1 + i + longest] != str2[start2 + i + longest]:
            running_sum += 1
        if running_sum > max_sum:
            if str1[start1 + i] != str2[start2 + i]:
                running_sum -= 1
            i += 1
        else:
            longest += 1
    return longest

import sys

data = sys.stdin.readlines()
num_cases = int(data.pop(0))
for ignore in xrange(num_cases):
    max_mismatches, str1, str2 = data.pop(0).split()
    max_mismatches = int(max_mismatches)
    m = n = len(str1)
    longest = 0
    for i in xrange(m + n + 1):
        if i > n:
            slice_size = m - (i - n)
        else:
            slice_size = min(i, m)
        if slice_size == 0:
            continue
        end1 = max(m, m - i)
        if i > n:
            end1 = m - (i - n)
        start1 = end1 - slice_size
        end2 = min(i, n)
        start2 = end2 - slice_size
        #print zeros_and_ones
        #print str1[start1:end1], ' - ', str2[start2:end2]
        longest_in_sub = longest_range_min_sum(str1, str2, start1, start2, slice_size, max_mismatches)
        #print longest_in_sub
        longest = max(longest, longest_in_sub)
    print longest

```

# Answer
One can reduce your problem to the following. Given a sequence of $N$ numbers, find a contiguous subsequence of length at most $K+1$ having maximal sum. This problem, in turn, is solvable in time $O(N)$.

What's the connection between your problem and mine? Let the positions of the mistakes be $I\_1,\ldots,I\_t$, and add $I\_0 = 0$, $I\_{t+1} = N+1$. The sequence in question is $J\_1 = I\_1 - I\_0,\ldots,J\_{t+1}=I\_{t+1}-I\_t$. Every $K+1$ consecutive numbers $J\_a,\ldots,J\_{a+K}$ correspond to a maximal solution for your problem of length $J\_a + \cdots + J\_{a+K} - 1$. The entire algorithm takes linear time.

Edit: This calculates the maximal $L$ such that $M(i,i,L) \leq K$ for some $i$. The actual problem wanted to find the maximal $L$ such that $M(i,j,L) \leq K$ for some $i,j$. By considering all possible shifts, we can solve this in $O(N^2)$ time and $O(K)$ space.
> 5 votes

# Answer
Using Yuval's reduction, the problem can be reformulated as "Find the largest range $(i,j)$ in a binary string $S \in \\{0,1\\}^\*$ such that the number of $1$s contained in the range is $\leq K$" (see this question).

The idea is to start with an initial valid range $(0,j)$ of length $maxlen$ and then shift the "window" $(i,i+maxlen)$ to the right, checking at every step if maxlen can be increased.

This is the pseudocode of a possible solution:

```
 INPUT : string P and Q of length n, integer K
         // string indexes are 0 based (P[0] = first char of P)
 maxidx = 0   // position of the largest interval
 maxlen = 0   // length of the largest interval
 i = 0        // current position of the "window" (i,i+maxlen)
 diffsum = 0  // sum of the mismatches in the range (i,i+maxlen)
 while ( i + maxlen < n ) do
   // update the number of mismatches of the window:
   if (P[i + maxlen] != Q[i + maxlen]) then diffsum = diffsum + 1
   if diffsum <= K
     then begin
       maxlen = maxlen + 1 // expand window
       maxidx = i  // update base pointer
     end
     else begin
       if (P[i] != Q[i]) then diffsum = diffsum - 1 // discard mismatches out of the window
       i = i + 1 // shift window to the right
     end

 OUTPUT : if maxlen > 0
            then output (maxidx, maxidx + maxlen - 1) // output the largest interval
            else output("no range with # of mismatches <= K")

```

Time complexity: $O(n)$, space $O(1)$.
> 5 votes

---
Tags: strings, dynamic-programming, substrings
---


# Question
Title: Formulating a linear program s.t. only extreme point solutions are found
If there are many solutions to a linear program s.t. the objective function is minimized/maximized (= optimal solutions are on an edge of the polytope), how can I force an LP solver to find only an extreme point solution?

# Answer
Perturb the vector of the objective function slightly. If you got multiple optimal solutions than this vector is orthogonal to a facet $F$ of the polytope that defines the feasible area of the LP. Notice that $F$ could be an edge, but also a higher dimensional flat. By changing the objective function slightly you will get an extreme point that lies on the boundary of $F$.

You might want to check that the perturbation was small enough. So check the computed point with the original objective function, if it produces the optimum.
> 3 votes

---
Tags: optimization, linear-programming
---