381
$\begingroup$

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.

Improve this question
$\endgroup$
10
  • 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
    Commented Aug 17, 2010 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
    Commented Aug 17, 2010 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
    Commented Aug 19, 2010 at 7:33
  • 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
    Commented Dec 15, 2010 at 3:17
  • 4
    $\begingroup$ This link is relevant: x86.cs.duke.edu/courses/fall06/cps258/references/topten.pdf $\endgroup$
    – Huck Bennett
    Commented Feb 11, 2011 at 2:18

92 Answers 92

Reset to default
1 2 3
4
-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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Feb 28, 2014 at 2:37
-3
$\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.

Improve this answer
$\endgroup$
3
  • 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
    Commented Feb 28, 2014 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
    Commented Feb 28, 2014 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
    Commented Feb 28, 2014 at 19:47
1 2 3
4

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