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.
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.
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.
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.
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.
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
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
If Dijkstra is specified, I think that Bellman-Ford is even a better candidate.
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.
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.