Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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:
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.
Spielman (1995) developed these ideas further to give a code with both linear time encoding and decoding.
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.
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
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:
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.
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.
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)
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.
Ford–Fulkerson Algorithm has to be there ... Also Sanjeev Arora's PTAS for Euclidean TSP will be there.
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.
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.
The (random projection algorithm implicit in the) Johnson-Lindenstrauss lemma!
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.
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.
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.
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).
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.
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.
The O(n) algorithm for finding the maximum-sum contiguous subarray of a list of integers 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).
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).
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.
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.
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.
I wonder nobody mentioned Schöning's random-walk algorithm for 3-SAT solving yet. It it very simple:
Nevertheless, it is to date one of the fastest algorithms in its class.
The Viterbi algorithm, low-density parity-check codes, and turbo codes- communication at the noise floor!
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.
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 !
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"