358
$\begingroup$

Paul Erdos 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.

$\endgroup$
  • 11
    $\begingroup$ Great question! [Edit:} One question. Where do we draw the line between algorithms and datastructures? What if the key insight to an algorithm is intimately related to a datastructure (for example UNION FIND in the inverse Ackermann function)? $\endgroup$ – Ross Snider Aug 17 '10 at 18:25
  • 4
    $\begingroup$ a great source and maybe a candidate for such a book is "Encyclopedia of Algorithms" springer.com/computer/theoretical+computer+science/book/… $\endgroup$ – Marcos Villagra Aug 17 '10 at 23:15
  • 21
    $\begingroup$ I'm a little surprised that algorithms which I consider quite tricky (KMP, linear suffix arrays) are considered by others as being "from the Book." To me, "from the Book" means simple and obvious, but only with hindsight. I'm curious how others interpret "elegant". $\endgroup$ – Radu GRIGore Aug 19 '10 at 7:33
  • 49
    $\begingroup$ @supercooldave You don't have to believe in God, but you should believe in his book. ;-) $\endgroup$ – Ross Snider Aug 24 '10 at 22:27
  • 10
    $\begingroup$ During a lecture in 1985, Erdős said, "You don't have to believe in God, but you should believe in The Book." $\endgroup$ – Robert Massaioli Dec 15 '10 at 3:17

93 Answers 93

20
$\begingroup$

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:

  1. 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.

  2. Spielman (1995) developed these ideas further to give a code with both linear time encoding and decoding.

$\endgroup$
  • $\begingroup$ Much more beautiful than LT or Raptor! $\endgroup$ – Ross Snider Aug 22 '10 at 2:12
18
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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

$\endgroup$
15
$\begingroup$

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:

  • Randomized equality testing (hugely important in communication protocols)
  • Hashing with chaining
  • Count-min sketches

$\endgroup$
  • $\begingroup$ another application: the perfect hashing algorithm of Fredman, Komlos, and Szemeredi, itself quite beautiful $\endgroup$ – Sasho Nikolov Mar 30 '12 at 22:39
13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ excellent idea !!!! $\endgroup$ – Suresh Venkat Aug 26 '10 at 5:07
13
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

Moore's O(n) Majority voting algorithm is like a magic-trick!

$\endgroup$
12
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ This would be an even better answer, if you could name a concrete algorithm for these problems which you think should be called an "algorithm from the book". (FFT is a fine answer already) $\endgroup$ – Moritz Aug 17 '10 at 21:44
  • 10
    $\begingroup$ Please, one algorithm per answer. (And we already have KMP.) $\endgroup$ – Jukka Suomela Aug 17 '10 at 23:18
  • $\begingroup$ I'm pretty sure Berlekamp-Massey's algo is not error correction. To me it seems more along the lines of reverse engineering an LFSR back to a particular state given the output bits of the mentioned LFSR. I don't see that as error correction more than a well formed parsing algorithm. $\endgroup$ – Corey Ogburn Aug 24 '10 at 18:05
11
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ thats an awesome choice...i like the way they analyze the algorithm...by picking what, in my opinion, is a very non-trivial thing to amortize on $\endgroup$ – Akash Kumar Feb 25 '11 at 3:08
10
$\begingroup$

Ford–Fulkerson Algorithm has to be there ... Also Sanjeev Arora's PTAS for Euclidean TSP will be there.

$\endgroup$
10
$\begingroup$

The (random projection algorithm implicit in the) Johnson-Lindenstrauss lemma!

$\endgroup$
10
$\begingroup$

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.

http://en.wikipedia.org/wiki/Cycle_detection

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ this is a great example, and the idea has found uses ranging from list decoding to secret sharing. $\endgroup$ – Sasho Nikolov Jun 16 '13 at 23:29
9
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

The O(n) algorithm for finding the maximum-sum subsequence of a list of integers L.

  • L can contain both positive and negative integers
  • L is not necessarily sorted
  • L can contain duplicate entries
  • subsequence length can be in the range [1, n] where n is the length of 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).

$\endgroup$
  • 1
    $\begingroup$ This algorithm is also known as “Kadane’s Algorithm.” I nearly missed this answer because searching for “Kadane” didn’t yield any result on this page, and was just about to write one suggesting this algorithm. $\endgroup$ – k.stm Nov 14 '15 at 17:27
  • $\begingroup$ can you please update the links, both are not working. $\endgroup$ – LoveToCode Sep 14 '17 at 7:02
9
$\begingroup$

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.

http://en.wikipedia.org/wiki/Risch_algorithm

$\endgroup$
  • $\begingroup$ That seems to be an incredibly complicated algorithm. According to Wikipedia, no software currently implements the full algorithm due to its complexity. In fact, it's not even a terminating algorithm. Other than the problem it solves, in what sense is this an "elegant" algorithm? $\endgroup$ – Mark Reitblatt Nov 16 '10 at 0:20
8
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ note that "Newtons method" for finding solutions via the derivative is a 1-d analogue of multivariate steepest descent. $\endgroup$ – vzn Jan 25 '12 at 23:08
8
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ In my book, that's someone everyone should now, very few heard the term, and many keep reinventing. $\endgroup$ – Radu GRIGore Aug 26 '10 at 9:38
8
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I disagree that "There is no way to make a good pivot choice." There may be no instant way to make a good pivot choice, but median of medians will find a good pivot. $\endgroup$ – jbapple Sep 22 '10 at 21:03
  • 1
    $\begingroup$ I think the point really is that in terms of simplicity, elegance, and computational economy, Mergesort belongs in the Book and Quicksort probably does not. I don't completely agree, but +1 for bringing up the idea that the Book isn't just a collection of favorite algorithms. $\endgroup$ – whuber Oct 1 '10 at 20:20
  • 4
    $\begingroup$ The most elegant way to choose the quicksort pivot is to choose it randomly. Then (and only then) quicksort belongs in The Book. $\endgroup$ – Jeffε Apr 1 '12 at 16:03
  • $\begingroup$ Choosing a pivot randomly is a deus ex machina non-answer. We're talking about The Book here, not The Book plus a qualified source of randomness. Mergesort in, quicksort out. $\endgroup$ – Daniel Lyons Jun 17 '13 at 3:28
8
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

I wonder nobody mentioned Schöning's random-walk algorithm for 3-SAT solving yet. It it very simple:

  • Start with a random assignment
  • As long as there exists an unsatisfied clause: Flip a randomly-selected variable in this clause

Nevertheless, it is to date one of the fastest algorithms in its class.

$\endgroup$
8
$\begingroup$

The Viterbi algorithm, low-density parity-check codes, and turbo codes- communication at the noise floor!

$\endgroup$
7
$\begingroup$

Knuth-Bendix algorithm and the analogous Buchberger's algorithm.

$\endgroup$
7
$\begingroup$

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 !

$\endgroup$
  • $\begingroup$ This result is very nice, but I don't think it classifies as beautiful as an algorithm. $\endgroup$ – Diego de Estrada Aug 24 '10 at 6:34
7
$\begingroup$

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"
$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh yes, I absolutely love this algorithm! And there is an even more preliminary version of it (same running time, though) which branches on edges. Pick an edge $(u,v)$. Since it must be covered, at least one of $u$ or $v$ must belong to any vertex cover; and we branch on both possibilities. Thank you for suggesting this, I was just about to! :) $\endgroup$ – Neeldhara Sep 4 '10 at 20:13

protected by Kaveh May 10 '13 at 6:52

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.