5 ms·
Send Me Your Nominations for Algorithms That Changed The World
- gne1963 18y agoThe point in polygon problem for arbitrary polygons I believe was first solved by Robert Sedgewick and published in his awesome algorithms book... it is discussed here... http://bit.ly/i1u1 http://bit.ly/i1u1 In most computer applications today we assume we can easily tell whether or not a point is within (or without)... But I think Robert published the first algorithm on how...
- russell 18y agoYea, Sedgewick. His books taught me algorithms. they are to the point, readable, and have working code.
- gne1963 18y agoYes me too. I still believe that the godfather is Knuth: http://en.wikipedia.org/wiki/Donald_Knuth http://en.wikipedia.org/wiki/Donald_Knuth think But as you highlight Sedgewick to me was more readable and applicable to the code I was writing in the early 90s.
- Dilpil 18y agoI don't know if I would call his algorithms readable, but they sure are to the point.
- russell 18y agoQuicksort: http://en.wikipedia.org/wiki/Quicksort http://en.wikipedia.org/wiki/Quicksort The wikipedia article has a great visualization of the algorithm in action.
- notaddicted 18y agoThis appeared here a few months ago; http://www.eecs.berkeley.edu/~karp/greatalgo/ http://www.eecs.berkeley.edu/~karp/greatalgo/ I think I'll nominate FFT.
- greendestiny 18y agoI was going to separately nominate back-projection for producing CAT scans, but its really another vote for the importance of FFTs.
- shrughes 18y agoI would nominate RSA.
- brl 18y agoI think it would be hard to argue that any other single modern algorithm had as much effect on the world as RSA.
- corentin 18y agoMP3?
- russell 18y agoDiscrete cosine transform and its variants gave us jpeg and mp3
- brl 18y agoOh, you're absolutely right of course. I completely overlooked that. In that case, I think that the top two prizes should go to one Fourier transform related algorithm and one algorithm from public-key cryptography.
- dfranke 18y agoI'd consider DH slightly more important.
- fgimenez 18y agoOn a related note, the Rabin-Miller primality test is needed just to find the primes for RSA to work.
- prakash 18y agoConsistent Hashing: http://en.wikipedia.org/wiki/Consistent_hashing http://en.wikipedia.org/wiki/Consistent_hashing
- gne1963 18y agorussell... I would perhaps nominate bubble sort above quicksort...for us old timers, it was easy to understand, code, and install in our programs where ever we need a sort... bubble sort I would argue first brought sorting to our discipline.
- jff 18y agoI was going to tongue-in-cheek nominate bubble sort, but you got to it first!
- russell 18y agoEarly in my career I implemented a cross reference function using bubble sort and was ridiculed by a Real Computer Scientist. I opted for quick sort, because I wasnt going to expose myself to that here. :-)
- gne1963 18y agoBut the more I think about it, I'd have to give Dijkstra's shortest path routing algorithm my highest marks... http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm it probably was used to route this message to all you who are reading this... and also used in the routing of the board design on which your screen is attached.,,and is the basis of many other technology and efficient scheduling applications in common use today...
- brl 18y agoEuclid's Algorithm
- 10ren 18y agoPageRank, in least in terms of transfer of wealth (only one measure, but at least it is a measure of impact on the world).
- greendestiny 18y agoIs it a good candidate as an algorithm though? The novel part of pagerank is representing hyperlinks as a connectivity matrix and using the eigenvalues as search ranking. Finding the eigenvalues themselves was not new, and the rest doesn't seem as important in an algorithmic sense.
- 10ren 18y agoI don't want you to be right, but... I think you are right. PageRank is an application of an algorithm; seeing a problem in such a way that it can be solved. I therefore instead nominate the algorithm which Pagerank applies.
- 10ren 18y agoBasic algorithms for arithmetic, when first originated thousands of years ago, have probably had a far more profound effect on the world than any recent computer-based algorithm. Particularly in accounting and engineering, they would have contributed to the ability to have economies that could support large civilizations. The earliest records found of ancient languages are sometimes accounting records. Interpreting "algorithms in computing" more widely than the questioner meant of course. :-)
- russell 18y agoAlgebra itself started out as a bunch of recipes for doing computations back in Babylonian times, "fathered" by Diophantus, and Al-Khwarizmi who named and codified Algebra.
- dhimes 18y agoI thought it was Al Jabar (or Al Jabbar) from whence we get the name.
- ewiethoff 18y agoName of author: Abu Ja'far Muhammad ibn Musa al-Khwarizmi. Name of work: al-Kitab al-mukhtasar fi hisab al-jabr wa'l-muqabala ("A Handbook of Calculation by Completion and Reduction"). 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."
- 10ren 18y ago> please send me your nominations, pointing to ... any evidence for its impact. I think that's the hardest part of the question.
- DaniFong 18y agoThe Finite Element Method. 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.
- cgranade 18y agoI have to second simulated annealing if only because it gets too ignored normally. It's a wonderful technique for attacking the optimization of intractable problems, and one that belongs in any good mental toolkit for optimization.
- michael_dorfman 18y agoI'm a little suprised nobody has mentioned the Simplex algorithm yet. I don't think it's importance in the history of optimization problems could be overstated. Also: does the Monte Carlo method count as an algorithm?
- schtog 18y agoMonte Carlo methods is a family of algorithms no? 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)?
- shrughes 18y agoThey are the kind of obvious thing that many people would invent for themselves, yes. But the question was about algorithms that changed the world, not about non-obvious algorithms. 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.
- hs 18y agobayesian spam filter
- deleted 18y ago[deleted]
- greendestiny 18y agoA few important ones: 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.
- cgranade 18y agoThe Deutsch-Jozsa Algorithm, while not immediately "practical" in the sense that it solved some real-world problem that had been vexing computer scientists, was instrumental in showing conclusively that quantum computers could be asymptotically faster than classical computers for some problems. This then led the way for more applied quantum algorithms such as Shor's Algorithm (itself a special case of QFT and period-finding algorithms). So I'd like to nominate DJA for an algorithm that changed the world.
- webmaven 18y agoI'm going to go for Long Division. Yes, I'm serious.
- slackerIII 18y agoI'd go with something like Reed-Solomon error correction. It makes CDs and DVDs work. Programmers have to be insulated from the flawed physical world and error correction codes do that.
- mhb 18y agoNewton's method, Euler's method