<p><strong>Union-find</strong> is a beautiful problem whose best algorithm/datastructure (<strong>Disjoint Set Forest</strong>) is based on a spaghetti stack. While very simple and intuitive enough to explain to an intelligent child, it took several years to get a tight bound on its runtime. Ultimately, its behavior was discovered to be related to the inverse Ackermann Function, a function whose discovery marked a shift in perspective about computation (and was in fact included in Hilbert's <i>On the Infinite</i>).</p>

<p>Wikipedia provides a good introduction to <a href="http://en.wikipedia.org/wiki/Disjoint-set_data_structure">Disjoint Set Forests</a>.</p>

CC BY-SA 2.5
2010-08-17T19:05:38.253Z
2010-09-15T08:37:58.823Z
2010-09-15T08:37:58.823Z
Ross Snider
<p><strong><a href="http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm">Knuth-Morris-Pratt</a></strong> string matching.  The slickest eight lines of code you'll ever see.</p>

CC BY-SA 3.0
2013-06-17T01:20:14.477Z
@Mechko The fact that this algorithm was discovered simultaneously and independently by separate people is an indication that it is obvious to an extent. Whether something is "obvious" is a function of project constraints and broader programming environment. If you need (1) fast text searching and (2) you're aware of the importance of truly O(n) algorithms, and (3) you've encountered text with partial matches before, and (4) you have the time to do things "right", then this algorithm is probably obvious.
Matt Gallagher
CC BY-SA 3.0
2014-10-15T01:07:36.320Z
@Kaveh Please read Section 7 (Historical Remarks) from the original KMP paper. It has great remarks. About Morris writing a text editor which "was too complicated for other implementors of the system to understand".  About Knuth "the first time in Knuth’s experience that automata theory had taught him how to solve a real programming problem better than he could solve it before". And " Knuth was chagrined to learn that Morris had already discovered the algorithm, without knowing Cook’s theorem;". FUN.
Hendrik Jan
CC BY-SA 3.0
2014-09-04T05:23:04.887Z
In [an interview](http://www.informit.com/articles/article.aspx?p=2213858) Knuth said that the idea for the algorithm came from studying Stephen Cook's [Two-way finite automaton](http://en.m.wikipedia.org/wiki/Two-way_deterministic_finite_automaton) for palindromes.
Kaveh
CC BY-SA 2.5
2010-09-02T12:50:00.480Z
It's kinda mind boggling to realize that that was something that wasn't obvious at some time and is only obvious now because they came up with it and we learnt it...  I think we should apply Carr's theory of history to Mathematics and Computer Science.
Ritwik Bose
CC BY-SA 2.5
2010-09-22T07:20:51.433Z
By the description, I'd say this is related to the Boyer-Moore fast substring search.
bart
CC BY-SA 2.5
2010-08-17T20:49:28.757Z
2010-08-18T16:01:11.407Z
2010-08-18T16:01:11.407Z
Jeffε
<p><a href="http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm">The algorithm of Blum, Floyd, Pratt, Rivest, and Tarjan</a> to <strong>find the <i>k</i>th element of an unsorted list</strong> in linear time is a beautiful algorithm, and only works because the numbers are <em>just right</em> to fit in the Master Theorem.  It goes as follows:</p>

<ol>
<li>Sort each sequence of five elements.</li>
<li>Pick out the median in each.</li>
<li>Recur to find the median of this list.</li>
<li>Pivot on the median of medians (as in Quicksort)</li>
<li>Select the proper side of the list and position in that list, and recur.</li>
</ol>

CC BY-SA 3.0
2012-03-30T22:34:57.747Z
This is one of my favorite algorithms. I like an intuition for it that I learnt from Chazelle's discrepancy book: the set of medians of groups of $1/\epsilon$ elements is like an $\epsilon$-net for intervals in the ordered list of the input numbers. So the algorithm follows a general paradigm: compute an $\epsilon$-net fast, solve the problem on the net, recurse on some part of the input to refine the solution, until you have the exact solution. it's very useful technique
Sasho Nikolov
CC BY-SA 3.0
2012-03-30T22:36:47.137Z
BTW once you parametrize the size of the groups, the constants are not so magical. they are of course optimized to give the right thing in the Master theorem
Sasho Nikolov
CC BY-SA 3.0
2013-11-23T15:37:42.820Z
Ruby implementation, https://gist.github.com/chadbrewbaker/7202412 Is there a version of the algorithm that uses (constant,log) space, or do you have to use linear scratch space to hold the medians?
Chad Brewbaker
CC BY-SA 3.0
2015-03-16T17:08:20.833Z
The claim that "this only works because the numbers are just right to fit in the master theorem" is not really true. If you replace the number $5$ with a larger number $n$, it is easy to see that the two numbers that have to sum to less than $1$ converge to $3/4$ and $0$, so all sufficiently large $n$ work. $5$ is just the first number that works, it's not the only one.
Will Sawin
CC BY-SA 3.0
2010-08-17T20:54:46.920Z
2013-06-16T15:00:31.670Z
2013-06-16T15:00:31.670Z
Derrick Stolee
<p><a href="http://en.wikipedia.org/wiki/Binary_search_algorithm">Binary Search</a> is the most simple, beautiful, and useful algorithm I have ever run into.</p>

CC BY-SA 3.0
2013-06-16T19:32:10.703Z
And insanely hard to write correctly– see "[Are you one of the 10% of programmers who can write a binary search?](http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/)"
jade
CC BY-SA 3.0
2017-10-20T12:45:21.433Z
In my first graduate algorithms course we had 15 minute quizzes where we had to solve 2-3 problems by hand. The first such quiz included a binary search tree and two questions about heaps. I was embarrassed and dismayed to learn I had gotten the binary search problem wrong, before being told that in a class of about 30 people there were two correct answers. But even knowing that, the fact that it took 15 years for the professional community to get right is staggering.
Stella Biderman
CC BY-SA 4.0
2023-08-14T20:19:14.130Z
@jade the link is broken. Here is an [archive](https://web.archive.org/web/20230127150411/http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/)
Benjamin Wang
CC BY-SA 4.0
2023-09-09T04:54:55.817Z
OK, prepare for heresy. Classic binary search, that you linked to, is one of the most awful algorithms that our field has the misfortune of cherishing. The biggest problem is that it's almost beautiful, but most people aren't aware of the wart. Don't have to believe me, a nobody: read From Mathematics to Generic Programming by Alex Stepanov.
The principle that it is based on, the bisection method, is beautiful. I can expand on this and explain in another comment if people are interested.
Jeremy W. Murphy
CC BY-SA 4.0
2023-09-23T04:10:01.673Z
Essentially, there are two warts: i) stopping immediately when the value is found, in a sequence with duplicates, you don't know which one you found or how many there are; ii) returning null when it's not found throws away the work done in finding that position, which is still useful in some applications such as finding where to insert that value or searching on a prefix of a value (e.g. search for "str" to find the first word starting with it).
So I'm sorry, but Binary Search, the classic definition in Knuth, is not beautiful. The beautiful variation is called equal_range.
Jeremy W. Murphy
CC BY-SA 2.5
2010-09-21T02:48:39.557Z
I would replace elegant with intuitive. There is nothing that elegant about it; its simplicity is its real beauty.
Robert Massaioli
CC BY-SA 2.5
2010-12-13T21:41:49.967Z
@Robert Massaili: I replaced elegant with beautiful.  You were right about that.
michalmocny
CC BY-SA 2.5
2010-09-20T13:59:39.237Z
2010-12-13T21:40:47.050Z
2010-12-13T21:40:47.050Z
michalmocny
<p>I'm surprised not to see the <a href="http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm">Floyd-Warshall algorithm</a> for all-pairs shortest paths here:</p>

<pre><code>d[]: 2D array. d[i,j] is the cost of edge ij, or inf if there is no such edge.

for k from 1 to n:
  for i from 1 to n:
    for j from 1 to n:
      d[i,j] = min(d[i,j], d[i,k] + d[k,j])
</code></pre>

<p>One of the shortest, clearest non-trivial algorithms going, and $O(n^3)$ performance is very snappy when you consider that there could be $O(n^2)$ edges.  That would be my poster child for dynamic programming!</p>

CC BY-SA 3.0
2013-11-25T00:31:50.860Z
This algorithm can be also generalised in a really neat way. See e.g. http://r6.ca/blog/20110808T035622Z.html and http://www.cl.cam.ac.uk/~sd601/papers/semirings.pdf
Mikhail Glushenkov
CC BY-SA 4.0
2019-11-01T21:48:08.843Z
And a striking fact is that we still don’t have (polynomially) faster algorithm for APSP than Floyd’s!
Lwins
CC BY-SA 2.5
2010-08-28T05:21:05.193Z
2010-08-28T05:21:05.193Z
user651
<p><a href="http://en.wikipedia.org/wiki/Euclidean_algorithm"><strong>Euclidean algorithm</strong></a> to compute <a href="http://en.wikipedia.org/wiki/Greatest_common_divisor">the greatest common divisor (GCD)</a></p>

CC BY-SA 3.0
2012-04-28T14:47:21.630Z
The greatest one of all :)
user3162
CC BY-SA 3.0
2017-08-31T06:35:46.700Z
and probably the oldest _and_ alive of them all!
lifebalance
CC BY-SA 2.5
2010-11-12T20:15:15.137Z
2010-11-12T20:15:15.137Z
Deyaa
<p>Might seem somewhat trivial (especially in comparison with the other answers), but I think that <strong><a href="http://en.wikipedia.org/wiki/Quicksort">Quicksort</a></strong> is really elegant. I remember that when I first saw it I thought it was really complicated, but now it seems all too simple.</p>

CC BY-SA 3.0
2013-06-16T13:48:35.720Z
Quicksort in theory is simple (can be outlined in 4 steps) and could be highly optimized, but in practice it's very difficult to code correctly. Which is why it doesn't get my vote.
Dennis
CC BY-SA 3.0
2013-06-16T16:37:41.397Z
@Konrad: Running time cannot have a lower bound than storage used, because you need to touch all the storage you use. Even if compare runtime initially dwarfs storage access, at large numbers, n-squared storage use means you have n-squared runtime. Quicksort, to be average n log n, requires in-place mutatability in the actual runtime.
Jon Watte
CC BY-SA 3.0
2013-06-16T20:18:30.933Z
@Jon Agreed with the first part of the comment but (functional) quicksort does *not* have quadratic storage – at least I don’t see why.
Konrad Rudolph
CC BY-SA 2.5
2010-09-03T22:28:17.190Z
Quicksort also raises interesting questions about what exactly the essence of an algorithm is. E.g. the standard elegant Haskell implementation *looks* exactly like the standard pseudo-code definition, but it has different asymptotic complexity. So, is Quicksort just about divide-and-conquer or is the clever in-situ pointer-fiddling an essential part of Quicksort? Can Quicksort even be implemented in a purely functional setting or does it require mutability?
Jörg W Mittag
CC BY-SA 2.5
2010-09-05T18:32:46.427Z
The idea of the "essence" or the "moral" of an algorithm comes of course from the beautiful paper *The Genuine Sieve of Eratosthenes* by Melissa E. O'Neill (http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf) and the quicksort discussion comes from the LtU discussion of that paper (http://lambda-the-ultimate.org/node/3127/), specifically starting at this comment: http://lambda-the-ultimate.org/node/3127/#comment-45549
Jörg W Mittag
CC BY-SA 2.5
2010-09-08T11:31:02.383Z
@Jörg: Implementing quicksort on linked lists is completely sensible, and has the **same asymptotic running time** as its in-place implementation on arrays (heck, even the naive out-of-place implementation on arrays has the same running time) – both on average and in the worst case. As for space usage, this is indeed different but it must be said that even the “in-place” version requires non-constant extra space (call stack!), a fact readily overlooked.
Konrad Rudolph
CC BY-SA 2.5
2011-01-31T23:31:09.740Z
Also it's worth to mention Vladimir Yaroslavskiy's Dual-Pivot Quicksort. That should be at least 20% faster original quicksort http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
SaveTheRbtz
CC BY-SA 2.5
2010-08-17T21:35:37.263Z
2010-08-19T15:45:14.253Z
2010-08-19T15:45:14.253Z
Tomer Vromen
<p><a href="http://en.wikipedia.org/wiki/Huffman_coding">Huffman coding</a> for data compression.</p>

CC BY-SA 2.5
2010-09-19T20:17:26.000Z
2010-09-19T20:17:26.000Z
Gary
<p>Polynomial identity testing with the <a href="http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma">Schwartz-Zippel lemma</a>:</p>

<p>If someone woke you up in the middle of the night and asked you to test two univariate polynomial expressions for identity, you'd probably reduce them to sum-of-products normal form and compare for structural identity. Unfortunately, the reduction can take exponential time; it's analogous to reducing Boolean expressions to disjunctive normal form.</p>

<p>Assuming you are the sort who likes randomized algorithms, your next attempt would probably be to evaluate the polynomials at randomly chosen points in search of counterexamples, declaring the polynomials very likely to be identical if they pass enough tests. The Schwartz-Zippel lemma shows that as the number of points grows, the chance of a false positive diminishes very rapidly.</p>

<p>No deterministic algorithm for the problem is known that runs in polynomial time. </p>

CC BY-SA 3.0
2015-12-03T07:28:14.970Z
I independently invented the same algorithm while I was working on a paper a couple years ago until someone asked me isn't it Schwartz-Zippel lemma? And I said, what is that? :)
Helium
CC BY-SA 2.5
2010-09-23T03:56:01.357Z
This should have been suggested long ago!  Thanks!
arnab
CC BY-SA 2.5
2010-09-23T04:21:29.130Z
There are several other randomized algorithms that deserve a prominent place in the Book. For these the contrast between the deterministic and probabilistic alternatives is less striking: a deterministic algorithm usually exists but is much more complicated.
Per Vognsen
CC BY-SA 2.5
2010-09-23T03:10:01.650Z
2010-09-23T03:10:01.650Z
Per Vognsen
<p>The <strong><a href="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test">Miller-Rabin primality test</a></strong> (and similar tests) should be in The Book.  The idea is to take advantage of properties of primes (ie using Fermat's little theorem) to probabilistically look for a witness to the number not being prime.  If no witness is found after enough random tests, the number is classified as prime.</p>

<p>On that note, the <strong><a href="http://en.wikipedia.org/wiki/AKS_primality_test">AKS primality test</a></strong> that showed PRIMES is in P should certainly be in The Book!</p>

CC BY-SA 2.5
2010-08-17T20:06:22.883Z
2010-08-18T16:19:02.033Z
2010-08-18T16:19:02.033Z
Lev Reyzin
<p><strong>Depth First Search</strong>. It is the basis of many other algorithms. It is also <em>deceivingly</em> simple: For example, if you replace the queue in a BFS implementation by a stack, do you get DFS?</p>

CC BY-SA 3.0
2013-06-16T13:28:40.077Z
What's the point about BFS with a stack I'm missing? I would have thought that the answer is "yes, you get DFS".
Omar Antolín-Camarena
CC BY-SA 3.0
2013-06-23T10:11:33.510Z
Well, everybody seems to think this problem is trivial. Also, everybody seems to think the answer is "yes", which is wrong. The answer is actually "depends on which BFS implementation you start with". See http://cs.stackexchange.com/questions/329/do-you-get-dfs-if-you-change-the-queue-to-a-stack-in-a-bfs-implementation (This is a question I posted to help with the beta phase of CS.SE)
Radu GRIGore
CC BY-SA 3.0
2013-06-23T10:16:15.043Z
It's also briefly discussed here: http://www.ics.uci.edu//~eppstein/161/960215.html
Radu GRIGore
CC BY-SA 2.5
2010-08-19T07:14:59.453Z
It is also the basis of Prolog execution!
muad
CC BY-SA 2.5
2010-08-18T16:07:29.687Z
2010-08-18T16:07:29.687Z
Radu GRIGore
<p>Gentry's Fully Homomorphic Encryption Scheme (either over ideal lattices or over the integers) is terribly beautiful. It allows a third party to perform arbitrary computations on encrypted data without access to a private key.</p>

<p>The encryption scheme is due to several keen observations.</p>

<ul>
<li>To get a fully homomorphic encryption scheme, one needs only to have a scheme that is homomorphic over addition and multiplication. This is because addition and multiplication (mod 2) are enough to get AND, OR and NOT gates (and therefore Turing Completeness).</li>
<li>That if such a scheme were to be had, but due to some limitations could only be executed for circuits of some finite depth, then one can <i>homomorphically</i> evaluate the decryption and reencyption procedure to reset the circuit depth limitation without sacrificing key privacy.</li>
<li>That by "squashing" the depth of the circuit version of the decryption function for the scheme, one might enable a scheme originally limited to finite, shallow circuits an arbitrary number of computations.</li>
</ul>

<p>In his thesis, Craig Gentry solved a long standing (and gorgeous) open problem in cryptography. The fact that a fully homomorphic scheme does exist demands that we recognize that there is some inherent structure to computability that we may have otherwise ignored.</p>

<p><a href="http://crypto.stanford.edu/craig/craig-thesis.pdf">http://crypto.stanford.edu/craig/craig-thesis.pdf</a></p>

<p><a href="http://eprint.iacr.org/2009/616.pdf">http://eprint.iacr.org/2009/616.pdf</a></p>

<p><a href="http://portal.acm.org/citation.cfm?id=1666420.1666445">http://portal.acm.org/citation.cfm?id=1666420.1666445</a></p>

CC BY-SA 2.5
2010-08-17T23:16:59.803Z
2010-08-17T23:16:59.803Z
Ross Snider
<p>The <a href="http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm">Cooley-Tukey FFT Algorithm</a>.</p>

CC BY-SA 3.0
2011-08-03T11:20:44.587Z
Yes, especially for its butterfly diagrams (http://en.wikipedia.org/wiki/Butterfly_diagram).
psihodelia
CC BY-SA 2.5
2010-08-25T21:12:25.127Z
2010-08-25T21:12:25.127Z
andand
<p><strong><a href="http://en.wikipedia.org/wiki/Strassen_algorithm">Strassen's algorithm</a></strong> for matrix multiplication.</p>

CC BY-SA 2.5
2011-03-19T10:02:45.410Z
Would probably wait till we know if it is optimal.
Thomas Ahle
CC BY-SA 3.0
2011-10-11T03:58:42.393Z
It isn't optimal, at least, asymptotically... I think that including Strassen's algorithm forces you to include Karatsuba's algorithm first.
Timothy Sun
CC BY-SA 2.5
2010-08-22T05:04:17.130Z
2010-11-24T07:23:04.000Z
2010-11-24T07:23:04.000Z
Noam
<p>The <a href="http://en.wikipedia.org/wiki/Stable_marriage_problem">Gale-Shapley stable marriage algorithm</a>. This algorithm is greedy and very simple, it isn't obvious at first why it would work, but then the proof of correctness is again easy to understand.</p>

CC BY-SA 3.0
2011-11-22T13:31:53.840Z
+1 because there's also a chapter in the published proofs from the book about marriages...
ixtmixilix
CC BY-SA 2.5
2010-08-26T07:34:05.457Z
2010-08-26T07:34:05.457Z
Konrad Swanepoel
<p>The linear time algorithm for constructing suffix arrays is truly beautiful, although it didn't really receive the recognition it deserved <a href="http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf">http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf</a></p>

CC BY-SA 3.0
2011-06-02T19:35:41.420Z
It is worth mentioning that there are now a number of other linear and non linear time suffix array construction algorithms which, although nowhere near as pretty, may be quite a lot faster in practice.  "An efficient, versatile approach to suffix sorting", Journal of Experimental Algorithmics (JEA), Volume 12, June 2008 has some experimental results along these lines.
Simd
CC BY-SA 3.0
2011-09-22T08:58:03.987Z
@Raphael: I'm a bit wary of the fact that on p. 3 of that JEA paper, they give only what they "believe" is a "loose" bound of O(n^2 log n)...  Do you know any papers with *provably linear-time* algorithms that are faster in practice than the Skew Algorithm?
user651
CC BY-SA 2.5
2010-09-08T11:11:58.913Z
I *do* think that it *has* received the recognition it deserves – what makes you think otherwise? For example, it’s implemented in the C++ sequence analysis library SeqAn.
Konrad Rudolph
CC BY-SA 2.5
2010-08-17T20:30:49.580Z
2010-08-17T20:30:49.580Z
zotachidil
<p>The <a href="http://en.wikipedia.org/wiki/Cycle_detection">Tortoise and hare Algorithm</a>. I like it because I'm sure that even if I wasted my entire life trying to find it, there is no way I would come up with such an Idea.</p>

CC BY-SA 2.5
2010-09-23T15:22:19.333Z
Do you know the dumb algorithm that solves the problem with the same asymptotics and follows an algorithmic design pattern? I'm talking about iterative deepening. In the nth iteration you start at the 2^n-th successor of the root and look 2^n successors forward in search of a recurrence. Even though you're retracing some of your steps with every iteration, the geometric growth rate of the search radius means that it doesn't affect the asymptotics.
Per Vognsen
CC BY-SA 2.5
2010-09-20T21:14:01.357Z
2010-09-22T18:26:16.260Z
2010-09-22T18:26:16.260Z
Tobias Neukom
<p><a href="http://en.wikipedia.org/wiki/Merge_sort">Merge Sort</a>. Simple, elegant, efficient.</p>

CC BY-SA 2.5
2010-10-01T09:45:44.240Z
2010-10-01T09:45:44.240Z
Giorgio Camerani
<p>An example as fundamental and "trivial" as Euclid's proof of infinitely many primes:</p>

<p><strong>2-approximation for MAX-CUT</strong> -- Independently for each vertex, assign it to one of the two partitions with equal probability.</p>

CC BY-SA 2.5
2010-08-17T20:23:39.647Z
Yes, a very nice algorithm. Less trivially, at the cost of another factor of 2, this algorithm also works for maximizing _any_ submodular function, not just the graph cut function. This is a result of Feige, Mirrokni, and Vondrak from FOCS 07
Aaron Roth
CC BY-SA 2.5
2010-08-17T20:18:59.267Z
2010-08-18T16:12:40.010Z
2010-08-18T16:12:40.010Z
arnab
<p>Gaussian elimination. It completes the generalization sequence from the Euclidean GCD algorithm to Knuth-Bendix.</p>

CC BY-SA 2.5
2011-02-16T21:36:45.990Z
+1: Euclidean algorithm solves the most celebrated equation ax-by=1 in math. Why it doesn't show up in CS more often is a mystery.
Tegiri Nenashi
CC BY-SA 2.5
2010-08-30T00:03:26.680Z
BTW, what's the generalization sequence, and where does Buchberger's algorithm for Grobner basis fit into it? (It seems analogous to Knuth-Bendix, but I've seen a mention somewhere that it sort of generalizes Gaussian elimination…)
ShreevatsaR
CC BY-SA 2.5
2010-08-30T15:59:28.780Z
the sequence is: Euclidean GCD -> Gaussian Elimination -> Buchberger -> Knuth-Bendix. One can also put in (instead of Gaussian Elimination) univariate polynomial division and modulo (in the generalization order it is 'apart' from Gaussian Elimination, GE is multivariate degree 1, polynomial ring is univariate unlimited degree, Buchberger's is multivariate unlimited degree. The generalization jump is largest from EGCD to GE or polynomial ring because of the addition of variables, and then also large from Buchberger to KB because of the unlimited signature.
Mitch
CC BY-SA 2.5
2010-08-25T16:03:35.483Z
2010-08-25T16:03:35.483Z
Mitch
<p>I've always been partial to <strong><a href="http://en.wikipedia.org/wiki/Christofides_algorithm">Christofides' Algorithm</a></strong> that gives a (3/2)-approximation for metric TSP.  In fact, call me easy to please, but I even liked <a href="http://en.wikipedia.org/wiki/Traveling_salesman_problem#Metric_TSP">the 2-approximation algorithm that came before it</a>.  Christofides' trick of making a minimum weight spanning tree Eulerian by adding a matching of its odd-degree vertices (instead of duplicating all edges) is simple and elegant, and it takes little to convince one that this matching has no more than half the weight of an optimum tour.</p>

CC BY-SA 2.5
2010-08-22T22:11:07.060Z
Indeed, there are also plenty of other simple and elegant approximation algorithms with decent approximation guarantees.
Janne H. Korhonen
CC BY-SA 2.5
2010-08-19T12:25:08.563Z
2010-08-21T21:10:39.193Z
2010-08-21T21:10:39.193Z
James King
<p>Marcus Hutter's <a href="http://www.hutter1.net/ai/pfastprg.htm">The Fastest and Shortest Algorithm for All Well-Defined Problems</a>.</p>

<p>This kind of goes against the spirit of the other offerings in this list, since it is only of theoretical and not practical interest, but then again the title kind of says it all.  Perhaps it should be included as a cautionary tale for those who would look only at the asymptotic behavior of an algorithm.</p>

CC BY-SA 2.5
2010-08-18T05:02:41.227Z
2010-08-18T05:02:41.227Z
Kurt
<p><strong>Knuth's Algorithm X</strong> finds all solutions to the <strong>exact cover problem</strong>. What is so magical about it is the technique he proposed to efficiently implement it: <a href="http://arxiv.org/abs/cs/0011047">Dancing Links</a>.</p>

CC BY-SA 2.5
2010-08-19T07:05:52.503Z
2010-08-19T07:05:52.503Z
didest
<p>Robin Moser algorithm for solving a certain class of SAT instances.  Such instances are solvable by Lovasz Local Lemma. Moser algorithm is indeed a de-randomization of the statement of the lemma.</p>

<p>I think that is some years his algorithm (and the technique for its correctness proof) will be well digested and refined to the point of being a viable candidate for an <strong>Algorithm from the Book</strong>.</p>

<p><a href="http://arxiv.org/abs/0903.0544">This version</a> is an extension of his original paper, written with Gábor Tardos.</p>

CC BY-SA 2.5
2010-08-19T13:27:18.467Z
2010-08-19T13:27:18.467Z
MassimoLauria
<p>I think we must include <strong>Schieber-Vishkin</strong>'s, which answers <strong>lowest common ancestor</strong> queries in constant time, preprocessing the forest in linear time.</p>
<p>I like Knuth's exposition in Volume 4 Fascicle 1, and <a href="https://www.youtube.com/watch?v=Xv-7xkMLaAw" rel="nofollow noreferrer">his musing</a>.
He said it took him two entire days to fully understand it, and I remember his words:</p>
<blockquote>
<p>I think it's quite beautiful, but
amazingly it's got a bad press in the
literature (..) It's based on
mathematics that excites me.</p>
</blockquote>

CC BY-SA 3.0
2013-06-16T14:42:19.580Z
@ShreevatsaR The book has fine print in the footnotes :)
hsmyers
CC BY-SA 2.5
2010-08-31T23:05:07.027Z
Wait, it may be beautiful, but if it took Knuth two entire days to fully understand it, is it really "from the book"?
ShreevatsaR
CC BY-SA 4.0
2010-08-18T07:21:50.300Z
2024-06-23T03:52:22.687Z
2024-06-23T03:52:22.687Z
didest
<p><strong>Expander codes</strong> </p>

<p>Gallager showed in the 1960's that random low density parity codes have good rate and relative distance with high probability.  But it was <a href="http://dx.doi.org/10.1109/SFCS.1994.365734">Sipser and Spielman (1994)</a>, following work of <a href="http://www.ldpc-codes.com/papers/rlcc.pdf">Tanner (1981)</a>, 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.  </p>

<p>Two footnotes:</p>

<ol>
<li><p>Graphs of such expansion were not explicitly constructible at the time of Spielman and Sipser, but they now are due to work of <a href="http://doi.acm.org/10.1145/509907.510003">Capalbo, Reingold, Vadhan and Wigderson (2002)</a>.  Sipser and Spielman themselves constructed linear time decodable codes by using the Tanner product construction.</p></li>
<li><p><a href="http://doi.acm.org/10.1145/225058.225165">Spielman (1995)</a> developed these ideas further to give a code with both linear time encoding and decoding.</p></li>
</ol>

CC BY-SA 2.5
2010-08-22T02:12:59.493Z
Much more beautiful than LT or Raptor!
Ross Snider
CC BY-SA 2.5
2010-08-22T01:41:28.590Z
2010-08-22T01:41:28.590Z
arnab
<p>The algorithm that amazed me the most is Timothy Chan's O(n log h) planar convex hull algorithm: <a href="http://www.cs.uwaterloo.ca/~tmchan/conv23d.ps.gz">http://www.cs.uwaterloo.ca/~tmchan/conv23d.ps.gz</a></p>

<p>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.</p>

CC BY-SA 2.5
2010-09-16T22:45:52.333Z
2010-09-16T22:45:52.333Z
Guilherme D. da Fonseca
<p>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: <a href="http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/lec/01_min_disk.pdf">http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/lec/01_min_disk.pdf</a></p>

CC BY-SA 2.5
2010-09-16T22:36:48.107Z
A version that I consider particularly elegant and easy to explain is due to Khuller and Matias http://www.cs.umd.edu/users/samir/grant/cp95.ps
Guilherme D. da Fonseca
CC BY-SA 2.5
2010-08-26T12:13:57.177Z
2010-08-26T12:13:57.177Z
Sariel Har-Peled
<p>How about <a href="http://en.wikipedia.org/wiki/Grover%27s_algorithm">Grover's algorithm</a>? It's one of the simplest quantum algorithms, and allows you to search an unsorted database in $O(\sqrt N)$. It is provably optimal, and also provably outperforms any classical algorithm. For a bonus it is very easy to understand and intuitive.</p>

CC BY-SA 2.5
2010-08-27T14:57:31.760Z
2010-08-29T18:20:03.447Z
2010-08-29T18:20:03.447Z
Joe Fitzsimons
<p>Algorithms for <strong>linear programming</strong>: Simplex, Ellipsoid, and interior point methods.</p>

<p><a href="http://en.wikipedia.org/wiki/Linear_programming#Algorithms">http://en.wikipedia.org/wiki/Linear_programming#Algorithms</a></p>

CC BY-SA 2.5
2010-11-16T02:00:23.660Z
@Ross Kantorovich won the Nobel prize in Economics for inventing LP and applying it to resource allocations. What other prizes were you thinking of?
Mark Reitblatt
CC BY-SA 2.5
2010-11-16T09:57:41.393Z
@Mark Koopermans was awarded the nobel prize with Kantorovich, but it was still inaccurate of me to say "several."
Ross Snider
CC BY-SA 2.5
2010-08-18T00:14:03.473Z
And indeed, several Nobel prizes were given for advancing our understanding of these problems.
Ross Snider
CC BY-SA 2.5
2010-08-17T21:52:31.363Z
2010-08-18T16:13:11.803Z
2010-08-18T16:13:11.803Z
Kaveh
<p>Moore's O(n) <a href="http://www.cs.utexas.edu/~moore/best-ideas/mjrty/">Majority voting algorithm</a> is like a magic-trick!</p>

CC BY-SA 3.0
2011-10-09T09:00:22.513Z
2011-10-09T09:00:22.513Z
Abhay
<p>This collection of answers would be a great start on an outline for a book with that title!
I have really enjoyed <em>Proofs from the Book</em>, have even purchased all four editions.</p>

<p>I would include the <a href="http://en.wikipedia.org/wiki/Delaunay_triangulation#Flip_algorithms">edge-flipping algorithm</a> for constructing the Delaunay Triangulation in 2D.
Even though it is not optimal.</p>

CC BY-SA 2.5
2010-08-26T05:07:19.023Z
excellent idea !!!!
Suresh Venkat
CC BY-SA 2.5
2010-08-23T19:23:25.643Z
2010-08-23T19:23:25.643Z
Joseph O'Rourke
<p>Avi Wigderson in Part II of <a href="http://hulk03.princeton.edu:8080/WebMedia/lectures/">these lectures </a> gives the following examples of algorithmic gems, with pseudocode:</p>

<p>Shortest path (Dijkstra's algorithm)</p>

<p>Pattern matching (Knuth-Morris-Pratt's algorithm)</p>

<p>Fast Fourier Transform (Cooley-Tukey's algorithm)</p>

<p>Error Correction (Berlekamp-Massey's algorithm)</p>

CC BY-SA 2.5
2010-08-24T18:05:00.943Z
I'm pretty sure Berlekamp-Massey's algo is not error correction. To me it seems more along the lines of reverse engineering an LFSR back to a particular state given the output bits of the mentioned LFSR. I don't see that as error correction more than a well formed parsing algorithm.
Corey Ogburn
CC BY-SA 2.5
2010-08-17T21:44:00.617Z
This would be an even better answer, if you could name a concrete algorithm for these problems which you think should be called an "algorithm from the book". (FFT is a fine answer already)
Moritz
CC BY-SA 2.5
2010-08-17T23:18:07.757Z
Please, one algorithm per answer. (And we already have KMP.)
Jukka Suomela
CC BY-SA 2.5
2010-08-17T21:21:31.377Z
2010-08-17T22:07:06.050Z
2010-08-17T22:07:06.050Z
Manu
<p>We cannot forget <strong>Binary Decision Diagrams</strong>, a family of data structures that have become <em>the</em> 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.)</p>

<p>My reference is again Knuth's Volume 4 Fascicle 1, and you can see his musings <a href="http://stanford-online.stanford.edu/seminars/knuth/080605-knuth-300.asx">here</a> and <a href="http://proedvid.stanford.edu/knuth/081209/081209-knuth-300.wmv">here</a>.</p>

CC BY-SA 2.5
2010-08-19T07:54:38.500Z
2010-08-19T07:54:38.500Z
didest
<p><a href="http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm">Kosaraju's Algorithm</a> 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.</p>

CC BY-SA 2.5
2010-09-13T13:47:58.910Z
2010-09-13T13:47:58.910Z
gphilip
<p><strong>Lenstra-Lenstra-Lovász</strong> 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.</p>

CC BY-SA 2.5
2011-02-25T03:08:23.617Z
thats an awesome choice...i like the way they analyze the algorithm...by picking what, in my opinion, is a very non-trivial thing to amortize on
Akash Kumar
CC BY-SA 2.5
2011-01-16T18:21:53.913Z
2011-01-16T18:21:53.913Z
alpoge
<p>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:<ul>
<li> Randomized equality testing (hugely important in communication protocols)
<li> Hashing with chaining
<li> Count-min sketches
</ul></p>

CC BY-SA 3.0
2012-03-30T22:39:00.597Z
another application: the perfect hashing algorithm of Fredman, Komlos, and Szemeredi, itself quite beautiful
Sasho Nikolov
CC BY-SA 2.5
2010-08-23T11:33:04.287Z
2010-08-23T11:33:04.287Z
Rasmus Pagh
<p>I propose <a href="http://en.wikipedia.org/wiki/Reed_Solomon">Reed-Solomon coding</a>. 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.</p>

<p>I find this extremely elegant. I just wish I had more cause to use it.</p>

CC BY-SA 3.0
2013-06-16T23:29:35.793Z
this is a great example, and the idea has found uses ranging from list decoding to secret sharing.
Sasho Nikolov
CC BY-SA 3.0
2013-06-16T09:59:35.460Z
2013-06-16T09:59:35.460Z
dan_waterworth
<p>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.</p>

<p><a href="http://en.wikipedia.org/wiki/Cycle_detection">http://en.wikipedia.org/wiki/Cycle_detection</a></p>

CC BY-SA 2.5
2011-01-16T11:48:26.983Z
2011-01-16T11:48:26.983Z
Ritwik Bose
<p>I think that there should be at least one persistant data structure. In particular, the <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.1317">"persistant array"</a> let us obtains a lot of other persistant data-structures where we wouldn't expect them. </p>

CC BY-SA 2.5
2010-08-24T04:13:36.057Z
2010-08-24T04:13:36.057Z
Arthur MILCHIOR
<p>I guess the algorithm to "<a href="http://en.wikipedia.org/wiki/Hash_consing">hash-cons</a>" 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).</p>

CC BY-SA 2.5
2010-08-26T09:38:01.080Z
In my book, that's someone *everyone* should now, very few heard the term, and many keep reinventing.
Radu GRIGore
CC BY-SA 2.5
2010-08-24T04:18:30.480Z
2010-08-24T04:18:30.480Z
Arthur MILCHIOR
<p>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.</p>

<p>In particular, it tells you <em>why</em> $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. </p>

<p><a href="http://en.wikipedia.org/wiki/Risch_algorithm">http://en.wikipedia.org/wiki/Risch_algorithm</a></p>

CC BY-SA 2.5
2010-11-16T00:20:29.027Z
That seems to be an incredibly complicated algorithm. According to Wikipedia, no software currently implements the full algorithm due to its complexity. In fact, it's not even a terminating algorithm. Other than the problem it solves, in what sense is this an "elegant" algorithm?
Mark Reitblatt
CC BY-SA 2.5
2010-09-22T00:34:06.900Z
2010-09-22T00:44:19.050Z
2010-09-22T00:44:19.050Z
nimish
<p>The <strong>O(n)</strong> algorithm for finding the <strong>maximum-sum contiguous subarray</strong> of a list of integers L.</p>
<ul>
<li>L can contain both positive and negative integers</li>
<li>L is not necessarily sorted</li>
<li>L can contain duplicate entries</li>
<li>subarray length can be in the range [1, n] where n is the length of L</li>
</ul>
<p>For example the list {-1, 500, -100, 101} has a maximum-sum subsequence of {500, -100, 101}.</p>
<p>I learned about this <a href="http://www.cs.bell-labs.com/cm/cs/pearls/maxsum.c" rel="nofollow noreferrer">algorithm</a> from <a href="http://www.cs.bell-labs.com/cm/cs/pearls/" rel="nofollow noreferrer">Jon Bentley's Programming Pearls</a>.  Note the code contains a few versions of this algorithm... the last version is O(n).</p>

CC BY-SA 3.0
2015-11-14T17:27:37.100Z
This algorithm is also known as “[Kadane’s Algorithm](https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm).” I nearly missed this answer because searching for “Kadane” didn’t yield any result on this page, and was just about to write one suggesting this algorithm.
k.stm
CC BY-SA 3.0
2017-09-14T07:02:55.363Z
can you please update the links, both are not working.
LoveToCode
CC BY-SA 4.0
2010-09-20T11:16:18.173Z
2022-11-30T21:57:55.160Z
2022-11-30T21:57:55.160Z
MrDatabase
<p>I looked through all the answers and it seems that many of them are not describing <em>Algorithms from the Book</em>. 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 <strong>quicksort would <em>not</em> be found in <em>The Book</em></strong>. It's a fairly simple algorithm, which makes it a good candidate for <em>The Book</em>, but there is one major issue:</p>

<p>The behaviour of quicksort is inconsistent. It performs well in practice, but bad pivot choices could lead to <strong>quadratic running-time</strong>. 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.</p>

<p>Though, there is a sorting algorithm that I would expect to find in <em>The Book</em>, and that is <a href="http://en.wikipedia.org/wiki/Merge_sort"><strong>mergesort</strong></a>:</p>

<pre><code>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.
</code></pre>

<p>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.</p>

CC BY-SA 3.0
2012-04-01T16:03:31.987Z
The most elegant way to choose the quicksort pivot is to choose it *randomly*.  Then (and only then) quicksort belongs in The Book.
Jeffε
CC BY-SA 3.0
2013-06-17T03:28:53.200Z
Choosing a pivot randomly is a _deus ex machina_ non-answer. We're talking about _The Book_ here, not _The Book_ plus a qualified source of randomness. Mergesort in, quicksort out.
Daniel Lyons
CC BY-SA 2.5
2010-09-22T21:03:14.020Z
I disagree that "There is no way to make a good pivot choice." There may be no instant way to make a good pivot choice, but median of medians will find a good pivot.
jbapple
CC BY-SA 2.5
2010-10-01T20:20:32.863Z
I think the point really is that in terms of simplicity, elegance, and computational economy, Mergesort belongs in the Book and Quicksort probably does not.  I don't completely agree, but +1 for bringing up the idea that the Book isn't just a collection of favorite algorithms.
whuber
CC BY-SA 2.5
2010-09-22T06:46:41.547Z
2010-09-22T06:46:41.547Z
ara
<p>An algorithm that I find truly simple and elegant is the <a href="http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm" rel="noreferrer">Rabin-Karp</a> algorithm of using rolling-hashes for linear time string search. A lot simpler to wrap your head around than KMP.</p>

CC BY-SA 2.5
2010-09-13T21:13:33.657Z
2010-09-13T21:13:33.657Z
2020-06-17T09:38:08.363Z
MAK
<p>Everyone says Knuth-Morris-Pratt. I don't think the <a href="http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm">Boyer-Moore</a> string-matching algorithm gets enough credit.</p>

<p>There's <a href="http://ridiculousfish.com/blog/archives/2006/05/30/old-age-and-treachery/">a wonderful exploration Boyer-Moore's implementation in grep on ridiculousfish</a>. For the more academically-inclined, Mike Haertel, grep's longtime maintainer, <a href="http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html">explains why grep is so fast</a>.</p>

CC BY-SA 2.5
2010-09-21T00:50:03.103Z
(2) http://ridiculousfish.com/blog/archives/2006/05/30/old-age-and-treachery/
(3) http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html
apc
CC BY-SA 2.5
2010-09-22T18:39:19.463Z
I've incorporated the links into your answer. If you're OK with my edit, I think that you (we) can remove the comment(s).
Yaser Sulaiman
CC BY-SA 2.5
2010-09-22T18:47:40.787Z
On a side note, there's actually [an older Boyer-Moore answer](http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book/1469#1469).
Yaser Sulaiman
CC BY-SA 2.5
2010-09-22T19:04:26.477Z
I'm ok with your edits. And I looked but didn't see it anywhere else, so I'll make a better effort in the future to avoid redundancies. Sorry about that.
apc
CC BY-SA 2.5
2010-11-05T10:04:28.740Z
Horspool (Boyer-Moore-Horspool) is even simpler to state (it’s a simplification of Boyer-Moore), and performs better in practice.
Konrad Rudolph
CC BY-SA 2.5
2010-09-21T00:49:35.193Z
2010-09-22T18:34:22.470Z
2010-09-22T18:34:22.470Z
apc
<p>I wonder nobody mentioned Schöning's random-walk algorithm for 3-SAT solving yet. It it very simple:</p>

<ul>
<li>Start with a random assignment </li>
<li>As long as there exists an unsatisfied clause: Flip a randomly-selected variable in this clause</li>
</ul>

<p>Nevertheless, it is to date one of the fastest algorithms in its class.</p>

CC BY-SA 2.5
2010-10-30T10:48:09.500Z
2010-10-30T10:48:09.500Z
Dimitri Scheftelowitsch
<p>The <a href="http://en.wikipedia.org/wiki/Viterbi_algorithm">Viterbi algorithm</a>, <a href="http://en.wikipedia.org/wiki/Ldpc">low-density parity-check codes</a>, and <a href="http://en.wikipedia.org/wiki/Turbo_code">turbo codes</a>- communication at the noise floor!</p>

CC BY-SA 2.5
2010-12-06T22:58:01.853Z
2010-12-06T22:58:01.853Z
johne
<p>I'm not sure if the question requests particularly beautiful algorithms, but as far as useful and simple algorithms go..</p>

<p>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.)</p>

<p>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.</p>

<p>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.)</p>

<p>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.</p>

<p>(*) 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).</p>

CC BY-SA 3.0
2012-01-25T23:08:21.070Z
note that "Newtons method" for finding solutions via the derivative is a 1-d analogue of multivariate steepest descent.
vzn
CC BY-SA 2.5
2010-08-23T19:27:29.597Z
2010-08-23T19:33:28.243Z
2010-08-23T19:33:28.243Z
matus
<p>The (random projection algorithm implicit in the) Johnson-Lindenstrauss lemma!</p>

CC BY-SA 2.5
2010-09-15T05:04:20.407Z
2010-09-15T05:04:20.407Z
Kunal
<p>I would like to put some non-deterministic algorithm, which may also be in the Book.</p>

<p>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).</p>

<p>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 !</p>

CC BY-SA 2.5
2010-08-24T06:34:35.263Z
This result is very nice, but I don't think it classifies as beautiful *as an algorithm*.
didest
CC BY-SA 2.5
2010-08-23T06:26:39.160Z
2010-08-23T06:26:39.160Z
Arthur MILCHIOR
<p>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. </p>

CC BY-SA 3.0
2012-04-01T00:19:55.977Z
2012-04-01T00:19:55.977Z
William Hird
<p>The 2-approximation algorithm for Knapsack:</p>

<p>First, consider the trivial algorithm: select the highest value item that fits. This can obviously be arbitrarily far from optimal.</p>

<p>Now consider the greedy algorithm: greedily select the highest value density items. This can also be arbitrarily far from optimal.</p>

<p>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.</p>

CC BY-SA 3.0
2013-06-17T00:49:07.613Z
Can you explain what "Run Trivial" means?
Dennis
CC BY-SA 2.5
2010-11-15T04:16:06.873Z
2010-11-16T04:51:18.673Z
2010-11-16T04:51:18.673Z
Mark Reitblatt
<p>I think that <a href="http://en.wikipedia.org/wiki/LR_parser">LR parsers</a> are beautiful. A language is deterministic context-free if and only if there exists a LR(1) grammar for it.</p>

CC BY-SA 2.5
2010-08-22T06:13:02.753Z
2010-08-22T06:13:02.753Z
didest
<p>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$. </p>

<p>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:</p>

<pre><code>G: a graph with n vertices
k: the maximum size of the cover

def Vertex_Cover(G,k): 
    if k&lt;=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|) 
</code></pre>

<p>Of course such procedure can be implemented in a decision tree fashion.</p>

CC BY-SA 2.5
2010-09-04T20:13:57.523Z
Oh yes, I absolutely love this algorithm! And there is an even more preliminary version of it (same running time, though) which branches on edges. Pick an edge $(u,v)$. Since it must be covered, at least one of $u$ or $v$ must belong to any vertex cover; and we branch on both possibilities. Thank you for suggesting this, I was just about to! :)
Neeldhara
CC BY-SA 2.5
2010-08-31T13:30:06.053Z
2010-08-31T13:38:33.927Z
2010-08-31T13:38:33.927Z
MassimoLauria
<p><a href="http://en.wikipedia.org/wiki/Knuth%E2%80%93Bendix_completion_algorithm">Knuth-Bendix algorithm</a> and the analogous <a href="http://en.wikipedia.org/wiki/Buchberger%27s_algorithm">Buchberger's algorithm</a>.</p>

CC BY-SA 2.5
2010-08-22T06:16:59.093Z
2010-08-22T06:16:59.093Z
didest
<p>I think that the process of finding a diagonal proof is an algorithm.</p>

<p>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. </p>

<p>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.</p>

<p><img src="https://i.sstatic.net/oJHE1.png" alt="alt text"></p>

<p><a href="http://en.wikipedia.org/wiki/Cantor&#39;s_diagonal_argument" rel="noreferrer">image sourced from this wikipedia article</a></p>

CC BY-SA 2.5
2010-10-29T11:02:24.687Z
2010-10-29T11:02:24.687Z
Ilan
<p>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!</p>

<p>I simply love that the following is actually an algorithm that will work:</p>

<pre><code>def solve(problem):
    foreach answer in generate_all_possible_answers(problem): 
        if is_good_enough(answer, problem): 
            return answer
    return "No answer found"
</code></pre>

CC BY-SA 2.5
2010-08-30T02:35:04.323Z
2010-08-30T02:35:04.323Z
Peter Boothe
<p><a href="http://userweb.cs.utexas.edu/users/moore/best-ideas/string-searching/" rel="noreferrer">Boyer-Moore</a> string matching.</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-19T22:38:21.237Z
2010-09-22T18:59:03.053Z
2010-09-22T18:59:03.053Z
Martin
<p><a href="http://en.wikipedia.org/wiki/Savitch%27s_theorem" rel="noreferrer">Savitch's Algorithm</a>: a simple recursive algorithm for the <a href="http://en.wikipedia.org/wiki/St-connectivity" rel="noreferrer">Reachability</a> problem, with a conceptually deep consequence: <a href="http://en.wikipedia.org/wiki/PSPACE" rel="noreferrer">PSPACE</a>=<a href="http://en.wikipedia.org/wiki/NPSPACE" rel="noreferrer">NPSPACE</a>. </p>

CC BY-SA 3.0
2013-06-16T19:36:26.123Z
2013-06-16T19:36:26.123Z
Vincenzo
<p>The Shift-And algorithm by Baeza-Yates and Gonnet (<a href="http://en.wikipedia.org/wiki/Bitap_algorithm" rel="nofollow">Bitap</a> @Wikipedia) for finding all occurrences of a pattern in a text. In my opinion the simplest example of a useful seminumerical algorithm.</p>

CC BY-SA 2.5
2010-08-31T13:35:35.947Z
2010-08-31T13:35:35.947Z
Gianluca Della Vedova
<p><a href="http://mathworld.wolfram.com/ZeilbergersAlgorithm.html" rel="nofollow noreferrer">Zeilberger's algorithm</a>, which extends Gosper's algorithm for finding closed-forms of binomial sums.</p>

<p>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.</p>

CC BY-SA 3.0
2016-11-12T16:11:49.880Z
2016-11-12T16:11:49.880Z
Andrew
<p>If Dijkstra is specified, I think that <a href="http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm" rel="nofollow">Bellman-Ford</a> is even a better candidate.</p>

CC BY-SA 3.0
2014-09-04T05:54:35.923Z
I think Dijkstra's algorithm is actually an ugly one compared to Bellman-Ford!
Helium
CC BY-SA 2.5
2010-10-20T12:56:02.977Z
2010-10-20T12:56:02.977Z
rursw1
<p>Although perhaps as much a heuristic as an algorithm, since I heard about it a year or two ago, I think that the <a href="http://en.wikipedia.org/wiki/Fast_inverse_square_root" rel="nofollow">fast inverse square root</a> is interesting.  And even more intriguing that we don't know it's author or how she/he settled upon the magic number. </p>

CC BY-SA 2.5
2011-02-12T03:42:02.877Z
2011-02-12T03:42:02.877Z
John Berryman
<p>I just learned about a book entitled <a href="http://www.springerlink.com/content/978-3-642-15327-3/contents/" rel="nofollow">Algorithms unplugged</a>, which seems relevant to this topic.</p>

CC BY-SA 3.0
2012-04-02T04:00:34.603Z
A very good collection indeed!
Dai Le
CC BY-SA 3.0
2011-04-11T13:30:56.360Z
2011-04-11T13:30:56.360Z
Anthony Labarre
<p>theres a really wonderful way to describe <strong>in place quicksort</strong></p>

<p>in particular:</p>

<p>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$. </p>

<p>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.</p>

<p>edit: note that there is actually <strong>no special treatment</strong> needed for the pivot value, we just apply the swapping operation uniformly.</p>

<p>then recursively sort the intervals you get from the final placement of the pivot value.</p>

<p>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! </p>

<p>:)</p>

<p>note that this isn't a stable sort algorithm</p>

CC BY-SA 2.5
2010-08-28T04:59:52.213Z
+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.)
user651
CC BY-SA 2.5
2010-09-05T22:03:14.337Z
good clarification
Carter Tazio Schonwald
CC BY-SA 2.5
2010-08-24T05:24:25.670Z
2010-08-24T16:31:00.137Z
2010-08-24T16:31:00.137Z
Carter Tazio Schonwald
<p>The divide and conquer algorithm by Michael Shamos to solve the planar <a href="http://en.wikipedia.org/wiki/Closest_pair_of_points" rel="nofollow">Closest pair of points problem</a> 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.</p>

CC BY-SA 3.0
2014-02-28T09:46:29.590Z
2014-02-28T09:46:29.590Z
Arindam Pal
<p>The Kalman filter, absolutely brilliant for handling data with noise: <a href="http://en.wikipedia.org/wiki/Kalman_filter" rel="nofollow">http://en.wikipedia.org/wiki/Kalman_filter</a></p>

CC BY-SA 2.5
2010-09-13T18:27:08.340Z
2010-09-13T18:27:08.340Z
Michael
<p>The <a href="http://swtch.com/~rsc/regexp/regexp1.html" rel="nofollow">Thompson NFA construction</a> and, in particular, <a href="http://swtch.com/~rsc/regexp/regexp1.html" rel="nofollow">evaluation method</a>.  Probably the slickest bit of code I've ever seen.</p>

CC BY-SA 2.5
2010-12-06T22:50:46.217Z
2010-12-06T22:50:46.217Z
johne
<p>It's such a simple thing, but in it's simplicity is it's elegance: <a href="http://en.wikipedia.org/wiki/LFSR" rel="nofollow">Linear Feedback Shift Registers</a>. 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.</p>

CC BY-SA 2.5
2010-08-24T18:00:41.760Z
2010-08-24T18:00:41.760Z
Corey Ogburn
<p>In THE BOOK, there should include "The Power of Random Two Choices" paradiam.</p>

<p><a href="http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf" rel="nofollow">http://www.eecs.harvard.edu/~michaelm/postscripts/handbook2001.pdf</a></p>

<p>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"</p>

CC BY-SA 3.0
2013-11-23T11:59:06.380Z
2013-11-23T11:59:06.380Z
xbob.ym
<p>I think that <a href="http://www.cse.iitk.ac.in/users/manindra/CS681/2005/Lecture17.pdf" rel="nofollow">Hensel Lifting</a> is pretty nifty too, and it has many applications in algorithmic number theory and algebra.</p>

CC BY-SA 3.0
2012-03-30T03:30:01.017Z
2012-03-30T03:30:01.017Z
Shitikanth
<p>If union-find is in the book,
why can't <a href="http://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow">Bloom filters</a> be there?
If you are not familiar with Bloom filters, <a href="https://www.youtube.com/watch?v=-SuTGoFYjZs" rel="nofollow">this video</a> is a quick but nice introduction.</p>

CC BY-SA 3.0
2014-09-04T04:50:56.413Z
2014-09-04T04:50:56.413Z
Helium
<p>Hook and shortcut from:</p>

<p>AN EFFICIENT PARALLEL BICONNECTIVITY ALGORITHM</p>

<p>Tarjan and Vishkin</p>

<p><a href="http://www.umiacs.umd.edu/users/vishkin/TEACHING/ENEE759KS12/TV85.pdf" rel="nofollow">http://www.umiacs.umd.edu/users/vishkin/TEACHING/ENEE759KS12/TV85.pdf</a></p>

<p>This Ruby implementation returns the partitions of a transformation where elements x,y interact with each other.</p>

<pre><code>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]] &lt; parent[parent[index]])
        parent[parent[index]] = parent[trans[index]]
      end
      if (parent[index] &lt; parent[parent[trans[index]]])
        parent[parent[trans[index]]] = parent[index]
      end
    end
  end
  return parent
end
</code></pre>

CC BY-SA 3.0
2013-06-21T20:28:37.217Z
2013-06-21T20:28:37.217Z
Chad Brewbaker
<p><strong>Polynomial time Max-Cut algorithm in planar graphs</strong> 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.  </p>

CC BY-SA 3.0
2015-01-25T23:35:24.147Z
2015-01-25T23:35:24.147Z
Hung Le
<p>I am sure "<a href="http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication" rel="nofollow">Ancient Egyptian Multiplication</a>" 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.</p>

CC BY-SA 3.0
2012-04-18T03:59:05.770Z
2012-04-18T03:59:05.770Z
Sai Venkat
<p>I like the <a href="http://en.wikipedia.org/wiki/CORDIC" rel="nofollow">CORDIC</a> algorithm for solving trigonometric and hyperbolic functions, especially when implemented using fixed-point integer representations.</p>

CC BY-SA 2.5
2011-01-18T23:08:57.423Z
2011-01-18T23:08:57.423Z
oosterwal
<p>The algorithm that uses <strong><a href="http://en.wikipedia.org/wiki/Pascal%27s_triangle" rel="nofollow">Pascal's Triangle</a></strong> (wikipedia) to find <strong>"a choose b"</strong>.  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". </p>

CC BY-SA 2.5
2010-09-20T10:58:07.540Z
2010-09-20T10:58:07.540Z
MrDatabase
<p>As we talk of a book of "God" and a beautiful algorithm, something that comes to my mind is <a href="http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life" rel="nofollow">Conway's Game of Life</a>. It sets a grid as a cellular automaton and sets the following simple rules:</p>

<ol>
<li><p>Any live cell with fewer than two live neighbours dies, as if caused
by under-population.</p></li>
<li><p>Any live cell with two or three live neighbours lives on to the next
generation.</p></li>
<li><p>Any live cell with more than three live neighbours dies, as if by
overcrowding.</p></li>
<li><p>Any dead cell with exactly three live neighbours becomes a live
cell, as if by reproduction.</p></li>
</ol>

<p>Amazing, how simple rules like these and a random seeded initialization can achieve something as beautiful as life and evolution. </p>

CC BY-SA 3.0
2014-02-28T02:37:32.013Z
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. http://www.hpl.hp.com/techreports/2006/HPL-2006-2.pdf
Super0
CC BY-SA 3.0
2014-02-27T19:50:28.087Z
2014-02-27T19:59:04.967Z
2014-02-27T19:59:04.967Z
saikat
<p>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:</p>

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

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-02-28T16:46:12.330Z
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.
Sasho Nikolov
CC BY-SA 3.0
2014-02-28T18:33:00.687Z
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.
Super0
CC BY-SA 3.0
2014-02-28T19:47:38.880Z
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..
Sasho Nikolov
CC BY-SA 3.0
2014-02-26T15:02:31.667Z
2014-02-28T02:53:07.380Z
2014-02-28T02:53:07.380Z
Super0
<p>From the world of purely functional data structures and algorithms, Gérard Huet's <a href="http://gallium.inria.fr/~huet/PUBLIC/zip.pdf" rel="nofollow noreferrer">zipper</a> comes to my mind.</p>

<p>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. </p>

<p>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.</p>

<p>If God is not a functional programmer and would only include one PFDS in the Book, it would have to be the zipper.</p>

CC BY-SA 4.0
2019-01-05T10:30:48.807Z
2019-01-05T10:30:48.807Z
xrq
<p>Paul Erdős talked about the &quot;Book&quot; 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): <a href="http://en.wikipedia.org/wiki/Proofs_from_THE_BOOK" rel="noreferrer">Proofs from the Book</a>.</p>
<p>If God had a similar book for algorithms, what algorithm(s) do you think would be a candidate(s)?</p>
<p>If possible, please also supply a clickable reference and the key insight(s) which make it work.</p>
<p>Only one algorithm per answer, please.</p>

CC BY-SA 2.5
2010-12-15T03:17:48.103Z
During a lecture in 1985, Erdős said, "You don't have to believe in God, but you should believe in The Book."
Robert Massaioli
CC BY-SA 2.5
2011-02-11T02:18:30.303Z
This link is relevant: http://x86.cs.duke.edu/courses/fall06/cps258/references/topten.pdf
Huck Bennett
CC BY-SA 3.0
2012-09-19T16:00:48.013Z
see also [which are the significant algorithms for humankind in past decades](http://programmers.stackexchange.com/questions/20128/which-are-the-significant-algorithms-for-humankind-in-past-decades)
vzn
CC BY-SA 3.0
2012-09-19T16:09:22.833Z
see also [Nine algorithms that changed the future](http://www.amazon.com/Nine-Algorithms-That-Changed-Future/dp/0691147140/) by MacCormick
vzn
CC BY-SA 2.5
2010-08-19T07:33:26.430Z
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".
Radu GRIGore
CC BY-SA 2.5
2010-09-05T04:00:45.143Z
@Radu: As a possible explanation, some might consider algorithms to be book-worthy if they have a surprisingly simple implementation, regardless of whether they are obvious/intuitive.
user651
CC BY-SA 2.5
2010-09-30T07:07:05.550Z
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.
Geek
CC BY-SA 2.5
2010-08-17T18:25:51.220Z
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)?
Ross Snider
CC BY-SA 2.5
2010-08-17T18:34:40.717Z
@Ross: I would say include it.
Aryabhata
CC BY-SA 2.5
2010-08-17T23:15:17.840Z
a great source and maybe a candidate for such a book is "Encyclopedia of Algorithms"
http://www.springer.com/computer/theoretical+computer+science/book/978-0-387-30770-1
Marcos Villagra
<ds.algorithms><soft-question><ds.data-structures><big-list>
Algorithms from the Book
Aryabhata
# Algorithms from the Book

(Asked by: username_0 on 2010-08-17)

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](http://en.wikipedia.org/wiki/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.

**Tags:** ds.algorithms, soft-question, ds.data-structures, big-list
> **Comments:**
> **username_7**: 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)?  
> **username_0**: @Ross: I would say include it.  
> **username_8**: a great source and maybe a candidate for such a book is "Encyclopedia of Algorithms" http://www.springer.com/computer/theoretical+computer+science/book/978-0-387-30770-1  
> **username_4**: 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".  
> **username_5**: @Radu: As a possible explanation, some might consider algorithms to be book-worthy if they have a surprisingly simple implementation, regardless of whether they are obvious/intuitive.  
> **username_6**: 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.  
> **username_1**: During a lecture in 1985, Erdős said, "You don't have to believe in God, but you should believe in The Book."  
> **username_2**: This link is relevant: http://x86.cs.duke.edu/courses/fall06/cps258/references/topten.pdf  
> **username_3**: see also [which are the significant algorithms for humankind in past decades](http://programmers.stackexchange.com/questions/20128/which-are-the-significant-algorithms-for-humankind-in-past-decades)  
> **username_3**: see also [Nine algorithms that changed the future](http://www.amazon.com/Nine-Algorithms-That-Changed-Future/dp/0691147140/) by MacCormick  

---

## 81 answers

### Answer by username_7 on 2010-08-17. Score: 125

**Union-find** is a beautiful problem whose best algorithm/datastructure (**Disjoint Set Forest**) is based on a spaghetti stack. While very simple and intuitive enough to explain to an intelligent child, it took several years to get a tight bound on its runtime. Ultimately, its behavior was discovered to be related to the inverse Ackermann Function, a function whose discovery marked a shift in perspective about computation (and was in fact included in Hilbert's *On the Infinite*).

Wikipedia provides a good introduction to [Disjoint Set Forests](http://en.wikipedia.org/wiki/Disjoint-set_data_structure).


---

### Answer by username_9 on 2010-08-17. Score: 116

**[Knuth-Morris-Pratt](http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm)** string matching. The slickest eight lines of code you'll ever see.

> **Comments:**
> **username_13**: It's kinda mind boggling to realize that that was something that wasn't obvious at some time and is only obvious now because they came up with it and we learnt it...  I think we should apply Carr's theory of history to Mathematics and Computer Science.  
> **username_14**: By the description, I'd say this is related to the Boyer-Moore fast substring search.  
> **username_10**: @Mechko The fact that this algorithm was discovered simultaneously and independently by separate people is an indication that it is obvious to an extent. Whether something is "obvious" is a function of project constraints and broader programming environment. If you need (1) fast text searching and (2) you're aware of the importance of truly O(n) algorithms, and (3) you've encountered text with partial matches before, and (4) you have the time to do things "right", then this algorithm is probably obvious.  
> **username_12**: In [an interview](http://www.informit.com/articles/article.aspx?p=2213858) Knuth said that the idea for the algorithm came from studying Stephen Cook's [Two-way finite automaton](http://en.m.wikipedia.org/wiki/Two-way_deterministic_finite_automaton) for palindromes.  
> **username_11**: @Kaveh Please read Section 7 (Historical Remarks) from the original KMP paper. It has great remarks. About Morris writing a text editor which "was too complicated for other implementors of the system to understand".  About Knuth "the first time in Knuth’s experience that automata theory had taught him how to solve a real programming problem better than he could solve it before". And " Knuth was chagrined to learn that Morris had already discovered the algorithm, without knowing Cook’s theorem;". FUN.  

---

### Answer by username_15 on 2010-08-17. Score: 100

[The algorithm of Blum, Floyd, Pratt, Rivest, and Tarjan](http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm) to **find the *k*th element of an unsorted list** in linear time is a beautiful algorithm, and only works because the numbers are *just right* to fit in the Master Theorem. It goes as follows:

1. Sort each sequence of five elements.
2. Pick out the median in each.
3. Recur to find the median of this list.
4. Pivot on the median of medians (as in Quicksort)
5. Select the proper side of the list and position in that list, and recur.

> **Comments:**
> **username_16**: This is one of my favorite algorithms. I like an intuition for it that I learnt from Chazelle's discrepancy book: the set of medians of groups of $1/\epsilon$ elements is like an $\epsilon$-net for intervals in the ordered list of the input numbers. So the algorithm follows a general paradigm: compute an $\epsilon$-net fast, solve the problem on the net, recurse on some part of the input to refine the solution, until you have the exact solution. it's very useful technique  
> **username_16**: BTW once you parametrize the size of the groups, the constants are not so magical. they are of course optimized to give the right thing in the Master theorem  
> **username_17**: Ruby implementation, https://gist.github.com/chadbrewbaker/7202412 Is there a version of the algorithm that uses (constant,log) space, or do you have to use linear scratch space to hold the medians?  
> **username_18**: The claim that "this only works because the numbers are just right to fit in the master theorem" is not really true. If you replace the number $5$ with a larger number $n$, it is easy to see that the two numbers that have to sum to less than $1$ converge to $3/4$ and $0$, so all sufficiently large $n$ work. $5$ is just the first number that works, it's not the only one.  

---

### Answer by username_19 on 2010-09-20. Score: 96

[Binary Search](http://en.wikipedia.org/wiki/Binary_search_algorithm) is the most simple, beautiful, and useful algorithm I have ever run into.

> **Comments:**
> **username_1**: I would replace elegant with intuitive. There is nothing that elegant about it; its simplicity is its real beauty.  
> **username_19**: @Robert Massaili: I replaced elegant with beautiful.  You were right about that.  
> **username_20**: And insanely hard to write correctly– see "[Are you one of the 10% of programmers who can write a binary search?](http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/)"  
> **username_21**: In my first graduate algorithms course we had 15 minute quizzes where we had to solve 2-3 problems by hand. The first such quiz included a binary search tree and two questions about heaps. I was embarrassed and dismayed to learn I had gotten the binary search problem wrong, before being told that in a class of about 30 people there were two correct answers. But even knowing that, the fact that it took 15 years for the professional community to get right is staggering.  
> **username_22**: @jade the link is broken. Here is an [archive](https://web.archive.org/web/20230127150411/http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/)  
> **username_23**: OK, prepare for heresy. Classic binary search, that you linked to, is one of the most awful algorithms that our field has the misfortune of cherishing. The biggest problem is that it's almost beautiful, but most people aren't aware of the wart. Don't have to believe me, a nobody: read From Mathematics to Generic Programming by Alex Stepanov. The principle that it is based on, the bisection method, is beautiful. I can expand on this and explain in another comment if people are interested.  
> **username_23**: Essentially, there are two warts: i) stopping immediately when the value is found, in a sequence with duplicates, you don't know which one you found or how many there are; ii) returning null when it's not found throws away the work done in finding that position, which is still useful in some applications such as finding where to insert that value or searching on a prefix of a value (e.g. search for "str" to find the first word starting with it). So I'm sorry, but Binary Search, the classic definition in Knuth, is not beautiful. The beautiful variation is called equal_range.  

---

### Answer by username_5 on 2010-08-28. Score: 90

I'm surprised not to see the Floyd-Warshall algorithm for all-pairs shortest paths here:
d[]: 2D array. d[i,j] is the cost of edge ij, or inf if there is no such edge.

for k from 1 to n:
  for i from 1 to n:
    for j from 1 to n:
      d[i,j] = min(d[i,j], d[i,k] + d[k,j])

One of the shortest, clearest non-trivial algorithms going, and $O(n^3)$ performance is very snappy when you consider that there could be $O(n^2)$ edges.  That would be my poster child for dynamic programming!

> **Comments:**
> **username_24**: This algorithm can be also generalised in a really neat way. See e.g. http://r6.ca/blog/20110808T035622Z.html and http://www.cl.cam.ac.uk/~sd601/papers/semirings.pdf  
> **username_25**: And a striking fact is that we still don’t have (polynomially) faster algorithm for APSP than Floyd’s!  

---

### Answer by username_26 on 2010-11-12. Score: 86

[**Euclidean algorithm**](http://en.wikipedia.org/wiki/Euclidean_algorithm) to compute [the greatest common divisor (GCD)](http://en.wikipedia.org/wiki/Greatest_common_divisor)

> **Comments:**
> **username_27**: The greatest one of all :)  
> **username_28**: and probably the oldest _and_ alive of them all!  

---

### Answer by username_29 on 2010-08-17. Score: 76

Might seem somewhat trivial (especially in comparison with the other answers), but I think that **[Quicksort](http://en.wikipedia.org/wiki/Quicksort)** is really elegant. I remember that when I first saw it I thought it was really complicated, but now it seems all too simple.

> **Comments:**
> **username_33**: Quicksort also raises interesting questions about what exactly the essence of an algorithm is. E.g. the standard elegant Haskell implementation *looks* exactly like the standard pseudo-code definition, but it has different asymptotic complexity. So, is Quicksort just about divide-and-conquer or is the clever in-situ pointer-fiddling an essential part of Quicksort? Can Quicksort even be implemented in a purely functional setting or does it require mutability?  
> **username_33**: The idea of the "essence" or the "moral" of an algorithm comes of course from the beautiful paper *The Genuine Sieve of Eratosthenes* by Melissa E. O'Neill (http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf) and the quicksort discussion comes from the LtU discussion of that paper (http://lambda-the-ultimate.org/node/3127/), specifically starting at this comment: http://lambda-the-ultimate.org/node/3127/#comment-45549  
> **username_32**: @Jörg: Implementing quicksort on linked lists is completely sensible, and has the **same asymptotic running time** as its in-place implementation on arrays (heck, even the naive out-of-place implementation on arrays has the same running time) – both on average and in the worst case. As for space usage, this is indeed different but it must be said that even the “in-place” version requires non-constant extra space (call stack!), a fact readily overlooked.  
> **username_34**: Also it's worth to mention Vladimir Yaroslavskiy's Dual-Pivot Quicksort. That should be at least 20% faster original quicksort http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628  
> **username_30**: Quicksort in theory is simple (can be outlined in 4 steps) and could be highly optimized, but in practice it's very difficult to code correctly. Which is why it doesn't get my vote.  
> **username_31**: @Konrad: Running time cannot have a lower bound than storage used, because you need to touch all the storage you use. Even if compare runtime initially dwarfs storage access, at large numbers, n-squared storage use means you have n-squared runtime. Quicksort, to be average n log n, requires in-place mutatability in the actual runtime.  
> **username_32**: @Jon Agreed with the first part of the comment but (functional) quicksort does *not* have quadratic storage – at least I don’t see why.  

---

### Answer by username_35 on 2010-09-19. Score: 63

[Huffman coding](http://en.wikipedia.org/wiki/Huffman_coding) for data compression.


---

### Answer by username_36 on 2010-09-23. Score: 56

Polynomial identity testing with the [Schwartz-Zippel lemma](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma):

If someone woke you up in the middle of the night and asked you to test two univariate polynomial expressions for identity, you'd probably reduce them to sum-of-products normal form and compare for structural identity. Unfortunately, the reduction can take exponential time; it's analogous to reducing Boolean expressions to disjunctive normal form.

Assuming you are the sort who likes randomized algorithms, your next attempt would probably be to evaluate the polynomials at randomly chosen points in search of counterexamples, declaring the polynomials very likely to be identical if they pass enough tests. The Schwartz-Zippel lemma shows that as the number of points grows, the chance of a false positive diminishes very rapidly.

No deterministic algorithm for the problem is known that runs in polynomial time.

> **Comments:**
> **username_38**: This should have been suggested long ago!  Thanks!  
> **username_36**: There are several other randomized algorithms that deserve a prominent place in the Book. For these the contrast between the deterministic and probabilistic alternatives is less striking: a deterministic algorithm usually exists but is much more complicated.  
> **username_37**: I independently invented the same algorithm while I was working on a paper a couple years ago until someone asked me isn't it Schwartz-Zippel lemma? And I said, what is that? :)  

---

### Answer by username_39 on 2010-08-17. Score: 55

The **[Miller-Rabin primality test](http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)** (and similar tests) should be in The Book. The idea is to take advantage of properties of primes (ie using Fermat's little theorem) to probabilistically look for a witness to the number not being prime. If no witness is found after enough random tests, the number is classified as prime.

On that note, the **[AKS primality test](http://en.wikipedia.org/wiki/AKS_primality_test)** that showed PRIMES is in P should certainly be in The Book!


---

### Answer by username_4 on 2010-08-18. Score: 49

**Depth First Search**. It is the basis of many other algorithms. It is also *deceivingly* simple: For example, if you replace the queue in a BFS implementation by a stack, do you get DFS?

> **Comments:**
> **username_41**: It is also the basis of Prolog execution!  
> **username_40**: What's the point about BFS with a stack I'm missing? I would have thought that the answer is "yes, you get DFS".  
> **username_4**: Well, everybody seems to think this problem is trivial. Also, everybody seems to think the answer is "yes", which is wrong. The answer is actually "depends on which BFS implementation you start with". See http://cs.stackexchange.com/questions/329/do-you-get-dfs-if-you-change-the-queue-to-a-stack-in-a-bfs-implementation (This is a question I posted to help with the beta phase of CS.SE)  
> **username_4**: It's also briefly discussed here: http://www.ics.uci.edu//~eppstein/161/960215.html  

---

### Answer by username_7 on 2010-08-17. Score: 45

Gentry's Fully Homomorphic Encryption Scheme (either over ideal lattices or over the integers) is terribly beautiful. It allows a third party to perform arbitrary computations on encrypted data without access to a private key.

The encryption scheme is due to several keen observations.

* To get a fully homomorphic encryption scheme, one needs only to have a scheme that is homomorphic over addition and multiplication. This is because addition and multiplication (mod 2) are enough to get AND, OR and NOT gates (and therefore Turing Completeness).
* That if such a scheme were to be had, but due to some limitations could only be executed for circuits of some finite depth, then one can *homomorphically* evaluate the decryption and reencyption procedure to reset the circuit depth limitation without sacrificing key privacy.
* That by "squashing" the depth of the circuit version of the decryption function for the scheme, one might enable a scheme originally limited to finite, shallow circuits an arbitrary number of computations.

In his thesis, Craig Gentry solved a long standing (and gorgeous) open problem in cryptography. The fact that a fully homomorphic scheme does exist demands that we recognize that there is some inherent structure to computability that we may have otherwise ignored.

<http://crypto.stanford.edu/craig/craig-thesis.pdf>

<http://eprint.iacr.org/2009/616.pdf>

<http://portal.acm.org/citation.cfm?id=1666420.1666445>


---

### Answer by username_42 on 2010-08-25. Score: 44

The [Cooley-Tukey FFT Algorithm](http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm).

> **Comments:**
> **username_43**: Yes, especially for its butterfly diagrams (http://en.wikipedia.org/wiki/Butterfly_diagram).  

---

### Answer by username_44 on 2010-08-22. Score: 41

**[Strassen's algorithm](http://en.wikipedia.org/wiki/Strassen_algorithm)** for matrix multiplication.

> **Comments:**
> **username_45**: Would probably wait till we know if it is optimal.  
> **username_46**: It isn't optimal, at least, asymptotically... I think that including Strassen's algorithm forces you to include Karatsuba's algorithm first.  

---

### Answer by username_47 on 2010-08-26. Score: 37

The [Gale-Shapley stable marriage algorithm](http://en.wikipedia.org/wiki/Stable_marriage_problem). This algorithm is greedy and very simple, it isn't obvious at first why it would work, but then the proof of correctness is again easy to understand.

> **Comments:**
> **username_48**: +1 because there's also a chapter in the published proofs from the book about marriages...  

---

### Answer by username_49 on 2010-08-17. Score: 34

The linear time algorithm for constructing suffix arrays is truly beautiful, although it didn't really receive the recognition it deserved <http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf>

> **Comments:**
> **username_32**: I *do* think that it *has* received the recognition it deserves – what makes you think otherwise? For example, it’s implemented in the C++ sequence analysis library SeqAn.  
> **username_50**: It is worth mentioning that there are now a number of other linear and non linear time suffix array construction algorithms which, although nowhere near as pretty, may be quite a lot faster in practice.  "An efficient, versatile approach to suffix sorting", Journal of Experimental Algorithmics (JEA), Volume 12, June 2008 has some experimental results along these lines.  
> **username_5**: @Raphael: I'm a bit wary of the fact that on p. 3 of that JEA paper, they give only what they "believe" is a "loose" bound of O(n^2 log n)...  Do you know any papers with *provably linear-time* algorithms that are faster in practice than the Skew Algorithm?  

---

### Answer by username_51 on 2010-09-20. Score: 33

The [Tortoise and hare Algorithm](http://en.wikipedia.org/wiki/Cycle_detection). I like it because I'm sure that even if I wasted my entire life trying to find it, there is no way I would come up with such an Idea.

> **Comments:**
> **username_36**: Do you know the dumb algorithm that solves the problem with the same asymptotics and follows an algorithmic design pattern? I'm talking about iterative deepening. In the nth iteration you start at the 2^n-th successor of the root and look 2^n successors forward in search of a recurrence. Even though you're retracing some of your steps with every iteration, the geometric growth rate of the search radius means that it doesn't affect the asymptotics.  

---

### Answer by username_52 on 2010-10-01. Score: 32

[Merge Sort](http://en.wikipedia.org/wiki/Merge_sort). Simple, elegant, efficient.


---

### Answer by username_38 on 2010-08-17. Score: 32

An example as fundamental and "trivial" as Euclid's proof of infinitely many primes:

**2-approximation for MAX-CUT** -- Independently for each vertex, assign it to one of the two partitions with equal probability.

> **Comments:**
> **username_53**: Yes, a very nice algorithm. Less trivially, at the cost of another factor of 2, this algorithm also works for maximizing _any_ submodular function, not just the graph cut function. This is a result of Feige, Mirrokni, and Vondrak from FOCS 07  

---

### Answer by username_54 on 2010-08-25. Score: 32

Gaussian elimination. It completes the generalization sequence from the Euclidean GCD algorithm to Knuth-Bendix.

> **Comments:**
> **username_56**: BTW, what's the generalization sequence, and where does Buchberger's algorithm for Grobner basis fit into it? (It seems analogous to Knuth-Bendix, but I've seen a mention somewhere that it sort of generalizes Gaussian elimination…)  
> **username_54**: the sequence is: Euclidean GCD -> Gaussian Elimination -> Buchberger -> Knuth-Bendix. One can also put in (instead of Gaussian Elimination) univariate polynomial division and modulo (in the generalization order it is 'apart' from Gaussian Elimination, GE is multivariate degree 1, polynomial ring is univariate unlimited degree, Buchberger's is multivariate unlimited degree. The generalization jump is largest from EGCD to GE or polynomial ring because of the addition of variables, and then also large from Buchberger to KB because of the unlimited signature.  
> **username_55**: +1: Euclidean algorithm solves the most celebrated equation ax-by=1 in math. Why it doesn't show up in CS more often is a mystery.  

---

### Answer by username_57 on 2010-08-19. Score: 31

I've always been partial to **[Christofides' Algorithm](http://en.wikipedia.org/wiki/Christofides_algorithm)** that gives a (3/2)-approximation for metric TSP. In fact, call me easy to please, but I even liked [the 2-approximation algorithm that came before it](http://en.wikipedia.org/wiki/Traveling_salesman_problem#Metric_TSP). Christofides' trick of making a minimum weight spanning tree Eulerian by adding a matching of its odd-degree vertices (instead of duplicating all edges) is simple and elegant, and it takes little to convince one that this matching has no more than half the weight of an optimum tour.

> **Comments:**
> **username_58**: Indeed, there are also plenty of other simple and elegant approximation algorithms with decent approximation guarantees.  

---

### Answer by username_65 on 2010-08-27. Score: 28

How about [Grover's algorithm](http://en.wikipedia.org/wiki/Grover%27s_algorithm)? It's one of the simplest quantum algorithms, and allows you to search an unsorted database in $O(\sqrt N)$. It is provably optimal, and also provably outperforms any classical algorithm. For a bonus it is very easy to understand and intuitive.


---

### Answer by username_12 on 2010-08-17. Score: 27

Algorithms for **linear programming**: Simplex, Ellipsoid, and interior point methods.

<http://en.wikipedia.org/wiki/Linear_programming#Algorithms>

> **Comments:**
> **username_7**: And indeed, several Nobel prizes were given for advancing our understanding of these problems.  
> **username_66**: @Ross Kantorovich won the Nobel prize in Economics for inventing LP and applying it to resource allocations. What other prizes were you thinking of?  
> **username_7**: @Mark Koopermans was awarded the nobel prize with Kantorovich, but it was still inaccurate of me to say "several."  

---

### Answer by username_59 on 2010-08-18. Score: 22

Marcus Hutter's [The Fastest and Shortest Algorithm for All Well-Defined Problems](http://www.hutter1.net/ai/pfastprg.htm).

This kind of goes against the spirit of the other offerings in this list, since it is only of theoretical and not practical interest, but then again the title kind of says it all. Perhaps it should be included as a cautionary tale for those who would look only at the asymptotic behavior of an algorithm.


---

### Answer by username_60 on 2010-08-19. Score: 22

**Knuth's Algorithm X** finds all solutions to the **exact cover problem**. What is so magical about it is the technique he proposed to efficiently implement it: [Dancing Links](http://arxiv.org/abs/cs/0011047).


---

### Answer by username_61 on 2010-08-19. Score: 22

Robin Moser algorithm for solving a certain class of SAT instances. Such instances are solvable by Lovasz Local Lemma. Moser algorithm is indeed a de-randomization of the statement of the lemma.

I think that is some years his algorithm (and the technique for its correctness proof) will be well digested and refined to the point of being a viable candidate for an **Algorithm from the Book**.

[This version](http://arxiv.org/abs/0903.0544) is an extension of his original paper, written with Gábor Tardos.


---

### Answer by username_60 on 2010-08-18. Score: 21

I think we must include **Schieber-Vishkin**'s, which answers **lowest common ancestor** queries in constant time, preprocessing the forest in linear time.

I like Knuth's exposition in Volume 4 Fascicle 1, and [his musing](https://www.youtube.com/watch?v=Xv-7xkMLaAw).
He said it took him two entire days to fully understand it, and I remember his words:

> I think it's quite beautiful, but
> amazingly it's got a bad press in the
> literature (..) It's based on
> mathematics that excites me.

> **Comments:**
> **username_56**: Wait, it may be beautiful, but if it took Knuth two entire days to fully understand it, is it really "from the book"?  
> **username_62**: @ShreevatsaR The book has fine print in the footnotes :)  

---

### Answer by username_38 on 2010-08-22. Score: 20

**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)](http://dx.doi.org/10.1109/SFCS.1994.365734), following work of [Tanner (1981)](http://www.ldpc-codes.com/papers/rlcc.pdf), 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:

1. 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)](http://doi.acm.org/10.1145/509907.510003). Sipser and Spielman themselves constructed linear time decodable codes by using the Tanner product construction.
2. [Spielman (1995)](http://doi.acm.org/10.1145/225058.225165) developed these ideas further to give a code with both linear time encoding and decoding.

> **Comments:**
> **username_7**: Much more beautiful than LT or Raptor!  

---

### Answer by username_63 on 2010-09-16. Score: 18

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.


---

### Answer by username_64 on 2010-08-26. Score: 16

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>

> **Comments:**
> **username_63**: A version that I consider particularly elegant and easy to explain is due to Khuller and Matias http://www.cs.umd.edu/users/samir/grant/cp95.ps  

---

### Answer by username_77 on 2010-08-23. Score: 15

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:

* Randomized equality testing (hugely important in communication protocols)* Hashing with chaining* Count-min sketches

> **Comments:**
> **username_16**: another application: the perfect hashing algorithm of Fredman, Komlos, and Szemeredi, itself quite beautiful  

---

### Answer by username_67 on 2011-10-09. Score: 13

Moore's O(n) [Majority voting algorithm](http://www.cs.utexas.edu/~moore/best-ideas/mjrty/) is like a magic-trick!


---

### Answer by username_68 on 2010-08-23. Score: 13

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](http://en.wikipedia.org/wiki/Delaunay_triangulation#Flip_algorithms) for constructing the Delaunay Triangulation in 2D.
Even though it is not optimal.

> **Comments:**
> **username_69**: excellent idea !!!!  

---

### Answer by username_70 on 2010-08-17. Score: 12

Avi Wigderson in Part II of [these lectures](http://hulk03.princeton.edu:8080/WebMedia/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)

> **Comments:**
> **username_72**: This would be an even better answer, if you could name a concrete algorithm for these problems which you think should be called an "algorithm from the book". (FFT is a fine answer already)  
> **username_73**: Please, one algorithm per answer. (And we already have KMP.)  
> **username_71**: I'm pretty sure Berlekamp-Massey's algo is not error correction. To me it seems more along the lines of reverse engineering an LFSR back to a particular state given the output bits of the mentioned LFSR. I don't see that as error correction more than a well formed parsing algorithm.  

---

### Answer by username_60 on 2010-08-19. Score: 12

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](http://stanford-online.stanford.edu/seminars/knuth/080605-knuth-300.asx) and [here](http://proedvid.stanford.edu/knuth/081209/081209-knuth-300.wmv).


---

### Answer by username_74 on 2010-09-13. Score: 11

[Kosaraju's Algorithm](http://en.wikipedia.org/wiki/Kosaraju%27s_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.


---

### Answer by username_75 on 2011-01-16. Score: 11

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

> **Comments:**
> **username_76**: thats an awesome choice...i like the way they analyze the algorithm...by picking what, in my opinion, is a very non-trivial thing to amortize on  

---

### Answer by username_78 on 2013-06-16. Score: 10

I propose [Reed-Solomon coding](http://en.wikipedia.org/wiki/Reed_Solomon). 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.

> **Comments:**
> **username_16**: this is a great example, and the idea has found uses ranging from list decoding to secret sharing.  

---

### Answer by username_13 on 2011-01-16. Score: 10

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.

<http://en.wikipedia.org/wiki/Cycle_detection>


---

### Answer by username_94 on 2010-09-15. Score: 10

The (random projection algorithm implicit in the) Johnson-Lindenstrauss lemma!


---

### Answer by username_79 on 2010-08-24. Score: 9

I think that there should be at least one persistant data structure. In particular, the ["persistant array"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.1317) let us obtains a lot of other persistant data-structures where we wouldn't expect them.


---

### Answer by username_79 on 2010-08-24. Score: 9

I guess the algorithm to "[hash-cons](http://en.wikipedia.org/wiki/Hash_consing)" 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).

> **Comments:**
> **username_4**: In my book, that's someone *everyone* should now, very few heard the term, and many keep reinventing.  

---

### Answer by username_80 on 2010-09-22. Score: 9

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.

<http://en.wikipedia.org/wiki/Risch_algorithm>

> **Comments:**
> **username_66**: That seems to be an incredibly complicated algorithm. According to Wikipedia, no software currently implements the full algorithm due to its complexity. In fact, it's not even a terminating algorithm. Other than the problem it solves, in what sense is this an "elegant" algorithm?  

---

### Answer by username_81 on 2010-09-20. Score: 9

The **O(n)** algorithm for finding the **maximum-sum contiguous subarray** of a list of integers L.

* L can contain both positive and negative integers
* L is not necessarily sorted
* L can contain duplicate entries
* subarray length can be in the range [1, n] where n is the length of L

For example the list {-1, 500, -100, 101} has a maximum-sum subsequence of {500, -100, 101}.

I learned about this [algorithm](http://www.cs.bell-labs.com/cm/cs/pearls/maxsum.c) from [Jon Bentley's Programming Pearls](http://www.cs.bell-labs.com/cm/cs/pearls/). Note the code contains a few versions of this algorithm... the last version is O(n).

> **Comments:**
> **username_82**: This algorithm is also known as “[Kadane’s Algorithm](https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane.27s_algorithm).” I nearly missed this answer because searching for “Kadane” didn’t yield any result on this page, and was just about to write one suggesting this algorithm.  
> **username_83**: can you please update the links, both are not working.  

---

### Answer by username_84 on 2010-09-22. Score: 8

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.

> **Comments:**
> **username_86**: I disagree that "There is no way to make a good pivot choice." There may be no instant way to make a good pivot choice, but median of medians will find a good pivot.  
> **username_87**: I think the point really is that in terms of simplicity, elegance, and computational economy, Mergesort belongs in the Book and Quicksort probably does not.  I don't completely agree, but +1 for bringing up the idea that the Book isn't just a collection of favorite algorithms.  
> **username_9**: The most elegant way to choose the quicksort pivot is to choose it *randomly*.  Then (and only then) quicksort belongs in The Book.  
> **username_85**: Choosing a pivot randomly is a _deus ex machina_ non-answer. We're talking about _The Book_ here, not _The Book_ plus a qualified source of randomness. Mergesort in, quicksort out.  

---

### Answer by username_88 on 2010-09-13. Score: 8

An algorithm that I find truly simple and elegant is the [Rabin-Karp](http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm) algorithm of using rolling-hashes for linear time string search. A lot simpler to wrap your head around than KMP.


---

### Answer by username_89 on 2010-09-21. Score: 8

Everyone says Knuth-Morris-Pratt. I don't think the [Boyer-Moore](http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm) string-matching algorithm gets enough credit.

There's [a wonderful exploration Boyer-Moore's implementation in grep on ridiculousfish](http://ridiculousfish.com/blog/archives/2006/05/30/old-age-and-treachery/). For the more academically-inclined, Mike Haertel, grep's longtime maintainer, [explains why grep is so fast](http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html).

> **Comments:**
> **username_89**: (2) http://ridiculousfish.com/blog/archives/2006/05/30/old-age-and-treachery/ (3) http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html  
> **username_90**: I've incorporated the links into your answer. If you're OK with my edit, I think that you (we) can remove the comment(s).  
> **username_90**: On a side note, there's actually [an older Boyer-Moore answer](http://cstheory.stackexchange.com/questions/189/algorithms-from-the-book/1469#1469).  
> **username_89**: I'm ok with your edits. And I looked but didn't see it anywhere else, so I'll make a better effort in the future to avoid redundancies. Sorry about that.  
> **username_32**: Horspool (Boyer-Moore-Horspool) is even simpler to state (it’s a simplification of Boyer-Moore), and performs better in practice.  

---

### Answer by username_91 on 2010-10-30. Score: 8

I wonder nobody mentioned Schöning's random-walk algorithm for 3-SAT solving yet. It it very simple:

* Start with a random assignment
* As long as there exists an unsatisfied clause: Flip a randomly-selected variable in this clause

Nevertheless, it is to date one of the fastest algorithms in its class.


---

### Answer by username_92 on 2010-12-06. Score: 8

The [Viterbi algorithm](http://en.wikipedia.org/wiki/Viterbi_algorithm), [low-density parity-check codes](http://en.wikipedia.org/wiki/Ldpc), and [turbo codes](http://en.wikipedia.org/wiki/Turbo_code)- communication at the noise floor!


---

### Answer by username_93 on 2010-08-23. Score: 8

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

> **Comments:**
> **username_3**: note that "Newtons method" for finding solutions via the derivative is a 1-d analogue of multivariate steepest descent.  

---

### Answer by username_79 on 2010-08-23. Score: 7

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 !

> **Comments:**
> **username_60**: This result is very nice, but I don't think it classifies as beautiful *as an algorithm*.  

---

### Answer by username_95 on 2012-04-01. Score: 7

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.


---

### Answer by username_66 on 2010-11-15. Score: 7

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.

> **Comments:**
> **username_30**: Can you explain what "Run Trivial" means?  

---

### Answer by username_60 on 2010-08-22. Score: 7

I think that [LR parsers](http://en.wikipedia.org/wiki/LR_parser) are beautiful. A language is deterministic context-free if and only if there exists a LR(1) grammar for it.


---

### Answer by username_61 on 2010-08-31. Score: 7

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.

> **Comments:**
> **username_96**: Oh yes, I absolutely love this algorithm! And there is an even more preliminary version of it (same running time, though) which branches on edges. Pick an edge $(u,v)$. Since it must be covered, at least one of $u$ or $v$ must belong to any vertex cover; and we branch on both possibilities. Thank you for suggesting this, I was just about to! :)  

---

### Answer by username_60 on 2010-08-22. Score: 7

[Knuth-Bendix algorithm](http://en.wikipedia.org/wiki/Knuth%E2%80%93Bendix_completion_algorithm) and the analogous [Buchberger's algorithm](http://en.wikipedia.org/wiki/Buchberger%27s_algorithm).


---

### Answer by username_98 on 2010-08-30. Score: 7

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"


---

### Answer by username_97 on 2010-10-29. Score: 6

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.

![alt text](https://i.sstatic.net/oJHE1.png)

[image sourced from this wikipedia article](http://en.wikipedia.org/wiki/Cantor's_diagonal_argument)


---

### Answer by username_99 on 2010-09-19. Score: 5

[Boyer-Moore](http://userweb.cs.utexas.edu/users/moore/best-ideas/string-searching/) 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.


---

### Answer by username_100 on 2013-06-16. Score: 5

[Savitch's Algorithm](http://en.wikipedia.org/wiki/Savitch%27s_theorem): a simple recursive algorithm for the [Reachability](http://en.wikipedia.org/wiki/St-connectivity) problem, with a conceptually deep consequence: [PSPACE](http://en.wikipedia.org/wiki/PSPACE)=[NPSPACE](http://en.wikipedia.org/wiki/NPSPACE).


---

### Answer by username_101 on 2010-08-31. Score: 4

The Shift-And algorithm by Baeza-Yates and Gonnet ([Bitap](http://en.wikipedia.org/wiki/Bitap_algorithm) @Wikipedia) for finding all occurrences of a pattern in a text. In my opinion the simplest example of a useful seminumerical algorithm.


---

### Answer by username_102 on 2016-11-12. Score: 4

[Zeilberger's algorithm](http://mathworld.wolfram.com/ZeilbergersAlgorithm.html), 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.


---

### Answer by username_103 on 2010-10-20. Score: 4

If Dijkstra is specified, I think that [Bellman-Ford](http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm) is even a better candidate.

> **Comments:**
> **username_37**: I think Dijkstra's algorithm is actually an ugly one compared to Bellman-Ford!  

---

### Answer by username_104 on 2011-02-12. Score: 4

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](http://en.wikipedia.org/wiki/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.


---

### Answer by username_105 on 2011-04-11. Score: 4

I just learned about a book entitled [Algorithms unplugged](http://www.springerlink.com/content/978-3-642-15327-3/contents/), which seems relevant to this topic.

> **Comments:**
> **username_106**: A very good collection indeed!  

---

### Answer by username_107 on 2010-08-24. Score: 4

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

> **Comments:**
> **username_5**: +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.)  
> **username_107**: good clarification  

---

### Answer by username_108 on 2014-02-28. Score: 3

The divide and conquer algorithm by Michael Shamos to solve the planar [Closest pair of points problem](http://en.wikipedia.org/wiki/Closest_pair_of_points) 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.


---

### Answer by username_109 on 2010-09-13. Score: 3

The Kalman filter, absolutely brilliant for handling data with noise: <http://en.wikipedia.org/wiki/Kalman_filter>


---

### Answer by username_92 on 2010-12-06. Score: 3

The [Thompson NFA construction](http://swtch.com/~rsc/regexp/regexp1.html) and, in particular, [evaluation method](http://swtch.com/~rsc/regexp/regexp1.html). Probably the slickest bit of code I've ever seen.


---

### Answer by username_71 on 2010-08-24. Score: 3

It's such a simple thing, but in it's simplicity is it's elegance: [Linear Feedback Shift Registers](http://en.wikipedia.org/wiki/LFSR). 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.


---

### Answer by username_110 on 2013-11-23. Score: 3

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"


---

### Answer by username_111 on 2012-03-30. Score: 2

I think that [Hensel Lifting](http://www.cse.iitk.ac.in/users/manindra/CS681/2005/Lecture17.pdf) is pretty nifty too, and it has many applications in algorithmic number theory and algebra.


---

### Answer by username_37 on 2014-09-04. Score: 2

If union-find is in the book,
why can't [Bloom filters](http://en.wikipedia.org/wiki/Bloom_filter) be there?
If you are not familiar with Bloom filters, [this video](https://www.youtube.com/watch?v=-SuTGoFYjZs) is a quick but nice introduction.


---

### Answer by username_17 on 2013-06-21. Score: 1

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


---

### Answer by username_112 on 2015-01-25. Score: 1

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


---

### Answer by username_113 on 2012-04-18. Score: 0

I am sure "[Ancient Egyptian Multiplication](http://en.wikipedia.org/wiki/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.


---

### Answer by username_114 on 2011-01-18. Score: 0

I like the [CORDIC](http://en.wikipedia.org/wiki/CORDIC) algorithm for solving trigonometric and hyperbolic functions, especially when implemented using fixed-point integer representations.


---

### Answer by username_81 on 2010-09-20. Score: 0

The algorithm that uses **[Pascal's Triangle](http://en.wikipedia.org/wiki/Pascal%27s_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".


---

### Answer by username_117 on 2019-01-05. Score: 0

From the world of purely functional data structures and algorithms, Gérard Huet's [zipper](http://gallium.inria.fr/~huet/PUBLIC/zip.pdf) 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.


---

### Answer by username_115 on 2014-02-27. Score: -1

As we talk of a book of "God" and a beautiful algorithm, something that comes to my mind is [Conway's Game of Life](http://en.wikipedia.org/wiki/Conway%27s_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.

> **Comments:**
> **username_116**: 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. http://www.hpl.hp.com/techreports/2006/HPL-2006-2.pdf  

---

### Answer by username_116 on 2014-02-26. Score: -3

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.

> **Comments:**
> **username_16**: 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.  
> **username_116**: 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.  
> **username_16**: 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..  

---

