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."
I'm not surprised that the Fortran compiler is included. Like it or not, Fortran is the grand-daddy of high-level languages for science and numerical apps.
Like it or not, "The Fortran Optimizing Compiler" is not an algorithm. There are numerous Fortran compilers available, and each has its own algorithms (note the 's') for performing optimization. It's like saying "what's the best vehicle of the 20th century" and answering "interstate freeways". Yes, they help transporation, but...
Are any of these algorithms related to things like compression algorithms (MP3, Zip, LZW, etc.), encryption algorithms (DES, RSA, Blowfish, etc.) or search algorithms (like the one Google uses, for instance)?
Not really. They are much more important than that. Essential for putting man on the Moon, solving air flows to optimize the shape of a jet fighter, protein folding calculations, you know, this kind of stuff. These algorithms made it possible to solve large equations back in the 60's (imagine the processing power back then...)
Ducks, runs, hides.
That's an interesting rant about the FFT, but it seems to me that the Fourier Transform was invented by Gauss in the 1800's, while the Fast Fourier Transform is what was invented in the 60's. Given that you use the two interchangably, I don't know how much of your comment to believe.
--
No more e-mail address game - see my user info. Time for revenge.
Win dain a lotica, en vai tu ri silota
Actually, the commerical out and out
:)
suggested using 2 tablets for faster relief.
And showed 2 tablets falling into the water, etc.
Sales did nearly double, however. True story!
-bugg
HAH! Now that's progress! It's funny, it's a self-extracting archive, but it has no compression. I did a rar of the .ocx it extracted, and it went to 45K. Even as a self-extracting .exe it was only 63k
---
DO NOT DISTURB THE SE
Although not yet fully realized, Shor's algormithm for factorization blows the lid off encryption, and is an excellent example of quantum parallelism, and inteference.
To me, it's a glaring ommission to not have any string matching algorithms. In other words, where are the regular expressions?!? One of the most impressive algorithms I have ever seen is related to regular expressions. There are two types of regular expression algorithms. On follows directly from the regular expression, and the complexety of the regular expression directly correlates with the running time of the algorithm. With the second type of algorithm, the running time of the algorithm is proportional to the length of the string, and the length of the regular expression. In other words, you can always predict how long it will take to run. No matter how complicated. The first kind is NFA, or non-deterministic finite automata. The next kind is DFA, ie. deterministic finita-automata. Anyway, it is really easy to write a NFA, but writing a DFA is super complicated, it involves this awesome thing called the E-closure. The algorithm to product a DFA via the E-closure is the impressive algorithm I think should have been on the list.
I heard about this algorithm in the book: Compilers: Priciples, Techniques and Tools (The Dragon Book, Second Edition) It doesn't have a name for the algorithm though. Anyone who is interested in regular expressions, parsers, lexers, compilers, interpreters and validators should deffinatly check out this book.
Yes, I'm still a junky. Are you still a bitch?
The travelling salesman problem can be solved using simulated annealing which is the Metropolis algorithm for Monte Carlo.
What's with all the numerical algorithms? Isn't this supposed to be about computing rather than engineering? The algorithm/data structure that comes to mind for me is the B-Tree. Database systems would be a lot less useable without it. "Your fingers are soaking in it now."
I don't use the two interchangeably. Maybe I worded the post unclearly.
Gauss invented the Fourier transform *and* the FFT before Fourier invented the Fourier transform. Fourier never figured out the FFT, as one poster has pointed out. If that was unclear from my original text, then sorry about that.
Gauss basically came up with the FFT out of necessity... he was processing a ton of planetary observation data by hand.
Anyway, you say you "don't know how much of my comment to believe", but that's why I included references, eh. The FFT has been invented many times in the 20th century, all of them rediscoveries of what Gauss did. Check any signal processing book that has historical notes.
-N.
The magazine printed this big poster of these top-ten algorithms, and a numerical computation person across the hall from us has had it pinned to her door for a month now. We've had so much fun mocking it these last few weeks.
So here's a short list of algorithms that, I guarantee, are far more important than Fast Multipole. :-)
- A*. It's just absurd that A*'s not on their list. A* is the basic deterministic search algorithm behind game playing, planning, scheduling, knowledge representation, and a large chunk of symbolic AI. Why should it then be on a top-ten list for science and engineering, you ask? Because A* is the smarts behind the symbolic integration, root finding, closed-form symbolic sum determination, algebraic simplification, and other automated mathematics procedures found in MACSYMA, Mathematica, MathCad, Maple, and now your handy-dandy HP calculator. Mathematicians and science theorists for the last fifteen years have relied heavily on A* to help them find solutions and prove difficult theorems underlying all of science.
- B+ Tree Manipulation. Revolutionized operating systems and databases.
- Dynamic Programming. And they call themselves a scientific computing group. Dynamic programming has done more for engineering than practically the entire list of theirs combined.
- RSA and DES. You're gonna tell me that Krylov is more important than these?
- Z-Buffering. Which made graphics economical.
- Knuth-Morris-Pratt String Matching. The guts behind information retrieval systems.
- Graph Algorithms (MST, Shortest Path, etc). They didn't list a single one. Yet these algorithms are vital to networking, databases, an astounding number of computer science fields, and much of the infrastructure of the internet.
The published list is just idiotic.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?
The truly optimal encoding isn't Huffman coding --
although it's inspirational. Arithmetic coding
has beautiful properties that allow for partial
bit codes.
Muh!
How To Write A Letter
1) Get Pen
2) Get Paper
3) Apply pen to paper
4) Move pen according to the following movement pattern:
5) (etc)
The above is certainly an algorithm. But try porting it to X-Windows. Just because an algorithm relies on certain other things being present (pen and paper in this case, specific computer architecture in the other) doesn't make it less of an algorithm.
Every who'se complained about the Fortran compiler, stop it: an algorithm takes inputs and produces outputs based on those inputs in a deterministic way. Quicksort is an algorithm, even though it *contains* other algorithms, such as those for iterating through a list and comparing elements. Fortran compiler is an algorithm, even though it contains many smaller algorithms.
This one was widely used back in the 80's:
10 PRINT "RADIO SHACK SUCKS!!!!!"
20 GOTO 10
Over half of those algorithms are patented by UNISYS! I think they are charging $1000 per use of each algorithm (that's per use, not per application!!)
--
"And is the Tao in the DOS for a personal computer?"
python -c "x='python -c %sx=%s; print x%%(chr(34),repr(x),chr(34))%s'; print x%(chr(34),repr(x),chr(34))"
You forgot the most widely used algorithm in the most widely used OS on the planet.... wait();
The most important one is sleep(-1). It's tricky to implement, but when used properly, it turns all other algorithms into O(1). NP-Completeness, my ass!
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
What other algorithms would you folks suggest?
I do a lot of computer graphics work, so the FFT is among my top 10 for that field. Marching cubes, phong shading, environment mapping, bilinear interpolation, BSP & portal PVS are also on top of my list.
What a perfect nerd question: what's your favorite algorithm, baby?!
magic
Here's another. IIRC you can thank the Simplex algorithm for Linear Programs for Kentucky Fried Chicken.
In the old days, chicken was expensive. Then Purina (and probably other feed companies) discovered Linear Programming. The chickens have certain nutrient requirements which must be met by some combination of ingredients in the chicken feed. Various ingredients have different amounts of nutrients at prices determined by the current market. Solving the Linear program finds (one of) the cheapest ways to make chicken feed. The feed companies helped set up poultry farmers in a high volume low margin business. Incidentally, solving a Linear Program also gives the cost of each constraint.
Some of the algorithms I don't recognize, but they all seem to make major (orders of magnitude) differences is what can be computed.
Why does everyone speak about their favourite childhood algorithm as an "omission" from the top ten list? If they added your algorithm, it would be a top eleven list. If there were truly an omission, I would expect to see nine algorithms under the heading "top ten".
"Someone left out error-correcting codes!"
"Someone left out crypto!"
"Someone left out the following list of algorithms you learn in the third year of a CS program!"
"Someone left out LLL!"
Well, whoop-dee-do. If we added all of your "GLARING" omissions, we'd have a top 100 list. The problem here is that there are too many really good, beautiful, poetic algorithms out there, and no objective way to compare them.
Someone pointed out that this list was biased towards numerical computation and someone else defended this, saying that they wanted practical algorithms anyways, which is a bit silly, because different people have different practical needs. Some of us really don't have any use for the Fast Fourier Transform. Some of us think that an O(N^log 7) matrix multiplication algorithm is kinda cute, but don't really give a rat's ass about it.
I suggest that this list does not achieve its goal. Perhaps it publicizes a couple of numerical methods that people might not have heard of (except LLL), but it certainly doesn't live up to the title "Top Ten Algorithms of the Century". I don't think such a list could really exist. If it could, perhaps Donald Knuth wouldn't be spending so much time on that series of books he's so passionate about...
Donny
I'm amazed none of you low-level hardware hacker guys have got this one - of the sorts that have been mentioned (QS, Insertion, Merge, Selection etc) - Bubble is the only one which doesn't need extra memory. All the others need a target buffer, while Bubble works in place.
Or am I wrong? I'm not sure....please feel free to correct.
---- Den ene knappen er powerknapp, den andre er Bender voice knapp "Bite My Shiny Metal Ass"
Yes, there _is_ FFT in MPG. It's Discrete Cosinus Transform (DCT).
I think you mean Hugues Hoppe.
Yes, progressive meshes have a number of applications: compressing the mesh, progressively refining the mesh during download, sampling the mesh at given detail level (to be able to render it efficiently) etc.
And what about the other comp geom algorithms; Delaunay triangulation/Voronoi diagram, convex hulls, Minkowski sum, visibility graphs...
-- v --
Firstly, the heap sort. When I was learning about computers I studied sorting methods. The idea that inputting your random data into a linked list allowed you to just read it out in the right order was a revelation.
The next important algorithm that I came across but unfortunately can't describe properly here is used to produce molecular shapes from X-ray diffraction patterns. This helped mankind to understand DNA.
My third most important algorithm is the state engine that drives the TCP/IP stack. This is whats bringing my burblings to you now.
I'm happy with quite a few of the algorithms in the top 10 list - fourier transforms in particular but some of them seem rather esoteric.
-- Don't believe everything you read, hear or think
I was also disappointed not to see a symbolic logic algorithm such as the Resolution Theorem Prover (Robinson, 1965) or Circumscription (McCarthy, 1980). I'd like to have been able to point to something of Jon Barwise' Situation Semantics, but couldn't think of a specific algorithm to highlight.
I'm old enough to remember when discussions on Slashdot were well informed.
What about good old Huffman coding? Seems like all compression algorithms came from that first insight. Even better, it perfectly illustrates the entropy measure of information.
(Reality reasserts itself sooner or later.)
Lots of people are complaining that an optimized Fortran compiler isn't an algorithm.
An algorithm is a deterministic set of procedures for turning a given input into a given output. A good algorithm is one that executes quickly and whose output is as close to some ideal as possible.
An optimized Fortran compiler is a deterministic set of procedures for turning Fortran source code into machine code, and it's a good one because its output executes quickly.
It may not be an algorithm that scientific computational people explicitly write into their code, but it *is* an algorithm that has improved our ability to solve complicated problems as quickly as possible.
[TMB]
btree? there's probably more data stored with that than any other structured approach. -dB
"It if was easy to do, we'd find someone cheaper than you to do it."
seriously, what about JeffSort? it's used to sort numbers in a fixed range (like most computer science numbers are) here's the algo:
:= 0;
:= 1 to JeffCount[i] do := i;
:)
procedure JeffSort (var a: array of integer; lo, hi,
rangelo, rangehi: integer);
var
JeffCount: array [rangelo..rangehi] of integer;
i, j: integer;
begin
for i:=rangelo to rangehi do
JeffCount[i]
for i:=lo to hi do
inc (JeffCount[a[i]]);
for i:=rangelo to rangehi do
if (JeffCount[i] > 0) then
for j
begin
a[lo]
inc (lo);
end;
end;
this is really O(R) for R>>n where R is the range of the numbers and since the range is constant it's O(1). However for n>>R it's O(n). I've ran this algo for large datasets and it easily outperforms quicksort and other fast sorting algos. However it does have that one restriction that it can only be used for a countably infinate set of numbers so it can't be used to sort floating point numbers.
disclaimer: I really know this is only a slight modification of shell sort so don't flame me please
Things you think are in the Constitution, but are not.
Vorbis uses every listed Algorithm in the top ten, from Monte Carlo for codebook train to Fast Multipole Method for LPC fitting.
Ha! Lets see mp3 beat that!
For those who are unaware, Vorbis is a nifte patent free alternitave to MP3, it offers native VBR and better quality.
Have we forgotten about the algorithm which makes the minimzation/optimization of circuits possible? If it weren't for Quine-McKluskey, we'd all still be running at 286 speed! :)
"and say (as an example) algorithms for solving the Travelling Salesman Problem?"
Well, not to be anal, but there are no "feasible" algorithms in existence for the TSP. I presume you mean approximation algorithms, or heuristics, of which there are many to solve this particular problem in a reasonble amount of time with some degree of error.
By definition, an algorithm terminates.
hmmm. bioinformatics/computational biology perhaps :)
How could they have left out ROT13?
Slashdot monitor for your Mozilla sidebar or Active Desktop.
"But I'm guessing it's not on the list because it's not an algorithm. It's a lack of an algorithm. It's simple enough to multiply two large primes together. The reason public-key crypto works is that there is no known algorithm to turn the product back into its constituent primes in reasonable time. "
Not quite. Public-key encryption is certainly an algorithm. The lack of an algorithm is what makes it _useful_. And isn't the real significance of algorithms found in how useful they are, in either a literal or more theoretical sense?
I'm amazed that RSA wasn't on this list. It's an incredibly seful security tool; it makes secure e-commerce plausible and has produced no small amount of headaches for government officials.
But, not that interesting. Its just a list, no details. I suppose they figure we already know this stuff is, I sure don't (other then the FFT, quicksort, and optimizing compiler). I would have liked to have seen a more indepth description of what each algorithem did and what its impact had actualy been...
ReadThe ReflectionEngine, a cyberpunk style n
Double the sales? If people only followed the directions they should repeat until they run out of shampoo.It's an infinate loop!
Meanwhile, we can take over the world?
I don't see the bubble sort anywhere? :-)
"Elmo knows where you live!" - The Simpsons
cut-n-pasted:
---
---
You are not what you own -- Fugazi, "Merchandise"
And finally, DES *has* to at least be an "honorable mention". DES, despite being dated on the day it was created with its 56-bit keys, was the first publically-implemented Feistel-class symmetric cipher, and brought S-boxes and other encryption techniques now commonplace out of the world of spooks and into common parlance. All ciphers since DES have been either inspired by DES or have been a reaction to what people view as flaws in DES. If that isn't "influential", I don't know what is!
-E
Send mail here if you want to reach me.
wait();
I haven't followed the link, but I hope the winner was:
1. Turn on TV
2. Watch Until bored
3. Change channel
4. Go back to 2
(8-DCS)
Quick sort deserves to be number 1.
Quick sort is the only one on the list I know.
But I am really glat to see it.
-----
If my facts are wrong then tell me. I don't mind.
I can see how all of these got in here, but I would expect that the greatest algorithms of all time would last for a bit longer than that. Its not as if the fortran compiler reached its pinnacle of evolution in 1957 and has remained relatively unchanged since.
Other entries like the matrix computation methods, fast fourier transform, etc are still in wide use today because we haven't found (or there aren't) any better algorithms we can use.
Maybe its just me...
--
Eric is chisled like a Greek Godess
marotti.com
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...
Only one of these was developed in my lifetime.
On an unrelated note - I only recognize three of the ones on their list. I would have liked to see a description of what each one does, what impact it had, and perhaps how it works. That would make for interesting reading.
--
grappler
Vidi, Vici, Veni
On a side note, who decided what the 10 top algo's should be? Where's the skiplist?
Make sure everyone's vote counts: Verified Voting
FFTs have been used for everything. Someone once said -- find a way to turn an O(n^2) alg to O(n lg n) time, and they will beat a path to your door finding uses for it.
Also, it we should mention (alhough I've been skimming previous comments, so maybe redundant) that Gauss used FFT to compute fourier series -- he didn't make a big deal out of it, as he no doubt conscidered it a straight forward application of base principles. Smart man that.
It's too bad that they didn't poll slashdot. I can think of a few algorithms that have a great impact on humanity, and probably more in use today:
.GIF files use for compression.
1. How about the LZW algorithm that
2. PK ZIP - arguably the most common file compression format in use today. Rest in peace, Phil Zimmerman.
3. BSP trees used in DOOM, and I believe also in Quake.
4. B-Trees and their derivatives, used in searching and sorting in relational databases.
Maybe slashdot should conduct their own poll on this one, since results from us common developers might be startlingly different.
hmm...
Don't forget Diffie-Hellman(sp?) key Exchange, DES, etc.
These crypto algorithms pretty much made secure e-commerce of the 90's possible.
Where's the Kalman filter ? We couldn't have got to the Moon without it.
Equally, we'd never have ICBMs and an arms race without it, but when did morality ever stop geeks inventing stuff ?
They forgot things like hash tables, binary trees, and so on. Of these, they only mention quicksort.
As in everyday algorithms used all the time that actually make commonplace software work well.
I'm surprised that data compression hasn't been mentioned, nor public key cryptography.
What about the algorithms used in networking? Surely TCP/IP has a greater impact than some obscure matrix multiplication.
That primary sppedup vanishes on modern processors - these generally do multiplications as fast as additions.
CSS encryption scheme for the smartest implementation of the most secure algorithm in the entire history of CS!
You can't handle the truth.
I looked a bit around in my region and I can get articles either via the local university library for about 10 cent copy fee per xeroxed page or delivered via email as TIFF files from the JASON server for about $1.50 per article. This link will send a test article to your email address. You then need an uudecode utility to turn the attachment into a binary und the result (a selfexploding ARJ for DOS) can be unpacked with the unarj utility that is available for UNIX too.
I believe you should find similiar offers.
The inspiration for the "random sort" that you talk about _must_ be the "bogo-sort" entry in The Jargon File: http://www.tuxedo.org/~es r/jargon/html/entry/bogo-sort.html
As a math major I appreciate the artistry and science of all this but I havn't been paid to do much math programming in the 28 years I've hacked code. If I were asked what the most usefull-neat-cool algorithms I've seen and *used* were I'd have to say 1) The boyer-moore string search algorithm and 2) the (unnamed) adaptive list search algorith where you move up an item you've found in a list by one slot if it's the one you've searched for. There's also a really cool adaptive servo algorithm out there somewhere that let even a lowly Z-80 run rings around 16 bit processors using more conventional algorithms.
Now THOSE were elegant... and usefull.
Need Mercedes parts ?
It's an infinite loop if you read it like a moron. It's not a simple program, it uses the English language (which is not programmatic). People understand that the word "repeat" applies to the first two instructions and not the "repeat" itself. If this were the meaning, it would read "repeat indefinitely". Clearly the fact that people understand what it means (in English) is an indication that the concept of it being a "infinite loop" is simply nonsensical.
Well, if you've once sorted a list of objects according to a certain criterion and they all change a bit maybe then ? For instance, depth sorting polygons in a game might qualify for this.
Yes, but I thought that at a certain point, it would be faster to do a quick bubble sort on 2 to 3 items rather than running throught the entire qsort algorithm over and over until the partitions were one a peice. Oh well, I guess I didnt imply that in the original message.
- - - - - - - - -
I think you miss the point... the list was for the most influential algorithms in science and engineering. My guess is that they mean classical science and engineering rather than computer science/engineering. IMO, there should always be a distinction between these fields. Public-key cryprography serves no purpose in the classical sciences (other than protecting your sensitive data on radioactive isotopes, etc. :)
Eric
You are, of course, neglecting the inevitable arrival of radio shack employees who will scratch their heads and then turn the computer off as you snicker and peer in the windows.
An excellent list of suggestions! Of course, there's not room in the top 10 for all of them, but I think that more than a couple are a match for the ones in their list...
Wherever there's a will, there's a motorway.
This is the transpose heuristic for linked lists. Some others are move-to-front and frequency-count, which are pretty self-explanatory. Another nice adaptive data structure is a splay tree by Sleator and Tarjan. It's a binary tree that changes shape on operations, so it's basically self-balancing. There are also some nice adaptive heaps, but really there are too many different data structures to keep up with ;)
Well, hmm, how else are we supposed to read this?
___
A requirement of creativity is that it contributes
to change. Creativity keeps the creator alive.
___
I'm an exhibit on the mounted animal nature trail.
compilers perform a series of iterative steps and it completes. an algorithm.
-- You see, there would be these conclusions that you could jump to
1946: The Metropolis Algorithm for Monte Carlo is historically important and I can appreciate such great algorithms as The Decompositional Approach to Matrix Computations, QR Algorithm for Computing Eigenvalues and Quicksort Algorithms for Sorting.
However I don't think 10 algorithms is enough to describe the greatest achievements of computer science. Binary search, Binary Tree Manipulations, Data Structure algorithms such as Hashing, BTrees, Heap Manipulations, Queues, Stacks, various forms of Linked Lists. Searching algorithms, heuristic bound searching algorithms such as Chess game algorithms, Dijkstra, Travelling Salesman (unsolved). Recursive algorithms. etc...
The list is by far not exhausted but the only 10 algorithms listed are defenetely not the top priority algorithms (except quick sort)
You can't handle the truth.
If I recall, Strassen's algorithm gets you down to something like O(n^2.8something), and then some related variants get you down to O(n^2.7). Not sure about other decompositions. It's been awhile since my algorithms class, and since I don't use these things every day, I tend to forget them quickly. :)
Wherever there's a will, there's a motorway.
I'd bet that most of these 10 algortihms were first introduced before 1970.
You're right. I know this beacuse they listed the actual date right there on the page...
ReadThe ReflectionEngine, a cyberpunk style n
As for that FORTRAN thing, I guess that was mentioned because it was the *first* optimising compiler, ever, and it served as an example to every compiler that was made ever since. Talk about influence now...
Oh and of course do I love Binary Space Partioning. Thats the most important algorithm ever. (so what, DOOM is old, but its still fun and at least it has an atmosphere...)
There's a great paper about pessimal algorihtms. These two guys from DEC look at slowsort and reluctant search. The idea is that they provably terminate, but take the longest time they can to do so, without ever wasting a computation.
I don't know much about the Fortran algorithm, but since Fortran was the first compiled language, I imagine the ideas about compilation and optimization were pretty revolutionary at the time. We may have better ways of doing now-a-days, but it got the whole ball of wax rolling.
Dana
Was the number field sieve developed in the 20th century? If I recall correctly it is by far the fastest integer-factoring algorithm that has been developed. Important for all kinds of brute-force applications, notably that "crack the encryption" distributed-computing program on your computer. Granted the viability of PGP style encryption relies on any factoring method being slow, but the number field sieve is still pretty important.
I believe the Fortran compiler was the first fully functional (non prototypical) optimizing compiler. It's not really the language we're interested in anyway because most compilers look the same once you get past the token recognition stage. It's the fact that the Fortran compiler was the first to implement modern compiler theory that makes it special.
Michael Gentili
- He's just some guy, you know?
Duh!
Did you even read the algorithms first to see if it was worth posting? That is one big huge crap!!!!
duh!
Actually, Emmett is like santa claus. He sees you when you are sleeping, he knows when you're awake, and he knows if you have been qsorting or compiling Fortran on an outdated compiler. HE SEES ALL. Stop trying to weasel out and say you were not doing at least one thing on that list. YOU KNOW YOU WERE! Ve haf vays of making your processor TALK!
And if you weren't, join a distributed project already! You may not be working with a top-10 algorithm, but you will be doing SOMETHING useful with your number cruncher.
Speeding never killed anyone. Stopping did.
It's unfortunate that the genetic algorithm didn't make the grade. Time, I think, will remedy this oversight.
Thanks for answering, but didn't the "get rid of" the DCT for MPEG2 because it was "too slow"? I'm pretty sure it is part of MPEG1 and JPEG, but not so clear on MPEG2.
Not only that, but without the Z-Buffer, 3D graphics in general wouldn't be where it is today.
In advanced discrete mathematics class, we learned about a graph theory algorithm that was unsolved for many years. AT&T wanted it solved, because it was essential for telephone networks. They eventually gave a fat reward to some computer scientist who figured it out. Though the algorithm was fairly simple, we spent the entire semester building up our knowledge base so that we might understand it. It seemed important. Damn I wish I could remember its name.
Some wavelet algorithms resemble the FFT,
i.e. iteratively compute the basis.
Some don't.
1) Use Wintel machine
2) 5-30 minutes "blue screen of death"
3) Reboot machine
It's an infinite loop if you read it like a moron.
Somebody should have stopped at half a cup eh? It's only a joke!
What? It's just a LIST? Where's the beef?
Boyer-Moore, on the other hand, uses a similar idea to KMP, but to much better advantage. A typical search pattern will let you skip large chunks of data (when there is no match) where KMP would have to examine every character.
-y
150 Opening BINARY mode data connection for slashdot.sig (129323052 bytes).
A compiler takes a set of input (source code) and produces an output (machine code) based on an ordered series of steps.
I dunno, sounds a lot like an algorithm to me...
Wherever there's a will, there's a motorway.
Somebody mentioned Error Correction algorithms, which brought to mind one of the few algorithms I've ever heard of that really hasn't been superceded since its debut: The Reed-Solomon Error Correction system.
My memory of it is a bit shaky(I studied it somewhat a few years back when I picked up a copy of Digital Audio Processing), but it essentially specifies an method by which an arbitrary number of bits in any block can be in error and the algorithm itself will A) Detect that error in the bitstream and B) Correct that error, if the number of misread bits is within the specifiable boundries of the algorithm. So you have situations where merely n extra bytes appending to an m byte block will automatically correct for some amount of error *anywhere* within that block.
Also a nice touch is that one can easily specify a specific number of bits which may have identical values--it turns out that CD's cannot write more than eleven 0's in a row--the head loses the ability to follow the "groove". No problem at all for this code.
This is essentially <i>the</i> system by which arbitrary-quality error correction is implemented. I'm not saying that the selection of algorithms was in error--but Reed Solomon does deserve some kind of honorary mention.
Oh well, at least it gets a better treatment than the Discrete Cosine Transform, which (literally) was <i>rejected by the NSF because it was considered too simple.</i> The DCT is at the core of both JPEGs(it compresses into a quantizable domain 8x8 blocks of YUV domain pixels) and MP3's(compresses into a quantizable domain each of 32 frequency subbands into 18 frequency coeffecients).
Yours Truly,
Dan Kaminsky
DoxPara Research
http://www.doxpara.com
Everyone decided they suddenly needed two tablets. Sales doubled.
Paul
They aren't as different as you might think. The language parser remains the same, it's just that the code generation portion of the compiler is different.
Wherever there's a will, there's a motorway.
I was about to ask this very question when I saw this thread and decided to ask this. Are these algorithms discussed in any detail anywhere? The only book I have on the subject is one that is far from including anything interesting and is all in pascal (yuck). Anyway they do look interesting. How about the first one about "stumbling on a solution to a problem"? That sounds interesting? Has anything to do with Newton's method of arriving at the solution to an N degree polynominal with iterative methods?
What is power if not for the furtherance of power. Power is a gift in it's own right and a means unto itself.
BUBBLE SORT!!!!!!
:)
Seriously, it's first sort most of us learn, and it has the cutest name.
One of the profs who teaches an algorithms course at my university always shows his class a program that displays performance graphs as various sorts chew through large data sets. Invariably, most of the students cheer for bubble sort, even though we know it will loose. Favouring the under-dog, I guess
Dana
I don't know about the majority of /.ers but one of the major algorithms which has influenced my life is those which encode/decode MPEG encoded data. If I turn on my TV, which happens to be digital, I will see pictures decoded from an MPEG stream sent over the airwaves.
I want to listen to music? I pick up my Rio or turn on my computer and listen to MP3s of tracks, again encoded using MPEG algorithms.
The whole Napster thing is caused by people using these algorithms to encode music to such an extent that it becomes distributable across the internet. Imagine- only a few minutes to download a track rather than the hours it would take using CD-style encoding! Magic!
Attitudes in the world have changed a lot over the last few years, and all because of the application of a simple algorithm to a form of mass entertainment.
--
Said it couldn't last, said it wouldn't last... This is the last stand against tomorrow's world.
Always a personal favorite of mine.
I normally wouldn't bother to reply, but most people are missing that the list is ordered by date, not some arbitrary "importance" ranking!
Architecture wars, OS wars, language wars...algorithm wars.
b&
All but God can prove this sentence true.
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?
What the hell? How can they possibly leave off the most influential
algorithm in modern times:
Amazon's One-Click shoppint.
Seriously, I guess this list shows the value of unpatented computer
algorithms. Any of these can be reimplemented, and are actually
innovative, while dispensing software patents to such silly ideas as
saving credit card info.
And why would you leave out Diffie-Hellman
asymmetrical key encryption algorithms?
Any hope you have of privacy now or in the
near future is going to be based on this.
Didn't the person who wrote than go on to found Computer Sciences Corporation (CSC)?
Sheesh...now just another glorified IT company.
Treatment, not tyranny. End the drug war and free our American POWs.
See my user info for links.
Any computer program is an algorithm.
In fact, a good definition of 'algorithm' is 'anything that can be run on a computer' (or more precisely, on a universal Turing machine). When Turing designed Turing Machines, his goal was to define computation and algorithms, and his results are largely accepted.
The Rete match algorithm made rule-based systems computationally practical. Discovered by Charles Forgy in 1979 or so, it was probably the most important event in the expert systems boom of the 1980's.
To a Lisp hacker, XML is S-expressions in drag.
Quicksort is elegantly small, great for demonstrating the power of recursive algorithms in a comp sci class, and performs very well in the average case.
However,it has a really bad worst case, which happens to be fairly common: when your data to be sorted is already more or less in order. Then it performs about the same as bubble sort [O(N^2)]. It also uses O(n) levels of recursion in the worst case, which may cause stack overflow in some cases.
For that reason I personally wouldn't put it in a library routine, because some programmer will eventually use it to sort an array of keys, collect a few more key, and resort the array. I'd only use it where I was fairly sure I was collecting keys whose order had considerable entropy.
Quicksort may be influential because of its simplicity (I believe it is even easier to understand than bubble sort) and widely used because it is easy to code, but it is hardly the best all around sorting algorithm.
My personal favorite sorting alogorithm is Shell sort; this is not to say it is the best algorithm in existence, but it is easy to code and performs just a tad slower than Quicksort in the average case. Most importantly the spread between worst case and best case is small. It is also well suited for internal sorting. The only drawback to this algorithm is that it is not stable, that is to say that two keys of equal value will sometimes end up in different relative order to when they started. This is easy to fix, however.
Quicksort works because it gets rid of large amounts of entropy fast. Where entropy is low (e.g. the keys are already ordered), this advantage is neutralized. It is possible to code hybrid algorithms that use Quicksort at the outset to divide the key file into a number of smaller sets, and then use a different algorithm when the key files become relatively small. I've heard that some people combine Quicksort with Linear Insertion sort when the keyfile get to be ten keys or less, because while Linear Insertion Sort is generally slow [O(N^2)], its simplicity makes it faster on very small key files. Perhaps starting with Quicksort and switching to Shellsort or some other algorithm for some key file size (perhaps 100 or so) would result in a large decrease in worst case times and similar performance in the best case.
Post may contain irony: discontinue use if experiencing mood swings, nausea or elevated blood pressure.
ALGORITHM: What you get when the Vice President plays drums...
And the ultimate, number zero algorithm having the most impact on computing is the past century is ...
(drumroll)
... the recipe for Classic Coke.
This algorithm is used for efficient decoding of convolutional error correction codes and for untangling signals corrupted by multipath dispersion. It has been developed by Andrew J. Viterbi (founder of Qualcomm) while at NASA for receiving the ultra-faint signals transmitted by deep space probes.
An introduction to the Viterbi Algorithm
Technically speaking, it is an efficient implementation of the Maximum Likelyhood Sequence (MLS) detector, just like the FFT is an efficient implementation of the discrete fourier transform.
----
Stop worrying about the risks of nuclear power and start worrying about the risks of not using nuclear power.
Anyone wishing he was there? In 1996 trying out one of his/her first algorythms on an Eniac or similar bigmomma computer, when assembler would be considered a high-level programming language? Being a pioneer, having your name mentioned more like an ubiquitous piece of standard code or part of a CPU ("the ALU is usually connected to the Haggar through a FIFO...") :o)
OTOH (OT): I am entertaining the idea of making a little FORTH compiler that would be also some sort of OS. Anyone with some good references/resources that coud help (ok, I know, read the Linux kernel source...)
Sigged!
Take a look at your list. Every single thing you mention depends in some way on something on THEIR list.
Getting tired of Slashdot... moving to Usenet comp.misc for a while.
The Internet has brought totally new versions of business, entertainment, and information exchange to the world -- and the algorithms that help run it are certainly some of the most influential ones in existence. Such as:
1) TCP algorithms -- Reno? Tahoe? Any of the algorithms that help keep our packets flowing have helped the network flourish as a reliable means for getting packets from Here to There.
2) Dijkstra's Shortest Path -- Everyone's favorite link state routing protocols use Dijkstra's algorithm to get your packets from Here to There as quickly and reliably as possible. It's helped make the Internet scalable and reliable enough for real work to get done.
These are just the first few that popped into my sleep-deprived brain -- I'm sure that the initiated reader could merely read through their nearest TCP reference (I suggest Comer's texts...) and get a real idea for some of the most important algorithms around today, even if some uppity article doesn't acknowledge them.
I learned to program from magazines, I never took any CS classes after changing mode on the BBC thing (used to explode). does this mean I am doomed to fail, because I don't know the perfect algorithm for the problem, I learned from 'use what works', I learn all the time but is the fact that I have never studied CS & the math onvolved mean that I am now obsolete?
~ppppppppö
Just goes to show that every algorithm, or theorem, or idea, was more influenced than influential. For Shannon I'd be tempted to create another honor for maximum influence per pages of manuscript. He had a profoundly useful idea and explained it as simply and clearly as possible.
(Reality reasserts itself sooner or later.)
Yes, Dijkstra's Algorithm (and not just because I sat in on his lecture at my University - The University of Texas) and heaps. I want two types of heaps in that list, each with the word "Fibonacci" in them:
1) Fibonacci Heap (priority queue style) = fastest heap known to man. Amortized O(1) insert, theta(1) decrease key, O(ln n) insert, theta(ln g) removeMin, and a lot of other theta(1) and O(1)s. Makes Dijkstra's Algorithm run 2-16 times faster.
2) Fibonacci Buddy System - Heap memory allocation. Fast as Binary Buddy system O(ln freelist) but MUCH better memory fragmentation. Guess the list author's don't need dynamic memory allocation?
Being a graphics geek, what about the newest one's for graphics and games? I have a large liking for the progressive mesh technique (collapse list to scale polygon counts in realtime) using Quadric Error Metrics (Hoppes and Hughes of Micrsoft respectively... Oh, Stan Melax of BioWare rules).
Ryan Earl
Software Engineer
Ryan Earl
Software Engineer
I found the first link too expensive, since I am not a member, it would require $10.00 per algorithm....... I'm sure I can do better online, at my local library or at the closest University library. Thanks anyway.....
I did find the second link interesting.
Based on a description in "Algorithms in C" by R. Sedgewick, I implemented a Quicksort (for a class) that used a Bubble sort to finish the last few steps after Quicksort had collated most of the data. A neat exercise, and my Quicksort ended up being among the fastest in the class (and it was faster than the pure Quicksort due to reduction of recursion overhead and partitioning, etc.)
"It's overkill, of course. But you can never have too much overkill." - Anonymous Slashdot Coward
Rather use this link - it has the missing explanations.
And this link explains integer relations.
here.
Don't be silly. If you do a symbol dump on the programs you're running, I bet at least one will call qsort().
Oh, go on, check out my job.
FFT should be much higher, it is so very very useful and important.
The Fortran compiler??? Is this a joke?
Where are the compression algorithms? LZW, Wavelets, etc. Where are the error correction algorithms?!
Compression, error correction, and the FFT are like the holy trinity of modern computing. Everything from CD's DVD's and spacecraft orbiting Mars and Jupiter use compression and error correction. How could they deny the importance of sheer power of these algorithms?!
Where the hell is Bubble Sort?
And Hello World! ?
Geez, without those two we would understand where Operating Systems
like Windows 3.1 are derived from.
I'm glad you said this. It makes me feel better about the list. Still I wonder what Emmett was smoking when he wrote (on the main page):
"If you use a computer, some of these algorithms are no doubt crunching your data as you read this.
Really?? I do my share of fancy math, though I'm not in the Big Leagues, and I'd be surprised if and of these algorithms are crunching *my* numbers (except maybe in some NSA basement supercomputer, where they are just now learning that my SSN + selected other ID numbers translates into the punch line of a dirty in EBCDIC)
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
Here are a few others, some of which have been mentioned before:
:)
1. "Similarity" based algorithms like hashing and radix sort. It still seems magical to me that hashing is constant-time and radix sort O(n). They are reminders that if you know a bit about the data you'll be handed as input, you can often do better than more general algorithms.
2. Using dynamic programming to solve certain kinds of optimization problems in polynomial time. Show-stopping examples (for me) are "memoization," the Earley parsing algorithm, and Korf's work on macroperator induction.
3. Everyone has their favorite recursive algorithm. Mine is the ID3 algorithm (now, C4.5) developed by Quinlan. It's simple (a page or two of Lisp) and it works well.
4. The British Museum Algorithm
Well, not to be even more anal, but the poster was just talking about algorithms that solve the TSP problem, not how feasible they are. There /are/ algorithms in existence that solves the TSP problem. They are just NP-complete. And for small amounts of data, why, they might even be 'feasible'.
"When in doubt, use brute force." --Ken Thompson
Admittedly it's more of a class of algorithms, (and the people who mentioned KMP string matching touched on it indirectly), but I'd really have like to have seen DFA's or NFA's listed on the list.
At least to me, DFA's are an extraordinarily elegant solution to a number of interesting programs. They run quickly, they're easy to program, and you can do a lot of neat stuff with them. One of the really spiffy examples being regular expression pattern matching or other string matching. (Okay, so regexes in grep and perl aren't regular anymore by the formal definition. But it's still a very elegant idea.)
There's an incredible amount of theoretical computer science behind finite automata.
Frankly, I'm not surprised giving where the information is coming from. One of the two writers works at an above-Top-Secret Institute for Defense Analyses super-computing facility. He probably spends most of his time researching number-crunching algorithms and the like.
I think I like dynamic programming algorithms the best, even though they are so hard to come up with.
it wasn't emmett who wrote it. it was what brian copied from the linked web page. and that web page was taken from a science news article (links on comment #187)
Greengard and Rokhlin's Fast Multipole Method (FMM) algorithm computes an approximation for the sum total of the interactions between all pairs of elements out of a large group.
For instance, in astrophysics simulations, one quantity that needs to be computed is the total force on a star that results from the gravitational attraction from each of the other stars. If you have to do this computation for each star, then the total ammount of computation required grows as N^2, given N total stars.
This is where the name "The N-body Problem" comes from.
The FMM algorithm essentially models distant groups of particles (stars) as a single mathematical object and by using other fairly complex operations and representations, reduces the overall complexity from N^2 to N.
The importance of this algortihm comes from the fact that in many different types of scientific simulations (astrophysics, molecular modeling, computational fluid dynamics, etc.) the N-body computation was the limiting factor in the performace of these algorithms. Use of FMM and similar algortihms has reduced the overall simulation times by orders of magnitudes for large systems, allowing simulations that once required CPU-decades to be completed in CPU-months.
There are several good sources of FMM material on the web. You can try:
Mario's Nbody resources
More Nbody
Leslie Greengard's page
And of course, I'll have to plug our research group page at Duke
Hope this helps
-bill
What? Who uses computers? I listen to the screeching noises from the phone to read Slashdot!
it's green.
Hrm. I could have sworn Ireplied to this. anyways, no :-( but I can supply a bit more accurate biblio info:
Pessimal algorithms and the simplexity of computations. A. Broder and J. Stolfi. (Satyrical article.) ACM SIGACT News vol. 16 no. 7, 49--53. Fall 1984. [bro-sto-84-pes]
Because I seem to have implemented all the first 8 algorithms before, either in CS class or in the course of working as a research intern - all except the Fortran compiler. I find it silly that a particulat language compiler is considered to be a top ten algorithm. I have no quarrels with the choices except for this one. Seems to me that the list is heavily biased towards scientific and numerical applications, and therefore the Fortran compiler. What about operation research and say (as an example) algorithms for solving the Travelling Salesman Problem? Or what about innovative (eeks - hate that word) data-structures such as, say, kd-trees that facilitate and suggest the development of a whole class of extremely fast algorithms in geometry?
...then, on the other end of the scale, there's AssumeSort, a sorting approach that some friends of mine devised for a class assignment back in the day. The algorithm worked in (N) time in all cases, and operated under the assumption that the input string was already sorted. Due to the open-to-interpretation nature of the wording of the assignment this algorithm was written for, they got extra credit for blowing everybody else's chosen sorting algorithm out of the water. I'll leave it as an excercise for the reader to write the algorithm itself...
Remember, kids, it's only premarital if you plan on getting married.
Hmmm... there is a definite bias in the top 10 list.. Most of the top 10 are from the last 30 years and none are from before 1946. Maybe they should have called this list "the top 10 algorithms since the study of algorithms got really big". Hey, isn't that the year the thing at Area 51 happened? Maybe there's some connection... :-)
These are just what they came up with. Don't complain that they "forgot one". Instead, just write your own. A lot of these comments say that "it should have been in there" when it would have been good enough to say "I'd have put this in there." This list is a starting point, not the ending one.
Personally, I favour the suggestion I saw about polling Slashdot. Maybe an Ask Slashdot article: What's Your favourite?
it's green.
"Great algorithms are the poetry of computation"
:-)
Funny, I thought Perl was
(note to moderators: it's a joke, ok?)
nuclear cia fbi spy password code encrypt president bomb
Friends don't let friends misuse the subjunctive.
1) 2000: The Microsoft End User Licence.
Turns network admins into Linux users.
___
The overhead of quicksort gets to be a drag when the size of the sorted list is really small (2 or 3 itemsl as you say). So some implementors have chosen to modify quicksort so that it does another kind of sort during the dash to the finish line.
:)
But in its purest form quicksort don't play that game. Hey, there are other mods that people do to quicksort to increase its performance (like not blindly choosing the first element of a subsection as a pivot point -- this can lead to order n squared performance if the data is already sorted).
The bottom line is that you can still call it a quicksort even if you've tweaked it a bit... otherwise we'd have a different name for each implementation of quicksort ever written
Regards, your friendly neighbourhood cranq
Regards, your friendly neighbourhood cranq
Completely wrong. Quicksort finishes when it has partitioned the array into partitions of 1 element apiece. At this point it is completely sorted. Since it is not possible to Bubblesort (or anything-sort) sequences of length = 1, Bubblesort cannot possibly be used.
Damn. I can see the bubble sort program I wrote in the 5th grade didn't make it ... :)
My journal has hot
I love Monte-Carlo simulations - it's the only way to do research ;-)
And it nicely adapts to implementation across Beowulf clusters.
Now you know why we asteroid Catastrophists talk in probablilities all the time - we just play games with dropping random asteoids onto the Earth and call it work.
what about cordic?
wavelet uses FFT, so it's covered.
Some special variant of wavelets might use FFT, but in general your statement is not correct. FFT (or actually DFT) is a special case of wavelets, and thus it is not covered. Most wavelet bases aim to be compact both in spatio-temporal domains, and in the frequency domain, and can thus be said to land somewhere in between.
Huffman code construction and Adaptive Least
Mean Squares (or stochastic optimization in
general) are widely used algorithms in many fields,
but especially telecommunications.
Since everyone uses telecommunications, I these
algorithms deserve some consideration, and also
that the list was put together by a bunch of
old physicists. (joking about the last part).
But I'm guessing it's not on the list because it's not an algorithm. It's a lack of an algorithm. It's simple enough to multiply two large primes together. The reason public-key crypto works is that there is no known algorithm to turn the product back into its constituent primes in reasonable time.
Maybe that missing algorithm should have been listed as #0...
Jamie McCarthy
Jamie McCarthy
jamie.mccarthy.vg
(a) As someone has already pointed out, it is heavily biased toward numerical computation, fully ignoring the rest of the (very wide) field of algorithms.
(b) Items on the list are individually pretty ignorant. The Fortran optimizing compiler sticks out like a sore thumb, but even worse is the listing for "Fast Fourier Transform".
The FFT was actually invented by Gauss, before Fourier. Yes, Gauss actually invented the Fourier transform in 1805; he was afraid to publish it due to persecution. When Fourier published regarding the Fourier transform, he was indeed heavily ridiculed; the usefulness of the Fourier transform was not generally acknowledged until after Fourier's death. Gauss' document describing the FFT did not see the light of day until 1866 (this document was "Theoria Interpolationis Methodo Nova Tractata", which as you can see was written in Latin).
The "discovery" of the FFT that this list refers to is the paper by Cooley and Tukey written in 1965, "An Algorithm for the Machine Calculation of Complex Fourier Series". However, this was not even the first rediscovery of the FFT that happened in the 20th century. Several people rediscovered and published FFT algorithms between 1910 and 1965 but the Cooley and Tukey paper is the first one that was seized upon by computer science guys, so they get all the recognition.
Most books that go into depth about signal processing will have this information about the FFT; I am looking right now in my favorite, very accessible signal book, "A Digital Signal Processing Primer" by Ken Steiglitz. Not all the books go all the way back to the discovery by Gauss, but they all pretty much mention that the FFT has been rediscovered several times in the 20th century.
Now the web page in question says that this list was published in "Science", which makes me feel really bad for Science. I have not been around for very long (I'm 28) and I am not any kind of algorithms specialist (I'm a game programmer) but even I can tell that this list is bogus.
Now give me a "10 greatest algorithms" list written by Knuth and maybe I will take it seriously.
That is all.
List is definitely biased towards that more numerical side of CS. I would personally like to see search algorithms, graph algorithms, advanced data structures, etc. Here is an assortment of more realistic CS stuff (in no specific order), I tried to put in stuff not talked about in previous posts.
:)
:)
;)
1. A^* search and variants. Simulated annealing, heuristic repair, etc. You know, GOFAI search algorithms.
2. Minimum Spanning Tree algorithms. Shortest path algorithms. Graph partitioning algorithms.
3. Data structures: heap (the usual one, and the variants such as binomial fibonacci), tree structures(bst, r-b, avl, b+, bsp, quad-, oct- etc.), disjoint sets, hash tables.
4. I don't wanna admit it, but perhaps back propagation algorithm for ANN
5. LR(1) parsing algorithms, without which you can't write decent compilers!
6. Round-Robin scheduling algorithm. Where're you heading without pre-emptive multitasking?
7. Median-of-medians. Power of recursion!
8. LCS (Longest common subsequence), demonstrative of dynamic programming. And you used some diff program surely...
9. RSA and similar public key crypto-algos.
Hope you like this slightly alternative supplement
--exa--
Granted, that was a list of many fine algorithm discoveries, but is it a correct list? The many notable omissions that slashdotters here are bringing up (my personal fave that didn't make the list: Reed Solomon encoding) would indicate not.
Moreover, didn't all the "Top Ten" lists from other fields come and go last December?
So how good can the best computer algorithms be, when it still takes them 6 months to generate a "Top Ten" list, and the list is incorrect?
It's pretty clear that any "top X" algorithms list strongly reflects the bias of the people compiling it, so here's another extremely biased list (in no particular order):
* Smith-Waterman alignment algorithm
* BLAST search algorithm (Altschul et al)
* Ukkonen's suffix tree construction
* expectation maximization
* inference algorithm(s) for Bayes nets
* Davis-Putnam procedure for SAT
Bonus points to those who can guess what I do for a living (without checking my home page)...
Also note the GREATEST INFLUENCE part; recent algorithms or clever algorithms don't necessarily make the cut (because influential algorithms usually need time to build up influence, and sometimes the most influential ones are the simplest and not always the most clever).
Without them, Quake is impossible. :)
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
Huffman encoding is exactly the same thing as Shannon-Fano encoding, which predates it by at least 10 years.
No, it isn't. Huffman generates optimal codes. Shannon-Fano does not. Yes, Huffman is esentially a "tweak" of Shannon-Fano (the code generation is done in the reverse order), but it's a very powerful tweak that turns a "pretty good" algorthm into an "optimal" algorithm. (given certain constraints. I know arithmetric encoding is better in many ways.)
Bresenham's line drawing algorithm is nothing but solving the equation of a line, only with repeated subtractions instead of a division. (Faster on processors with slow floating point.) Including this would be ridicolous.
All algorithms are nothing but performing a bunch of simple computations to achive some bigger result. Bresenham's algorithms have become "staples" of computer graphics though.
Incidently, Bresenham's algorithm is useful even on machines that don't have slow floating point. Bresenham produces "nice looking" lines. Simple linear interpolation produces ugly lines. If you don't know what I mean, try drawing some diagonal lines in GIMP using the pencil and a 1x1 brush. See how ugly they are? That's because GIMP uses linear interpolation, rather than Bresenham. I hate to say it, but even MS Paint produces nicer looking lines, simply because it uses Bresenham. (and if you think how it looks isn't important... sorry, but that's the way it is in graphics...)
I think you mean Binary Splay Partition algorithms, which truly also are in widespread use. But in such a list it would be better to include some of the real raytracing algorithms.
No, I meant Binary Space Partitioning trees aka BSP trees, which are used for all sorts of things in graphics including polyhedral rendering systems, raytracing optimization, polyhedral set operations, and collision detection. Yes, there are other techniques for achieving all of these, but BSP trees show amazing versatility.
Incidently, I've never heard of "Binary Splay Partition algorithms". Are you talking about binary splay trees?
KMP search is hardly in use except in very special cases. There are more efficient algorithms around.
Yes, I made a mistake. KMP and Boyer-Moore are very similar (in much the same way that Shannon-Fano an Huffman are similar, actually...), but Boyer-Moore is clearly the superior algorithm. I think Boyer-Moore and KMP have become intertwined in my head, because I learned both of them at the same time. (perhaps also because "the BM algorithm" has nasty connotations...)
Okay, strike my vote for KMP, and add one more vote for Boyer-Moore...
In any case, the list I posted was not intended to be "the 9 best algorthms of the 20th century". It was more like "the 9 best non-numerical algorithms that came to me as I was posting to Slashdot". So take it with a grain of salt. I know I missed some great ones in there... I didn't have any tree balancing algorithms in the list, for example. Skip-lists are also pretty cool, and probably deserve a mention, despite the fact that almost no-one seems to use them. Systems algorithms like process scheduling algorithms, caching algorithms, and even the elevator algorithm (used for scheduling requests to "seekable" devices like hard drives) probably deserve a mention too. And how about database algorithms, like the various join algorithms? Or the numerous AI algorithms? A "top 10" list is really too short. We really need a "top 100" list...
Boyer-Moore, on the other hand, uses a similar idea to KMP, but to much better advantage. A typical search pattern will let you skip large chunks of data (when there is no match) where KMP would have to examine every character.
You're right. I got them confused.
Abstract and source PDF doc for the Fast Multipole method can be found at the source site
The Fortran Optimizing Compiler?!?! I don't consider that an algorithm, because... well it doesn't FEEL like an algorithm! Look, it just isn't an algorithm, ok?
*sigh* I've come up with a reason why. It's because it's machine dependent - an i386 Fortran compiler and a PDP11 compiler are completely different.
Any technology which is distinguishable from magic is not sufficiently advanced.
Shannon outlined RLE and Shannon-Fano-coding (a kind of top-down Huffman, less efficient, though) in his "Mathematical Theory of Communication", which predates Huffman coding. Also there are a lot of methods that aren't at all like Huffman coding (aside from the fact that they compress data). If there would be data compression then it would be arithmetic coding (quite new), which is about as near optimal as you can get (optimal, if your numerical precision is infinite).
It seems to me that Dijkstra's algorithm should be on there. It's certainly as important as quick-sort...
You're right, performing fast convolution is faster when the filter is long enough, but your n is a bit off. Longer filters are required for steeper frequency responses. The fast convolution approach gets faster than FIRs around 40 taps (n = 40, for audio). This would also depend on the FFT algorithm used; there are many, like radix-2, radix-4, different split-radix algorithms.
Any such list that doesn't include Bellman-Ford distance vector or Dijksta's algorithm can't be taken seriously.
COuld you give a link or some explanation of what the Kolman Predictor is? It sounds quite interesting and I didn't find anything on a basic web search.
Does anyone care to translate these algorithms to something us lesser geeks might know? I recognize the quicksort, Fourier, and Fortran algorithms, but the rest are rather over my head.
It'd be interesting to see how these relate to the algorithms that computer jockeys see as king (obviously, the list is biased towards science and numbers). Are any of these algorithms related to things like compression algorithms (MP3, Zip, LZW, etc.), encryption algorithms (DES, RSA, Blowfish, etc.) or search algorithms (like the one Google uses, for instance)?
What would a computer geek's top ten algorithms list look like? Would they be scientifically/technologically important or more socially important (like MP3, RSA, or Google)?
Can't believe the Viterbi algorithm didn't make this list ... without it, so much communications and data storage would be slow and/or unreliable.
This algorithm decreases the amount of time used to multiply to matricies from O(N^3) to around O(N^2.72) (or less) by breaking the matrix up into little pieces that are multiplied by each other (or broken into smaller pieces with the same process) then added together to get the result.
The primary speedup in this algorithm is that additions are much faster for a computer to complete than multiplications, and a single multiplication can be replaced with several additions.
The other benefit of this algorithm is that it divides the work into subproblems that can be dispatched to alternate processors and then recombined centrally.
Unfortunately, due to the large overhead costs of this method it only works well on very large data sets, such as 1000x1000 or larger arrays. Once you get below this size it is best to use the standard matrix multiplication.
Here is a section of code from a matrix multiplication algorithm using this method I wrote for an algorithm analysis class: if (this.length == 2) /* 2x2 matrix */
{
int x1, x2, x3, x4, x5, x6, x7;
int x1a, x1b, x6a, x6b, x7a, x7b, x2a, x3b, x4b, x5a;
x1a = a11.add(a22).getElement(0,0);
x1b = b11.add(b22).getElement(0,0);
x1 = x1a * x1b;
x2a = a21.add(a22).getElement(0,0);
x2 = x2a * b11.getElement(0,0);
x3b = b12.sub(b22).getElement(0,0);
x3 = a11.getElement(0,0) * x3b;
x4b = b21.sub(b11).getElement(0,0);
x4 = a22.getElement(0,0) * x4b;
x5a = a11.add(a12).getElement(0,0);
x5 = x5a * b22.getElement(0,0);
x6a = a21.sub(a11).getElement(0,0);
x6b = b11.add(b12).getElement(0,0);
x6 = x6a * x6b;
x7a = a12.sub(a22).getElement(0,0);
x7b = b21.add(b22).getElement(0,0);
x7 = x7a * x7b;
c11 = new Matrix(1);
c12 = new Matrix(1);
c21 = new Matrix(1);
c22 = new Matrix(1);
c11.setElement(0, 0, x1 + x4 - x5 + x7);
c12.setElement(0, 0, x3 + x5);
c21.setElement(0, 0, x2 + x4);
c22.setElement(0, 0, x1 + x3 - x2 + x6);
}
--
Eric is chisled like a Greek Godess
marotti.com
I can't believe they left out compression, error correction/detection, crypto, DSP (but at least FFT is there).
No compression = no gif, jpg, mp3 etc.
No ECC = no Internet or comms or HDDs.
No crypto = no encryption, signatures/hashes, and hashes are really useful.
Aside: I've also always wondered about disk defragmentation algorithms, never seen much info on that.
Cheerio,
Link.
As one of the gurus of Pi, he came up with some algorithms himself. Look here.
Given that the focus of this list is Computational Algorithms (rather than Analytical Algorithms), I believe some implicit biases must exist: The
algorithm must be elegant to implement and efficient to run on a computer.
But beyond that, there are algorithms that "mediate" between our world and the world of the computer. Chief among these is the most fundamental problem of Computer Graphics: What is the best way to draw a line or a curve onto a rectilinear array of pixels?
The problem is VERY non-trivial! "Good" lines must look the same if drawn from A to B as they do when drawn from B to A. Many early line drawing
programs failed miserable at this task, forcing drawing programs to sort the line endpoints before calling the drawing algorithm.
Bresenham's Line Algorithm was the first to meet these constraints (when properly implemented, of course) in a manner that was also EXTREMELY
computationally efficient. Not only did this algorithm give you "good" lines, it also gave you "fast" lines!
The problem gets worse with curves: In addition to directional symmetry, they must also exhibit reflective (not rotational) symmetry. That is, an arc drawn from 1 o'clock to 3 o'clock must be identical to all of its mirror reflections: The horizontal reflection from 9 o'clock to 11 o'clock, the vertical reflection from 3 o'clock to 5 o'clock, and the combined reflection from 7 o'clock to 9 o'clock. Deviations from such symmetry are extremely noticeable to the human eye.
For the generalized ellipse (which trivially includes the circle), an algorithm that meets the above requirements will have an extremely valuable
secondary effect: The algorithm need only be used, at most, to draw just one quadrant of any closed ellipse, since the other three quadrants can be drawn by reflecting the original arc. For a circle, only a single OCTANT (1/8 of a circle) is needed!
While other circle, arc and ellipse algorithms preceded Bresenham's, again none was simpler, more accurate or faster.
The underlying problem has to do with errors: When is it appropriate to turn on this pixel instead of that one? The "easy" result is to work in floating point, with fractional pixels, then round to 1 or 0 to decide if a specific pixel is on or off. And this, in turn, would seem to demand the use of trigonometry, in the case of a circle! Clearly, doing floating point and trig just to draw a line or circle is impractical, yet that is exactly what many of the earliest hardware accelerators did!
Bresenham's algorithms managed to draw accurate and precise lines and circular arcs, accurate to within half a pixel, without floating point math.
Now that's what I call one hell of an algorithm.
More complex curves, including arbitrary curves, lacked an "adequate" solution until the advent of the B-spline and NURBS techniques. While extremely efficient, they resemble elephants compared to the cheetah of Bresenham's.
And, of course, Bresenham's algorithms don't generalize well to meet the contemporary need for things such as alpha blending and dithering in the
color space. But the best of such algorithms still have a bit of Bresenham at their core.
A very good summary of the derivation of Bresenham's Line Algorithm may be found here.
Bresenham's Algorithms (along with many other graphic algorithms such as flood and fill, and "XOR" cursor drawing) are fundamentally what made
"Personal Computing", that is, interactive computing with a GUI, possible with inexpensive hardware.
Bresenham's Algorithms (especially the Line Algorithm) are a glaring omission from the list.
They missed the compressed dictionary tree substring search algorithm, which is a very important one these days.
It takes a O(length of document) time and space preprocessing step, and then each query takes O(length of query) (i.e., it doesn't matter how long the document is for doing the searches).
In addition to being good for simple text searching, it's really good for searching DNA databases. When you've got 4 T of data, and want to find a 1 k sequence, it's really good if the time required doesn't depend on the size of the whole database.
With open source catching on more and more with the big companies (finally!), perhaps this is where the new money will be made?
Anyone who buys software these days (except for highly specialized purposes) is generally not doing themselves a favour, and with linux (finally) becoming pre-bundled, the newbies might not even know they are using linux.
With a patent office that is giving out patents broad enough for the HTTP protocol to be included, just about giving patents broad enough for multiplication to be included, perhaps companies will see this and decide to get on the algorithm research game.
Perhaps the two most valuable types of patents these days will be low-overhead (but secure) encryption, and low-overhead (but effective) compression?
Lets face it, I'm not the only one who would appreciate fitting 10,000 images on my 1.44 mb floppy disk, or being (for once) not under echelon's watch :-).
SSL Certificate
Maybe my memory is going spotty early, but I recall it being "Plop, plop, fizz, fizz..." instead of "Pop, pop, fizz, fizz..." Am I incorrect?
Maybe I should say my is going spotty because I can't remember what the recommended dosage was/is. Then again, I've only used it once in my entire life.
Medication is for wusses. :)
J. T. "Mac" MacLeod
While it's true that many of these algorithms are the fastest possible ways of doing things (aside from minor tweaks on a case-by-case basis), it is wrong to say that this will always be the case. I know this seems oxymoronic, but it makes sense if you consider that our methods of computing may soon undergo fundamental changes. Quantum computing has produced algorithms which are abstractly faster than their conventional counterparts, so much so that even a 1 MHz quantum processor may be several orders of magnitude faster than a 1 GHz conventional processor on these specialized tasks, so far including factoring huge numbers (encryption) and extremely fast data searching. I think that quantum computing will fundamentally change the way we look at high performance algorithms, because it requires much more specialization at the hardware level. Any thoughts on this?
WARNING: there is a trojan on your
You wouldn't perhaps know where an online copy of this paper might be found, would you?
(I did search Google. All I found was one of the authors' Web site - no copy there - and about a thousand references to the "lion in the Sahara" problem.)
To the editors: your English is as bad as your Perl. Please go back to grade school.
In my opinion, error correcting codes are the most important algorithm of this century.
Without them, hard drives would be useless or contain 1/3 of the data or less (mirroring isn't enough, since you don't know whether the mirror or the original got corrupted). Digital phones would suffer the same kind of audio glitches that analog phones do.
An transmission technology, in fact, would suffer without ECCs, so it's rather surprising that they're not on this list.
I think that the most important algorithm ever conceived has to be BUBBLESORT!!
-binner
Say what you mean, mean what you say! But please know what #$@% you are talking about!
If you don't know, this algorithm powered most of not all of the old computer line drawing displays (possibly including ones like Apple II's, C-64's and maybe even some of the early Evans and Sutherland machines). The algorithm is that old at least, and quite clever. For a given line (y=mx+b) it figures out which pixels on the screen are the closest to lying on this line, and it does it all in integer arithmetic!
Bresenham(sp?) has a similar circle drawing algorithm.
I'll confess my ignorance of modern day graphics hardware. I do not know if this algorithm is still at the heart of graphics machines, heart being just where the number hits the phosphor. But I wouldn't be surprised it if were still in use.
I think they left out two important categories of algorithms. They should have had at least on data compression algorithm (LZW, wavlet, or something like that) and an encryption algorithm (DES or RSA).
Regarding the Fortran optimizing compiler. fi you assuem they are speakign of the Fortrancompiler as the first compiler to generate machine code that was efficient enough to rival most handwritten machine code I would say it had a huge impact on computing today. High level programming languages make programmers more efficient, but without a compiler that generates sufficiently optimized machine code the advantages of increasing programmer efficiency will be overwhelmed by the program inefficiency. So, a compiler that generates machine code on par with most handwritten machine code revolutionizes computing by making programmers capable of writing more and larger programs that are easier to maintain while still maintaining reasonable performance.
And, assuming Fortran compiler to achieve the balance between programmer efficiency and program efficiency, all other compilers since have their roots in the Fortran compiler.
Dastardly
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.
What about these algorithms. While they may seem trivial to all those people in CS gradschool, someone had to come up with these. Not only are they extremely cool, but they are used very frequently.
Is there some part of the contest I am missing, becuase these algorithms seem to be on the smae level as the quicksort algorith, (which is also very cool). Anyway, can someone set me straight?
--Alex
I thought the KMP search allows you to search for multiple strings, not just one, à la B-M. In which case we're not comparing the same kind of task.