Obviously this is not an exhaustive list, and it omits some important algorithms as well (e.g. Lempel-Ziv family). I'm also not interested in listing algorithms whose common name is quite descriptive (e.g. Sieve of Eratosthenes, Gauss-Jordan elimination, etc).

Shortest path in a graph:

- Dijkstra's algorithm - single-source

- Bellman-Ford algorithm - single-source, negative edges

- Floyd-Warshall algorithm - all-pairs (it's neat how concise and straightforward this solution is to what at a glance looked to be a harder super-problem)

Maximum flow of a network:

- Ford-Fulkerson algorithm

- Edmonds-Karp algorithm (frankly I don't think this deserves its own name)

Minimum spanning trees:

- Kruskal's algorithm

- Prim's algorithm

String search:

- Knuth-Morris-Pratt algorithm (cool automaton!)

- Boyer-Moore algorithm (it works backward!)

Computational biology:

- Smith-Waterman algorithm - local sequence alignment

- Ukkonen's algorithm - suffix tree construction

- "Kärkkäinen's algorithm" - suffix array construction (not sure what other people think of it, but it still blows my mind how elegant it is)

Pseudorandom number generator:

- Blub Blum Shub (I don't think I can ever say it with a straight face)

Matrix multiplication:

- Strassen algorithm (it took me a few years before I gave this algorithm a chance; it's actually pretty cool, not to mention revolutionary)

- Cannon's algorithm (surprised that Wikipedia doesn't have more on this rather neat algorithm; maybe I'll contribute some day!)

Quantum:

- Shor's algorithm - prime factorization

Letter:

- Algorithm P - random shuffle

- Algorithm X - exact cover

- Algorithm W - type-inferrence (this is what inspired this entry, actually)

And I guess I'll mention this one for giggles:

- God's algorithm

## Saturday, January 16, 2010

Subscribe to:
Post Comments (Atom)

You might want to take a look at my collection:

ReplyDeletehttp://nick-black.com/dankwiki/index.php/Category:Computer_Science_Eponyms