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.
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.
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!
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?
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).
The Sieve of Eratosthenes, simple & intuitive.
I also like the beauty of Horner's Algorithm.
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
Strassen's algorithm for matrix multiplication.
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
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.
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.
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.
Expander codes
Gallager showed in the 1960's that random low density parity codes have good rate and relative distance with high probability. But it was Sipser and Spielman (1994), following work of Tanner (1981), who had the beautiful insight that it is the expansion of the natural bipartite graph associated with the parity check matrix of the code that leads to the code being good. They then proved that the following simple decoding algorithm runs in linear time for any expander code: repeatedly check if there exists a bit of the received word which violates more than half of the parity checks it is involved in, and if there is such a bit, flip it.
Two footnotes:
Graphs of such expansion were not explicitly constructible at the time of Spielman and Sipser, but they now are due to work of Capalbo, Reingold, Vadhan and Wigderson (2002). Sipser and Spielman themselves constructed linear time decodable codes by using the Tanner product construction.
Spielman (1995) developed these ideas further to give a code with both linear time encoding and decoding.
The algorithm that amazed me the most is Timothy Chan's O(n log h) planar convex hull algorithm: http://www.cs.uwaterloo.ca/~tmchan/conv23d.ps.gz
I find it impressive how the proper application of several simple techniques led to an optimal algorithm for such a classic problem, 10 years after the first optimal algorithm for the problem.
Computing the closest pair of points in the plane in linear time (especially because there is Omega(n log n) lower bound in the comparison model). The algorithm is originally due to Rabin, but there are considerably simpler and more elegant versions. See for example: http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/lec/01_min_disk.pdf
I would add universal hashing (or more generally pairwise independent hash functions) of Carter and Wegman. While not really an algorithm in itself, it is the enabling technology in a lot of fantastic randomized algorithms. To name a few:
The Goemans-Williamson algorithm for MAX-CUT. It was one of the first SDP rounding schemes to be analyzed, and uses a simple geometric fact that seems totally unrelated to the problem at first sight.
This collection of answers would be a great start on an outline for a book with that title! I have really enjoyed Proofs from the Book, have even purchased all four editions.
I would include the edge-flipping algorithm for constructing the Delaunay Triangulation in 2D. Even though it is not optimal.
Avi Wigderson in Part II of these lectures gives the following examples of algorithmic gems, with pseudocode:
Shortest path (Dijkstra's algorithm)
Pattern matching (Knuth-Morris-Pratt's algorithm)
Fast Fourier Transform (Cooley-Tukey's algorithm)
Error Correction (Berlekamp-Massey's algorithm)
We cannot forget Binary Decision Diagrams, a family of data structures that have become the method for representing boolean functions. I think the key insight is the dual nature of being a data structure and a "algorithm" at the same time (which indeed is the powerful idea behind Knuth-Morris-Pratt.)
My reference is again Knuth's Volume 4 Fascicle 1, and you can see his musings here and here.
Ford–Fulkerson Algorithm has to be there ... Also Sanjeev Arora's PTAS for Euclidean TSP will be there.
Kosaraju's Algorithm to find the strongly connected components of a directed graph. Consists essentially of doing two DFS traversals on the digraph, the second after reversing all the edges and picking vertices in the reverse order as they were seen in the first traversal.
Lenstra-Lenstra-Lovász Lattice Basis Reduction. Maybe not quite from the book (since it's, at least to me, a bit messy), but it definitely is worth a mention here.
I propose Reed-Solomon coding. The basic idea is that you can encode your data as a polynomial over a finite field. You can then evaluate this polynomial at several different points and these values become the messages that you will send. If the degree of the polynomial is N, then a receiving party only needs to receive N+1 messages in order to reconstruct the polynomial and hence the original data.
I find this extremely elegant. I just wish I had more cause to use it.
Floyd's Cycle Finding Algorithm is one of the most beautiful things I've seen. Especially the part where he finds where the cycle begins.
The O(n) algorithm for finding the maximum-sum contiguous subarray of a list of integers L.
For example the list {-1, 500, -100, 101} has a maximum-sum subsequence of {500, -100, 101}.
I learned about this algorithm from Jon Bentley's Programming Pearls. Note the code contains a few versions of this algorithm... the last version is O(n).
The Risch algorithm finds a nice, elementary form of integrals or tells you that it doesn't exist. Solves a problem open since Newton/Leibniz invented calculus and is so complicated that the full version has never been implemented.
In particular, it tells you why $e^{x^2}$, $x^x$, $\frac{log x}{x}$ and the like don't have elementary primitives, and gives you a way of constructing the primitive if your function admits one.
I think that there should be at least one persistant data structure. In particular, the "persistant array" let us obtains a lot of other persistant data-structures where we wouldn't expect them.
I guess the algorithm to "hash-cons" is really interesting. This idea let us usually save both memory, time, and avoid doing many time the same computation by finding quickly equality between many structures in memory, or that has been in memory (at least that has been in memory and did not need to be garbage collected).
The Simplex Algorithm is an algorithm for solving linear programming problems. While it has an exponential worst case running time it is very fast in practice. There are polynomial running time algorithms, but none are as simple to implement as the simplex algorithm. The algorithm works by traversing the edges of a simplex and it's possible that you will have to traverse every edge, which is where the exponential bound comes from.
An algorithm that I find truly simple and elegant is the Rabin-Karp algorithm of using rolling-hashes for linear time string search. A lot simpler to wrap your head around than KMP.
Everyone says Knuth-Morris-Pratt. I don't think the Boyer-Moore string-matching algorithm gets enough credit.
There's a wonderful exploration Boyer-Moore's implementation in grep on ridiculousfish. For the more academically-inclined, Mike Haertel, grep's longtime maintainer, explains why grep is so fast.
I looked through all the answers and it seems that many of them are not describing Algorithms from the Book. Some are extremely useful, but not particularly beautiful, in my opinion. It's hard to say what makes an algorithm beautiful, but I will try to argue that quicksort would not be found in The Book. It's a fairly simple algorithm, which makes it a good candidate for The Book, but there is one major issue:
The behaviour of quicksort is inconsistent. It performs well in practice, but bad pivot choices could lead to quadratic running-time. And the pivot choice is arbitrary. There is no way to make a good pivot choice. Since we are talking about algorithms, I think we can agree that running-time matters.
Though, there is a sorting algorithm that I would expect to find in The Book, and that is mergesort:
Each element is viewed as a sorted subsequence of size one.
Merge pairs of adjacent subsequences repeatedly.
Stop when there is only one sorted subsequence left.
The beauty of mergesort is in the simplicity of the merge function that merges two sorted subsequences into one sorted subsequence. Try to code this function, and enjoy.
I wonder nobody mentioned Schöning's random-walk algorithm for 3-SAT solving yet. It it very simple:
Nevertheless, it is to date one of the fastest algorithms in its class.
The Viterbi algorithm, low-density parity-check codes, and turbo codes- communication at the noise floor!
I'm not sure if the question requests particularly beautiful algorithms, but as far as useful and simple algorithms go..
I propose steepest descent. By this I specifically mean an iterative minimization technique for a function $f$ over a domain with norm $\|\cdot\|$ which, at every step, from an iterate $x$, performs linesearch in the direction(*) $v := \textrm{argmin}_u \{\nabla f(x)^T u : \|u\| = 1\}$. (For two texts which use this terminology and provide discussion, see Boyd/Vandenberghe or Hiriart-Urruty/Lemarechal.)
When $\|\cdot\|$ is the $l_2$ norm, this gives gradient descent, which was certainly known to Cauchy but arguably known by every living organism. When $\|\cdot\|$ is the $l_1$ norm, this is greedy coordinate ascent, which includes boosting, which is similar to Gauss-Seidel iterations.
When $\|\cdot\|$ is any norm over $\mathbb{R}^n$ and $f$ is strongly convex, this method exhibits linear convergence (i.e. $\mathcal{O}(\ln(1/\epsilon))$ iterations to error $\epsilon$); for a proof of this, see Boyd/Vandenberghe. (The constants are bad because it uses the ones provided by norm equivalence.)
Certainly, there are methods with faster convergence, the ability to handle nonsmooth objectives, etc. But this method is simple and can work decently, and thus is in widespread use, and always will be.
(*) There may be more than one minimizer (consider $l_1$ norm), but there is always at least one (gradients are linear, and the set is compact).
How can we forget Shor's quantum factoring algorithm ? Even though there may never be a universal quantum computer capable of demonstrating the ability of the algorithm to factor really large integers, it is still a stroke of genius to even think of such an algorithm in the first place.
The 2-approximation algorithm for Knapsack:
First, consider the trivial algorithm: select the highest value item that fits. This can obviously be arbitrarily far from optimal.
Now consider the greedy algorithm: greedily select the highest value density items. This can also be arbitrarily far from optimal.
Now, the 2-approximation algorithm: Run Trivial and Greedy. Take whichever solution has the highest value. This is guaranteed to be within a factor of 2 of optimal.
I think that LR parsers are beautiful. A language is deterministic context-free if and only if there exists a LR(1) grammar for it.
I would like to put some non-deterministic algorithm, which may also be in the Book.
In particular, I think of the Immerman's algorithm for non-reachability in directed graph in non deterministic log space ! (or equivalently reachability in universal logspace).
And also probably the algorithm to reduce any problem in NP into an NP-complete problem like SAT; because it is really impressive that one algorithm like this exists !
The (exponential time) algorithms for generating all combinations or all permutations of a given set, list, or structure. They can usually be expressed both concisely and beautifully, and optimizations in this combinatorial generation are often equivalent to some of the most celebrated algorithms. For example: A* search instead of unordered search, when applied to the "generate all paths from X and find the shortest ones" problem, exactly yields Dijkstra's Algorithm!
I simply love that the following is actually an algorithm that will work:
def solve(problem):
foreach answer in generate_all_possible_answers(problem):
if is_good_enough(answer, problem):
return answer
return "No answer found"
An algorithm I consider to be very nice and simple is the classic fixed parameterized algorithm for vertex covers of size at most $k$. It runs in time $2^k n^c$ for some constant $c>0$.
It is based on the simple observation that either a vertex is in the cover or all its neighbors must be. Thus the following pseudo-code applies:
G: a graph with n vertices
k: the maximum size of the cover
def Vertex_Cover(G,k):
if k<=0 and |E(G)|!=0: return False
else:
N= the set of neighbors of an arbitrary vertex v
H1= G - {v}
H2= G - N
return Vertex_Cover(H1,k-1) or Vetex_Cover(H2,k-|N|)
Of course such procedure can be implemented in a decision tree fashion.
Do you know bucket sort?
In my opinion, it is the most elegant, simply & yet it is an incredibly powerfull sorting algorithm
I think that the process of finding a diagonal proof is an algorithm.
The idea of if you can generate a matrix for various things and then if you can find some answer that differs on the diagonal you have a reductio ad absurdam.
I find them sublime.... and beautiful. I somehow feel when you are at the moment of grasping, for example, the diagonal for the proof of the uncountability of the real,.. its always for me like you are peering through reality into the great mystery of it all.
I would add reservoir sampling and the Knuth-Fisher-Yates shuffle. Especially when you start to see the connection between the 2 algorithms.
Boyer-Moore string matching.
I remember when our lecturer taught us about it. He said: "And here comes an algorithm which is impossible to understand completely...". He was right, I still don't fully understand why and how it works, but I nevertheless believe it's an elegant algorithm.
Savitch's Algorithm: a simple recursive algorithm for the Reachability problem, with a conceptually deep consequence: PSPACE=NPSPACE.
The question:
Given an array [a1 a2 ... an b1 b2 ...bn] of 2n elements. Give an in-place algorithm to convert that array to [b1 a1 b2 a2 ... bn an].
I like the linear time solution for this here: http://arxiv.org/abs/0805.1598
If Dijkstra is specified, I think that Bellman-Ford is even a better candidate.
Zeilberger's algorithm, which extends Gosper's algorithm for finding closed-forms of binomial sums.
Knuth included an exercise in TAoCP "[50] Develop computer programs for simplifying sums that involve binomial coeficients" and thanks to Zeilberger's algorithm and related developments it can be considered solved.
theres a really wonderful way to describe in place quicksort
in particular:
let i,j be your initial upper and lower indices for an array a (or slice thereof) . randomly pick an integer $\ell$ in the interval [i,j] as the pivot $p=a[\ell]$. As for the the number of entries greater or equal to p, call this $m$.
We know that there are at most $\min(j-i -m+1, m)$ swap operations needed between the interval $[i, j-m]$ and the interval $[j-m+1,j]$ for us to be able to then recursively sort these two intervals. these swaps can be done by starting from indices $i$ and $j$ and scanning inward on both sides until each side has found an index that violates the ordering relative to the pivot value, at which point a swap is done, then the search continues inward, terminating at the point when these two searches meet.
edit: note that there is actually no special treatment needed for the pivot value, we just apply the swapping operation uniformly.
then recursively sort the intervals you get from the final placement of the pivot value.
this gives you the "c-style" in place quick sort, but explained in a a high level way that has very very clear correctness properties!
:)
note that this isn't a stable sort algorithm
Although perhaps as much a heuristic as an algorithm, since I heard about it a year or two ago, I think that the fast inverse square root is interesting. And even more intriguing that we don't know it's author or how she/he settled upon the magic number.
I just learned about a book entitled Algorithms unplugged, which seems relevant to this topic.
The Ramsey-based complementation construction for Buechi automata. This is something from my advisor, that is pretty obscure, and supplanted by more recent constructions with massively better bounds. However, I really think this specific construction and the math behind it are just amazingly elegant.
If anyone is actually interested, it's section 2 introduction, 2.1, and 2.2 in the below paper, building up to Lemma 2.3.
http://www.cs.rice.edu/~vardi/papers/icalp85rj.pdf
As a fair note for anyone excited to see Ramsey there, it's a very trivial application of the infinite Ramsey theorem. However, it is also (IMO), one of the most beautiful.
Let me also put in a vote for the diagonalization proof of uncountability.
The Shift-And algorithm by Baeza-Yates and Gonnet (Bitap @Wikipedia) for finding all occurrences of a pattern in a text. In my opinion the simplest example of a useful seminumerical algorithm.
The Kalman filter, absolutely brilliant for handling data with noise: http://en.wikipedia.org/wiki/Kalman_filter
I think two algorithms that require place number notation deserve a prominent place in the book: long multiplication and division. Especially in binary these are quite elegant. Moreover, there are few algorithms that do not benefit from them.
In THE BOOK, there should include "The Power of Random Two Choices" paradiam.
http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf
Result is pretty simple, but super helpful to use in practical scenarios, and algorithm design . It can help to reduce computation complexity by load balance in algorithm based on "the power of random two choices"
The divide and conquer algorithm by Michael Shamos to solve the planar Closest pair of points problem in $O(n \log n)$ time. Not only is this optimal in the algebraic decision tree model of computation, it also illustrates the power of recursive thinking in a non-trivial setting.
The Thompson NFA construction and, in particular, evaluation method. Probably the slickest bit of code I've ever seen.
It's such a simple thing, but in it's simplicity is it's elegance: Linear Feedback Shift Registers. As a datastructure they are simply the number of bits in the loop and at most 4 pots, in many cases only 2. With simple actions of an XOR logical equation and a shift and you have a system that goes through every possible state in a very efficient way. They're an easy to implement PRNG (psuedo random number generator) all while being easy to implement in both hardware and software.
I think that Hensel Lifting is pretty nifty too, and it has many applications in algorithmic number theory and algebra.
If union-find is in the book, why can't Bloom filters be there? If you are not familiar with Bloom filters, this video is a quick but nice introduction.
Hook and shortcut from:
AN EFFICIENT PARALLEL BICONNECTIVITY ALGORITHM
Tarjan and Vishkin
http://www.umiacs.umd.edu/users/vishkin/TEACHING/ENEE759KS12/TV85.pdf
This Ruby implementation returns the partitions of a transformation where elements x,y interact with each other.
def partitions(trans)
parent =Array.new()
0.upto(trans.length-1) do |index|
parent.push(index)
end
0.upto(trans.length-1) do |outer_index|
0.upto(trans.length-1) do |index|
#shortcut
parent[index] = parent[parent[index]]
end
0.upto(trans.length-1) do |index|
#hook
if (parent[trans[index]] < parent[parent[index]])
parent[parent[index]] = parent[trans[index]]
end
if (parent[index] < parent[parent[trans[index]]])
parent[parent[trans[index]]] = parent[index]
end
end
end
return parent
end
Polynomial time Max-Cut algorithm in planar graphs of F. HADLOCK. Hadlock gave an elegant reduction from Max-Cut to several other problems on the dual of planar graphs and finally to maximum matching problem which is polytime-solvable. I think this algorithm is very beautiful and should be included in THE BOOK.
I am sure "Ancient Egyptian Multiplication" algorithm will at least find a mention in sidenote in the BOOK. Simple, elegant and has an known or most probably unknown side effect of one of the first usages of binary number. Still wondering how they figured it out in the first place.
The algorithm that uses Pascal's Triangle (wikipedia) to find "a choose b". Especially useful when a!, b!, and/or (a - b)! is so large that the traditional expression a!/b!(a-b)! is hard to compute. For example "51 choose 23".
From the world of purely functional data structures and algorithms, Gérard Huet's zipper comes to my mind.
Normally, PFDS do not expose local structure, due to the absence of explicit pointers. If you want to access a certain node in a tree, you're out of luck.
However, with an extremely simple insight (just "turn the tree inside-out" and remember the path structure from your location), accessing specific locations in PFDS is made possible, all in a purely-functional manner. This, basically, is the essence of the zipper.
If God is not a functional programmer and would only include one PFDS in the Book, it would have to be the zipper.
As we talk of a book of "God" and a beautiful algorithm, something that comes to my mind is Conway's Game of Life. It sets a grid as a cellular automaton and sets the following simple rules:
Any live cell with fewer than two live neighbours dies, as if caused by under-population.
Any live cell with two or three live neighbours lives on to the next generation.
Any live cell with more than three live neighbours dies, as if by overcrowding.
Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
Amazing, how simple rules like these and a random seeded initialization can achieve something as beautiful as life and evolution.
I would like to make a basic remark which doesn't appear in the other answers. The elegance/beauty is somewhat subjective so I wouldn't pick it as a primary criterion for a book of algorithms. It seems more rational to consider the following criterions:
Personally, I rank these three criterions in this order, from the most to the least important. In particular, I advocate a "principle of maximum usefulness", i.e. a good algorithm is one that finds multiple uses for seemingly unrelated applications.
An example is provided by the "merge sort" algorithm: in addition to providing a fast sorting method, it also allows to compute the number of inversions of a permutation in quasi-linear time, i.e. better than the naive quadratic approach. Another example is the simple polynomial algorithm for coloring chordal graphs, which finds applications such as timetabling and register allocation.
