Top 10 Algorithms
A Group-Participation Session
Criteria for a Top 10 Algorithm
An algorithm on the top-10 list should:
-
clearly illustrate a general principle,
-
provide motivation for other algorithms,
-
have real-world applications,
-
be elegant,
-
include something surprising or clever or amazing,
-
be "classic" in some sense.
Collectively, the top 10 algorithms should:
-
illustrate a range of ideas,
-
cover a broad range of the discipline,
-
include at least a couple algorithms that invite comparison
in solving the same problem
Suggested Algorithms for the Top 10 List
During the session, attendees divided into four groups to brainstorm
candidates for a Top 10 list. Each group reported three algorithms
at the end of the session, as follows:
-
Binary search
-
Euclidean GCD
-
Quicksort (or quickfind)
-
Newton's Method for finding roots
-
Matrix chain multiplication (dynamic programming)
-
Minimal spanning tree (2 algoritms)
-
RSA public key encryption
-
Huffman encoding (example of greedy algorithm)
Plane sweep (convex hull, or other geometric algorithm)
-
Dijkstra's mutual exclusion
li>
Dijkstra's shortest path
-
Fast Fourier Transform
The following additional algorithms were identified within groups, although
time prevented their mention during the session itself.
-
mergesort (as an example of divide-and-conquer algorithms)
-
alpha-beta pruning
-
pre- and post-order tree traversals
-
hashing
-
tree sorting
-
Quine-McCluskey procedure for constructing minimal coverings of sets of
Boolean vectors
-
construction of Hamming error-correcting codes
-
Knuth-Morris-Pratt string matching
-
unification
-
critical-path scheduling
-
conversion of nondeterministic finite automata to deterministic ones
-
Ford-Fulkerson network-flow algorithm
-
Perlman spanning-tree protocol for self-organizing network topology
-
map coloring (as an example of backtracking)
-
AES encryption
-
the Towers of Hanoi
-
nonattacking queens (as an example of backtracking)
-
Hamming code
This document is available on the World Wide Web as
http://www.cs.grinnell.edu/~walker/ia-cs/program.02.html