Slashdot Mirror
Top Ten Algorithms of the Century
brian writes "'Great algorithms are the poetry of
computation,' says Francis Sullivan of the Institute for Defense Analyses'
Center for Computing Sciences in Bowie, Maryland. He and Jack Dongarra of the
University of Tennessee and Oak Ridge National Laboratory have put together a
sampling that might have made Robert Frost beam with pride--had the poet been a
computer jock. Their list of 10 algorithms having 'the greatest influence
on the development and practice of science and engineering in the 20th
century' appears in the January/February issue of Computing in Science
& Engineering. If you use a computer, some of these algorithms are no doubt
crunching your data as you read this."
the significance of the fortran compiler is not necessarily because of any particular optimizing techniques that the compiler used. Rather the invention of the optimizing fortran compiler is significant because it was the first time that a compiler was written that could be as efficient or more efficient than a reasonably experience programmer doing his own hand rolled assembly. The compiler was written specifically with the goal of being efficient at numerical operations while still using normal mathematical notation (ie. w = x + y + z; as opposed to add w, x, y; add w, w, z; ) this allowed programmers to be much more efficient without sacrificing execution speed. this was a vastly innovative concept as the time, as the reigning concept at the time was that no good programmer would use a compiled language, it being too much slower than writing the program in straight assembler.
it was also instrumental in the vast popularity of the (IBM?) computer it was originally developed for and sold with.
disclaimer: this is all stuff that i remember from my programming languages class last year. it may not be completely correct, as i don't really know anything about fortran other than what i learned in that class...
If I don't put anything here, will anyone recognize me anymore?
Here's my commentary on the some of the algorithms selected. I've included brief descriptions/references to further information where useful.
...
The Metropolis Algorithm for Monte Carlo: Based on the thermodynamic equivalent of crystals forming in cooling solids. As opposed to the naive optimization algorithm, the Metropolis algorithm sometimes allows a step to be taken even when it decreases the objective evaluation function with a probablity equal to the value of an exponentially decaying "entropy" function. _Numerical Recipes_ has a nice description, although their example is quite abysmal. The GNU Scientific Library (sourceware.cygnus.com/gsl) has an implementation of the algorithm, referred to as simulated annealing.
The Fortran Optimizing Compiler: compiler techniques in general have improved enormously since the 1950s...this selection doesn't really make much sense to me, as this field has been more about continous and gradual improvement, whether than the developement of some breakthrough optimization techniques. If anything, the pioneering work of Zhang and Roberts establishing the computation infeasibilty of an "universal optimizer" is a much more interesting result.
QR Algorithm for Computing Eigenvalues: Elegant method for determining the values for which A*x_i=\lambda\_i*x_i for a square matrix A. the eigenvalues and corresponding eigenvectors (the vectors belonging the the nullspace of (A-\lambda\_i*I)) are in a certain sense the natural frequencies of a matrix. Determining the eigenvalues without solving the characteristic polynomial (as with the QR method) is critical for avoiding numerical analysis problems.
Some notable algorithms which seem to be missing:
-Sieving techniques for the decomposition of large composites into prime factors
-RSA/other asymmetric key exchange algorithms
-Huffman codes, LZ sliding-window compression techniques, arithmetic encoding
-MDS matrices, error correction codes, cyclic redundancy checks
-The linear feedback shift register
-Predictor/corrector methods, adaptive numerical intergration and approximation of ODEs and PDEs
-Lenstra-Lenstra-Lovasz lattice basis reduction algorithm
-Berlekamp's Q-matrix algorithm for the factorization of polynomials
Dictionary of Algorithms, Data Structures, and Problems is a pretty good "dictionary" of algorithms. Another good place, if you know the name of the algorithm, is of course Google...
The following algorithm, though peculiarly simple, was single-handedly responsible for DOUBLING sales of shampoo:
1. Lather
2. Rinse
3. Repeat
I seem to recall that Nolan Bushnell did a similar thing in the instructions for Pong. Does anyone recall what those were?
I really don't care for their choices at all. A lot of them are more like general approaches than algorthms, and I'm not at all sure they are the most influential. I think they are supposed to be "the cleverest of the common fancy methods"
Simple algorithms for common problems are much more widely used, and have far more impact and influence, but try telling *them* that!
I hope these links help. (Warning: many are technical) If anyone has personal favorites that are less dry than many of these, please post!.
10. 1987: Fast Multipole Method. A breakthrough in dealing with the complexity of n-body calculations, applied in problems ranging from celestial mechanics to protein folding. [Overview] [A math/visual approach]
9. 1977: Integer Relation Detection. A fast method for spotting simple equations satisfied by collections of seemingly unrelated numbers. [Nice article with links]
8. 1965: Fast Fourier Transform. Perhaps the most ubiquitous algorithm in use today, it breaks down waveforms (like sound) into periodic components. Everyone knows this one (or should) [Part II of my personal favorite FFT and wavelet tutorial]
7. 1962: Quicksort Algorithms for Sorting. For the efficient handling of large databases. [Definition][Basic Method][Mathworld][More technical explanation][A lecture with animations and simulations]
6. 1959: QR Algorithm for Computing Eigenvalues. Another crucial matrix operation made swift and practical. [Math] [Algorithm
5. 1957: The Fortran Optimizing Compiler. Turns high-level code into efficient computer-readable code. (pretty much self-explanatory) [History and lots of info]
4. 1951: The Decompositional Approach to Matrix Computations. A suite of techniques for numerical linear algebra. [matrix decomposition theorem] [Strategies]
3. 1950: Krylov Subspace Iteration Method. A technique for rapidly solving the linear equations that abound in scientific computation. [History] [various Krylov subspace iterative methods]
2. 1947: Simplex Method for Linear Programming. An elegant solution to a common problem in planning and decision-making. [English} [Explanation with Java simulator] [An interactive teaching tool
1. 1946: The Metropolis Algorithm for Monte Carlo. Through the use of random processes, this algorithm offers an efficient way to stumble toward answers to problems that are too complicated to solve exactly. [English] [Code and Math] [Math explained]
If you can go to bed, knowing you did a valuable thing today, you're very lucky. If you can't... it's not bedtime
And the Fortran optimization one is... well, that's not really an "algorithm", now is it? It's a whole bunch of algorithms, and presumably each Fortran compiler does different things to optimize. Again, the numerical/scientific bias is obvious though... who else would use Fortran today?
Some algorithms (and data structures) I'd nominate are (note that I'm purposely avoiding numerical algorithms here, because the article aleady lists more than enough good ones):
I don't see random sort anywhere in the list?
Oh, for those who don't know: It's the winning entry in a competition held at IBM. The competition was about the slowest search algorithm.
--The knowledge that you are an idiot, is what distinguishes you from one.
--The knowledge that you are an idiot, is what distinguishes you from one.