Tuesday, September 25, 2007

Book Algorithms

We know the legend of Paul (Uncle, to some) Erdos and the Erdoslore of Book Proofs, proofs brilliant and perfect from The Book.

To an algorithmus, the question is, what are examples of Book Algorithms? Algorithms is a broad research area and it is hard for any one to select Book Algorithms or to even define one or elicit any consensus at a dinner table of algorithmii. In string matching algorithms, I think the suffix tree algorithm of Karkkainen and Sanders is an example. What about geometry, scheduling, graphs, approximate, random, online or other algorithms, data structures included?


Blogger JeffE said...

A few off the top of my head:

"Russian peasant" multiplication

Euclid's GCD algorithm

Boruvka's MST algorithm

Brepth-first search (uses a quack)

Cooley + Tukey's FFT

Dantzig's simplex algorithm

Knuth-Morris-Pratt string matching

Computational geometry: Clarkson-Shor randomized incremental construction; fractional cascading

Data structures: splay trees; treaps; van Emde Boas trees; cuckoo hashing

10:47 AM  
Blogger Inbok said...

Karkainen and Sanders's algorithm is about suffix arrays.

10:55 AM  
Anonymous Anonymous said...

Count my votes for FFT and cuckoo hashing.

10:56 AM  
Blogger Mihai said...

A few in data structures, in no particular order:

* cuckoo hashing with variations (Bloomier filters, uniform hashing)

* Dynamic connectivity in O(lg^2 n) by Holm, de Lichtenberg, Thorup.

* LCA/RMQ in linear time and constant time.

* searching with wildcards (the simple algorithm in Cole, Gottlieb, Lewenstein)

* 1d range reporting in linear space and constant time [Alstrup, Brodal, Rauhe]

* 3d range reporting by Nekritch (only the simple existential version)

* approximate nearest neighbor in constant dimension [Chan]

1:36 PM  
Anonymous Anonymous said...

You mean perhaps:

E. Ukkonen. On-line construction of suffix trees. Algorithmica, 14(3):249–260,

Also I'll add the Fisher algorithm for computing majority on a string in one/two passes using a single counter.

Burrows-Wheeler is also amazingly effective as a compression algorithm. On the same vein Lempel-Ziv never ceases to amaze me. The coder and decoder fit in less than a page of code!

3:06 PM  
Blogger metoo said...

* Inbok: you are right of course, it is an algorithm for suffix sorting, I don't typically make internalize array/tree.

* Jeff: Not clear KMP or splay trees will make my list.

* MIP: LCA/RMQ is cool. Wildcard matching is phenomenally simple and cool.

* Yet another Anonymous: Burrows-Wheeler is a nifty algorithm, almost non-intuitive at first look. yes, I think it will make it to my list too.

9:45 PM  
Anonymous Anonymous said...

Which GCD algorithm? As much as I like Euclid's I might go for the variant with parity checks, subtraction and division by 2 rather than general division with remainder. The implementation of general division is relatively complicated.

Some algorithms to add:

Batcher's bitonic sort

Fischer-Ladner's parallel prefix algorithm

8:49 AM  
Anonymous Anonymous said...

Median of Five

M. Blum, R. Floyd, V. Pratt, R. Rivest, and R. Tarjan. Time bounds for selection. J. Computer and System Sciences, 7:448-461, 1972.

2:15 PM  
Blogger pálenica said...

Steve Fortune's Voronoi diagram algorithm.

12:34 PM  
Anonymous Anonymous said...

qISO4M Your blog is great. Articles is interesting!

12:37 AM  
Anonymous Anonymous said...

bGgSjx Please write anything else!

11:00 AM  
Anonymous Anonymous said...

roMf6g actually, that's brilliant. Thank you. I'm going to pass that on to a couple of people.

12:00 PM  
Anonymous Anonymous said...

Thanks to author.

12:14 PM  
Anonymous Anonymous said...


12:32 PM  
Anonymous Anonymous said...

Please write anything else!

12:11 PM  
Anonymous Anonymous said...


1:00 PM  
Anonymous Anonymous said...

Hello all!

7:36 AM  
Anonymous Anonymous said...

Nice Article.

11:10 PM  
Anonymous Anonymous said...

Hello all!

2:23 AM  
Anonymous Anonymous said...

Wonderful blog.

6:17 AM  
Anonymous Anonymous said...

rCrDEX Please write anything else!

11:26 AM  
Anonymous Anonymous said...

Wonderful blog.

11:54 AM  
Anonymous generic propecia said...

Hello people want to express my satisfaction with this blog very creative and I really like the views of the focus very good indeed Thank you for the helpful information. I hope you keep up the good work on making your blog a success!

9:32 AM  

Post a Comment

<< Home