The Best Algorithms of the 20th Century [pdf]

For more on #5 (original Fortran optimizing compiler), including the source code, see http://www.softwarepreservation.org/projects/FORTRAN/ .

For more on #7 (Quicksort), I especially recommend Hoare's paper in the Computer Journal, which explains many details about the algorithm that are unfortunately not widely known (such as the correct way to partition for Quicksort): http://comjnl.oxfordjournals.org/content/5/1/10.abstract (the full text is freely downloadable).

Why?

Hmm, let's see: One of the algorithms is the fast Fourier transform (FFT). It is sometimes described as a form of matrix factorization and multiplication.

Another algorithm is Dantzig's simplex algorithm for linear programming: It is basically just elementary row operations much as in Gauss elimination on a, usually, vastly 'under determined' system of linear equations. The math for the simplex algorithm is mostly nicely presented via matrix theory.

A third algorithm in the list is the QR algorithm for finding eigenvalues.

So, of the 10 algorithms, at least three are closely related to just matrix theory. Amazing.

Then, for computer science I would add an observation: A few days ago a venture firm principal asked me about my project, "So you have an algorithm?". I had to respond, "Well, yes, but by itself an algorithm doesn't have much to recommend it and, thus, doesn't mean much.".

Well, this list of 10 algorithms supports my observation: For a problem as complicated as those solved by the 10 algorithms in the list, an algorithm by itself doesn't mean much, really doesn't mean anything. Instead, to take any such algorithm seriously, we need something we can take seriously and logically prior to the algorithm.

Well, as in the 10 algorithms, what is prior is just some applied math, typically with theorems and proofs. Then due to the theorems and proofs, we take the applied math seriously. Then we take the algorithm seriously because and only because it is a careful implementation of the data manipulations in the applied math. So, net, what is really crucial for such an algorithm is the logically prior applied math.

Of course, at times we can proceed without any prior applied math and work just with an algorithm that we got, say, from just heuristics. Then we may be able to take the algorithms seriously after a lot of empirical testing.

So, here's my point: For reasonably complicated problems, the key is some applied math, and we take a corresponding algorithm seriously only because of the logically prior applied math.

Or, computer science: The most important work with algorithms is work with logically prior applied math complete with theorems and proofs. Work with algorithms without such prior applied math is close to hopeless.

Venture firms and limited partners: If an entrepreneur has some crucial, core 'secret sauce' in running code that can be called an 'algorithm', what is crucial (prior to already having a financially successful company based on that code) is the corresponding applied math, not the 'algorithm' and not just the code.

Information technology entrepreneurs: If your business is trying to solve a serious problem with an algorithms and some corresponding code, then don't start with the algorithm and, instead, start with some applied math.

Computer science students: If you want to do good work with algorithms, study appropriate topics in a math department, not 'algorithms' in a computer science department.

Computer science professors: Algorithms are crucial to your field, but your approach to algorithms skipping prior applied math complete with theorems and proofs is bankrupt, with no good reason to take any such algorithm seriously, and will lead to a long walk on a short pier and blocked progress for your field. What's just crucial for your interest in algorithms is in the math department and not in your department. Sorry 'bout that!

It's an article from SIAM. Of course it's heavily biased towards applied mathematics. It's not only biased against computer science, it's biased against pure mathematics. Do you doubt that Buchberger's algorithm will reverberate down through the millenia? Even within applied mathematics, the list leaves out multigrid methods, the only linear-time algorithms in their class, which seem a shoe-in given their criteria for inclusion.

It would hardly be difficult to make a very long list of pure CS algorithms and data structures that could stand head to head against the likes of the multipole method in both industrial application and scientific value.

Your knowledge of computer science is evidently shallow. Educate yourself and you might think twice before making such ignorant pronouncements.

I see your point and agree. However, many will not readily discern Persian from Arab and focus on the more interesting content: the algorithms