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.
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.
Purely to add a little bit of the aesthetic to the list. [Check it out]
Dijkstra's Single Source Shortest Path Algorithm
Boyer-Moore Fast String Searching Algorithm
While I would consider myself geeky, I'm much more of a science geek than computer geek (even though I read /. on a daily basis) I have no real understanding of a computer algorithm, deep or otherwise, my search for "computer science deep algorithm" on google wasn't much help either. Could any one help the uninitiated.
We had to destroy the sig to save the sig.
You start with 2 sets of items that are related in some way. Next, you identify possible matching relationships. You then rank each relationship pair with some metric, sort the relationship list, and remove all lower ranking relationships. This leaves you with a list of the highest ranking relationships, with items appearing only once in the relationship list.
This was a trivial exercise in Lisp (where I first implemented it), but I've used it quite a few times in various other languages. Anyone know the name of this?
In a band? Use WheresTheGig for free.
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
Resolving dependencies between any number things requires this very useful graph sorting algorithm.
The Official Steve Ballmer Webpage
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??).
Good quote, too many chars. Seriously, the slashdot 120 char limit sucks!
Paul
One of the most important algorithms ever invented.
Seriously, how about Simulated Annealing or Genetic Algorithm?
It is so far-reaching.
linear programming, minimax game searches, network flow, primal-dual techniques for approximation algorithms......
Hashing algorithms. Stick that in your pipe and smoke it.
On basis of frequency, it's obvious that simple algorithms are the most common. Linear search of an array, bubble sorts (no matter how bad they are), and linked lists are so common that its hard to believe that anything could be more popular (or frequently abused)
int fib(n)
{
if(n==0|| n==1)
return n;
else
return fib(n-1)+fib(n-2);
}
in this you will find the meaning of life
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..
Chaos is a name for any order that produces confusion in our minds. --George Santayana
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.
Without it Slashdot would not exist.
"I have opinions of my own, strong opinions, but I don't always agree with them." -- George H. W. Bush
So what are the best texts on algorithms? I mean texts that describe the algorithm and cover the etiology and perhaps importance rather than just being a cookbook or leaving everything as an exercise for the reader?
The Knuth books? Or is there something better?
I'm surprised that nobody has mentioned finite element analysis as the most important algorithm. Just about any modern structure built today is analyzed to determine it's structural characteristics using FE analysis. From a car bumper to the Sears Tower, it's all about FE.
No temporary storage needed!
Jono
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.
Natural selection is the algorithm that solves all of life's problems :)
My favorite is Djikstra's Communicating Semaphores, along with the related algorithms documented in Djikstra & Riddle's paper "The 'T.H.E.' multiprogramming System".
With Mark Weiser's addition of the "T" primative (more commonly called "non-blocking P" i.e. "Try to P but if that would block return an error flag instead.") you have a fantastically powerful tool in a tiny amount of code.
For instance: I was able to implement a kernel for an actor-based, real-time, prioritized, preemptive multitasking system, including initialization code, an idle task, and a minimal startup task table (i.e. everything but the application tasks and device drivers):
- In under 512 bytes of code and initialization data.
- On an 8080.
Communicating P, V, and T, (along with a flavor of "V" doubling as a return-from-interrupt) are a complete set of primitives for such work.
For those not familiar, an "actor" in this context is a class such that each instance of that class or any subclass of it is a separate thread of execution. Messages are exchanged between threads via queues on semaphores rather than C++ member function calls / Smalltalk message sends, but otherwise all the object-oriented concepts apply directly.
Communicating Semaphores handle locking (like normal semaphores), message queueing, and resource allocation (by holding a queue of messages, each of which represents, or actually is, a resource).
"T" lets interrupt routines run initially as parasites on the interrupted task, then "T" a free-message-buffer queue, fill in the message, and "V" it to the incoming-work semaphore of the actual service routine as the interrupt exits - provoking a context switch if the service routine is higher priority than whatever was running. The interrupt routine can punt and return to the interrupted task if no buffers are available.
Bantam Dominique roosters crow a four-note song. Once you've heard it as "Happy BIRTHday" you can't NOT hear it that way
What about Newton's Method (and its variants like Quasi-Newton and Gauss-Newton)? This algorithm solves a system of nonlinear equations iteratively by solving a sequence of linear systems of equations. With Newton's method, one can use the extremely effective matrix decompositions (QR, LU, etc.) to solve nonlinear equations. Under typical conditions, it exhibits quadratic convergence (basically, the number of decimal places of precision double after each iteration). Plus, it is very easy to understand. (It is taught in many freshman calculus classes.)
Sorts of all types. Weve got bubble sorts for the kids. Merge sorts for singles. And quick sorts for couples and for all you real CS people out their tell me what the Big O stats for a merge sort are?
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.
The only thing necessary for the triumph of evil is for good men to do nothing. - Edmund Burke
There's a clever derivative called "Shell short", which might be what you're refering to.
It sends coarse combs across the data at first
Then it sends finer ones, and finally the last comb is the same as the 'exchange consecutive elements only' step in quicksort.
However, whilst it appears similar, it's actually very different because it uses an iterative refinement, first coarse, then medium, then fine. The number of phases is normally much closer to about n^0.4 in typical implementations, rather than n in BS.
To say it's like bubble-sort is to say quick-sort is like radix-sort. In some ways it's true, but it misses a lot of the point.
(One pass of an in-place binary radix sort is just like one pass of a quick-sort - notta lotta people know that! You lose the order-preserving nature, but you gain in-place. Basically you hard-code the pivots to be the odd multiples of decreasing powers of 2. b10000..., then b01000... and b11000... etc.)
THL.
It's in Knuth.
Keeping
Merge sort does, and it is much more efficient. That is to say it's a "stable" sort. That is one reason why the C library qsort() is often implemented as a merge sort!
All sort algorithms can be made stable by putting the original positions into the keys you are sorting.
-Kevin
Bubble sort is frequently the right choice and, more often, the "good enough" choice. I learned this the hard way a long time ago. Unless you're sorting at least tens of thousands of items, with today's computers it's unlikely the user will notice any difference in execution time regardless of the sort algorithm used.
Bubble sort has the huge advantage that it can be programmed in about five minutes without reference to any algorithm book and it's simple enough you're unlikely to make any mistakes.
Academia has incorrectly given bubble sort a bad rap. The same could be said about the "goto", but that's a different discussion.
My favorite algorithm, so simple yet so powerful, is the Fast Folding Algorithm, the one used by the seti@home client in your computer to detected repetitions in the signal, it's also used to detect unknown pulsars in space and I have experimented successfully with it on BPM detection in musical signals.
Look it up, you'll like it.
lone.
And the correct answer is: never.
Off the top of my head I can think of at least three major factors BubbleSort has in it's favor.
The fastest to write.
The lowest chance you will write a bug into it.
The best known. Any programmer who sees the comment /*BubbleSort*/ will have instant and complete understanding of your code. It is also the easiest to spot when it isn't commented.
BubbleSort is often the best choice for trivial tasks. A rock may not be the best tool for any job, but sometimes it is the simplest and most convient.
-
- - You can't take something off the Internet! That's like trying to take pee out of a swimming pool.
I have an unpublished "superalgorithm" in my desk drawer... Seriously, it is true.
But, should I first try to patent it or should I publish it to get scientific credit?
Cannot make up my mind. Please advice, with no nonsense arguments.
Pessimal Algorithms and Simplexity Analysis Read it---you'll like it. Find out the best algorithm to use if your boss makes you sort a list in Paris.
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?
For every complex problem there is an answer that is clear, simple, and wrong. -- H L Mencken
GCD is used for simplifying rational numbers. So it's used in pretty much any decent maths library.
And rational numbers have a *lot* of uses. CAD, spreadsheets, high precision calculations, financial figures where rounding is unacceptable etc.
I expect GCD also has implications for packing problems and complex scheduling algorithms where you need a quick check on which items are likely to "fit" together effectively. Anyone have experience of this?