Paul Erdős talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book.
If God had a similar book for algorithms, what algorithm(s) do you think would be a candidate(s)?
If possible, please also supply a clickable reference and the key insight(s) which make it work.
Only one algorithm per answer, please.
Union-find is a beautiful problem whose best algorithm/datastructure (Disjoint Set Forest) is based on a spaghetti stack. While very simple and intuitive enough to explain to an intelligent child, it took several years to get a tight bound on its runtime. Ultimately, its behavior was discovered to be related to the inverse Ackermann Function, a function whose discovery marked a shift in perspective about computation (and was in fact included in Hilbert's On the Infinite).
Wikipedia provides a good introduction to Disjoint Set Forests.
Knuth-Morris-Pratt string matching. The slickest eight lines of code you'll ever see.
The algorithm of Blum, Floyd, Pratt, Rivest, and Tarjan to find the kth element of an unsorted list in linear time is a beautiful algorithm, and only works because the numbers are just right to fit in the Master Theorem. It goes as follows:
Binary Search is the most simple, beautiful, and useful algorithm I have ever run into.
I'm surprised not to see the Floyd-Warshall algorithm for all-pairs shortest paths here:
d[]: 2D array. d[i,j] is the cost of edge ij, or inf if there is no such edge.
for k from 1 to n:
for i from 1 to n:
for j from 1 to n:
d[i,j] = min(d[i,j], d[i,k] + d[k,j])
One of the shortest, clearest non-trivial algorithms going, and $O(n^3)$ performance is very snappy when you consider that there could be $O(n^2)$ edges. That would be my poster child for dynamic programming!
Might seem somewhat trivial (especially in comparison with the other answers), but I think that Quicksort is really elegant. I remember that when I first saw it I thought it was really complicated, but now it seems all too simple.
The Miller-Rabin primality test (and similar tests) should be in The Book. The idea is to take advantage of properties of primes (ie using Fermat's little theorem) to probabilistically look for a witness to the number not being prime. If no witness is found after enough random tests, the number is classified as prime.
On that note, the AKS primality test that showed PRIMES is in P should certainly be in The Book!
Polynomial identity testing with the Schwartz-Zippel lemma:
If someone woke you up in the middle of the night and asked you to test two univariate polynomial expressions for identity, you'd probably reduce them to sum-of-products normal form and compare for structural identity. Unfortunately, the reduction can take exponential time; it's analogous to reducing Boolean expressions to disjunctive normal form.
Assuming you are the sort who likes randomized algorithms, your next attempt would probably be to evaluate the polynomials at randomly chosen points in search of counterexamples, declaring the polynomials very likely to be identical if they pass enough tests. The Schwartz-Zippel lemma shows that as the number of points grows, the chance of a false positive diminishes very rapidly.
No deterministic algorithm for the problem is known that runs in polynomial time.
Depth First Search. It is the basis of many other algorithms. It is also deceivingly simple: For example, if you replace the queue in a BFS implementation by a stack, do you get DFS?
The Sieve of Eratosthenes, simple & intuitive.
I also like the beauty of Horner's Algorithm.
Dijkstra's algorithm: the single-source shortest path problem for a graph with nonnegative edge path costs. It's used everywhere, and is one of the most beautiful algorithms out there. The internet couldn't be routed without it - it is a core part of routing protocols IS-IS and OSPF (Open Shortest Path First).
Gentry's Fully Homomorphic Encryption Scheme (either over ideal lattices or over the integers) is terribly beautiful. It allows a third party to perform arbitrary computations on encrypted data without access to a private key.
The encryption scheme is due to several keen observations.
In his thesis, Craig Gentry solved a long standing (and gorgeous) open problem in cryptography. The fact that a fully homomorphic scheme does exist demands that we recognize that there is some inherent structure to computability that we may have otherwise ignored.
http://crypto.stanford.edu/craig/craig-thesis.pdf
The Gale-Shapley stable marriage algorithm. This algorithm is greedy and very simple, it isn't obvious at first why it would work, but then the proof of correctness is again easy to understand.
The linear time algorithm for constructing suffix arrays is truly beautiful, although it didn't really receive the recognition it deserved http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf
I was impressed when I first saw the algorithm for reservoir sampling and its proof. It is the typical "brain teaser" type puzzle with an extremely simple solution. I think it definitely belongs to the book, both the one for algorithms as well as for mathematical theorems.
As for the book, the story goes that when Erdös died and went to heaven, he requested to meet with God. The request was granted and for the meeting Erdös had only one question. "May I look in the book?" God said yes and led Erdös to it. Naturally very excited, Erdös opens the book only to see the following.
Theorem 1: ...
Proof: Obvious.
Theorem 2: ...
Proof: Obvious.
Theorem 3: ...
Proof: Obvious.
The Tortoise and hare Algorithm. I like it because I'm sure that even if I wasted my entire life trying to find it, there is no way I would come up with such an Idea.
An example as fundamental and "trivial" as Euclid's proof of infinitely many primes:
2-approximation for MAX-CUT -- Independently for each vertex, assign it to one of the two partitions with equal probability.
Gaussian elimination. It completes the generalization sequence from the Euclidean GCD algorithm to Knuth-Bendix.
I've always been partial to Christofides' Algorithm that gives a (3/2)-approximation for metric TSP. In fact, call me easy to please, but I even liked the 2-approximation algorithm that came before it. Christofides' trick of making a minimum weight spanning tree Eulerian by adding a matching of its odd-degree vertices (instead of duplicating all edges) is simple and elegant, and it takes little to convince one that this matching has no more than half the weight of an optimum tour.
How about Grover's algorithm? It's one of the simplest quantum algorithms, and allows you to search an unsorted database in $O(\sqrt N)$. It is provably optimal, and also provably outperforms any classical algorithm. For a bonus it is very easy to understand and intuitive.
Algorithms for linear programming: Simplex, Ellipsoid, and interior point methods.
Marcus Hutter's The Fastest and Shortest Algorithm for All Well-Defined Problems.
This kind of goes against the spirit of the other offerings in this list, since it is only of theoretical and not practical interest, but then again the title kind of says it all. Perhaps it should be included as a cautionary tale for those who would look only at the asymptotic behavior of an algorithm.
Knuth's Algorithm X finds all solutions to the exact cover problem. What is so magical about it is the technique he proposed to efficiently implement it: Dancing Links.
Robin Moser algorithm for solving a certain class of SAT instances. Such instances are solvable by Lovasz Local Lemma. Moser algorithm is indeed a de-randomization of the statement of the lemma.
I think that is some years his algorithm (and the technique for its correctness proof) will be well digested and refined to the point of being a viable candidate for an Algorithm from the Book.
This version is an extension of his original paper, written with Gábor Tardos.
I think we must include Schieber-Vishkin's, which answers lowest common ancestor queries in constant time, preprocessing the forest in linear time.
I like Knuth's exposition in Volume 4 Fascicle 1, and his musing. He said it took him two entire days to fully understand it, and I remember his words:
I think it's quite beautiful, but amazingly it's got a bad press in the literature (..) It's based on mathematics that excites me.