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

Boyer-Moore String Searching

[Foresto]

I dont think I'd call it my favorite algorithm, but the Boyer-Moore string searching algorithm is pretty cool.

Re:Basic of algorithms

[GreenPhreak]

Dictionary.com defines an algorithm as:

A step-by-step problem-solving procedure, especially an established, recursive computational procedure for solving a problem in a finite number of steps.

Another way to think about an algorithm is this, you start out with input data in a given format, and then run some set steps on that input data until eventually it gives you output data. The nice thing about algorithms is that when they are correctly formulated, they can work without human intervention or without thinking/reasoning (just following the steps on the data). That is why they are particularly useful for computers. But they don't have to be limited to computers. Most recipes for food could be considered algorithms, that is, a set of procedures that bring you from input to output.

A good example of a computer algorithm is one of the many sorting programs. Quicksort, bubblesort, mergesort, heapsort...these are just different algorithms for taking a list of unorganized integers and by following their steps, you get a list of integers in numerical order.

When it comes to beauty in algorithms, people are generally referring to simplicity and efficiency in algorithms. Doing things in a way that most people wouldn't normally think to do them, yet doing them in terse and efficient ways (elegance).

I'm not exactly sure what is meant by a 'deep' algorithm, but I would think it would reference just how complex the task that the algorithm solves is.

My vote for best algorithms are: Sieve of Eratosthenes (an ancient greek method for finding a list of all prime numbers), and the Fast Fourier Transform, an algorithm that has revolutionized several industries.

Re:Basic of algorithms

[Sangui5]

An algorithm is simply a series of steps one can take that, once you have finished them, will have solved your problem. A deep algorithm is one that is especially useful, applicable in many circumstances, and has some inate cleverness that makes it non-trivial to come up with.

So, for example, an algorithm for searching could be:

1. For i first item to last item
2. If item i is what you are looking for, return it
3. otherwise, go onto the next i.

This isn't a very fancy algorithm, but it works, and it is useful in many many circumstances. Of course, it is also trivial to come up with (look at every item one at a time untill you find your goal), and therefore isn't deep.

It is interesting to compare an algorithm to a heuristic. Heuristics would make great algorithms, if not for the bugs. That is, a heuristic is a set of steps you can follow that are likely to solve your problem, but aren't guarunteed. In that sense, they're just buggy algorithms.

There are also approximation algorithms. Suppose your problem is to find the shortest route that will visit a set of cities, and return you to your starting point. This, btw, is a classic problem called the Traveling Salesman Problem, and is provably rather nasty to solve (it belongs to a class of problems called "NP-Complete"). That is, if you want the SHORTEST route, the best know method is to try all possible routes (and for even a relatively few cities, that's a lot). However, there are algorithms, that if you follow them, are guarunteed to give you an answer no worse than twice as long as the best possible. That is, we can approximate the answer, within some provable bound of optimal, with a set deterministic steps. (For the nitpickers, the approximation only works with Euclidian TSP, not general TSP, and .: doesn't give a solution to the Hamiltonian Cycle problem).

Any other questions?

Re:Binary Search

[Hater's Leaving, The]

Gotta agree with you, but not on its own.

I can't narrow it down to about 50, personally. Here're the broad-brush "highlights":

a) All of quicksort, mergesort, heapsort and radixsort.

b) FFT, DFT, their relatives, whilst I'm divide and conquering. Convolutions and shite too.

c) Graph algorithms including Kruskal's, Dijkstras. Coloring algorithms (useful for compilers).

d) Parsing algoriths, while I've got compilers in mind

e) String matching algoritms ditto

f) Compression algorithms - Huffman, Arithmetic, LZ*, BWT.

g) Cryptographic algorithms - Hashes, Private Key Fiestel Networks, Public Key 'bignum' techniques. I'll throw in CRCs here too as they're close to hashes.

h) Bignum algorithms - Karatsuba, Barrett, Montgomery, Oooh, I've had FFTs already, can I have them again?

i) Pure Maths - Euclid, XGCD. Addition Chains (e.g. Pippinger). Eratosthenes, Bernstien-Atkin likewise.

j) Trial division, Fermat's Method, Brent/Pollard Rho, Pollard/Williams P+/-1, Lenstra's ECM, Quadratic Sieve, (S/G)NFS.

k) Applied Maths - Newton-Raphson, Runge-Kutta, Tchebyshev interpolation.

Too many to count...

THL