Friday, July 18, 2014

The Top 10 Algorithms

I am teaching a senior undergrad seminar (for Scientific Computing majors) in the Fall semester, and thought it would be a good idea to pick some kind of a theme.

After some thought, I figured that "famous algorithms" may be a good idea. I tried to google "top algorithms" and came up with many lists. Let me begin for bad lists (in my opinion) to good ones.

A.  George Dvorsky has a list of "the 10 algorithms that dominate the world"

1. Google Search
2. Facebook's News Feed
3. OKCupid Date Matching
4. NSA Data Collection, Interpretation, and Encryption
5. "You May Also Enjoy..."
6. Google AdWords
7. High Frequency Stock Trading
8. MP3 Compression
10. Auto-Tune

While the list is interesting, it is somewhat disappointing. It conflates software products with actual algorithms.

HFT is not an algorithm; although the words algorithmic trading and HFT are often used synonymously. Sure, there are important algorithms lurking under many of these "products"

B. Marcos Otero has a better list of "the real 10 algorithms that dominate the world"

This list is a reaction to the one above. The author prefaces his comments with:
Now if you have studied algorithms the first thing that could come to your mind while reading the article is “Does the author know what an algorithm is?” or maybe “Facebook news feed is an algorithm?” because if Facebook news feed is an algorithm then you could eventually classify almost everything as an algorithm.
1. Merge Sort, Quick Sort and Heap Sort
2. Fourier Transform and Fast Fourier Transform
3. Dijkstra’s algorithm
4. RSA algorithm
5. Secure Hash Algorithm
6. Integer factorization
7. Link Analysis
8. Proportional Integral Derivative Algorithm
9. Data compression algorithms
10. Random Number Generation

While this is a better list, in the sense the the items listed are usually "real" algorithms, or something close, it has a strong computer science bias. For example, #4, #5, and #6 are all algorithms for encryption. While encryption is clearly important, it is probably not 30% by weight of the most important algorithms.

C. SIAM has its own list (pdf) of the "top 10 algorithms of the 20th century"

I like this more comprehensive list the best (although I still have some reservations), because the forest in which they hunt is the biggest. Also, the list is a collaboration of two people, which provides some balance on the topics that are touched.

1. Monte Carlo Method
2. Simplex Method for Linear Programming
3. Krylov Subspace Iteration Methods
4. Decompositional Approach to Matrix Computations
5. Fortran Optimizing Compiler
6. QR Algorithm
7. QuickSort
8. FFT
9. Integer Relation Detection Algorithm
10. Fast Multipole Method

No comments: