Send Me Your Nominations for Algorithms That Changed The World
parlezuml.com
parlezuml.com
I think I'll nominate FFT.
Also: does the Monte Carlo method count as an algorithm?
I still haven't groked exactly what is so special about them. Incredibly useful, sure, but aren't they just simulations? Ie, isn't it something anyone would have come up with(sorry if I'm just ignorant here)?
I would argue that in the case of Monte Carlo methods, computers are what deserve credit (for making obvious methods like Monte Carlo affordable) rather than the methods themselves.
The Fast Fourier Transform.
Max-Flow-Min-Cut. (Ford-Fulkerson)
Simulated annealing.
Carrier sense multiple access with collision detection (the protocol used by ethernet)
And if it counts, dynamic programming, in its many variants. If it doesn't, Dijkstra's algorithm.
Interpreting "algorithms in computing" more widely than the questioner meant of course. :-)
John Derbyshire examines al-Khwarizmi's work in chapter 3 of Unknown Quantity: A Real and Imaginary History of Algebra [ISBN 978-0-452-28853-9], which I just finished reading a few days ago.
The first part of al-Khwarizmi's book concerns finding the roots of first- and second-order polynomials of one unknown. He classified the polynomials into 6 fundamental types, with all positive coefficients. Keep in mind, that negative numbers did not exist at the time, though subtraction did. He showed how to manipulate polynomials into a suitable one of the 6 types by adding a term (al-jabr, completing) or subtracting a term (al-muqabala, reducing).
Says Derbyshire, "al-Khwarizmi has no literal symbolism--no way to lay out equations in letters and numbers, no sign for the unknown quantity and its powers." The problems, the fundamental types, the procedures are all presented in words.
Interestingly, Diophantus 600 years earlier did addition and subtraction of polynomial terms using "a rich literal symbolism to aid the manipulations."
I therefore instead nominate the algorithm which Pagerank applies.
Lempel-Ziv compression: Though it's hard to point to things that would have been impossible without it, it's saved so much transfer and storage capacity in its time that the economic impact would be huge.
Apriori association mining: Of fairly limited application, but it's use in market basket data has probably had quite a large impact on our retail sector for one.
I think that's the hardest part of the question.