# Algorithms from the Book.

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.

• 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)? Aug 17, 2010 at 18:25
• a great source and maybe a candidate for such a book is "Encyclopedia of Algorithms" springer.com/computer/theoretical+computer+science/book/… Aug 17, 2010 at 23:15
• 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". Aug 19, 2010 at 7:33
• During a lecture in 1985, Erdős said, "You don't have to believe in God, but you should believe in The Book." Dec 15, 2010 at 3:17
• This link is relevant: x86.cs.duke.edu/courses/fall06/cps258/references/topten.pdf Feb 11, 2011 at 2:18

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.

• Can you explain what "Run Trivial" means? Jun 17, 2013 at 0:49

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.

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.

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.

image sourced from this wikipedia article

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.

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

• +1, nice description of a nice algorithm, but I believe that technically it's not completely "in-place" because you need O(log n) (i.e. more than O(1)) stack space to store the final positions of the pivots. (Notice e.g. heapsort doesn't need this.) Aug 28, 2010 at 4:59
• good clarification Sep 5, 2010 at 22:03

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

• Also there is a linear time algorithm for triples Apr 6, 2012 at 21:27

If Dijkstra is specified, I think that Bellman-Ford is even a better candidate.

• I think Dijkstra's algorithm is actually an ugly one compared to Bellman-Ford! Sep 4, 2014 at 5:54

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.

• A very good collection indeed! Apr 2, 2012 at 4:00

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.

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.

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.

The Thompson NFA construction and, in particular, evaluation method. Probably the slickest bit of code I've ever seen.

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.

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.

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

I like the CORDIC algorithm for solving trigonometric and hyperbolic functions, especially when implemented using fixed-point integer representations.

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.

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.