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.
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
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!
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.
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.
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
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