Saturday, January 16, 2010

Named algorithms

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

- Shor's algorithm - prime factorization

- 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

1 comment:

  1. You might want to take a look at my collection: