4 ms·

The Best Algorithms of the 20th Century [pdf]

62 points by tizzdogg 11y ago

mturmon 11y ago
An evergreen. See also: https://news.ycombinator.com/item?id=4468057 https://news.ycombinator.com/item?id=4468057 (with wildly varying comment quality)
- harakiri 11y ago
  Thanks for the link, I laughing my ass off the comments...
deleted 11y ago
[deleted]
tomkat0789 11y ago
For the full text: http://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2_i1/index.html http://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2_... Ask yourself, which of the 10 have you used today?
- GFK_of_xmaspast 11y ago
  I've been in meetings all day today, but I think I got at least four explicitly yesterday (quicksort, qr, matrix decomposition, simplex), not to mention all the implicit ones we all use everyday.
tizzdogg 11y ago
I submitted this, mostly because I was wondering what more recent algorithms would be added to the list if you were to do a new "best algorithms up until 2015". The most recent algorithm here is from 1987. What new things from the past 30 years might qualify for future best-of lists, assuming they have enough time to gain widespread adoption?
- asgard1024 11y ago
  Wikipedia to the rescue: https://en.wikipedia.org/wiki/Timeline_of_algorithms https://en.wikipedia.org/wiki/Timeline_of_algorithms (Interestingly, some of the algorithms mentioned in the article are missing from the list. It also doesn't list many algorithms from 19th century.) And indeed it seems, there are not so many recently, though I think AKS Primality Test would qualify as a great algorithm of 21st century.
- GFK_of_xmaspast 11y ago
  Pagerank is the first thing that comes to mind (and there was a big survey article about it in the latest SIAM Review https://www.siam.org/journals/sirev.php https://www.siam.org/journals/sirev.php)
  - pathsjs 11y ago
    Hardly 21st century. In its essence it was known to Markov, who died in 1922. For comparison, the idea of TUring machines came in 1936
    - cbd1984 11y ago
      And if you take that idea back, it goes directly to the Jacquard loom, because Knuth Knows we can't possibly have any advances due to modern times. This Debased Era must always be in awe of our Glorious Past. Keeps the kids in line. Keeps people from thinking they know anything.
msravi 11y ago
Sort of surprised that the Viterbi Algorithm (1967) doesn't make the list. The simplicity and efficiency of the algorithm for finding a maximum likelihood sequence is astounding.
nickpsecurity 11y ago
I would've thrown a LISP or Scheme interpreter in there given (a) what McCarthy accomplished by inventing it and (b) how much has been done with it. It was to non-imperative programming what Fortran was to imperative programming.
- GFK_of_xmaspast 11y ago
  I realize lisp is popular here on hn, but it's absurd to compare it to fortran in terms of influence on the field of numerical computation.
  - nickpsecurity 11y ago
    I didnt say anything about LISP's effect on numerical computation. I'm saying it and its decendents had a similar effect on symbolic computation and functional programming. It axiomitized computation, created extremely flexible programming system, dominated in AI, and continued widespread in Comp Sci via scheme. In terms of its prior uptake & results, I think it compares favorably to Fortran. It's even making a comeback via Clojure while Fortran is still legacy stuff.
  - cbd1984 11y ago
    Perhaps not Lisp in specific, but the idea of symbolic computation (that is, computers are more than Big Adding Machines) is important and should be on there.
    - nickpsecurity 11y ago
      That's what I'm getting at with LISP the exemplar and most successful implementation of the concept. That plus functional techniques that followed are huge innovations. Their advantages keep showing up over and over throughout decades in enhancement of them and in other works.
ssalazar 11y ago
Thats a good list. I'd also include linear predictive coding, the foundation of basically all digital telecommunications.
mamcx 11y ago
I found this remark: https://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2_i1/fortran.pdf https://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2... The Fortran I compiler would expand each operator with a sequence of parentheses. In a simplified form of the algorithm, it would • replace + and – with ))+(( and ))-((, respectively; • replace * and / with )*( and )/(, respectively; • add (( at the beginning of each expression and after each left parenthesis in the original expression; and • add )) at the end of the expression and before each right parenthesis in the original expression. This is the first time I hear about this, this technique will work with today compilers vs. most others like precedence climb?
DanBC 11y ago
Mildly surprised not to see public key crypto in there. Maybe I'm misunderstanding what makes a best algorithm? http://www.cesg.gov.uk/publications/Documents/nonsecret_encryption.pdf http://www.cesg.gov.uk/publications/Documents/nonsecret_encr... He did this in his head, and had to keep it there overnight until he got to work the next morning. http://www.zdnet.com/article/gchq-pioneers-on-birth-of-public-key-crypto/ http://www.zdnet.com/article/gchq-pioneers-on-birth-of-publi... This article also shows GCHQ's failure of imagination: > Ralph Benjamin: It was revolutionary in the intellectual schema, and eventually in its operational impact. We didn't then foresee the full eventual operational impact. My conclusion was that the process would be so cumbersome, especially considering the computing ability of the time, it might have been useful for the occasional short message, but its main use would be a short message to transmit a key for conventional cryptography.

62 points by tizzdogg 11y ago

An evergreen. See also: https://news.ycombinator.com/item?id=4468057 https://news.ycombinator.com/item?id=4468057 (with wildly varying comment quality)

harakiri 11y ago
Thanks for the link, I laughing my ass off the comments...

deleted 11y ago

[deleted]

tomkat0789 11y ago

For the full text: http://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2_i1/index.html http://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2_... Ask yourself, which of the 10 have you used today?

GFK_of_xmaspast 11y ago
I've been in meetings all day today, but I think I got at least four explicitly yesterday (quicksort, qr, matrix decomposition, simplex), not to mention all the implicit ones we all use everyday.

tizzdogg 11y ago

I submitted this, mostly because I was wondering what more recent algorithms would be added to the list if you were to do a new "best algorithms up until 2015". The most recent algorithm here is from 1987. What new things from the past 30 years might qualify for future best-of lists, assuming they have enough time to gain widespread adoption?

asgard1024 11y ago
Wikipedia to the rescue: https://en.wikipedia.org/wiki/Timeline_of_algorithms https://en.wikipedia.org/wiki/Timeline_of_algorithms (Interestingly, some of the algorithms mentioned in the article are missing from the list. It also doesn't list many algorithms from 19th century.) And indeed it seems, there are not so many recently, though I think AKS Primality Test would qualify as a great algorithm of 21st century.
GFK_of_xmaspast 11y ago
Pagerank is the first thing that comes to mind (and there was a big survey article about it in the latest SIAM Review https://www.siam.org/journals/sirev.php https://www.siam.org/journals/sirev.php)
- pathsjs 11y ago
  Hardly 21st century. In its essence it was known to Markov, who died in 1922. For comparison, the idea of TUring machines came in 1936
  - cbd1984 11y ago
    And if you take that idea back, it goes directly to the Jacquard loom, because Knuth Knows we can't possibly have any advances due to modern times. This Debased Era must always be in awe of our Glorious Past. Keeps the kids in line. Keeps people from thinking they know anything.

msravi 11y ago

Sort of surprised that the Viterbi Algorithm (1967) doesn't make the list. The simplicity and efficiency of the algorithm for finding a maximum likelihood sequence is astounding.

nickpsecurity 11y ago

I would've thrown a LISP or Scheme interpreter in there given (a) what McCarthy accomplished by inventing it and (b) how much has been done with it. It was to non-imperative programming what Fortran was to imperative programming.

GFK_of_xmaspast 11y ago
I realize lisp is popular here on hn, but it's absurd to compare it to fortran in terms of influence on the field of numerical computation.
- nickpsecurity 11y ago
  I didnt say anything about LISP's effect on numerical computation. I'm saying it and its decendents had a similar effect on symbolic computation and functional programming. It axiomitized computation, created extremely flexible programming system, dominated in AI, and continued widespread in Comp Sci via scheme. In terms of its prior uptake & results, I think it compares favorably to Fortran. It's even making a comeback via Clojure while Fortran is still legacy stuff.
- cbd1984 11y ago
  Perhaps not Lisp in specific, but the idea of symbolic computation (that is, computers are more than Big Adding Machines) is important and should be on there.
  - nickpsecurity 11y ago
    That's what I'm getting at with LISP the exemplar and most successful implementation of the concept. That plus functional techniques that followed are huge innovations. Their advantages keep showing up over and over throughout decades in enhancement of them and in other works.

ssalazar 11y ago

Thats a good list. I'd also include linear predictive coding, the foundation of basically all digital telecommunications.

mamcx 11y ago

I found this remark: https://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2_i1/fortran.pdf https://www.cs.fsu.edu/~lacher/courses/COT4401/notes/cise_v2... The Fortran I compiler would expand each operator with a sequence of parentheses. In a simplified form of the algorithm, it would • replace + and – with ))+(( and ))-((, respectively; • replace * and / with )*( and )/(, respectively; • add (( at the beginning of each expression and after each left parenthesis in the original expression; and • add )) at the end of the expression and before each right parenthesis in the original expression. This is the first time I hear about this, this technique will work with today compilers vs. most others like precedence climb?

DanBC 11y ago

Mildly surprised not to see public key crypto in there. Maybe I'm misunderstanding what makes a best algorithm? http://www.cesg.gov.uk/publications/Documents/nonsecret_encryption.pdf http://www.cesg.gov.uk/publications/Documents/nonsecret_encr... He did this in his head, and had to keep it there overnight until he got to work the next morning. http://www.zdnet.com/article/gchq-pioneers-on-birth-of-public-key-crypto/ http://www.zdnet.com/article/gchq-pioneers-on-birth-of-publi... This article also shows GCHQ's failure of imagination: > Ralph Benjamin: It was revolutionary in the intellectual schema, and eventually in its operational impact. We didn't then foresee the full eventual operational impact. My conclusion was that the process would be so cumbersome, especially considering the computing ability of the time, it might have been useful for the occasional short message, but its main use would be a short message to transmit a key for conventional cryptography.