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.

Comments

My pick goes for RSA

[dgerman]

THe algorighm is simple, powerful and beautiful. Its properties allows to use for encryption or for authentication. It is simple enough that can be described in a piece of paper, and understood with basic mathematical background, and it affected the e-world in many different, some of them still to be seen.

Well, technically a data structure

[Sangui5]

My personal favorite is the skiplist. O(ln n) insert, search, and delete in the average case. Simple to understand, has good constant factors, doesn't require maintence (unlike trees). Really, what more could you want?

Here's the paper:

ftp://ftp.cs.umd.edu/pub/skipLists (many formats)
PDF

Topological Sort

[CvD]

Resolving dependencies between any number things requires this very useful graph sorting algorithm.

Algorithms?

[FortKnox]

Algorithms? Its all about PATTERNS now-a-days!

Honestly, I don't think CS will be considered "mature" just by the number of complex algorithms it has.
There's more to CS than algorithms.

And, I always thought algorithms were grouped into "Discrete Mathematics" not "Computer Science" (granted, there is overlap, but isn't there overlap in most sciences??).

Re:Algorithms?

[wdr1]

Er, not really.

It depends on what field you're working in. Patterns are all the rage in OOP, and especially in Java. No doubt about that. Alas, they alone do not encompass all that is technology.

But, more to the point, patterns are a component of software engineering. Similiar to patterns, algorithms are a component of computer science. (Although it's probably safe to to say algorithms play a *much* larger compontent in CS, than patterns are in S.E.).

What's the difference between software engineering and computer science? Hard to explain, but it's a little bit akin to the difference between Physics and Engineering. The former tends to deal with matters more theoritcal, the latter, matters more pratical.

It worth noting that both algorithms and patterns feed into being a good software engineer, as least IMHO.

-Bill

Diffie-Hellman, too

[paulschreiber]

Don't forget Diffie-Hellman key exchange, RSA's lesser-known partner in crime.

Paul

Hello World

[Wolfier]

One of the most important algorithms ever invented.

Seriously, how about Simulated Annealing or Genetic Algorithm?

simplex method

[Gary Yngve]

It is so far-reaching.

linear programming, minimax game searches, network flow, primal-dual techniques for approximation algorithms......

Fast Fourier Transform

[sketchy_gomez]

I'm going with the Fast Fourier Transform, because it is ubiquitous in signal processing and it has various number theoretic applications. As an added bonus: The Quantum Fourier Transform can be used in Shor's Algorithm to factor numbers in polynomial time! Although, this is not yet practically realizable..

Prune your betas!

[Logician007]

Alpha-Beta Pruning or "minimax" is my favorite. It is a good way to trim your search space, but as far as I know pretty much is only used in strategy game playing. Chess specifically. The hard part about it is comming quantifying the value of the moves each player can make (Number of pieces, position on the board, tactics, blah!). Unlike most tradeoffs in CS, this one saves both time & space.

The funniest algorithm

[leob]

The funniest, while quite deep, algorithm is a text compression (or, rather, transformation) algorithm called Burrows-Wheeler Transform. It is quite a surprizing realization that you can write the letters of a message in a somewhat "sorted" way, but it is still possible to restore the message. The algorithm was only invented in the 1980's, but it is so simple and cute that even (bright) children can understand it and use it for "cryptograms". I am somewhat surprized that it was not invented earlier.

Speaking of sorting, the scientists contemporary to Galileo used it to "patent" their yet unverified ideas and hypotheses by publishing a "one-way hash" of the statement describing the idea by alphabetically sorting the letters of that statement. E.g. a hypothesis "Mars has two satellites" will be "Aaaeehillmorsssstttw". Of course, to be secure, the statement must be much longer.

1000 is too naive

[B.D.Mills]

500 deep algorithms, 1000 is maturity? To me this sounds a bit like like Bill Gates saying that 640K is enough for anyone, or the ancient Greeks saying that mathematics is mature because Euclid has codified his geometric axioms, or the head of the US patent office saying that everything's been invented in 1899. (All of which are probably apocryphal, but I digress.)

It's too premature. Computer science has been around for little over half a century. Who knows what will be discovered in the centuries ahead? Mathematics is the source of many algorithms, yet new discoveries are being made in mathematics even now. Don't stop searching when we get to 1000. There's still going to be many new and wondrous algorithms to discover for the geniuses of the future.

Re:Basic of algorithms

[Hercynium]

What about a function that calculates sucessive digits of pi??? I'm not trying to troll here, I'm just wondering. Definitions are important things in any area of academia! As far as I know the function for calculating pi is not a finite process (unless you count each digit an a discreet process)

A little side note: as a kid I used to crash both web servers and browsers by implementing this as a CGI script! :p

Re:Bubble Sort?

[coyote-san]

Why are you writing sorting routines anyway?

The fastest sort to write is the call to the library sort. qsort().

The lowest chance of writing a bug into a sort is the library sort. qsort().

The best known sort is the library sort. qsort().

Obviously other languages may have different library sorts, but IMHO any C/C++ developer who claims ignorance of qsort() is immediately and ruthlessly demoted to "2 years experience with little likelihood of succeeding in the field" category. This is a hard line, but I have yet to hear any reasonable excuse for being ignorant of the basic tools of your profession and being proud of it.

There are rare circumstances where I'll write my own sorts... but only after looking HARD for a way to call the library sort, and only because I've had a full year of graduate-level algorithms. Writing a good sort routine is *hard*, and it should only be done by people who know sorts cold. E.g., can you provide the running time and worst case performance of quick sort, Shell sort and heap sorts, and when those sorts might be worth the the effort instead of using the standard library sort?