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.
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?
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)
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.
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.
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.
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.
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.
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.
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.
19 comments
[ 3.2 ms ] story [ 46.4 ms ] threadAsk yourself, which of the 10 have you used today?
(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.
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?
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-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.