355
$\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

-1
$\begingroup$

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:

  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.

  2. Any live cell with two or three live neighbours lives on to the next generation.

  3. Any live cell with more than three live neighbours dies, as if by overcrowding.

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

$\endgroup$
  • $\begingroup$ While Conway has made significant contributions to mathematics (surreal numbers, monstrous moonshine, free will theorem not to mention them), I am skeptical of the claims regarding the Game of Life. Is there any evidence that it allows the emergence of complex multiscale structures as witnessed in real life? See e.g. hpl.hp.com/techreports/2006/HPL-2006-2.pdf $\endgroup$ – Super0 Feb 28 '14 at 2:37
-2
$\begingroup$

All the answers are so amazingly good. What about the most widely used Algorithm called 'Linear Search' ? Yes it is too simplistic but isn't it the most widely used ? At least worth a mention.

$\endgroup$
-2
$\begingroup$

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:

  • usefulness: does the algorithm have important applications?
  • intuitivity: is the algorithm easy to understand/implement; does it avoid complex data structures?
  • conciseness: does the algorithm have a short description in pseudo-code or natural language?

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.

$\endgroup$
  • 1
    $\begingroup$ I think you are missing the joke. The mathematician Paul Erdős was famous for exclaiming "This one is from The Book" when he learned of a beautiful and elegant proof. He imagined that the Supreme Fascist (his term for God) greedily kept all the most beautiful proofs in The Book, but would not reveal them to mere mortals. Later this inspired a book titled "Proofs from The Book" but that is beside the point. So this question is not about writing a book of algorithms, it's about elegance and beauty. $\endgroup$ – Sasho Nikolov Feb 28 '14 at 16:46
  • $\begingroup$ I think that the quest for beauty in math is due to cultural reasons, probably because of its roots in geometry. On the other hand, algorithmics is about solving concrete problems, and thus can be pushed in two antagonistic directions: maximum efficiency versus maximum applicability. It seems clear to me that a book of algorithms, should it ever exist, must favor the second direction, possibly excluding some established algorithms that are fast but of limited use. Then again, I apologize for my bad sense of humor, but I consider this a serious question even if it seems a joke on the surface. $\endgroup$ – Super0 Feb 28 '14 at 18:33
  • 1
    $\begingroup$ the question is serious, but it asks about elegance, not "what should be in a book about algorithms" (rather it's "what algorithms are from The Book"). by the way quite a few books on algorithms exist.. $\endgroup$ – Sasho Nikolov Feb 28 '14 at 19:47

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.