Slashdot Mirror
Deep Algorithms?
Stridar writes "A paper presented in a recent article quotes Donald Knuth as saying the computer science has 500 deep algorithms. He mentions that Euclid's algorithm is one of the most important, and he seems to agree with the idea that CS will be mature when it has 1000 deep algorithms. What I would like to ask Slashdot is the following. What are the most important algorithms in CS? What is your favorite algorithm? And finally, what are the outstanding problems for which algorithms would be immediately placed in the "Top 1000" category." We had an older story where two scientists picked their top ten algorithms.
In the real world 99.999% of people, smart and stupid, should use the algorythms that smart people like Knuth have invented. It would take a stupid person to think that in all but the 0.001% of cases there is any need for any more. And if you are wondering if you are in the 0.001% of cases - you're not.
James Gosling said the same thing recently.
The rest of the world learnt a long time ago to stop re-inventing the wheel why can't CS people learn the same lessons. Algorithms may keep your CS master happy, but they won't help you in the real world.
DWR is Ajax for Java
Quicksort
The Unification Algorithm
Skip Lists
Conjugate Gradients
Karmarkar's linear programming algorithm
Knuth-Morris-Pratt string matching
Multidimensional scaling
The Kernighan-Lin TSP & graph-partitioning methods
Lempel-Ziv compression
Fast Fourier Transform
Quine-McCluskey optimization
Celine/Gosper/Zeilberger/Wilf algorithm for hypergeometric identities
Fast Multipole method
-Tom Duff
* Randomized primality testing
* Gaussian elimination
* Euclid's gcd algorithm
All three run in time polynomial in the bitlength of the input, yet the first thing that springs to mind is exponential time:
primality testing: try dividing by every number between 2 and sqrt(N).
matrix determinant: the straight definition has n! terms. With Gaussian elimination you can compute the determinant in O(n^3) time.
gcd: factorize both number and compare? (ugh)
Gotta appreciate algorithms that show real insight into a problem.
IMHO, asking "what are the outstanding problems for which algorithms would be immediately placed in the "Top 1000" category?" reveals a misunderstanding of Knuth's article (All Questions Answered). In regards to "deep algorithms", Knuth was speaking of the maturity of computer science as a theoretical discipline, not as an engineering science. An algorithm is "deep" because it is beautiful (to use another of Knuths words), that is, it demonstrates a penetrating insight into the nature of computation. In this regard, the actual problem domain addressed by any given algorithm, in and of itself, is irrelevant. In fact, in the same article, Knuth is asked to give the five most important problems in computer science. He replies that he "doesn't like this top ten business", but prefers the "bottom ten". What is important, he says, is "the little things ... the stones in the wall".
First off, it's clear that you have a very narrow view of what is actually done with computer science. Granted a lot of what the casual or application programmer deals with can seldom involve the creation of a new algorithm. However, the field of algorithms is constantly expanding.
Examples would be:
A guidance system
Any artificial intelligence
Image manipulation
Video games (quake engines!?!?!)
Telecommunications routing software
VLSI Design
etc..
As far as I know, that stuff is pretty important in the real world. Yes, algorithms exist to do pretty much all of those (in fact, with brute force, many are trivial). However, we are constantly looking for "better" algorithms. If new algorithms are not relevant, why would companies, like Intel, pay hundreds of millions of dollars for a program that would optimally lay out the elements on their chips for them?
This is a standard interview question for me, when I interview programmers. "In what case would you want to use a bubble sort?" The answer, my friends, is very simple. The bubble sort is extremely fast when your list is almost always very nearly sorted, with very few (or no) elements out of order. For some algorithms, the already-sorted order is the worst case. For the bubble sort, it's the best case. So if you have a data structure that is updated frequently, but the order of the elements very rarely changes, you can use a bubble sort without being too embarrassed. :)
In any field, find the strangest thing and then explore it. -John Archibald Wheeler
There is a big difference between programming and computer science.
Patterns have more to do with programming than computer science.
My one professor was fond of telling us everytime we showed up in class, not understanding his advanced statitistical discussions of machine states and the like:
"Oh yes, you are programmers, not Computer Scientists."
'Companions the Creator seeks, not corpses, not herds and believers. Fellow creators the Creator seeks, those who write new values on new tablets. Companions the Creator seeks, and fellow harvesters, for everything about him is ripe for the harvest.'
(Friedrich Nietzche)
It's well and fine to say that we should use the algorithms "that smart people like Knuth have invented", but that's not enough if you're going to make your living as a genuine developer. I agree that we should use the frameworks we are provided in order to get the highest productivity, but if you can't take some pleasure in the construction of an elegant piece of code (algorithmic or otherwise), then you're just a technician who can easily be replaced when the next fad rolls out.
You can put people like Knuth on a pedestal if you like, and that is certainly warranted in his case. But real progress will only be realized when you disregard people like him and do something of your own.
Please mod this post only if you think others should/n't read this. I have enough ego^H^H^Hkarma. Thanks!
Metropolis algorithm for Monte Carlo
Simplex Method for Linear Programming
Krylov Subspace Iteration Methods
The Decompositionnal Approach to Matrix Computations
The Fortran Optimizing Compiler
QR Algorithm for Computing Eigenvalues
Quicksort Algorithm
Fast Fourier Transform
Integer Relation Detection
Fast Multipole Method
And the correct answer is: never.
It's true that for small lists, or lists that are nearly sorted, you want to use an O(N^2) algorithm rather than (say) quicksort. The mistake is making the leap from "an O(N^2) algorithm" to "bubble sort".
There are lots of O(N^2) sorting algorithms, with different constant factors. Bubble sort is one of the worst; see Knuth (v. 3, of course) for a detailed analysis. If you're dealing with a small list or a nearly-sorted list, you should probably use insertion sort. (Or, in some special cases, you might want selection sort or merge sort instead.)
I have yet to find any case, anywhere, where bubble sort is the right choice. If I ever teach an introductory algorithms class, I will probably omit bubble sort.
Do you mean that it is irrelevant to you? For some people, Knuth for example, the obsession with algorithms is very important. Thank goodness that they did do this so that you and I could borrow their work and not invent it ourselves. Some people spend a great deal of time trying to construct and refine algorithms. I would guess that few people in our society care, but it is greater than .001% of the people in the scientific computation communittee.
Believe nothing -- Buddha
That's a bit like saying that there is no need to understand calculus because Newton and company already figured it out for you.
To the professional programmer an algorithm is a tool, and like any other kind of tool it is important to know how it works even if you didn't invent or produce it yourself.
This may suddenly dawn on you when you're coding an algorithm out of a book, and find you don't know whether it's safe to take a particular shortcut or not because you don't understand the algorithm well enough to analyze the implications. Or you're looking at some values in a debugger and can't figure out if they're correct or have been clobbered by a bug because you don't understand the algorithm well enough. And so on.
Never? Can you prove that there are no data structures and change patterns that do not result in the bubble sort being the fastest over all? I'd be very interested to see that proof.
I still maintain that there may be a situation in which a bubble sort is the right choice, and that the question is a good one. Maybe I can't think of it (and honestly, I've never used a bubble sort in any code I've written) and apparently neither can you.
For me, the most important thing to think about is to consider the situation in which you're using the algorithms. I ask the question, because I want to challenge the person I'm interviewing. The people who immediately laugh and say "Never!!" without thinking about it for a minute get passed over. If someone thought about it for a minute and replied what you did, I'd be happy with that. I'd be just as happy if someone thought about it for a minute and said, "maybe some cases in which the list is already sorted, but I'm trying to imagine how that would work".
There may be a pattern to the way the data is changed over time that means that bubble sorts will be the best. I want people to think about that, rather than laugh about the bubble sort as a terrible algorithm. It's not -- it does what its supposed to do and nothing more. It just may be an algorithm that has an extremely narrow range of applicability.
I would definitely teach the bubble sort, even if the lesson is, "sometimes there are simple and easy-to-use algorithms that are rarely the most useful." People have to learn to recognize that.
In any field, find the strangest thing and then explore it. -John Archibald Wheeler
I would vote for Fortune's algorithm to compute the Voronoi diagram. It is a beautiful algorithm, which almost gave me an orgasm when I looked into its guts. I am shocked that no computational geometry algorithm was included in the top 10 list. Not only have they proved already to be extremely useful, but they are alos going to be more and more important in the future (especially in my case, working on next generation user interfaces).
As I noted in another post, one problem with skip lists is that each node must be dynamically resizable because the number of forward pointers is changing and not known at compile-time.
Another problem with skip lists is that they are not very friendly to multiple readers and writers because the nodes provide unfortunate concurrency "chokepoints". In a binary tree, for example, subtrees can be locked without blocking readers in adjacent subtrees.
cpeterso
No way man the Number Field Sieve ownz RSA.
:-)
Everyone is forgetting that simple tests count as algorithms. No one has mentioned Eistenstein's Criterion, or the Weierstrauss M test, or Miller's Primality tests. Some of these tests are quite deep, and at very least they bear consideration alongside some of the more obvious tests from CS, analysis, and basic math.
:-P but I'd be shot.
Heh, I would say the deepest and most important algorithm is the process of induction
or a infinately long tape divided into squares, each of which is inscribed with a 0 or 1. fed into a machine...
four-oh-four
Computer science is the branch of mathematics dealing with computation and computability. Algorithms is contained in that. :)
It's more like you have to consider real-life situations individually. My point is very much like what you said -- you can construct a zillion different algorithms to do something, but the vast majority of them will be practically useless in anything but a really weird situation. Recognizing when they are and aren't useful is an important skill. And most of the time, you'll go with the tried-and-true quicksorts etc.
However, it's important to think about each situation. Pure algorithms are usually designed with the general case in mind. Individual situations, however are always specific cases. Most of the time, the general solution is obviously useful. Sometimes, however, there is a special case that might not fit the mold, and one of these crazy one-off algorithms might fit the bill exactly.
In my mind, you will not get a job with me if you cannot see what makes each application of an algorithm unique. Computer science optimizes the general case. Real-life programming optimizes the special case that you're dealing with in your particular program.
In any field, find the strangest thing and then explore it. -John Archibald Wheeler
I think what Knuth means by "deep algorithm" is one that seems fundamental, something that tells us about the nature of reality, not necessarily something that is useful.
- Have a picture
BGP's routing algorithm and those of its its cousins and ancestors. Without this routing algorithm, you couldn't read /.
Tastes like burning! - Ralph Wiggum
In somewhat saner assmbly, it looks like:
"We returned the General to El Salvador, or maybe Guatemala, it's difficult to tell from 10,000 feet"
When science "matures", it becomes technology and engineering. Science, by definition, is the eternal process of charting the unknown, and re-examinating the known.