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."
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
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
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 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?
This one was widely used back in the 80's:
10 PRINT "RADIO SHACK SUCKS!!!!!"
20 GOTO 10
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
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.)
By definition, an algorithm terminates.
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?
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)
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
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.
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.
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
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
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.
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
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?
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!
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
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 normally wouldn't bother to reply, but most people are missing that the list is ordered by date, not some arbitrary "importance" ranking!
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.
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.
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!
Rather use this link - it has the missing explanations.
And this link explains integer relations.
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?!
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
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?
"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.
___
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.
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
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?
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...
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.
No. The asymtoptic speedup is still present; adding matrices is easy, but multiplying them is significantly harder. The method of matrix multiplication described recursively reduces the sizes of the matrices to be multiplied at the expense of more adds. For dimensions over 2000 or so on a modern computer, the improved method wins out.
It seems to me that Dijkstra's algorithm should be on there. It's certainly as important as quick-sort...
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)?
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
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.
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
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).
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.