5 ms·

The Best Algorithms of the 20th Century [pdf]

87 points by sirchristian 14y ago

pmcjones 14y ago
For more on #5 (original Fortran optimizing compiler), including the source code, see http://www.softwarepreservation.org/projects/FORTRAN/ 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 http://comjnl.oxfordjournals.org/content/5/1/10.abstract (the full text is freely downloadable).
eternalban 14y ago
Khawrazmi was a Persian Muslim. I stopped reading right there.
- Confusion 14y ago
  Because someone didn't factcheck an irrelevant fact othside of his expertise, for which it is entirely normal to trust 'dubious' sources? (In which I include the author's memory)
- voltagex_ 14y ago
  Why?
- brianobush 14y ago
  What does religion have to do with algorithms?!
  - justin66 14y ago
    The article's statement in the second sentence that al-Khwarizmi was an Arab is an error. The person you're responding to was almost certainly not being bigoted, he was reacting to a factual error in the introductory paragraph of the article.
    - brianobush 14y ago
      I see your point and agree. However, many will not readily discern Persian from Arab and focus on the more interesting content: the algorithms
      - justin66 14y ago
        Fair enough. I commented because it seemed very unfair that he was downvoted. People are too eager to do that. The point he made might not seem very important, and might be misunderstood, but it's true.
  - tzs 14y ago
    Suppose the article was about the greatest boxers of the 20th century, and it talked about the Arab boxer Muhammad Ali. Would you object to someone pointing out that Ali was not Arab, but rather an American Muslim? His being Muslim is relevant not because it is his religion, but because it explains why an American of his era has such a foreign name--he changed his name when he converted to Islam. Same thing is going on here. The article says al-Khwarizmi was an Arab. He was actually a Persian who followed the Arab religion (Islam), which probably explains the Arab-appearing aspects of his life and work. Does it matter if he was Arab or Persian? Some might argue that all that matters is what he discovered. The counter argument is that by mentioning things like nationality, ethnicity, religion, etc., in these kind of articles, it helps reinforce the idea that science transcends national borders, ethnic boundaries, religion, and so on. I believe I read something by Asimov once where he said that was the reason he always included the nationality of scientists he wrote about.
    - da_n 14y ago
      So is it somewhat equivalent to saying someone is protestant when they are catholic, and being outraged at such a mix-up? I still don't quite understand why it has emoted such apparent disgust as to stop reading, but then I am not a religious person.
      - lmm 14y ago
        It's not about religion. Equivalent would be something like saying an important Mexican scholar was Canadian.
      - tzs 14y ago
        I doubt it has anything to do with religion. He is inferring from the mistake of saying a Persian Muslim was an Arab that the author did not put much effort into research for the article, and so has decided it is not worth reading.
- deleted 14y ago
  [deleted]
ten_fingers 14y ago
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!
qoo 14y ago
FFT FTW!

87 points by sirchristian 14y ago

For more on #5 (original Fortran optimizing compiler), including the source code, see http://www.softwarepreservation.org/projects/FORTRAN/ 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 http://comjnl.oxfordjournals.org/content/5/1/10.abstract (the full text is freely downloadable).

eternalban 14y ago

Khawrazmi was a Persian Muslim. I stopped reading right there.

Confusion 14y ago
Because someone didn't factcheck an irrelevant fact othside of his expertise, for which it is entirely normal to trust 'dubious' sources? (In which I include the author's memory)
voltagex_ 14y ago
Why?
brianobush 14y ago
What does religion have to do with algorithms?!
- justin66 14y ago
  The article's statement in the second sentence that al-Khwarizmi was an Arab is an error. The person you're responding to was almost certainly not being bigoted, he was reacting to a factual error in the introductory paragraph of the article.
  - brianobush 14y ago
    I see your point and agree. However, many will not readily discern Persian from Arab and focus on the more interesting content: the algorithms
    - justin66 14y ago
      Fair enough. I commented because it seemed very unfair that he was downvoted. People are too eager to do that. The point he made might not seem very important, and might be misunderstood, but it's true.
- tzs 14y ago
  Suppose the article was about the greatest boxers of the 20th century, and it talked about the Arab boxer Muhammad Ali. Would you object to someone pointing out that Ali was not Arab, but rather an American Muslim? His being Muslim is relevant not because it is his religion, but because it explains why an American of his era has such a foreign name--he changed his name when he converted to Islam. Same thing is going on here. The article says al-Khwarizmi was an Arab. He was actually a Persian who followed the Arab religion (Islam), which probably explains the Arab-appearing aspects of his life and work. Does it matter if he was Arab or Persian? Some might argue that all that matters is what he discovered. The counter argument is that by mentioning things like nationality, ethnicity, religion, etc., in these kind of articles, it helps reinforce the idea that science transcends national borders, ethnic boundaries, religion, and so on. I believe I read something by Asimov once where he said that was the reason he always included the nationality of scientists he wrote about.
  - da_n 14y ago
    So is it somewhat equivalent to saying someone is protestant when they are catholic, and being outraged at such a mix-up? I still don't quite understand why it has emoted such apparent disgust as to stop reading, but then I am not a religious person.
    - lmm 14y ago
      It's not about religion. Equivalent would be something like saying an important Mexican scholar was Canadian.
    - tzs 14y ago
      I doubt it has anything to do with religion. He is inferring from the mistake of saying a Persian Muslim was an Arab that the author did not put much effort into research for the article, and so has decided it is not worth reading.
deleted 14y ago
[deleted]

ten_fingers 14y ago

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!

qoo 14y ago

FFT FTW!