Slashdot Mirror

← Back to Stories (view on slashdot.org)

Deep Algorithms?

Posted by michael on from the post-pattern dept.

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.

2 of 570 comments (clear)

  1. Off the top of my head by td · · Score: 5, Insightful

    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
  2. Re:Bubble Sort? by Matthew+Austern · · Score: 5, Insightful
    This is a standard interview question for me, when I interview programmers. "In what case would you want to use a bubble sort?"

    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.