# Question
Title: Get the nth lexicographic string of "all" possible combinations of an alphabet
Is there a way to find the nth string of characters from an alphabet, without having to store "all" of the combinations?

**Example:**

Alphabet $A = \\{a,b,c\\}, n=12$.

All possible combinations *in lexicographic order* are $C = \\{a, ab, abc, ac, acb, b, ba, bac, bc, bca, c, ca, cab, cb, cba\\}$.

*You can see that there's no repetition of characters in any string and the empty string is not a member of $A$.*

So, the nth string is: $ca$.

Clearly, to find this I'm iterating over the set $C$.

The problem is that I have to generate all these strings, wich takes a really long time, and then search for the nth one. If the alphabet is large $(1 \leq A \leq 26 )$ the set $C$ grows too fast (not sure how much) and is impossible to store.

My questions is if *exists* a way to find these nth one, without generating all the strings.

Also, I'm not sure if this question goes in this StackExchange site.

# Answer
It is better if you include the empty string as the $0$th string in lexicographic order. Here is how you convert an index into a word.

First, we are going to find the first letter of the word, and an internal index among all words starting with this letter. We do this by counting how many words start with each letter, including the "empty letter". I'll let you figure out how to do that. In your case, we get $1,5,5,5$. This means that $\[0,1)$ corresponds to the empty sword, $\[1,6)$ to words starting with $a$, $\[6,11)$ to words starting with $b$, $\[11,16)$ to words starting with $c$.

Given an index, you locate which interval it belongs to, and record the starting character and the internal index inside the interval. In your example, $12$ belongs to $\[11,16)$ (and so starts with $c$), and its internal index is $1$.

If the index is $0$, then we are done. Otherwise, we recurse. In your example, we are left with the alphabet $\\{a,b\\}$ for which the intervals are $\[0,1),\[1,3),\[3,5)$. The current index is $1$, so the word at this level of recursion starts with $a$, and the new index is $0$. That means that the recursion ends here. The outputs is thus $ca$.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Consensus problem of distributed systems
I just started reading about distributed systems for the first time ever. There is a fairly slick proof of the impossibility of consensus in an asynchronous model using some combinatorial topology. On the other hand, there are multiple consensus protocols used in practical systems to synchronize distributed state machines like Paxos and Raft. It seems like the key to this perceived contradiction is what is called failure detection.

My question is the following: What does protocols like Paxos and Raft give up, i.e. how are they not contradicting the theorem? How does failure detection fit in here?

Are there any papers that discuss these relationships that are worth looking at?

# Answer
> 6 votes
The FLP theorem \[1\] says that

> It is impossible for a set of processors in an ***asynchronous*** distributed system to ***agree on*** a binary value, even if only a single processor is subject to an ***unannounced crash***.

There are several ways to circumvent this impossibility results, by, according to Jennifer Welch; I suggest you to read the linked webpage

1. changing the system assumptions

* Assuming a synchronous system such as in the "Byzantine Generals" problem \[2\]
    * Assuming a partial synchronous system in which failure detectors \[3\] are used
2. or changing the problem statement

* No guarantee for termination (progress) such as Paxos \[4\]
    * Randomized protocol \[5\]
    * No need to agree on a single value such as in $k$-set agreement problem
    * No need to agree on exact values in approximate agreement

---

\[1\] Impossibility of Distributed Consensus with One Faulty Process) JACM, 1985.

\[2\] Reaching Agreement in the Presence of Faults JACM, 1980.

\[3\] Unreliable Failure Detectors for Reliable Distributed Systems JACM, 1996.

\[4\] Paxos Made Simple TR. By Lamport

\[5\] Another Advantage of Free Choice (Extended Abstract): Completely Asynchronous Agreement Protocols PODC, 1983. It has just received the 2015 Edsger W. Dijkstra Prize.

---
Tags: distributed-systems
---


title: Multiple FPT Parameters

text:
# Question
Title: Multiple FPT Parameters
The class $FPT$ (fixed-parameter tractable) is defined here. However, there is only one "parameter" that is studied from the given problem/language.

Is there an equivalently defined class that can take $O(1)$ parameters? It may be useful for defining this for problems that are not driven by a single parameter. Unfortunately, there does not seem to be any material on extra parameters, including in the book Parameterized Complexity Theory.

# Answer
Yes, it's exactly the same class. You can take any constant size list of parameters and combine them just using addition. This is particularly obvious in Flum and Grohe's formulation of $FPT$ where problems are equipped with a parameterization $\kappa : x \rightarrow \mathbb{N}$.

So for example, you can take a problem with two parameters $k$ and $r$, and produce a combined parameter $k+r$ (or indeed using any moderately sane function), as if the running time is bounded by some function $f(k,r)$ (we can ignore the $|x|^{O\*(1)}$ part for the moment)), then it is bounded by the function $f(g(k+r),h(k+r)) = f'(k+r)$, where $g$ and $h$ do whatever is necessary to turn $k+r$ into a sufficiently usable form (in most cases, this is nothing).

Note that this produces the intuition you expect. If $(\Pi,\kappa) \in FPT$, then it is still in $FPT$ when you add a new parameter, however it is not necessarily true that if $(\Pi,\kappa\_{1} + \kappa\_{2}) \in FPT$ then either $(\Pi,\kappa\_{1}) \in FPT$ or $(\Pi,\kappa\_{2}) \in FPT$.

As an example, deleting $k$ vertices to obtain an $r$-regular graph is $W\[1\]$-hard with parameter $k$, $paraNP$-complete with parameter $r$ but in $FPT$ with parameter $k+r$.
> 3 votes

---
Tags: complexity-theory, parameterized-complexity
---


# Question
Title: Is it possible to implement a dictionary with efficient access according to insertion order?
I am trying to build a generic data structure that needs to hold keys and values and in the same time keep track on the indices in which keys and values were put in, like arraylists do but in a complexity of $O(\log n)$ or less.

I tried to work around a solution to this problem and created various TreeMaps that has Integer indices and values and vice-versa, and the same with keys.

Just to make it more clear, the indices symbolize the insertion order from the user. So if I had 3 elements then their index values are 0, 1, 2 and if element 0 was deleted then I need to push 1 to 0 and 2 to 1 and a new element would be added with index 2.

My problem is when I remove a key and its value, if I want to insert the next key and value in the right index I have to make sure all the old ones were set back by 1. I don't know how to do it and not to fall into $O(n)$ complexity.

My goal is to use existing data structures and mix them to get this result, please take a look at the methods I implemented as I need those.

What I am asking is how can I create a data structure for keys and values that has the `put`, `remove`, `get`, `getValueByIndex`, `getKeyByIndex`, `getIndexByKey` methods in it while each method takes $O(\log n)$ or less and the indices change at each deletion.

Is it possible? And if so what is the mixture of Data-structures to create this?

# Answer
> 6 votes
To summarize, this is what you require:

* a dictionary that
* offers `find`, `add` and `delete` in $O(\log n)$ time and also
* `GetByIndex`, `KeyByIndex` and `IndexByKey` in $O(\log n)$ time, where the index is determined by insertion order.

The first part is easy: use any balanced search tree. Say we use AVL trees.

For the second, we can use a second tree but use an increasing counter as key. With a small change to the data structure, we can find the $i$th element in $O(\log n)$ time (rank selection). Thus, we don't *have* to change any indices; the tree structure maintains the order for us.

We can further link the two AVL trees back and forth.

Assuming we have an implementation `AVL` which provides efficient `select` and `rank` (zero-based) and has a field for crosslinks, this would be rough pseudocode:

```
class IndexedDictionary {
  dataTree  = new AVL()
  indexTree = new AVL()
  nextId = 0

  add(key, data) {
    dataNode  = dataTree.add(key, data)
    indexNode = indexTree.add(nextId, data)
    dataNode.crosslink = indexNode
    indexNode.crosslink = dataNode
    nextId += 1
  }

  delete(key) {
    i = index(key)
    dataTree.delete(key)
    indexTree.delete(indexTree.select(i).key)
  }

  find(key) {
    return dataTree.find(key).value
  }

  get(index) {
    return indexTree.select(index).value
  }

  key(index) {
    return indexTree.select(index).crosslink.key
  }

  index(key) {
    return indexTree.rank(dataNode.find(key).crosslink.key)
  }
}

```

Of course, `delete(index)` can be implemented similarly to `delete(key)`. Delete can be implemented faster if you add an operation `delete-ith` to AVL, and have AVL-`delete` return the removed node.

---
Tags: data-structures, efficiency, dictionaries
---


# Question
Title: Could an NP-hard problem have a mechanical or physical solution method?
Is there any NP-hard problem that we can find a mechanical "polynomial time" solution to? For example, suppose we construct a graph out of something physical, e.g. we have have pipes through which we can move water. If this pipe system was suitably built, could we solve say some routing problem by seeing if water flows from one node to another?

So by a mechanical solution, I mean a physical configuration and not a computer program, i.e. I am not looking for a computer algorithm. I also used "polynomial mechanical solution" to describe a solution on a physical device that runs in time polynomial in the order of the input. For example, a piping system could yield the answer in "number of nodes squared" seconds.

# Answer
Scott Aaronson examines "mechanical" solutions to NP-complete problems in the odd and entertaining paper "NP-complete Problems and Physical Reality". The paper is mostly theoretical discussions of increasingly exotic physical systems but Aaronson does indulge in a bit of empiricism; he tries to use soap bubbles to find Steiner trees. The results were negative:

> In general, the results were highly nondeterministic; I could obtain entirely different trees by dunking the same configuration more than once. Sometimes I even obtained a tree that did not connect all the pegs.
> 7 votes

# Answer
No.

Unless $P=NP$, it's unlikely that any mechanical process can solve an $NP$-hard problem efficiently. Given a mechanical approach to solving a problem, we could run a physics simulation on a computer to get the same result.

Of course this depends on being able to simulate what happens in the real world efficiently. In order for "mechanical polynomial time" to be stronger than "polynomial time" you'd need to find some physical process that can not be simulated efficiently. One possible candidate would be quantum mechanics but that doesn't seem to be what you're asking about (and it is speculated that even quantum computing doesn't allow one to solve $NP$-hard problems efficiently).
> 7 votes

# Answer
I'd say "perhaps", but it depends on what you mean by "polynomial mechanical solution". For example, it is possible to sort in constant time in one sense: Given a collection of pieces of spaghetti of various lengths, one could sort them by length by picking up all of them, holding them vertically, and bringing them down on a flat surface. Having done that, the pieces will be sorted.

Now there are lots of perfectly reasonable objections to this algorithm, but in one sense, it does accomplish sorting in constant time, which we know is not possible, if for no other reason than that in the usual computational model it would take $n$ steps just to inspect $n$ strands to know their lengths.

Frankly, I don't know how one might apply this sort of construction to an NP-hard problem, but at the same time I'm not sure that it would be impossible. My feeling is that if one could come up with a solution like this, it would likely be regarded (as the spaghetti sort example) as nothing but a mildly amusing construction.
> 1 votes

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


title: Symmetric protocols for consensus

text:
# Question
Title: Symmetric protocols for consensus
All the consensus algorithms that I've seen always depend on having a leader elected with all queries directed at the leader (assuming that we're not OK with getting back stale data). Are there any efficient algorithms that are completely symmetric, i.e. which do not elect a leader and therefore allows querying any server in the cluster?

Since a given server doesn't crash very often, from an engineering perspective it would seem like electing a leader is simpler because you can worry separately about what to do when the leader goes down, which would seem to allow for more modular protocol design. On the other hand, if all the queries are directed at one sever, then this server will get hammered, since in addition to all queries, it will have to send updates to all other servers in the cluster.

My questions can be phrased as follows: is dependence on a leader seen as a problem? Are there some fundamental issues with this approach in addition to problems with load? Do we have some fundamental problems when running a leaderless protocol? Do we know if there exists efficient leaderless protocols?

# Answer
This paper \[1\] provides a consensus algorithm in a model where, in each round, each node can query 2 randomly chosen nodes and update its own value accordingly. As this is essentially a balls-into-bins scenario, the load balancing will be very good. It is shown that this "converges" to a consensus within $O(\log n)$ rounds even if an omniscient adversary corrupts up to $O(\sqrt{n})$ values of the nodes in *each* round.

I would say the main reason why many protocols have a leader is for having a coordinator that orchestrates the progress of the protocol. Note that most classic work on consensus focuses on achieving the best possible fault-tolerance, whereas load balancing as not always a primary concern.

\[1\] Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, Christian Scheideler: Stabilizing consensus with the power of two choices. SPAA 2011: 149-158 http://www.cs.ox.ac.uk/people/leslieann.goldberg/papers/SelfStabilizing.pdf
> 2 votes

---
Tags: distributed-systems, consensus
---


# Question
Title: How can P=NP relate to creativity and proof automation, as said by Scott Aaronson?
I read several times of Scott Aaronson saying that P=NP implies that human creativity is boring and something like that, and that P=NP has something to do with proof automation. I don't get his argument, despite having studied basic complexity theory. What is he talking about?

# Answer
There is a relatively often cited quote

> "If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett."

However, Scott has later distanced from it:

> Given how many confusions and weird misinterpretations it’s spawned, **I, Scott Aaronson, hereby formally disown my statement about how “everyone who could appreciate a symphony would be Mozart” if P=NP.**

(source)
> 4 votes

# Answer
Here is a take on the idea in your question (trying not to put words in anyone's mouth). NP can be viewed as the class of statements that have "reasonable" proofs. Here statements are technically of the form "this string is in this language" and the proof is the "witness"/"certificate", and by "reasonable proof" I mean of polynomial size and verifiable in polynomial time.

P can be viewed as the subset of NP for which these proofs can be found *efficiently* and *mechanically* by an algorithm. If $\mathsf{P}=\mathsf{NP}$, then the algorithm removes the need for human creativity in finding the proof. If $\mathsf{P} \neq \mathsf{NP}$, then any algorithm would take a very long time and to get a fast proof of the statement, we need some heuristic like human creativity. In theory, anyway.

To make this viewpoint really bite, you'd want to connect the statements we want to actually prove to $\mathsf{NP}$ languages, which, like vzn, I haven't seen completely formalized. But I think the idea would be to consider a verifier that knows all of the axioms and rules of logic in your proof system and can check that each step in a given proof is an application of one of these axioms or logical rules to the previous step. Therefore, the language of interest is the set of true statements that can be deduced in your logic in $p(n)$ many steps, for a fixed polynomial $p(n)$. If $\mathsf{P}=\mathsf{NP}$, then there is an algorithm that checks if a given statement is in this language: given the statement we want to prove, it quickly and mechanically deduces whether it is true and provable in $p(n)$ steps.

It would be great if any experts could comment or improve this response....
> 1 votes

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: A and B are Turing recognizable, is A - B Turing recognizable?
If A and B are Turing recognizable, is A - B Turing recognizable?

I think that A - B would be Turing recognizable because they're both in the space of Turing recognizability. For example, if A is context free and B is a regular language A - B would result in a language that is sill Turing recognizable.

However, does this become a question about emptiness? Two Turing recognizable languages equal to each other leave an empty set. Is the empty set Turing recognizable? I would still say yes.

Not sure if I'm thinking about this correctly...

# Answer
Suppose that $L$ is a Turing-recognizable language and $L^C$ is its complement. Let's assume, for the purposes proof by contradiction, that $L^C$ is also Turing-recognizable. This means that a recognizer exists for each of these two languages: we will call them $M\_L$ and $M\_{L^C}$. How might we use these two recognizers to do something absurd?

For starters, we can construct a *decider* for the language $L$. Given any string $w$, we can use it as input for both $M\_L$ and $M\_{L^C}$. $M\_L$ will halt and accept if $w$ is in $L$ (and halt and reject or loop forever if not). Conversely, $M\_{L^C}$ will halt and accept if $w$ is in $L^C$ (and halt and reject or loop forever otherwise). In any case, our constructed machine *will halt with a decision about $w$*, and so we've proven the existence of a decider for $L$.

By assuming that any Turing-recognizable language $L$ is closed under complement, we can show that $L$ is also Turing-decidable, which implies that $R=RE$. So we must conclude that Turing-recognizable languages are not closed under complement!

If they're not closed under complement, is it possible for them to be closed under set difference? (Hint: the set of Turing-recognizable languages *is* closed under intersection. Can you rewrite $A-B$ in terms of complement and intersection?)

(Solution: $A-B$ can be written $A \cap B^C$; loosely speaking, both describe the set of elements which belong to $A$ but not to $B$. Since set difference can be expressed using intersection and complement operators, and since Turing-recognizable languages are not closed under complement, we conclude that Turing-recognizable languages are not closed under set difference.)
> 5 votes

---
Tags: computability, closure-properties, semi-decidability
---


# Question
Title: Irregularity of L = {a^i b^(j+3)| i!=j }
I have a question to find out that $L = \\{a^i b^{j+3}\mid i\ne j \\}$ is regular or not. I know that it is not regular. I tried with pumping lemma but I am finding just a specific number of $v$'s in $u v^i w$ that not satisfies the language condition, but not ALL $v$'s. What are the best choices for $i$ and $j$ to prove with pumping lemma that this is not a regular language?

# Answer
When you get stuck trying to prove a language is not regular by the Pumping Lemma, as in this example, because there doesn't seem to be a good choice of $u,v,w$, it's sometimes helpful to use closure properties first, to transform the problem. This is a good example of when this paradigm is useful.

We'll do this by contradiction. Suppose that $L$ were regular. Then since regular languages are closed under complement, $\overline{L}$ would be regular. Now $\overline{L}$ isn't particularly easy to describe, since it contains strings like $bababbba$, but what is $\overline{L}\cap a^\*b^\*$? This is just $a^nb^{n+3}=a^nb^nb^3$. Since regular languages are closed under intersection and $a^\*b^\*$ is regular, that would mean that $a^nb^nb^3$ would be regular. I'll bet you can now do a pumping lemma proof to show that this language wasn't regular.
> 3 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


title: An AC$^1$ circuit for 2-SAT

text:
# Question
Title: An AC$^1$ circuit for 2-SAT
We know that $NC^1 \subseteq NL \subseteq AC^1$ and that 2-SAT is complete for $NL$.

> How does one construct an $AC^1$ circuit for 2-SAT?

Recall that $AC^1$ circuits have $O(\log n)$ depth where $n$ is the number of bits in the input.

I have read Herbert Vollmer's book on Circuit Complexity as well as the chapter in Arora-Barak's book. Still, appears to be very challenging.

For example, we can fix the length of the input for each variable (say $3$ bits). For each literal, let the first bit indicate whether it is positive or negative. So each literal is represented by $1+3 = 4$ bits.

Thus the negative literal $\neg x\_1 \equiv 0001$ and the positive literal $x\_2 \equiv 1010$.

Let FALSE $\equiv 0000$ and let a unit clause (a clause with one literal) ($x\_i$) be represented as $(x\_i \lor FALSE)$.

Hence a 2SAT formula $\phi = (x\_1 \lor \neg x\_2) \land (x\_5 \lor \neg x\_6)$ would be represented as

$11110$-$1001$-$0010$-$1101$-$0110~ $ as input to the circuit (dashes just added for reading clarity only).

The first $4$ bits $1111$ mean that each literal is represented by $4$ bits --- the fifth bit ($0$) is just a separator before the actual input $\phi$ begins.

And then we have to implement an algorithm in the (C $\log n$) levels above the input level, for some constant $C$, using $AND$, $OR$ and $NOT$ gates, allowing unbounded fan-in.

Is this going in the right direction?

# Answer
> 5 votes
The proof that $\mathsf{NL} \subseteq \mathsf{AC}^1$ is constructive, giving an $\mathsf{AC}^1$ circuit for directed reachability. Since directed reachability is $\mathsf{NL}$-complete and 2SAT is in $\mathsf{NL}$, there is an $\mathsf{AC}^0$ reduction from 2SAT to directed reachability. Combining the $\mathsf{AC}^1$ circuit for directed reachability with the $\mathsf{AC}^0$ reduction from 2SAT to directed reachability, we obtain an $\mathsf{AC}^1$ circuit for 2SAT.

It might be better, however, to construct such a circuit directly using ideas from the proof of $\mathsf{NL} \subseteq \mathsf{AC}^1$. This could result is a smaller and simpler circuit.

The OP also asks whether HornSAT has $\mathsf{AC}^1$ circuits. Since HornSAT is $\mathsf{P}$-complete and we believe that $\mathsf{AC}^1 \neq \mathsf{P}$, the answer is probably no. The OP suggests using the switching lemma to prove this. However, the switching lemma only works for circuits of depth $O(\log n/\log\log n)$.

---
Tags: circuits
---


# Question
Title: Is this method of proving non-regularity is equivalent to pumping lemma?
I find it really difficult to prove non-regularity of a language using `pumping lemma`. I do understand that regular language is the language that can be expressed using DFA/RE. So if I can't create DFA/RE for language can I use that as proof of it's non regularity?

For example, following is an attempt to create a `DFA` for
`0^P`
where `p` is prime number.

Following machine accepts `2,3,5,7` which are primes. But it also accepts those which are not primes. Can it be considered as proof of non regularity of said language?

# Answer
> 3 votes
Here is how your method of proof works on the (regular) language $\\{0^2,0^3,0^5,0^7\\}$. I tried to construct a DFA for this language – the DFA accepting all strings, but while it accepts $0^2,0^3,0^5,0^7$, it also accepts other strings. What when wrong?

To prove that a language is not regular, we have to show that it is impossible to construct a DFA for it. Having tried and failed is not enough – maybe it's just difficult? For example, people believe that P$\neq$NP, but so far we haven't been able to prove this. Does this show that P=NP?

How, then, can we show that a language is not regular? One way is to construct the "canonical" DFA, and this leads to the Myhill–Nerode criterion (look it up). This method is *complete* in the sense that if a language is not regular, then you can prove this using this method.

Another technique is the pumping lemma, which is popular for historical reasons. The pumping lemma is not complete: there are irregular languages which satisfy the conditions of the pumping lemma, and so the pumping lemma cannot be used to prove that they are not regular.

There are other techniques as well, for example using closure properties of regular languages, or using structure theorems. Your specific language is a *unary language* (a language over an alphabet with size 1), and we have a complete structure theorem for these languages, which can be used to show that your language is not regular.

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


title: How n (1+b) is not prime?

text:
# Question
Title: How n (1+b) is not prime?
Here is the complete proof taken from this link

How do I convince myself that `n(1+b)` is not prime when b\>=1? Here is what I did: if n is 3 and b is 3. Then resulting string 111 111 is prime. Is this how it should be done it in proofs? The way I see is this. If n(1+b) is not proved for even one set of values then I can say it is not prime. Set of values in this case was n =3 & b = 3.

Is this approach of understanding poofs is right?

# Answer
> 2 votes
$n(1+b)$ is not prime for any integers $n\>1$ and $b\geq 1$, simply because it is divisible by both $n$ and $(b+1)$, and the conditions on $n$ and $b$ guarantee that neither of these factors is $1$.

Note that we must have $n\>1$, since $n\geq p$ where $p$ is the number of states in an automaton which we suppose to exist that accepts the given language. Since a $1$-state automaton can only accept $\emptyset$ or $\Sigma^\*$, we must have $p\>1$.

---
Tags: number-theory, primes
---


# Question
Title: Counting Number of arrays where sum of ith row is greater or equal to (i-1)th row
I am working on a problem where I am supposed to count the number of arrays of size $N\times M$ where the sum of elements in the $i$-th row is greater than or equal to the the sum of elements in the $(i-1)$-th row. And the the sum of elements in $N$-th row (the last row) is less than or equal to $M$. All the elements are non negative integers.

For example, $N=2, M=2$ there are 25 solutions.

The solution that I have worked out so far is that for a row to have sum less than $M$, the number of possible ways is $C(2M,M)$. But I am unable to implement the remaining constraint.

# Answer
The case where $N=2$ is fairly easy. For $M\ge N$ we'll have an array $$\begin{array}{ccccc} a\_{1,1} & a\_{1,2} & a\_{1,3} &\dotsm & a\_{1,M}\\ a\_{2,1} & a\_{2,2} & a\_{2,3} &\dotsm & a\_{2,M}\\ a\_{3,1} & a\_{3,2} & a\_{3,3} &\dotsm & a\_{3,M}\\ &\dotsm & & & \\ a\_{N,1} & a\_{N,2} & a\_{N,3} &\dotsm & a\_{N,M}\\ \end{array}$$ Define $t(k,M)$ to be the number of integer solutions of $x\_1+x\_2+\dotsm+x\_m=k$ with all $x\_i\ge 0$. The stars and bars theorem tells us that $$ t(k,M)=\binom{M-1+k}{M-1} $$ Then if we let $C(N,M)$ denote the number of solutions to the original problem, it's not hard to see that for $N=2$, $$\begin{align} C(2,M) &= \sum\_{i=0}^M\left\[t(i,M)\sum\_{j=0}^it(j,M)\right\]\\ &= \sum\_{i=0}^M\binom{M-1+i}{M-1}\sum\_{j=0}^i\binom{M-1+j}{M-1}\\ &= \sum\_{i=0}^M\binom{M-1+i}{M-1}\left\[\binom{M-1}{M-1}+\binom{M}{M-1}+\dotsm+\binom{M-1+i}{M-1}\right\]\\ &= \sum\_{i=0}^M\binom{M-1+i}{M-1}\binom{M+i}{M} \end{align}$$ The last step above uses a fairly well-known result on the sum of a column of Pascal's triangle. So finally we'll have $$ C(2,M) =\binom{M-1}{M-1}\binom{M}{M}+\binom{M}{M-1}\binom{M+1}{M}+\dotsm+\binom{2M-1}{M-1}\binom{2M}{M} $$ For $N=M=2$ we have $C(2,2)=1+6+18=25$, which agrees with your example.

---

**Added yet again**. For a (not particularly useful) general form, it's not hard to see that $$ C(N,M)=\sum\_{0\le i\_1\le i\_2\le\dotsm i\_N\le M} t(i\_1,M)t(i\_2,M)\dotsm t(i\_N,M) $$ In this expression, each of the $i\_k$ represents the possible sum of the $k$-th row.

I asked on Math.SE whether the expression for $C(2,M)$ had a closed form and the consensus was that it didn't (although it can be expressed as a hypergeometric series, for what that's worth).
> 2 votes

---
Tags: algorithms, permutations
---


# Question
Title: Solving the graph colourability problem in polynomial time if the equivallent decision problem is in $P$
For the graph colourability problem, we are given a graph and our goal is to find a colouring of the graph with the fewest possible number of colours so that no two adjacent vertices have the same colour. This problem is known to be NP complete.

Suppose that we have an algorithm $A$ that runs in polynomial time and tells us whether our graph can be coloured by using $\leq k$ colours. We can query this algorithm as many times as we want.

Would this imply that the graph colourability problem also be in $P$?

My approach would be to begin querying for $k=1$, and then keep incrementing $k$ until we get a positive response from $A$, which is going to be the answer to our problem.

However, if we know how many colours we can use to colour our graph, how do we then actually colour each node? Is there a known algorithm for this?

# Answer
Hint: If there is a valid coloring in which vertices $x,y$ get the same color then the graph resulting from merging $x,y$ into a single vertex has the same chromatic number. Otherwise, you can add an edge between them (if it doesn't already exist). Either way, the graph "simplifies" (either the number of vertices decreases, or the graph gets closer to a clique).
> 1 votes

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


# Question
Title: Can a language be Turing Complete if its only provision for unlimited code/memory is through recursion?
We've developed an esoteric language. In this language, a program contains a static amount of code, and a static amount of storage space. However, parts of the program can recurse, so the interpreter will spawn another copy of a subset of the code and additional storage space to match. Can this language be Turing Complete?

# Answer
Given your very strict interpretation of limited memory size, limiting also the size of integers, one consequence is that it is not possible to play encoding games with integers (such as Gödel enumerations or encodings).

Another consequence is that you cannot have a way of retrieving the address of a memory location in order to make pointers. The reason is that unbounded recursion implies that memory addresses will have unbounded size (which is a bit inconsistent on the implementation side, but I guess I have to ignore it). If there was an instruction to retrieve the address of a variable, the space needed to store this address could well exceed all of the memory available for a given recursive call. Hence there is no hope of manipulating addresses.

Hence, each recursive call can only access a finite amount of information, say $n$ bits, which may be seen also a one of $2^n$ symbols. There is as much information, i.e. one of those symbols, memorized for each of the previous calls, but not accessible on the recursion stack.

Of course a little bit of information is passed as parameter at each recursive call, and some is returned when it terminates.

So all this pretty well describes a pushdown automaton.

Hence **all you can do is recognize or generate context-free languages, or some equivalent computation**. You are pretty far from Turing completeness.

But if your model allowed storing pointers to local variables, then, even without Gödel encodings in integers, you could have Turing completeness.
> 7 votes

---
Tags: programming-languages, turing-completeness, language-design
---


# Question
Title: What is the origin of the client server model?
I was wondering if someone knew the origin of the client server model. Where does the term come from (paper, software application, book)?

# Answer
This is a good question.

It appears that the term **server** was commonly used already in 1960s. For example, RFC 5, which was published in **1969**, already uses the term, and it seems that it was in a common use already back then.

However, the term **client** in this context seems to be much more recent; the earliest references that I was able to find are from **1978**. The following paper seems to be the earliest hit:

* Jay E. Israel et al. (1978): Separating Data From Function in a Distributed File System.

I did not find the full text of this paper. It seems that it was published in the Proceedings of the *Second International Symposium on Operating Systems Theory and Practice*, which was held in October 1978. A preview is available here; I am quoting the relevant part (emphasis mine):

> The distributed file system (DFS) is so named because it is implemented on a cooperating set of **server** computers which together create the illusion of a single, logical system. The other computers in the network that use the DFS for creating, destroying, and randomly accessing files are called its **clients** (we employ the term "user" to stand only for human users; programs that access the DFS are always called clients).

This looks like a good candidate of the first paper that uses the client-server terminology. Note the way it is written: the authors clearly assume that the reader is familiar with the term "server", but they are here introducing the unfamiliar term "client"—so strange that they have to justify its use.

---

I checked various resources, including the digital libraries of IEEE and ACM, and I was not able to find any hits that predate 1978. However, already in 1979 there was at least one paper that is boldly using the new term "client" in its title. Unsurprisingly, it is citing Israel et al. (1978).

OED knows the term, but again the earliest use is by Isreal et al.

---

**Edit:** Here are some further comments on the term "server". Looking at various papers written in 1960s, it seems that the term "server" was primarily used in the context of queueing theory; there a "server" can be any kind of entity that provides some service.

Whenever a "server computer" was mentioned in computer science papers written in 1960s, it was typically related to the applications of queueing theory in the context of computer systems. Perhaps this is the origin of the term in our field?

I am not sure what is the first instance of a "server" used in this sense without any direct connection to queueing theory.

However, RFC 5 from 1969 that I mentioned above seems to be already using the term "server" in the context of client-server systems and computer networks, without any explicit references to queueing theory. Of course the term "client" was not introduced yet, so they used the words "server-host" and "user-host".
> 18 votes

# Answer
Originally the "Client-Server" model of computing was a little different to the dumb terminal to mainframe earlier models and the later web browser to backend web server models.

With Client-Server systems there was a sharing of processing between parts of the system, with the server handling the data and the client retrieving this data and then performing additional processing on it and managing it's graphical display.

One of the first examples of this was with Oracle Forms 4.0, released in 1992. An Oracle database server responded to requests over a TCP/IP network from a PC-based client running the Oracle Forms application. Data management and retrieval was handled by the server and the client processed the returned data and the user interface to this.

It was during the development of Oracle Forms 4.0 that I first heard the phrase "Client-Server" used during a customer familiarisation event at Oracle's HQ in Redwood Shores CA in May 1991. The words "server" and "client" were often mentioned but had not previously been coined linked together. Richard Moulding of the British company BT first started to use the phrase Client-Server during discussions. This was quickly picked up by the other participants, it then making its way into product literature and hence into general use in the computing community.

Later web-based client-server systems initially had lighter clients due to the simple web browsers available. The client then being limited to displaying the interface prepared on the server. Later browsers with Java and scripting tools enabled data to be manipulated in the browser, a more similar model to corporate client-server systems like Oracle Forms.
> 0 votes

# Answer
Perhaps it's easier to understand client-server computing and distributed processing if one looks at the history of networking. The ARPAnet came into being in the 1960s using Honeywell minicomputers as message processors. By 1973 ARPAnet supported transferring files across the network.

Digital Equipment Corporation (DEC) released DECnet 1.0 in 1975. It supported network connections (LAN and WAN) between minicomputers and mainframes, providing functionality such as file transfers, remote logins and virtual terminals. In the late '70s, Datapoint shipped ARCnet, a LAN that supported resource sharing and file serving.

Before the IBM PC arrived, a number of companies were selling CP/M systems (8-bit computers). Those micro systems typically had floppy drives. Because hard drives were expensive, there was a demand for a solution for sharing a hard disk. Several companies jumped into the market with file server products that would enable a CP/M computer to share a hard drive. Local area network operating systems from Novell and Corvus supported file sharing by CP/M computers before the IBM PC gained widespread acceptance, and later added disk and printer sharing for PCs.

Novell was founded in 1979 and it initially manufactured and sold hardware, including smart terminals, a dot matrix printer and the Nexus, a high-end CP/M-based workstation ($13-$18,000 dollars).

Novell's claim to fame for the Nexus products was that they would eventually connect to a Novell LAN that was in development. Novell's printers, terminals and Nexus computers did not sell well so Novell's leadership decided to re-organize the company and after 1983 it focused on software, file servers and boards for networking. Novell NetWare sales exploded in the 1980s. Novell had the predominant file server in terms of sales, but it was not the first file server

In 1984 Sybase was founded and it introduced the SQL client-server architecture, distributed processing with the SQL database on a server and applications running on clients that sent query requests to the server.
> 0 votes

---
Tags: terminology, reference-request, distributed-systems, history
---


# Question
Title: Prove that Ford-Fulkerson can decide if there is more than one min cuts
Probelm: Deciding whether a network flow graph has more than one min cut.

Optimal running time: O(V^2\*E).

I trying to prove the correctness of the next algorithm: run Dinitz to find max-flow and build the residual graph. One min cut will be all the vertices reachable from s (as T will be all other vertices) and second min cut will be all vertices reachable from t in the reverse graph. If both cuts are equal, than there is only one min cut. Otherwise, there are more.

I'm struggling proving this algorithm. I cannot find a reason for ensuring that I'll find another min cut if it exists. I tried to prove a lemma saying that a network flow graph has a unique minimum cut, iff each vertex is reacable from s or t in the residual graph. But I'm stuck proving the \<= direction.

# Answer
> 2 votes
The reason you can't prove your proposed algorithm correct is because.... it actually is not a correct algorithm for this problem. If you try running it on a small example of network flow graph with more than one unique min cut, you'll see immediately what goes wrong. In particular, this algorithm fails on *every* flow graph that contains more than one min cut, so the problem is not at all subtle.

Perhaps it would be helpful for you to recall properties of the min-cut that is produced by applying the min-cut/max-flow theorem to the flow output by a max-flow algorithm. In particular, define $S$ to be the set of vertices reachable from $s$ along some path in the residual graph, and $T$ to be the set of vertices that can reach $t$ along some path in the residual graph. Then $S \cap T = \emptyset$ and $S \cup T = V$, and $(S,T)$ is a $(s,t)$-cut. In particular, $(S,T)$ is the cut that is selected by the min-cut/max-flow theorem (for this flow). Good.

Now notice that $T$ is exactly the set of vertices that are reachable from $t$ in the reverse of the residual graph. Therefore, your proposed algorithm amounts to finding a max-flow, computing the sets $S$ and $T$, then checking whether $S$ and $T$ are the same cuts. But the only way to interpret $S$ as a cut is as the cut $(S,V\setminus S)$, and the only way to interpret $T$ as a cut is as the cut $(V\setminus T, T)$ -- and these are always exactly the same cut! In particular, $V \setminus S = T$ and $V \setminus T = S$, so both of these cuts will always be exactly the same cut -- even if the flow graph admits multiple different cuts, your procedure will only find one of them.

In short, your proposed lemma is wrong, and the method you suggest is not a correct algorithm for this problem. The good news is that it *is* possible to build a correct algorithm for this problem, within the running time that you specify; see my comments for more about how to do that -- but since you said in the question you don't want some other algorithm for this task, you just want to know if your proposed algorithm is correct, I won't try to elaborate in any further depth.

---
Tags: algorithms, correctness-proof, network-flow
---


# Question
Title: How does this instruction format limit the number of memory addresses?
I have come across a question like this. And I don't have any idea how to solve this.

> Suppose a machine with instruction format of the form `opcode A,B,R` where `A` and `B` are main memory addresses and `R` is a register. If there are 20 registers in the machine, how many addresses are possible to have in the main memory? An instruction occupies 32 bits and the instruction set has 32 opcodes.

Anyone have an idea?

# Answer
I think one of my friend have managed to solve this one.

20 registers need 5 bits. 32 opcodes needs 5 bits.

therefore remaining bits for main memory=32-5-5 =22 there are two locations in the instruction. so, bits for memeory location = 22/2=11

so, total memory locations = 2^11=2048

reason to get the 5 bits: to represent 20 registers you need at least 5 bits.it means 2^5 = 32.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: How do calculators convert from decimal to fraction?
*Sorry if this question is either obvious or ignorant. I am a high school student with only the computer science knowledge I have taught myself.*

Calculators have a function that can convert numbers from decimal to fractional equivalents. For example, 0.5 becomes 1/2, and 0.666666667 becomes 2/3.

I doubt that the calculator has these values kept in storage to look up, so there must be an algorithm for this to be determined.

The simplest possible algorithm I can imagine would resemble this:

```
for (double i = 0; i < someLimit; i++){
    for (double j = 0; j < someLimit; j += 1){
        if (i / j == decimal){ //return these values }
    }
}

```

This seems far too inefficient to be the algorithm used by calculators. Even on low power scientific calculators, this operation completes quickly.

**How do calculators calculate the fractional equivalent of a decimal?**

# Answer
> 5 votes
I don't know what calculators actually use, but there are definitely better algorithms than your brute force search.

There are several notions of “best approximation” of a real number by a rational. Depending on how you rate the benefit of a good approximation compared to the cost of a large denominator, you get different notions.

One of these is the best approximation with a bounded denominator: given $x \in \mathbb{R}$ (real to approximate) and $n \in \mathbb{N}^\*$ (denominator bound), find $p/q$ with $p \in \mathbb{Z}$, $q \in \mathbb{N} \cap \[1,n\]$ that minimizes $x-p/q$. The sequence of best approximations for increasing values of $n$ turns out to be relatively easy to calculate and to have other nice mathematical properties: it's the continued fraction expansion of $x$. The continued fraction expansion is a way to construct an infinite sequence of rationals that converges to $x$, and its terms are exactly¹ the best bounded-denominator approximations of $x$. The series is easy to calculate incrementally.

In a calculator, you don't necessarily want the best approximation in that sense: what denominator bound would you pick? If you pick one that's too low, you'll miss some “interesting” rationals. If you pick one that's too large, you end up treating basically everything as some large integer divided by a power of ten.

¹ <sub> Except for some boundary effects when $x$ is rational, see a reference for details. </sub>

# Answer
> 2 votes
Back in the CS pleistocene, early calculators like the HP35 (1972-1975) had a chip that supported bit shift, add, subtract, test for negative, and some memory. In those days, many of the mathematical operations like multiplication, division, trig and hyperbolic trig functions were done with what were known as CORDIC (COordinate Rotation DIgital Computer) algorithms. Some people find this interesting enough to look up: how on earth do you compute sines with such a limited collection of operations?

Now, of course, a modern calculator (or a smart phone, or, probably even a thermostat) has computational power that you couldn't have bought at any price 40 years ago, so I suspect that your suggested answer might very well be what they use today, perhaps with the embedded Java Virtual Machine that's part of the calculator.

---
Tags: algorithms, number-formats
---


# Question
Title: Top-down typing strategy - is there a name for this?
In most statically typed languages, each expression has an intrinsic type. E.g. in Java, `3` is an int, `3.0` is a double, `3+3.0` is also a double. Types do not depend on the context of the expression.

However, in the CSS type system described in the spec, some expressions have a type depending on the context. For example, the `red` token can be a `<color>`, a `<custom-ident>`, or an `<attr-name>`, depending on the context in which it is used.

I want to build a type system for a CSS-based programming langauge. In this type system, I want to use a typing strategy that does not go from the bottom up (starting from the leaves in the AST), but top down (starting from the root of the AST).

For example, when the compiler needs to derive that the `linear(red, yellow)` expression inhabits the `<bg-image>` type, it would do the following derivation:

```
we want to derive that
  linear(red, yellow) :: <bg-image>
<bg-image> is defined as <url> | linear(<color>, <color>), so
  linear(red, yellow) :: <url> | linear(<color>, <color>)
let us try the second branch
  linear(red, yellow) :: linear(<color>, <color>)
let us check sub-expressions
  red :: <color>
  yellow :: <color>
everything fine, OK

```

Can you point me to scholarly articles where this kind of typing strategy is discussed?

---

P.s. I don't know of other languages where a type of the expression depends on the context, except for Perl. In Perl, `("a","b")` can be interpreted as either a list or an integer (its length), depending on the context:

```
print ("a","b") # => ab
print 0+("a","b") # => 2

```

# Answer
> 4 votes
There is no top-down or bottom-up typing strategy when defining a language. It is an implementation issue. A type system will only define operator operand constraints on your AST. The kind constraints is fixed by the type system and is part of the design of the language. It can be very simple as in older languages, or be a sophisticated logical system. Even when simple, it can be seen as a logical system. Your AST may be seen as a proof tree in that logical system, where the nodes are to be decorated by types, that may be seen as logical propositions proved by by the sub-tree dominated by that node . For example, the type **int** found for an expression is a predicate satisfied by the expression.

So you can associate type inference rules to the operators of your AST. For example if you have an AST operator **+** with two operands, you can associate (among others) the inference rule: $X::int \\,\wedge\\, Y::int \\;\Rightarrow\\; X+Y::int$

Defining the type system of a language amount to defining such rules for all AST operators where that make sense, i.e. involved with the type system.

Type checking your program consists in finding a type for each (relevant) AST node, such that that there is an inference rule (associated to the operator of that node) that is satisfied by the node type and the types of its operands.

This can be done with top-down or bottom-up algorithms, or any mix. That is only a matter of finding efficient algorithms. But the checking strategy is an implementation issue, not a language definition issue. However, it is advisable to choose a type system that allows for a tractable type checking strategy.

Note that the types may not be all completely defined by the type system, and the checking strategy may actually infer the "details" of these types, in particular by means of unification techniques.

The above description may not seem too complex (I hope). One hidden aspect, that makes the whole thing a lot more interesting, is that in static typing (particularly) all occurences of the same variable must have the same type, which introduces additional constraints. But getting into the details is too much for a normally sized answer.

For more about this, you should look for type inference.

---
Tags: programming-languages, compilers, type-theory, type-inference, language-design
---


title: Simple error in C

text:
# Question
Title: Simple error in C
I cannot determine why the Celsius values in this code are producing rubbish values. (Look at second statement in the first for-loop).

CODE:

```
/* The program will output two columns with the temperature in degrees Fahrenhiet
and equivalent temperature in degrees Celcius. The range will be 0 to 300 farenhiet in
20 degree intervals. */

#include <stdio.h>

int main()

{
    double fahr[20], cel[20]; // there should be 16 values (300/20 + 1) in these arrays and a null zero. (total of 17 values)
                              // Doesn't hurt to make them a bit larger than necessary (i.e. 20 instead of 17 values)

    for (int i = 0; i < 16; i++)
    {
            fahr[i] = i*20; // Express Farhrenhiet as a linear function of i and iterate
            cel[i] = (5 / 9) * (fahr[i] - 32); // Express Celcius as a linear function of fahr[i]
    }

    printf("Fahrenheit\tCelcius\n"); //printing the column headers

    for (int j = 0; j < 16; j++)
    {
        printf("%.f", fahr[j]);
        printf("\t\t%.2f", cel[j]);
        printf("\n");
    }

    return 0;
}

```

# Answer
The expression 5/9 (the second statement of first loop) will make an integer division, which will result in 0. You have to write 5.0/9 or 5/9.0 to get a double value as result.
> 1 votes

---
Tags: c
---


# Question
Title: Is the language $L=\{a^{2^{n}} \mid$ n is a natural number$\} $ context free?
I have to determine, and prove, whether the language $L=\\{a^{2^{n}} \mid$ n is a natural number$\\}$ is context free or not (if it is by a grammar and not by the pumping lemma).

I tried to construct a grammar, but I don't have a working one. I have no problems to construct the language $L=\\{a^{2n} \mid$ n is a natural number$\\}$. So I tried the pumping lemma, but I don't find the proof, that this is not context free.

Can someone tell me of what type this language is? A hint how to prove this would also be very nice.

# Answer
> 1 votes
Suppose that $L$ is CFL then $L$ is regular because it is a unary language. So exist a constant $N$ associated to $L$ by the pumping lemma for regular languages.

We choose the word $\sigma = a^{2^N}$ and $|\sigma| = 2^N \> N $ so the pumping lemma should complies for $\sigma$. Then exist a factorization of $\sigma = \alpha \beta \gamma$ such that:

1) $|\alpha \beta|\leq N $

2) $|\beta|\geq 1$

3) $\alpha\beta^i\gamma \in L \forall i \in \mathbb{N}\_0$

$|\alpha\beta^i\gamma|= 2^N + |\beta|(i-1)$ choosing $i=2$:

$|\alpha\beta^2\gamma|= 2^N + |\beta|$ so: $$2^N+1\leq|\alpha\beta^2\gamma|\leq 2^N+N$$ $$2^N\<2^N+1\leq|\alpha\beta^2\gamma|\leq 2^N+N\<2^N +2^N$$ $$2^N\<|\alpha\beta^2\gamma|\<2^{N+1}$$

Then $|\alpha\beta^2\gamma|$ can't be a power of 2(with natural exponent) so $\alpha\beta^2\gamma\notin L$ and we find a contradiction. Finally $L$ can't be regular and it is not CFL too.

---
Tags: formal-languages, context-free, pumping-lemma
---


title: Algorithm: Cracking the Safe

text:
# Question
Title: Algorithm: Cracking the Safe
A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode.

For instance, if I enter the stream $012345$, I am trying each of the combinations $0123$, $1234$, and $2345$.

Clearly, a 40000-length string $000000010002...9999$ is guaranteed to crack the safe.

Can we try each of the 10000 combinations using a shorter string? What's the shortest string we can devise to try every combination?

# Answer
> 6 votes
The answer is to use a de Bruijn sequence, as discussed in response to this question on CS Theory. This gives a sequence of length $10^4=10\\,000$. However, the sequence is cyclic, in the sense that if you wrote it on a paper tape and joined the ends together to form a loop, only then would it contain every possible 4-digit sequence and some of those sequences would cross the join. So, for a linear sequence, you need to repeat the first three items at the end, giving $10\\,003$, improving on the obvious solution of length $40\\,000$.

(Thanks to PålGD for pointing out the issue with cyclicity.)

---
Tags: algorithms, algorithm-analysis, data-structures, combinatorics, group-theory
---


# Question
Title: CFG for all string that don't end at ba?
Here is my solution:

```
S-> Sab|Sbb|Saa
S->aS
S->bS
S->ε

```

Is this solution right?

# Answer
> 1 votes
It is wrong because you can use the fifth production, then the fourth production and finally the sixth production to make the string $ba$.

Just doing a little modification to your grammar you can obtain the right solution:

$S\to Xab|Xbb|Xaa|a|b|\epsilon$

$X\to aX|bX|\epsilon$

You can eliminate the epsilon production of $X$ as an exercise.

---
Tags: context-free, formal-grammars
---


# Question
Title: In a distributed system is it possible for both parties to simultaneously agree a message exchange was made?
Given that the two generals problema is unsolvable, which means that both parties involved cannot agree that both know something, i ask something simpler. Is it possible for both parties to agree that a message Exchange occurred? In other words, is it possible for both parties to agree that a "conversation" occurred?

For instance, if A and B communicate with messages Mx

```
A -M1 -> B
A <-M2 - B
A -M3 -> B

```

At this point B knows that a message Exchange occurred, but can he be sure that A also knows so?

Thanks in advance

# Answer
> 3 votes
I think it *is* the "two general" problem.

The "two general" problem is informally stated as follows \[1\]:

> The commanding general of the first division wishes to coordinate a simultaneous attack. The generals can ***communicate only by means of messengers***. Normally, it takes a messenger one hour to get from one encampment to the other. However, it is possible that he will get lost in the dark or, worse yet, be captured by the enemy.

What is the difference between this and your "message-exchanging" problem?

---

\[1\] Reasoning about Knowledge. By Ronald Fagin, Joseph Y. Halpern, Yoram Moses and Moshe Vardi.

---
Tags: distributed-systems
---


title: Finding a good loop invariant

text:
# Question
Title: Finding a good loop invariant
I want to prove that the following program is correct. The code takes an array `i` of length `N` and a number `x`. At the end, the value of `found` should be true if the array contains `x` and false otherwise.

```
found := false;
i := 0 ;
while i < N do {
    found := found || (a[i]=x);
    i:=i+1
}

```

The given **preconditions** are that `N >= 0` and that the array is sorted in ascending order (however, I don't know how the fact that it is sorted can help).

As **postcondition**, I think the following would suffice: the value of `found` equals the value of the predicate “there exists an i in the range \[0, N) such that `a[i] == x`

However, I am stuck at this point and don't know how to continue. I cannot think of any loop invariant that has any relation to the postcondition. What would you suggest as a loop invariant?

# Answer
> 5 votes
You have an intended postcondition for a loop, and you're looking for an interesting invariant. In this scenario, try taking the intended postcondition, and replacing the total number of iterations (here `N`) by the number of iterations so far (here `i`). There's no guarantee that this is an invariant: that's only the case if the way the postcondition is somehow related to the structure of the loop. But if it is an invariant, it's definitely interesting, because it lets you prove the postcondition.

So we're interested in the following property: “the value of `found` equals the value of the predicate there exists a $k$ in the range $\[0, i)$ such that $a\[k\] = x$”. Note that I use a name other than `i` for the existential variable, since `i` is now used in the context. The quantifier pile-up is:
for any value of `N` set before calling this snippet,
for any value of the variable `i`,
there exists an index $k$ such that …

It is easy to verify that this is indeed an invariant of the loop.

Intuitively, this property states that `found` reflects whether the element is in the array up to the point that has been traversed. At the end of the loop that traverses the whole array, `found` reflects whether the element is in the whole array.

---
Tags: correctness-proof, software-verification, loop-invariants
---


title: Sum of element of all subset of size k

text:
# Question
Title: Sum of element of all subset of size k
Efficient way to find the sum of all elements of all subsets of size $k$ for a given set $s=\\{1,2\dots,n\\}$ ($n\ge k$). Example:

$s=\\{1,2,3\\}$, $k=2$.

$s\_1=\\{1,2\\}:\\;1+2=3$
$s\_2=\\{1,3\\}:\\;1+3=4$
$s\_3=\\{2,3\\}:\\;2+3=5$.

And the sum is $3+4+5=12$.

# Answer
Every element of $s$ appears in the same number of $k$-subsets. So just figure out how many that is and multiply $\sum\_{x\in s}x$ by that number.
> 4 votes

---
Tags: algorithms
---


title: generating recursive descent parser

text:
# Question
Title: generating recursive descent parser
I have a grammar,

$L \to A \langle A \rangle^\*$

$A \to () \mid (L)$

but I am not sure how to generate parser for $\langle A \rangle$. I know in other case, for example, if $E \to T \langle^\*T\rangle^\*$ then I can create parser like

```
proc E begin
  T;
  while symbol='*' do
    T
  od

```

However in my case don't have any symbol. So how can I check symbol for while process? Or my grammar is incorrect?

# Answer
> 0 votes
From the first rules, it seems clear that the angle brackets are metasyntactic parenthesis used to denote Kleene closure over more than a single symbol. This is also suggested by the existence of normal brackets in the grammar. This also suggest that the example rule for $E$ is syntactically not well formed and means nothing at all, since the star cannot apply to a metasyntactic parenthesis (as the first star seems to be doing). The correct rule is probably: $E \to T \langle +T\rangle^\*$ and the corresponding parser:

```
proc E begin
  T;
  while symbol='+' do
    T
  od

```

Generating a parser for $\langle A \rangle$ is just generating a parser for $A$ alone. The angle brackets are just grammatical notation (like the arrow or the vertical bar), and are not supposed to appear in generated strings.

They are not necessary here, but could be if you had Kleene star over several symbols, such as $\langle AB \rangle^\*$, as in my corrected version of the rule for $E$.

With these corrections, you should be able to finish your recursive descent parser.

# Answer
> 0 votes
You do have a symbol, "$($". A bit more generally though (if I understand the notation you're using), if you're processing an $L$ and you see *anything*, it must come from an $A$, if it's not an error, so you can recurse to processing an $A$.

---
Tags: algorithms, context-free, formal-grammars, parsers, syntax
---


# Question
Title: Undirected graph G that has 12 vertices, 66 edges and 3 connected components?
Why would it be impossible to draw an undirected graph G that has 12 vertices, with 3 connected components if G had 66 edges?

# Answer
> 3 votes
**Hint.** How many edges does the complete graph on 12 vertices have?

# Answer
> 2 votes
Consider the following problem:

> What is the possible maximum number of edges in $G$, which has 12 vertices and consists of 3 components (I assume that loops and multiple edges are not allowed)?

Let $n\_1, n\_2, n\_3$ be the numbers of vertices in the three separated components. Then you are lookin for

$$\max \frac{n\_1(n\_1 - 1)}{2} + \frac{n\_2 (n\_2 - 1)}{2} + \frac{n\_3 (n\_3 - 1)}{2}$$ $$\text{subject to } n\_1 + n\_2 + n\_3 = 12$$

An optimal (*intuitive*) solution is $n\_1 = n\_2 = 1, n\_3 = 10$ and the maximum value is 45.

---
Tags: graphs, combinatorics
---


title: Creating a LCG with m = 32767

text:
# Question
Title: Creating a LCG with m = 32767
I want to create a PRNG for an integer only (with a max of 32767) system and tried to use an LCG. So I've chosen as $m = 32767$ and $c = 3$ and I tried to figure out a good $a$. However for the full period I have to choose $a = 32768$ which cannot be used since the maximum is 32767.

Can anyone help me creating a "good" LCG?

Another question: Since the maximum (could be / is) 32767 I don't know how to calculate the successor because $a * y\_{-1} + 3$ could become greater than 32767 and this is not allowed in the system. So should I use $a * (y\_{-1} \mod ((32767+3)/a) + 3$ then?

# Answer
> 2 votes
The output of an LCG with modulus $m$ is in range $\[0\dots m-1\]$. Hence the choice of $m=32767$ forbids the output to be $32767$. Perhaps the OP wants $m=32768$.

We want to compute $(a\cdot x+c)\bmod m$ for known constant integers $a$ $c$ $m$ on a system restricted to integers in $\[0\dots32767\]$ (or is it $\[-32767\dots32767\]$ or $\[-32768\dots32767\]$, but that only makes the problem easier).

We can compute $z=(x+y)\bmod m$ on this system, assuming $0\le x\<m$ and $0\le y\<m$, as
`if (m-x > y) z = x+y; else z = y-(m-x);` when $0\<m\le32767$, or as
`if (32767-x >= y) z = x+y; else z = (y-(32767-x))-1;` when $m=32768$

From this primitive, it is easy to build $(a\cdot x)\bmod m$ by an addition chain, then $(a\cdot x+c)\bmod m$.

---
Tags: random-number-generator
---


# Question
Title: Why is the class NP-Complete important compared to NP-hard?
I'm studying computational complexity and I was wondering why the NP-Complete (NPC) problems is an important class at all. I find it obvious why we're interested in showing a given NP problem is NP-hard.

I also understand the definition of NPC, and that showing a given decision problem is NP-hard, knowing it is in NP, is exactly was NPC means.

However, what I don't understand is: why this concept is so important? Surely, if we find any NP-hard algorithm which runs in time P (whether or not that is in NP), we have shown that $NP = P$.

Why is this concept so important?

# Answer
There are at least a few reasons that NPC is interesting:

* The class NP contains many problems that are interesting (both practically and theoretically), moreover many of these problems turn out to be NP-hard (and hence NP-complete), but *many problems outside of NP are almost certainly too hard to be of more than theoretical interest*, so NPC provides a (rough) group of problems that are apparently hard, but not so hard that we can't try to do something with them.
In other words, NPC is probably the limit of what we can hope might be polynomial-time solvable, it would seem a stretch to try for PSPACE = P (for example).
* The class is NP is structurally interesting. It's the basic example of "do we get any more computational 'speed' from nondeterminism". So we're interested whether P=NP or not, and NPC is (probably) an important component of working that out.
* NP-hard (as a class) is really too big and varied to deal with as a single thing, it's *everything that can be reduced to from an NP-complete problem*, including a huge swathe of stuff outside NP, so from the point of view of trying to develop general results and techniques, there's nothing to grab on to.
> 16 votes

# Answer
From the point of view of someone who writes code for a living, having a good familiarity with NP-completeness is important for:

## 1. Recognizing when you're barking up the wrong tree

NP-complete problems are the easiest of the NP-hard problems and yet as far as we can tell, it takes time exponential to the size of the input to solve such a decision problem. So, as a practical matter if you can show that the problem you're trying to solve is NP-hard (typically by showing that an efficient solution to it would also give an efficient solution to some NP-complete problem), you know that you can *stop searching* for an efficient algorithm to solve it exactly in general. Instead, you can select from known algorithms that promise good approximations for NP-hard optimization problems and get on with the rest of your project.

## 2. Finding the right tree

Because computers are often used to attack NP-hard problems, specialized solvers have been developed that can efficiently solve *some* NP-hard problem instances. Recognizing that your problem is NP-complete is the first step toward finding an existing tool (SAT, ILP, SMT, CSP to name a few) that might help you find exact solutions in some cases where you otherwise would have had to settle for an approximation.
> 9 votes

# Answer
"Surely, if we find any NP-hard algorithm which runs in time P (whether or not that is in NP), we have shown that NP=P. Why is this concept so important?"

Every NP problem reduces to any NPC problem, but it's not true that every NP problem reduces to any NP-hard problem, so proving an algorithm NP-hard is in P doesn't prove P=NP at all. It would be the case, however, for a NPC problem, that is precisely what "reduces" means. So, if we find an P algorithm for a NPC problem, then, we will have proven that P=NP.
> -3 votes

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


# Question
Title: How can I prove this language is not CFL?
I have a question to find out that $L = \\{a^m b^n\mid n\>0, m - is prime \\}$ is CFL or not. I know that it is not a CFL. But I don't know how to prove that. I know how to prove that $L = \\{a^m\mid m - is prime \\}$ is not CFL, by taking a random length for $vx$ ($uvwxy$) and prove that the length of the whole word is not prime (I manage to prove that this length is product of two factors). But with this problem I can't do this because of that $n$. At the end it results a non prime number (this product), but I have to decrease the length of $b$'s so I know nothing about that final number. Is there another method to prove that this language is not CFL or am I wrong somewhere?

# Answer
> 1 votes
The easiest way goes as follows: if $L$ were context-free than so $L \cap a^\*$ would be. Now $L' = L \cap a^\* = \\{ a^m : m \text{ is prime}\\}$ is a unary language, so $L'$ is context-free iff it is regular iff it is eventually periodic. If it were eventually periodic then it would be either finite or have finite asymptotic density, but we know that primes are infinite and have zero asymptotic density.

You can also prove that $L'$ is not context-free using the pumping lemma. The pumping lemma shows that for some $p$, every prime $q \> p$ satisfies the following: there is $1 \leq t \leq p$ such that $q + (\ell-1)t$ is prime for all $\ell$. Choosing $\ell = q+1$, we get that $q(t+1)$ has to be prime, which it isn't.

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


# Question
Title: Why is self-information defined the way it is?
The self-information of an event of probability $p\_x$ is defined as $I(p\_x)=-\log\_2(p\_x)$.¹

I fully understand this for equiprobable events of the form $p\_x = \frac{1}{2^k}$. In that case, we want to encode $2^k$ events so we need $\log\_2(2^k)=k$ bits. So $I(p\_x)$ should be $\log\_2(\frac{1}{p\_x}) = -\log\_2(p\_x)$

However I am confused about the generalization to events of different probabilities and probabilities where $p\_x \neq \frac{1}{2^k}$. Then, I am wondering why $\log$ is a good choice.

I've never come farther as to such tutorials: http://www.i-programmer.info/babbages-bag/213-information-theory.html But as I read it they just think about what they want, namely a function $I$ with $I(xy)=I(x)+I(y)$ and then find that $-\log\_2(p\_x)$ satisfies all their needs. But is $\log$ the only choice they have? $I(x)=0$ works too! What are the exact requirements that we need? And why do we finally choose $I(p\_x)=-\log\_2(p\_x)$?

¹I know $2$ is just the special case for bits, chosen for simplicity.

# Answer
Though it is more common to discuss axiomatic derivation of the expectaion of $I(\cdot)$, that it, the **entropy** function (to which, several sets of axioms exist, see here), for the self information $I(\cdot)$, we usually care about the following properties (as defined by Shannon):

1. If the event happens with certainty, there is no information in it. Thus, if $p=1$, $I(p)=0$
2. Furthermore, $I(p)$ must be decreasing with $p$: the more likely the event is, the less information it gives us (or alternatively, the more surprising the event is, the more information its occurrence contains)
3. As you mentioned, we want that the information of two independent events will add up: $I(p\_xp\_y)=I(p\_x)+I(p\_y)$. The event of both $X$ and $Y$ occurring has probability $p\_x\cdot p\_y$ if independent.

These axioms lead to $I(p) =\log \frac1p$, up to a normalization (e.g., choosing the basis of the logarithm).
> 4 votes

---
Tags: information-theory
---


# Question
Title: How do global variables and automatic variables with the same name interact?
Suppose I define a global variable and I define an automatic variable within a function definition with the same name as the aforementioned global variable.

What would happen to the global variable if I altered the automatic variable within the function body?

# Answer
In most programming languages, especially imperative languages, a “variable” is actually two things: a *name* and a *storage location*. The storage location is a block of memory where a value can be stored and retrieved. The variable's name is often called an *identifier*. An identifier is a way to refer to some object in the program, in this case a storage location. A variable has a *scope*, which is the part of the program where the variable's name refers to the variable.

For example, consider the following C snippet.

```
int foo;
void myfunction(void) {
    float foo;
    … /* Here the identifier foo refers to the variable that's of type float. */
}
/* Here the identifier foo refers to the variable that's of type int. */

```

This snippets declares two variables. The two variables happen to have the same name: both are called `foo`. They're distinct variables, refering to distinct storage location, same as if they'd been called by different names. The scope of the `foo` variable that's of type `float` is the function `myfunction`: inside the code of `myfunction`, the identifier `foo` refers to this variable; outside the code of `myfunction`, the identifier `foo` refers to some other variable, or none at all. The scope of the `foo` variable that's of type `int` is the file where it's declared; the identifier `foo` refers to this variable everywhere is the whole file, except for the functions (or more generally blocks¹) which declare another variable that's also called `foo`. The local variable `foo` is said to *shadow* the global variable `foo`.

A variable whose scope is a whole file is usually said to be *global*. A variable whose scope is a function, method, block, etc. is usually said to be *local*. In the example above, the `int`-typed `foo` is a global variable and the `float`-typed `foo` is a local variable, local to the function `myfunction`.

The scope of a variable is the part of a program where its name refers to that variable. This is not always the same thing as the part of the program where the storage location exists. There is some correlation between the two, because it's usually undesirable to have a name for a storage location that doesn't exist, and it's often desirable to have a name for storage locations that do exist.

In C, the time during which a storage location exists is called its *duration*. The duration of a global variable is the whole program execution (“static duration” in C jargon, but that jargon doesn't extend to other languages, unlike most of the terms I used in this answer). (That's in C and some other langauges; in many other languages the duration of a global variable starts when the variable is defined.) The duration of a local automatic variable is the time during which the block containing it is executing. Note that “automatic” refers to the duration, not to the scope; “automatic” is not the opposite of “global”, “local” is. In C, you can't have automatic duration at a global scope, but you can have static duration at a local scope, with a variable that's declared `static` or `extern`.

```
void myfunction(void) {
    static int s;
    extern int e;
}
/* Here s and e are not defined */

```

The duration of both `s` and `e` is the whole program execution, but their scope is only the function `myfunction`: the names `e` and `s` are not valid outside that function. The difference between `static` and `extern` is that the variable `s` cannot be accessed from another scope, whereas `e` is the same variable as any other `extern e` in any scope.

Coming back to the `foo` example above, since two variables in different scopes have no relation, altering `foo` in `myfunction` has no impact on the global `foo`. They're unrelated variables, they just happen to have the same name.

It would be possible to rename the local variable `foo` to avoid having a name conflict. If you change all occurrences of `foo` in the code of `myfunction` to a different name that isn't used elsewhere in the program, you get an equivalent function.² This renaming process is known as alpha conversion in programming language theory.

The main reason programming languages allow programmers to pick the same name for different variables is that doing otherwise makes it difficult to write large programs and especially to write programs in pieces. If adding a library to your program meant that you had to rename some of your local variables in unrelated parts of your program to avoid conflicts, it would be a nightmare. (As it is, C only has global names for functions, which can be troublesome.)

Basically all languages allow variables in unrelated scopes to have the same name. C also allows *shadowing*: defining a variable in a scope hides any variable by the same name in a surrounding scope. This is common, but not univeral. For example, in Java, if you define a variable in a block, you can't define another variable by the same name in a nested block. The advantage of this restriction is that it prevents a source of confusion: a programmer might inadvertently use the name to refer to the variable from the outer scope, and not realize it instead refers to the variable in the inner scope. The downside of this restriction is that it makes some program transformations impossible without renaming the variable.

```
void myfunction(void) {
    int x = 1;
    if (…) {
        int x = 2;  // allowed in C, forbidden in Java
        printf("%d\n", x); // prints 2
    }
    printf("%d\n", x); // prints 1
}

```

Some languages have a way to refer to a variable that's shadowed, but it's uncommon. C has no such way, but you can refer to the storage location of the outer variable if you have a pointer to it.

¹ <sub> More precisely, the scope of a variable defined in a block runs from the variable definition to the end of the block. If there is an outer scope with a variable of the same name, it's that same part which is excluded from that outer scope. </sub>
² <sub> This only works in languages where variable names are not significant. Actually, I lied here, because C can make variable names significant via the preprocessor. C is quite a complex language… If that preprocessor feature isn't used, variable names are not significant. </sub>
> 3 votes

# Answer
This is a good question, though extremely elementary. I try to give you a very general answer. There are variations with different programming languages, or other types of languages. The issue is really about the role of names, that we usually call *identifiers* in programming.

First note that a global variable may also be an automatic variable, but it is then defined in a larger function, in which your function is defined. But that is not very important here.

All languages, not just programming languages, but also mathematical and logical ones, or natural ones, have scoping rules, so that the same name may be used with different meanings in different context. A new function usually defines a new scope for names, and any name (including variable names) that is declared within the function gets a meaning given by the declaration, which hides the meaning it had outside.

This is not so much an issue of automatic allocation of variables (though there are relations) but much more of meaning of names. There are other mechanisms to structure the way names take meaning. When they combine, you need to know all the various rules to determine how a given name takes its meaning, i.e. to what definition (aka declaration) this use of the name refers. And that can be more subtle than your example.

In the case of your example, you have two unrelated variables that happen to have the same name. At any time, the name means only one of them. In your function, the local declaration gives a local meaning to the name, thus hiding the global meaning. So the global variable is untouched, when its name is used to modify another *homonymous* variable. For example, I expect you were not involved in Spielberg's movie on WW2, and no one came to save you. In the scope of the film Ryan did not mean you.

Actually, the name of your automatic variable could well be used globally to name a function, and locally to name a variable. It does not matter.

To know more on this topic, I suggest you look at "variable binding" and "scoping". It will be time well spent.
> 2 votes

---
Tags: programming-languages, variable-binding, language-design
---


# Question
Title: How to cluster similar objects into fixed size groups?
I have $n$ people each of which can meet on certain days of the week. I want to group them into $\frac{n}{k}$ groups of size $k$ such that all people in a group can meet on a day.

eg - Suppose there are 3 people who are free on (M,T,W,Th,F), (M,W) and (W,Th,F) respectively. They can all be placed in the same group since all of them can meet on Wednesday.

# Answer
> -1 votes
Just model your problem with graph and use any of the widely known search algorithm to help traverse your graph. After doing that, if you have any problem, let us know.

---
Tags: algorithms, dynamic-programming, randomized-algorithms, greedy-algorithms, cluster
---


# Question
Title: Data structure for sparse matrices for an online problem
I need to compute a large linear optimization problem very often after recieving updates to my optimization problem.

That is I have a linear problem to find an x such that

$x\_1 * c\_1 + ... + x\_n * c\_n$ is as small as possible

under the conditions that $Ax \\# b$ (where $\\#$ can be $\<=$, $\>=$ or $=$ on each row).

At some (small) time interval the $a\_{ij}$, $c\_i$ and $b\_i$ can get updates and I need to recompute. The updates only touch very few of the entries and most of the time the changes are only by small amounts.

Some of the $x\_i$ are integer variables, some are binary variables and some are real variables.

Current idea:

* find a sparse matrix data structure which allows for efficient updates
* implement a branch-and-bound algorithm which works on that data structure

**Question**: which combination of sparse matrix representation and linear optimization algorithm is the current state of the art for such a problem?

**Sub-question**: is there a way to use the result from the previous run if I know only a few entries change?

# Answer
> 3 votes
In low dimension, Seidel's algorithm can be useful: if we have the optimal solution to $m$ constraints in $d$ dimensions, and you add one more constraint, then the amortized cost to find the optimal solution to those $m+1$ constraints is $O(d!)$, assuming the constraints are being presented in a random order.

(It is usually presented in the following form: if we have $m$ constraints, and we add them one-by-one, updating the optimal solution after each constraint is added, then the total running time to do this is $O(d!m)$ using Seidel's method. But that's equivalent, if we assume constraints are added in a random order.)

In high dimension, I don't know of any good method. There is a trivial observation that if $x^\*$ is the optimal solution to the constraints, and we add a new inequality, and $x^\*$ satisfies this new inequality, then $x^\*$ remains the optimal solution, so there's no need to re-solve the LP. This condition can be tested in $O(d)$ time. However, if $x^\*$ doesn't satisfy the added inequality, I don't know if there's anything better you can do than solve the new LP from scratch. Same for changing or removing an existing inequality, or changing the objective function.

---

I'm not sure your question about data structures is well-defined. Data structures are chosen based upon the set of operations you intend to perform on them. In this kind of problem, it's usually the algorithm that is the more important part. You start with the algorithm, then choose a suitable data structure. But my impression is that with LP, the hard part is the algorithms, and the data structures tend to be comparatively simple. So asking about sparse matrix data structures for your problem seems to be putting the cart ahead of the horse.

# Answer
> 3 votes
The state-of-the art for any MILP like you describe, is complicated software like CPLEX (or some other expensive proprietary package). Such packages do take into account issues of sparse linear algebra, but this is a problem of numerical stability just as much as efficiency. See for example: (http://www.gurobi.com/resources/getting-started/lp-basics). Those packages may also contain a feature to *repair* an almost feasible solution, which you could use if the previous optimal solution is no longer feasible.

The *integrality* constraints make that the access times of the datastructure used to feed the algorithm, are dominated by the running time of the optimization part. This is combined with the fact that efficient approach to MILP's are not particularly amenable to reusing previous results. If you drop the integrality constraints (or they are redundant) this is different.

If you use the simplex method to solve an LP and then perturb the problem slightly, you may use the state of the algorithm at termination to solve the new problem, if the optimal solution doesn't change to much. What helps is that a local solution to an LP is also global. Ergo starting close to the previous optimal solution is beneficial.

If you start branching this is no longer the case. Though finding an optimal solution in somewhat similar, proving it's optimal requires you to rule out there is a better solution in every other branch. Branch and bound typically uses some binary tree to compactly express the branches that are 'ruled out'. The problem is that efficient branch and bound schemes do not retain information that could be used to adapt this tree if you change the problem coefficients slightly. Basically, since branches are ruled out based on results in solved sub-problems, changing the problem might invalidate the grounds on which a branch was ruled out. Only we don't know where this is happening, and therefore need to verify every ruled out branch. This is done most efficiently using a branching method again, which means we're back to square one (though it definitely helps if you have a good initial feasible solution).

Of course this is assuming a general MILP (i.e. not some special case that is polynomial time solvable), and that use a sensible datastructure (i.e. polynomial time mutations).

---
Tags: algorithms, data-structures, optimization, online-algorithms, sparse-matrices
---


# Question
Title: Select the n closest nodes from a starting node in a weighted directed graph
I need to select a given number of nodes from a weighted directed graph such that the nodes selected are the closest to a given starting node. This seems like a common problem to need to solve, but I haven't found much material on it. Does anyone know if this particular problem has a name, or any published material (formal or informal) related to it?

Note, I am not asking for a solution to the problem itself. I am interested in finding material related to the problem. For very large graphs, the canonical Dijkstra algorithm will not work because you must enqueue every node first. I believe a modified version of the Uniform Cost Search will do what I want, since it does not enqueue all the nodes first. Things get more interesting in this case, because you don't have full knowledge of all shortest paths. I'm interested in things like how do you know when you've found all the shortest paths for the closest nodes, without traversing the entire graph in the process. I think this is possible using an admissible heuristic as in the A\* search. These are the kinds of details I want to be able to read up on.

# Answer
> 2 votes
> ***Question 1.*** For very large graphs, the canonical Dijkstra algorithm will not work because you must enqueue every node first.

Yes, you are right about the disadvantage of canonical Dijkstra's algorithm. However, it can be easily adapted (wiki):

> The algorithm can start with a priority queue that contains only one item, and insert new items as they are discovered (instead of doing a decrease-key, check whether the key is in the queue; if it is, decrease its key, otherwise insert it).

See the paper for details (including experiments) on implementing Dijkstra's algorithm with such a modified priority queue.

> ***Question 2.*** I'm interested in things like how do you know when you've found all the shortest paths for the closest nodes, without traversing the entire graph in the process.

The Dijkstra's algorithm finds the shorted paths from a starting node in the order of increasing costs. So, the first $n$ vertices removed (`delete-min`) from the priority queue are the $n$ closest nodes from a starting node you are looking for.

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


# Question
Title: Which element is at its final position after the partitioning step in Quicksort?
In Algorithms, 4th Edition, I read that after the partitioning step one element is in its final position.

> The entry a\[j\] is in its final place in the array, for some j.
>
> No entry in a\[lo\] through a\[j-1\] is greater than a\[j\].
>
> No entry in a\[j+1\] through a\[hi\] is less than a\[j\].

And this comes from Algorithms, 4th Edition, as well:

> First, we arbitrarily choose a\[lo\] to be the partitioning item—the one that will go into its final position.

Does the pivot go into its final position for all inputs without exception?

# Answer
> 2 votes
The details depend on the partitioning method used, but usually *the pivot* ends up in its final position.

That follows from the second and third statement, by the way: all elements smaller than the pivot are to the left of it, and the larger to the right. The pivot is in between, and that is clearly its final position in the sorted array.

That the second and third statement hold is the central property of the partitioning method used.

---
Tags: algorithms, correctness-proof, quicksort, partitions
---


title: Quicksort bounds

text:
# Question
Title: Quicksort bounds
I found an implementation of Quicksort here, and now I cannot understand why it works with those left and right bounds.

Right now the link above is unavailable due to some problems with their hosting provider.

```
public class Main {

    public static void main(String[] args) {
        int array[] = new int[] {
                10, 3, 2, 5, 4
        };

        System.out.println("array == " + Arrays.toString(array));
        quickSortModified(array, 0, array.length - 1);
        System.out.println("sorted array == " + Arrays.toString(array));
    }

    private static int partition(int arr[], int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = arr[(left + right) / 2];

        while (i <= j) {
            while (arr[i] < pivot)
                i++;
            while (arr[j] > pivot)
                j--;
            if (i <= j) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

    private static void quickSortModified(int arr[], int left, int right) {
        int index = partition(arr, left, right);
        if (left < index - 1)
            quickSortModified(arr, left, index - 1);
        if (index + 1 < right)
            // TODO: index + 1 vs index for the bound here.
            quickSortModified(arr, index + 1, right);
    }
}

```

Why should left be less than `index - 1`, not just index?

Why should index (not `index + 1`) be less than right?

For example, on Wikipedia they use `index + 1` for the second recursive call.

# Answer
You haven't given us the complete picture, but in general, if you are going to call `quickSort` on the slice of the array `lo .. hi`, then there is only need to do so if `lo < hi`; otherwise the array has at most one element and doesn't need to be sorted.
> 2 votes

---
Tags: algorithms, quicksort
---