## Top 10 Algorithms

### 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
```