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

Bubble Sort?

[cjpez]

Does the Bubble Sort algorithm count as important?

Re:Bubble Sort?

[Odinson]

Without bubble it would be impossible to obtain a bell curve in computer science classes.

You're damn right it's important.

Re:Bubble Sort?

[cjpez]

lol. See, its uses go on and on! Soon we'll find it cleaning up the environment and solving all of the world's complicated social problems!

Re:Bubble Sort?

[Garin]

This is a standard interview question for me, when I interview programmers. "In what case would you want to use a bubble sort?" The answer, my friends, is very simple. The bubble sort is extremely fast when your list is almost always very nearly sorted, with very few (or no) elements out of order. For some algorithms, the already-sorted order is the worst case. For the bubble sort, it's the best case. So if you have a data structure that is updated frequently, but the order of the elements very rarely changes, you can use a bubble sort without being too embarrassed. :)

Re:Bubble Sort?

[Matthew Austern]

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.

Re:Bubble Sort?

[Hater's Leaving, The]

"Quick Sort is recursive"

Recursion adds _bugger all_ overhead.
What kind of machine are you using - is it based on punched cards? Recursion is no more expensive than a loop overhead. How many loops does bubble-sort have to set up?

"and then do bubble sort on those. "

I hope not. I mean, you've got selection, insertion, in-place merge, and hard coded minimal exchange sorts to chose from; there's no need to bubble. Ever!

"
There are also algorithms that do matrix multiplication in O(n^2.blah) time. The naive method is cubic. How come no one uses these fancy methods? Because they are a pain to implement and require n to be so large before they actually start performing better than the naive implementation.
"

Yeah but the 2.blah you're thinking about is 3*ln(8)/ln(9) = 2.84. Which is damn close to 3 compared with how vastly different O(n^(1+o(1))) is from O(n^2) in the sorting examples.

THL.

Re:Bubble Sort?

[Gary Yngve]

To address some of your points:
Hell yeah, recursion adds overhead. If it cannot be readily optimized into iteration (such as tail recursion), you need to maintain stack frames, allocate new local variables, etc. For tree recursions, such as quick sort (pick a pivot and resursively screw with each side), it is very hard to make the algorithm iterative without implicitly mimicing recursion or a stack.

Yes, I was not thinking perfectly when I claimed that a good quick sort implementation would use bubble sort when the chunks got small enough. They may use some other quadratic sort. But I am still willing to bet, that when tuned properly, using the bubble sort then is more efficient than using quicksort all the way down. I don't want to make any claims about performance on various architectures because it all boils down to freakly things such as cache hits. When I try to explain things for the layman, sometimes some details slip by, just waiting for the tight-assed dork to jump on.

By 2.blah, I was actually referring to the better results, rather than the boring divide-and-conquer method you cited. I recall results as good as n^2.23 or so, and I believe it is still unproven if matrix multiplication can be quadratic.

Re:Bubble Sort?

[Garin]

Never? Can you prove that there are no data structures and change patterns that do not result in the bubble sort being the fastest over all? I'd be very interested to see that proof.

I still maintain that there may be a situation in which a bubble sort is the right choice, and that the question is a good one. Maybe I can't think of it (and honestly, I've never used a bubble sort in any code I've written) and apparently neither can you.

For me, the most important thing to think about is to consider the situation in which you're using the algorithms. I ask the question, because I want to challenge the person I'm interviewing. The people who immediately laugh and say "Never!!" without thinking about it for a minute get passed over. If someone thought about it for a minute and replied what you did, I'd be happy with that. I'd be just as happy if someone thought about it for a minute and said, "maybe some cases in which the list is already sorted, but I'm trying to imagine how that would work".

There may be a pattern to the way the data is changed over time that means that bubble sorts will be the best. I want people to think about that, rather than laugh about the bubble sort as a terrible algorithm. It's not -- it does what its supposed to do and nothing more. It just may be an algorithm that has an extremely narrow range of applicability.

I would definitely teach the bubble sort, even if the lesson is, "sometimes there are simple and easy-to-use algorithms that are rarely the most useful." People have to learn to recognize that.

Re:Bubble Sort?

[harlows_monkeys]

Other than that, simplicity of implementation. I can knock out a bubble sort without thinking, whereas anything else requires actually looking something up.

If you need to look up straight selection sort, you've got problems. It is simpler than Bubble Sort, and it is twice as fast.

Re:Bubble Sort?

[khuber]

Bubble Sort retains the initial ordering of equally ranked items. Most other sorting algorithms don't.

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

Re:Bubble Sort?

[Garin]

It's more like you have to consider real-life situations individually. My point is very much like what you said -- you can construct a zillion different algorithms to do something, but the vast majority of them will be practically useless in anything but a really weird situation. Recognizing when they are and aren't useful is an important skill. And most of the time, you'll go with the tried-and-true quicksorts etc.

However, it's important to think about each situation. Pure algorithms are usually designed with the general case in mind. Individual situations, however are always specific cases. Most of the time, the general solution is obviously useful. Sometimes, however, there is a special case that might not fit the mold, and one of these crazy one-off algorithms might fit the bill exactly.

In my mind, you will not get a job with me if you cannot see what makes each application of an algorithm unique. Computer science optimizes the general case. Real-life programming optimizes the special case that you're dealing with in your particular program.

Re:Bubble Sort?

[adminispheroid]

But in -any- case, bubble sort is VERY fast when the list is already sorted. And yes, it is very useful in practice.

I recently invented an even faster sort for the case that the list is already sorted:

#define lightning_sort(x) (x)

Unfortunately, it only works in that one case.

Re:Bubble Sort?

[patchmaster]

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.

Re:Bubble Sort?

[Alsee]

"In what case would you want to use a bubble sort?"
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.

-

Re:Bubble Sort?

[zCyl]

I have yet to find any case, anywhere, where bubble sort is the right choice.

That's because of your definition of "right choice". Bubble sort is complete crap, of course. But let's say hypothetically you are writing a program in some obscure scripting language that you just learned an hour ago, you want to sort less than a thousand elements, and you want to write the program in a few seconds. Do you implement an efficient sorting algorithm? No. You type in the quickest thing possible to get the job done. For an administrator, the most common programming is probably quick hack jobs to get something done with very little invested programming time. For software development, sorts should be modular, and bubble sort can be thrown in for a prototype since it's so quick to type up, then replaced with something useful later. It's often easier to develop a program by getting it to do SOMETHING as early as possible, and then incrementally modifying it to be efficient, extensible, and adhere to specifications. The crap algorithms are useful for this intermediate step.

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?

Re:Bubble Sort?

[colmore]

Actually, even in those cases, there are better algorithms that run in a similar amount of time.

But running time isn't the only consideration.

In applications where speed of production matters more than speed of operation. (Prototyping, scripting, etc. etc.) bubble sort is just fine. it can be coded quickly with minimal debugging.

unless your job is doing data structures all the time, you'll probably have to look up QuickSort and go through a few debug cycles to get the thing working. there are times when this inconvenience outweighs performance considerations.

(for instance, in a timed coding contest, such as the one mentioned the other day, i'd use a simpler sort to save time to concentrate on the more difficult aspects of the program)

of course i'm not advocating this for final, published, software in any case i can think of.

Re:Bubble Sort?

[Stary]

Actaully I was wrong about the 2.84, it's 3*ln(7)/ln(8) = 2.80 (7 from 8 not 8 from 9!). Strassen's IIRC.

Indeed theres a ~2.3 theoretical method (Winograd), but the scaling constant is huge, and for most purposes the algorithm is of no use for anything short of unimaginable.

Not only for most purposes... for all purposes. In order for this algorithm to be useful, n has to be larger than the amount of atoms in the universe...

Re:Bubble Sort?

[cjpez]

Yes, I have a deep and undying hatred of Bubble Sort and feel compelled to mock it openly at every opportunity. I need to do this because otherwise my ego would deflate to the point that I'd be a miserable stain of biologic waste slithering around on the floor.

Re:Bubble Sort?

[Garin]

Sounds good to me. There's a situation where the bubble sort is the best thing to use. :)

One of the answers I can come up with is that you can use the bubble sort method when really do want the items to bubble up naturally and somewhat slowly. That is, the goal is not necessarily to completely sort everything in the smallest amount of time/space, but more like to have the list slowly tend toward sortedness, even as it may be changing and diverging from sortedness.

The thought is that it may be useful to do a single pass of the bubble sort, then do other stuff which might even occasionally mess up the order a bit more, then go through for another pass, and so on and so on. So as time goes on, the list stays more or less sorted, and it sorts organically and smoothly, but is rarely in perfectly sorted order.

Yeah, it's a liberal interpretation, but that's fine. I'm not sure where it would be useful, but I bet I'll find a use for it one day.

Re:Bubble Sort?

[joto]

It'd better be. For almost any situation, it is better to rely on your own sorting routine, than C's standard librarys qsort.

Case in point:

1. the algorithm qsort uses is undocumented (it's said to be "quicker sort", which nobody seems to really know what is, but most people tend to assume is quicksort).
2. It relies on function pointers to do comparison, etc. That has to be slow.
3. Because of it's need to be overly general, the interface is too complex to remember, and just writing your own sorting routine is probably more maintainable.

On the other hand: STL's sort is:

1. Well, still somewhat undocumented in what it does, but at least it offers you the choice between a simple sort and a stable_sort.
2. Fast, because it relies on templates, and not function pointers.
3. Relatively easy to understand, considering you have a basic understanding of STL.

Does STL sort bloat your program? Yes, if you use it lot's of places for lot's of different kinds of arguments. Is this bad? No, you would get that kind of bloat anyway, if you had to write each sort-routine individually. For most tasks, moderately bloated binaries are a better tradeoff than overly complex interfaces or slower code due to generality through function-pointers, boxing of values, etc...

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.

Re:My pick goes for RSA

[B.D.Mills]

It is simple enough that can be described in a piece of paper...

Any algorithm can be described on a piece of paper, provided you can get pieces of paper that are large enough.

Re:My pick goes for RSA

[TedCheshireAcad]

No way man the Number Field Sieve ownz RSA.

:-)

Re:My pick goes for RSA

[r00tarded]

or a infinately long tape divided into squares, each of which is inscribed with a 0 or 1. fed into a machine...

Re:My pick goes for RSA

[Nightpaw]

or a infinately long tape divided into squares, each of which is inscribed with a 0 or 1. fed into a machine...

Hey, what if you used some kind of ferrous material embedded in a tough substrate and encoded the 0s and 1s electromagnetically?

Mandelbrot set fractal generation

[PyroJimmy]

Purely to add a little bit of the aesthetic to the list. [Check it out]

My favorite algorithm

[jwinter1]

Of course,

Lather. Rinse. Repeat.

Re:My favorite algorithm

[seanadams.com]

Lather. Rinse. Repeat.

This fails the first requirement of an algorithm, according to Knuth:

1 Finiteness. An algorithm must always terminate after a finite number of steps.
- Knuth, TAOCP Vol 1, Page 4

You know there's some guy still in the shower...

Re:My favorite algorithm

[blazin]

I think at some point this algorithm should throw the outOfShampooException thus making it terminate after a finite number of iterations.

Assuming everything shuts down correctly, the destructor or finalization method should be something along the lines of

getOutofShower();
self.dry(self);
self.dress(s elf);

Re:My favorite algorithm

[deander2]

alright, not to nit-pick a joke here, but do you really need to pass self a reference to itself? :-)

Re:My favorite algorithm

[Syberghost]

Ok. Try this one:

:(){ :|:&};:

I promise you that will terminate after a finite number of loops.

Re:My favorite algorithm

[Jagasian]

Wait, is that always terminate on all inputs? If so, according to that criteria, a Java Virtual Machine isn't an algorithm. Nor is any universal (in the sense of Turing) programming language interpreter. Apply the diagonalization method, and its pretty obvious.

I always thought that Kleene's partial recursive functions were a good enough description of "algorithm".

Re:My favorite algorithm

[Bios_Hakr]

Yep, it most definately did terminate...asshole:)

Re:My favorite algorithm

[Fulcrum of Evil]

It's a variant on a vorpal fork bunny. Try typing it into a bash shell on a machine you won't mind hard booting

Re:My favorite algorithm

[Syberghost]

$0&$0

Sure, but mine works from the shell prompt; yours requires wrapping.

If you wanna wrap, then try this one Joey Hess gave me:

perl -e 'fork while time'

...which has the added benefit of being poetry.

Rank alg: Anyone know the name of this one?

[helixcode123]

I don't know the actual name of this algorithm. It's quite useful if, for example, you want to match items from two lists.

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?

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?

[dhogaza]

Well, one world-famous mathematician was once quoted as haughtily saying that "Computer Science is just a trivial subset of Discrete Mathematics"...

Re:Algorithms?

[Anonymous Coward]

There is a big difference between programming and computer science.

Patterns have more to do with programming than computer science.

My one professor was fond of telling us everytime we showed up in class, not understanding his advanced statitistical discussions of machine states and the like:

"Oh yes, you are programmers, not Computer Scientists."

Re:Algorithms?

[pmz]

Patterns and Algoritms are apples and oranges.

Patterns are reusable data models, whereas algorithms are reusable procedures that operate on data models. Sometimes a pattern does include an algorithm (factory objects are an example, where methods are needed to overcome the lack of multiple inheritence in a language).

Perhaps one way of putting it is that data models capture reality, and, then, algorithms do something interesting with that reality.

Data models and algorithms are about all there is to CS. Data models and algorithms pretty much wrap up all the other sciences and the arts, too, since that's just how humans think about things.

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

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:Boyer-Moore String Searching

[IvyMike]

For some reason, I like string searching algorithms too. Check out this monster list of thirty or so different exact string searching algorithms, complete with description, code, and an interactive java demo for each one.

I never thought I'd spend hours typing "baaabbabbabc" into a java applet until I found that page. :) Educational and cool.

Off the top of my head

[td]

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

Re:Off the top of my head

[cpeterso]

I like bubble sort.

Re:Off the top of my head

[cpeterso]

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.

Re:Off the top of my head

[cpeterso]

oh yeah, 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.

Re:Off the top of my head

[blazin]

I taught a C++ data structures course and used bogo-sort on a test to see if the students understood O() notation. I explained what it was based on using real word example of playing 52 card pickup until the cards were sorted, then left them to figure out if it would have a good runtime or not.

Re:Off the top of my head

[Pseudonym]

It's an interesting definitional problem as to what counts as "deep". My intuition (which may of course be faulty) suggests that a "deeper" algorithm is one that can be either used widely or extended to other areas. This would make merge sort "deeper" than quick sort and DMC or PPM "deeper" than L-Z compression.

Some more suggestions:

• A* search.
• The simplex method.
• Aho's DFA state minimisation algorithm.
• Risch integration.
• Dijkstra's shortest path algorithm.
• The "Graham scan" convex hull algorithm.
• Deterministic linear-time selection.
• Monte Carlo simulation. (Obligatory comment on patents held by td's employers deleted.)
• Pretty much anything by Robert Tarjan.

Re:Off the top of my head

[spencerogden]

From a quick perusal of the paper it would seem that a max number of forward pointers is set, and that each node could have this number. It would seem that an array of say ten points would not be that bad.

Diffie-Hellman, too

[paulschreiber]

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

Paul

An important algorithm I use everyday...

[gpinzone]

begin
while alarm ringing
cover head with blankets
mprecate the onerous noisemaker softly
consider turning the damn thing off
if feeling remarkably hyperactive
then
lethargically slither out of blankets
sinuously stretch out arm
sigh
bang it to kingdom come
else
go back to sleep sweet sleep
endif
if hear name being called
then
see who it is
if kid brother/sister
then
ready
aim
fire
watch baneful clock execute a parabolic trajectory
in approximate direction of youngster
if target intercepted
then
ignore howls for Amnesty International
else
swear a thousand maledictions
endif
else if father
then
get out of bed hyper-quickly
if feeling watched
then
turn alarm off gently
else
kick alarm off gently
endif
else if mother
then
scan her for arms, especially those prohibited by
Geneva Convention
if result is affirmative
then
begin negotiations
else
pretend not to have seen her
increase snoring intensity
endif
endif
if feel something cold and wet being sloshed onto
blankets
then
yell blue murder
get out
endif
endwhile
end

Dinoj Surendran @ 1995 - no rights reserved

Hello World

[Wolfier]

One of the most important algorithms ever invented.

Seriously, how about Simulated Annealing or Genetic Algorithm?

Fast routing agorithm

[zero2k]

Ok, since we're all stuck on the Internet, which is something that has to grow in size continually, I'd say one the routing algorithm has got to be one of the most important. The Internet can't exist without it. Also to note is that we do need faster routing algorithms to cater for future addressing.

simplex method

[Gary Yngve]

It is so far-reaching.

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

Re:simplex method

[mindriot]

Actually, if you say minimax, I'll have to say I prefer alpha-beta pruning...

Three favorite algorithms

[Anonymous Coward]

* Randomized primality testing
* Gaussian elimination
* Euclid's gcd algorithm

All three run in time polynomial in the bitlength of the input, yet the first thing that springs to mind is exponential time:

primality testing: try dividing by every number between 2 and sqrt(N).
matrix determinant: the straight definition has n! terms. With Gaussian elimination you can compute the determinant in O(n^3) time.
gcd: factorize both number and compare? (ugh)

Gotta appreciate algorithms that show real insight into a problem.

bogosort

[paulschreiber]

you can't forget bogosort. :-)

Paul

Re:My favorite algorythm

[geophile]

First of all, it's "algorithm". Second, an algorithm, by definition, terminates...

Favorite algorithms

[gewalker]

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)

Re:Favorite algorithms

[PD]

Hashes are just so useful. If I were among the group of people working on the C++ Standard Template Library I'd have stuck hashing containers in. Right now, things like hash_map are not a part of the official standard, BUT there are some good implementations out there. Supposedly, hashing containers are going to be in the next standard - hooray!

How about CSS?

[JonWan]

The "Content Scrambling System" it seems pretty Damn important to the MPAA and Congress. They even passed a law (DMCA) to support it..

discrete fast fourier transform

[Gary Yngve]

Anything from Photoshop to cellphones benefits from fast signal processing. A little complex analysis turns an O(n^2) algorithm to O(n log n).

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

Shallow algorithms

[csbruce]

1) Patent the obvious
2) Sue
3) PROFIT!!

confusing theory with engineering?

[Anonymous Coward]

IMHO, asking "what are the outstanding problems for which algorithms would be immediately placed in the "Top 1000" category?" reveals a misunderstanding of Knuth's article (All Questions Answered). In regards to "deep algorithms", Knuth was speaking of the maturity of computer science as a theoretical discipline, not as an engineering science. An algorithm is "deep" because it is beautiful (to use another of Knuths words), that is, it demonstrates a penetrating insight into the nature of computation. In this regard, the actual problem domain addressed by any given algorithm, in and of itself, is irrelevant. In fact, in the same article, Knuth is asked to give the five most important problems in computer science. He replies that he "doesn't like this top ten business", but prefers the "bottom ten". What is important, he says, is "the little things ... the stones in the wall".

The CORDIC Algorithm

[Caractacus Potts]

COordinate Rotation DIgital Computer

This algorithm is implemented by most FPUs and even some PGAs to calculate trigonometric and hyperbolic functions. It replaces the evaluation of those power series you've already forgotten about from school with a clever combinations of bit-shifts and additions. Back in the days when multiplications were much more expensive than additions, this is how it was done.

Re:Basic of algorithms

[nickynicky9doors]

Author: David Berlinski

Title: The Advent of the Algortihm

Publisher: Harcourt

Re:Theoretically interesting/Practically irrelevan

[Anonymous Coward]

First off, it's clear that you have a very narrow view of what is actually done with computer science. Granted a lot of what the casual or application programmer deals with can seldom involve the creation of a new algorithm. However, the field of algorithms is constantly expanding.

Examples would be:
A guidance system
Any artificial intelligence
Image manipulation
Video games (quake engines!?!?!)
Telecommunications routing software
VLSI Design
etc..

As far as I know, that stuff is pretty important in the real world. Yes, algorithms exist to do pretty much all of those (in fact, with brute force, many are trivial). However, we are constantly looking for "better" algorithms. If new algorithms are not relevant, why would companies, like Intel, pay hundreds of millions of dollars for a program that would optimally lay out the elements on their chips for them?

The pr0n algorithm

[NanoGator]

I have no idea how it works, but search engines have no trouble finding me pics of nekkid wimmenz. Kudos to whoever invented it!

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.

Re:Prune your betas!

[debrain]

It also has useful applications in pruning the SAT search space.

Re:Prune your betas!

[SplendidIsolatn]

The only problem with A/B (and I love it and have implemented it a number of times in games) is that it only works for abstract strategy games with a zero-sum score. (meaning, one player is winning by the exact same amount the other player is losing...thus, zero sum) So chess, backgammon, checkers, hex, and any other game with a zero-sum board evalution it'll do fine. Otherwise it won't work very well.

Plus, an A/B search is only as good as the method you are using to evaluate the game. I'll use minmax and a good heuristic rather than A/B with a bad one. Just some food for thought.

Re:Prune your betas!

[gregbaker]

Alpha-Beta pruning is "deep"? Isn't "If you did this and the outcome is be horrible, don't do that; if it would be really good, do it" not a more-or-less complete summary of it? This is the thinking that leads to software patents.

And, as another post mentioned, it's a heuristic, not an algorithm.

DeCSS

[mikeee]

Clearly, the most important algorythm. ;)

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:Are sorting algorithms "deep"?

[a_n_d_e_r_s]

I just live the bubble sort.

It is also the best algorithm to use to
sort a list....

...

... when there a few items in the list.

Hash tables and sort algorithms

[igrek]

Perhaps, hash tables and quicksort are the top software algorithms. They both are usually hidden from programmers (unless you're coding in low-level programming language), so we don't always $pay->{$attention} to the details.

Just think about it, how many times the hash tables and sort algorithms were used to render this very page?

van Jacobson's congestion avoidance and control

[Subcarrier]

Without it Slashdot would not exist.

But smart people won't ignore the topic...

[Da VinMan]

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.

Re:But smart people won't ignore the topic...

[jgerman]

That's ridiculous, you don't disregard them, you build on their work just like every other science, you stand on the shoulders of giants, maybe you become a giant for the next generation, but real progress is NEVER made when you disregard what came before you.

Re:But smart people won't ignore the topic...

[jgerman]

Fair enough, perhaps we are differing on the term disregard. I took your use of it to mean more of an ignore, while I feel that even the mistakes of the past need to be used to further technology in the future.

Re:But smart people won't ignore the topic...

[Da VinMan]

Apparently, you missed the "I agree that we should use the frameworks we are provided in order to get the highest productivity" part of my statement.

I'm not an idiot. In fact, my customers do depend on me for high quality and highly maintainable solutions. I'm pretty good at making my customers happy too.

Besides all that though, I agree with you, especially on the fact that the fundamentals are hard. The fundamentals keep getting harder too as folks find more and more ways in which to apply those implementations. Think about the linked list example. Now think about the linked list example in a multi-threaded situation. Now think about the linked list example in a multi-threaded *and* garbage collected situation. All of those are very different problems which add permutations of complications onto a very basic idea; the implementation of which becomes more complicated with each new dimension of functionality.

BTW - You could relax your finger a bit on that flamethrower. You're coming across as an over-reactive moron yourself since you don't appear to have read my whole post. I doubt that you are in fact an idiot, so why not put your best foot forward?

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?

Dr. Fun cartoon

[PD]

This cartoon is about Knuth

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

Re:Algorithm to understand what's an algorithm.

[nickynicky9doors]

I'm not trolling, but wouldn't your injunction: 'until understood', fail as a step in an anlgorithm?

algorithm example: long division

[upper]

An algorithm is a process for doing something. Perhaps the best example for non-programmers is long division, the way you learned to divide multi-digit numbers with pencil and paper. The basic mathematical definition of division is that it's the inverse of multiplication, which is a fine definition of an operation but doesn't tell you how to divide two numbers. Long division is a procedure which gives you the answer. Other procedures are possible.

This may sound like I'm describing a program, or a piece of code. A piece of code can implement an algorithm, but many different pieces of code can implement the same algorithm. An algorithm has a specific mathematical context in which it works -- e.g. the dividend is not zero. The piece of code has specific to a computational context -- written in C, divisor is in variable x, dividend is in variable y, quotient ends up in z, all of which are single precision floating point.

What's a deep algorithm? That's subjective, but I'd say it has to either be non-obvious or become obvious only after you learn a nontrivial piece of theory. There's probably an aesthetic component as well.

Re:algorithm example: long division

[magic]

I believe algorithms are also guaranteed to terminate in finite time.

-m

Re:My favorite algorythm

[protonman]

Er... no. You're wrong.

Here I'm citing from my "Introduction to the Theory of Computation" book from Michael Sipser from MIT (ISBN: 0-534-94728-X):

"Informally speaking, an algorithm is a collection of simple instructions for carrying out some task."

There probably is a real definition somewhere but I think it sufficies to say that algorithms are things done by Turing Machines (that's why Turing invented them in the first place), and since the a=a+10 stuff from the parent can be done by a TM, it's an algorithm.

Lewis Caroll's day of the week algorithm

[madmancarman]

My personal favorite (and one I use all the time) is Lewis Caroll's algorithm that allows you to find the day of the week (Monday, Tuesday, etc.) for any given date (for example, August 15, 2001 would return a Wednesday). It's pretty useful with our school's attendance system, which is written in Perl and run on Apache.

Personally, I find it interesting that this algorithm was developed by the same guy who wrote Alice's Adventures in Wonderland. A guy I teach with showed it to me a couple months ago, and I'm planning on using it in class soon to teach some programming concepts.

First they ignore you, then they laugh at you, then they fight you, then you win. -- Gandhi

Re:Basic of algorithms

[leifw]

(Stolen from http://www.digitale-medien.de/beckert/03_Definitio ns.htm) Donald E. Knuth gives in his book "The Art of Computer Programming" (1968) five criterias to determine if a process is algorithmic:

1. The process must be finite
2. Each step must be clearly defined
3. The process may have input
4. The process must have output
5. The process must be effective

To be finite, the process must end after a predictable number of steps. Each step must be unambiguous. The process may require input (parameters) to solve the problem but when complete it must return a result. The process must demonstrate effectiveness by solving the problem in a "sufficiently basic" manner.

Not all answers are in Knuth

[Goonie]

Further to your point, there is still a need for new algorithms.

There are plenty of real problems for which the "best" algorithm doesn't yet exist, and you come across them both in academia and in industrial settings.

Best texts on algorithms

[merkel]

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?

Finite Element

[the eric conspiracy]

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.

In place swap of two variables

[WeeGadget]

OK... It's not deep... but using XOR to swap the value of two variables is pretty fun.
No temporary storage needed!

// Swap A and B
A ^= B;
B ^= A;
A ^= B;
// Swap of A and B complete

Jono

Re:In place swap of two variables

[Tony Hoyle]

Indeed - the last time this came up I did some benchmarks. The 'old fashioned way' using temp variables when optimised runs about twice as fast as the xor version.

In not-quite-assembly it looks like:

foo(cx,dx)
mov ax,cx
mov bx,dx
mov ax,ax xor bx
mov bx,bx xor ax
mov cx,ax
mov dx,bx

vs.

foo(cx,dx)
mov ax,cx
mov bx,dx
mov cx,bx
mov dx,ax

Re:In place swap of two variables

[Fulcrum of Evil]

In somewhat saner assmbly, it looks like:

swap(r4, r5)
xor r4, r4, r5
xor r5, r4, r5
xor r4, r4, r5

versus

mov r6, r4
mov r4, r5
mov r5, r6

of course the real answer is 'oh, that's nice'

Quantum Algorithms

[Lictor]

I'm going to make the brave supposition that quantum computers will overcome the decoherence problem and scale to non-trivial sizes.

(Even if this doesn't happen, the following algorithms still deserve honorable mention for being the first to make use of quantum parallelism to give results unattainable thus far by classical algorithms):

- Shor's algorithm for factoring and discrete log
- Grover's search algorithm

My favorite AlGoreithm

[SecurityGuy]

Gotta be inventing the Internet! How could you top that?

Re: My favorite AlGoreithm

[aralin]

Gotta be inventing the Internet! How could you top that?

You are in wrong section here. This is 'AlGoreism'

Re: My favorite AlGoreithm

[Hal-9001]

If you read Knuth vol. 1, you'll discover that "algorism" is a deprecated word for "algorithm", so the pun still works... ;-)

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.

Re:Theoretically interesting/Practically irrelevan

[hij]

Do you mean that it is irrelevant to you? For some people, Knuth for example, the obsession with algorithms is very important. Thank goodness that they did do this so that you and I could borrow their work and not invent it ourselves. Some people spend a great deal of time trying to construct and refine algorithms. I would guess that few people in our society care, but it is greater than .001% of the people in the scientific computation communittee.

Douglas Adams was right

[Dances with Sheep]

Natural selection is the algorithm that solves all of life's problems :)

Djikstra's Communicating Semaphores

[Ungrounded Lightning]

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.

Parsing, interpreration and game theory

[MagikSlinger]

There's some good ones (like QuickSort) that should be #1, but here's a random collection of some algorithms I find interesting:

• The recursive-descent parser generator
• Regular expression to DFA algorithm (it's its own proof!)
• The Lisp interpreter written in Lisp (and no you can't use eval). An elegant algorithm demonstrating how data and code can become one.
• The Mini-Max Algorithm
• The Backfeed Neural Network Algorithm
• Euclid's greatest common divisor algorithm (technically not a computing science algorithm)
• Mandelbrot set algorithm
• The Ray-Tracing algorithm

Bresenham Line Algorithm

[sl3xd]

My vote: The Bresenham Line algorithm. It provides the most efficient method to draw arbitrary lines on a raster (ie. pixel-based) screen. All 3D Graphics are heavily dependant on this beautiful algorithm.

There have been improvements to the Bresenham line, effectively quadrupling the draw speed over the base Bresenham algorithm.

But the base aspect of Bresenham's work is critical: It allowed the drawing of lines on our computer screens using integer, rather than floating point, arithmetic. 3D Graphics wouldn't be the same without his contribution.

Re:Are sorting algorithms "deep"?

[Tony Hoyle]

I read in Dr.Dobbs years ago of someone who'd modified a bubble sort so it could outperform a quicksort... it worked, too. He called it a 'comb sort' but I've not seen anything of it since.. I expect his figures were a bit too optimistic (I wish I could remember the algorythm... all I can remember was it was almost exactly the same as a bubble sort with a few lines changed).

Re:If you have to ask

[sinserve]

I was going to protest this unfair moderation of my post (-1 Troll)
But I will execute Jessus's favorite algorithm, and turn the other cheek.

.solution:
mov eax, [input]
cmp eax, bitchslap
jz .solution
mov ebx, cheek_number ; boolean, toggles between left and right cheek
neg ebx ; inverting the value, changes cheek number
mov ah, [turn] ; movement type
mov dl, PORT_CHEECK ; /dev/cheek's port# defined in asm/i386/ioctl.h
out dl, ah ; write to the cheek port
return

You're kidding yourself

[edhall]

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.

-Ed

Re:You're kidding yourself

[t]

Man that's a crappy example. You've never heard of the electric motor? Too quick to post perhaps?

Also, your example also exemplifies why you need to understand the tools you use. What if you were in the midst of a storm, standing in pools of water sawing 2x4's to secure bits of your house. If you understood the tool you would know that water is not compatible with its use.

One day all we'll have are people who only know how to plug doohickeys together.

t.

Re:You're kidding yourself

[edhall]

Like I said, you're only kidding yourself.

What makes more sense: learning a long list of facts concerning each of a long list of algorithms, or learning the much smaller number of principles behind the algorithms themselves? The latter sort of knowledge -- "deep" knowledge -- is harder to acquire, but it is a much more useful form of learning than the rote memorization of facts. With it, you'll have the insight to evaluate the suitability of an algorithm without dredging up a long list of memorized do's and don't's.

Understanding an algorithm lets you adapt it rather than using it blindly. For example, the same principle of partitioning that's behind quicksort also yields fast algorithms for finding the top N items in a large list without having to sort the entire list. It also allows you to adapt quicksort to work on linked lists without first copying them into an array. There are dozens of variations of the principles behind quicksort that have potential uses -- variations you're not likely to find in a library. (I only chose quicksort because some many posts here mention it; most algorithms have similar mutability.)

If you don't understand the principles behind what you do, you've no right to call yourself an "engineer."

-Ed

Maybe I'm Shallow

[4of12]

But the first time I saw a recursive algorithm (eg, that for n!) I was quite impressed.

Re:Maybe I'm Shallow

[kubrick]

Recursion may not be deep, but it is definitely elegant :)

One Vote for Newton!

[jat2]

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

A considered list with footnotes

[Tupper]

is at The Computer Science Hall of Fame

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: 1000 is too naive

[aralin]

Maybe, if you'd read what prof. Knuth said, you'd know he mentioned the 1000 algorithm as a START. About the number of algorithms the CS should have to START to be recognized as a relevant science.

Re:My favorite algorythm

[walt-sjc]

Just run it under Windows and it terminates eventually just fine! Therefore it's an algorithm!

(I hated to lose the ability to mod, but I couldn't resist! :-) )

My Personal Favorite

[cube farmer]

Since I'm not formally trained as a computer scientist (I'm merely an information technology major, sorry), I can't offer much in the way of "deep" algorithms to this list.

However, I can poke fun...

My personal favorite algorithm is:

1. Launch Web Site
2. ??????
3. Profit!

(Ducks)

Re:My Personal Favorite

[Alsee]

The Dot-Com gnomes!

-

Re:Are sorting algorithms "deep"?

[Hater's Leaving, The]

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.

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

Hey, what about computational geometry?

[xelph]

I would vote for Fortune's algorithm to compute the Voronoi diagram. It is a beautiful algorithm, which almost gave me an orgasm when I looked into its guts. I am shocked that no computational geometry algorithm was included in the top 10 list. Not only have they proved already to be extremely useful, but they are alos going to be more and more important in the future (especially in my case, working on next generation user interfaces).

Google's Mentalplex algorithm

[Oink.NET]

Try out Google's Mentalplex search.

Or read the FAQ.

For best results, you may need to reference the illustrations of proper use.

I believe it breaks several laws of computational complexity, including NP-completeness and the halting problem.

Skip list problems

[cpeterso]

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.

Re:Skip list problems

[Subcarrier]

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

For a really long skip list you should consider using a skip list to store the forward pointers.

What, no else if SO?

[T1girl]

What then? Even if this was written by a fairly young teenager in 1995, it's kind of pathetic that seven years later there isn't some possibility of waking to the sound of a lover's voice, even if only in the imagination.

Actually he invented Spam

[Ungrounded Lightning]

My favorite AlGoreithm [has] Gotta be inventing the Internet! How could you top that?

Actually what Al Gore invented was Spam.

Really.

(The legislation he supported to open the Internet to commercial exploitation is part of why we can't do much about the spammers without further legislation.)

His wire-all-the-schools-for-internet was also a trojan horse. It gives government an excuse to censor the net down to elementary-school level to "Save the Children".

the Art of Computer Programming

[danny]

Before trying to answer any of those questions, you should go off and read Knuth's The Art of Computer Programming ...

Danny.

Obviously...

[Pig Hogger]

... 42!!!

That's what deep thought was all about, no?

Everyday life needs algorithms

[Pinball Wizard]

I wonder why geeky CS people have never applied algorithms to some of the vexing problems of everyday life.

For instance, figuring out that most people exercise with an exponential algorithm and devising an O(log n) way to get ripped abs in less than 5 minutes a day.

Or figuring out the shortest distance between meeting a beautiful woman and getting laid.

Devising a "quick sort" routing that got you out the door in the morning 5 minutes after waking up.

Perhaps an exponential growth algorithm for our bank accounts.

Why is it we only apply algorithms to move bits around?

Another Exception

[restless_ne'erdowell]

Don't forget about the outOfHotWaterException. If not caught properly, it results in a blue screen of freezing.

Why algorithms ??

[matsh]

I would say the number of unique patterns are much more important. At least to me in my everyday programming.

Hmm

[mlylecarlin]

Everyone is forgetting that simple tests count as algorithms. No one has mentioned Eistenstein's Criterion, or the Weierstrauss M test, or Miller's Primality tests. Some of these tests are quite deep, and at very least they bear consideration alongside some of the more obvious tests from CS, analysis, and basic math.

Heh, I would say the deepest and most important algorithm is the process of induction :-P but I'd be shot.

Re:Fibinacci Number Algorithm.... Very fun

[GMontag451]

Here's a much faster algorithim: gr = (sqrt(5) + 1) / 2; grp = (gr - 1) * -1; int fib(n) { return (gr^(n+1) - grp^(n+1))/(gr-grp); }

Dijkstra's Algorithm: All-pairs, shortest-path

[SkewlD00d]

Dijkstra's algorithm is very nice, and it's parallelisble too! I used a varation in a class called the Longest Common Subsequence algorithm and we had to parallelize it.

Dynamic programming =)

I also like radix sorting, BSP trees, and B+ trees. Memory managers (allocators/gc/swaping) are fun too.

Re:Dijkstra's Algorithm: All-pairs, shortest-path

[mikera]

I agree that radix sorting rocks.

I remember a programming contest where I had to sort a *huge* list of words into length order.

My algorithm was by far the fastest. Most fools seemed to think that you need painfully slow O(n log n) time algotithms like QuickSort for sorting. :-)

Re:Dijkstra's Algorithm: All-pairs, shortest-path

[SkewlD00d]

Major props. =) LSB radix sort is good too. O(1) insertion, O(1) search time is good.

Does google.com use B-trees or radix?

Wow, check this out... this could be adapted to the B-tree structure to make an awesome search engine!

I vote for "One Click Shopping"

[LM741N]

But I wasn't able to find that one in Netlib.

Re:Swap!

[GMontag451]

swap (int a, int b) { a = a + b; b = a - b; a = a - b; } // no pesky third variable

Re:Computer science is the study of Algorithms

[Requiem]

Computer science is the branch of mathematics dealing with computation and computability. Algorithms is contained in that. :)

Heh...heh

[waldoj]

You know there's some guy still in the shower...

OK, so it's 1987, and I'm 8 years old. My family has just gotten our first computer, an IBM PS/2 Model 30 -- one of the systems with BASIC in ROM. I''ve taken up writing in BASIC, and do so in most of my free time. Which, as an eight-year-old, is a considerably amount of time. I'd taught myself all about Boolean logic, loops, etc., etc.

This is the part that I don't remember, probably because it's been obliterated by my family repeating the story so often. I've been in the shower for something like half an hour when my mother starts knocking on the door, wanting to know if I'm OK. I insist that I'm fine. This process is repeated for a while until they finally force me to get out, no doubt prune-like by this time. My mother asks me what in the world I've been doing in the shower for so long.

I point to the directions on the back of the bottle and say, simply, "Wash. Rinse. Repeat."

-Waldo Jaquith

Re:Basic of algorithms

[Wolfier]

A function that calculates all digits of PI is not an algorithm because it will never terminate.

An "function" that never terminates, by definition, would not give you any result in finite time.

However, if you can tell the function to return up until the 100 billionth digit, or if you specify how many digits you want, then it is an algorithm.

A good algorithm of calculating PI just returns the text "PI", the textual representation of a series sum that sums up to PI (with "..." obviously), or a continued fraction (with "...") because a finite notation of this ratio in our current number notation system does not exist.

My favorite algorithm...

[wedg]

...is of course: BUBBLE SORT!

Why? It's the only sort algorithm you can ALWAYS remember off the top of your head. (Besides, optimizations are for version 2.0).

Elevator Awareness Algorithm

[Anonymous Squonk]

If x=2 Then y=2 Else y=1

Where x is the number of people in the elevator and y is the number of people who know for sure who farted.

Re:What about the

[t]

CowboyNeal could be exp(-ix) which would then make him purely imaginary...

My New Sorting Algorithm!

[Enonu]

while (!isSorted (array))
array.swap (random (0, length), random (0, length));

What is a deep algorithm?

[grytpype]

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.

Re:My favorite algorythm

[Evil Pete]

Hmmmm ... speccies ...

Wonderful little putes, especially liked the version of Basic. Easy & powerful, learn it in an afternoon. Ahhhh those were the days ... when sorting meant bubble sorts ... now there's an algorithm .. the kind of algorithm you pull out of your head because you didn't know enough to look up alternatives.

Re:Theoretically interesting/Practically irrelevan

[Evil Pete]

True. I agree 99%.

The other 1% is for weird situations where you want some weird variation on a sort etc or its an algorithm that's in a library not ported to your platform/language so you have to actually code the algorithm. I did this once for some code that determined optimum paths through a network that was changing in real time while the object was moving. I found that the library versions of quicksort made the code too complicated, sorry I forget all the details, so I rewrote it ... took no time to do and worked as advertised. Also used graph algorithms in that too but had to modify them pretty severely.

Hindley-Milner type inference

[Tom7]

Here's an important one that I bet will be overlooked: Hindley-Milner type inference. It's what makes programming in statically-typed languages require even less type annotations than languages like C!

Don't forget that Milner got a turing award, in part for his work on type systems.

The source of recursion is useful...

[Jagasian]

Therefore I nominate the least fixed-point of the lambda-calculus:
\x(xx)

BGP, IGRP, RIP, etc.

[kyras]

BGP's routing algorithm and those of its its cousins and ancestors. Without this routing algorithm, you couldn't read /.

Berlinski's book

[AutumnLeaf]

Berlinski, author of "A Tour of the Calculus" (a damn good book), later wrote "The Advent of the Algorithm". It's on my to-read stack. I would think many slashdotters would be interested in reading it, and most slashdotters would be interested in reading the last comment on Amazon's review section. :-)

FFA

[lonedfx]

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.

this is funny?

[Gumber]

Gore didn't claim he invented the Internet, but lots of idiots claim he claimed to invent the Internet. So, where does that leave you?

What Gore did claim was that he took initiative in creating the Internet, which he did. He drafted and sponsored key funding bills for NSFnet. The initiative put Internet access into the hands of univerisity students across all disciplines and, I think, proved that a large "Internet" could attract broad interest.

Evolutionary Computation

[GrEp]

Evolutionary Computations. Defining a fitness metric for some problem and then searching the space using Darwin's principle of natural selection. It has done wonders for biological computing systems, and shows(has shown) promise for getting good solutions to many "hard" problems.

Euclid's Algorithm?

[MattyT]

How on Earth could Euclid's algorithm be the most important CS algorithm? I'll be the first to say Euclid's algorithm is really cool (and I believe I did actually, two days ago on an unrelated matter), but how useful is it?

If we ignore for the moment the fact it isn't really CS at all, when was the last time you needed a GCD? Maybe I'm mathematically naive, but I can't think of one single use of a GCD. I'm sure there are plenty, but are there any outside of maths, physics, engineering, etc? Is there a general use of GCDs, like there is for say crypto or graphs?

Does a GCD have a use in writing an operating system, or a programming language? When was the last time you saw a gcd function provided to a programmer in a standard library?

Re:Euclid's Algorithm?

[Gary Yngve]

ummm, most crypto involves taking gcds at some point or another.

Re:Euclid's Algorithm?

[mikera]

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?

Pessimal Algorithms and Simplexity Analysis

[zook]

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.

Johnia Machine!

[Tazzy531]

Johnia Machine is definitely the way to go...

Re:BSP trees

[The Cookie Monster]

BSP trees don't give any visibility testing information. They provide a fast way of determining draw order, and ensure that there is always at least one correct draw order (an effect of the way surfaces are cut).

AFAIK (I might have this bit all wrong, the Quake engine changed many times in development and I might not have got it right to begin with) With Quake, JC (John Carmak, not that other guy ;)) attached a list of visible polys in each leaf node of the BSP tree, but since which-polys-are-visible can change as you move around within the space defined by a leaf node, I suspect this has little to do with BSPs and he just used the BSP as a convenient structure to bolt the visibility info on to - it's already built, it's very fast to locate the leaf node volume you are in, the size of the volume will be smaller in more complex areas (where presumably the visibilty-list changes more often), the volume will always be convex with no walls running through it etc.

But yeah, while I have yet to figure out exactly what people mean by "deep" (non-trivial and elegant?), BSP trees seem to be as classy as the other algorithms people are putting forward.

Re:Simplest of the Simple

[mikera]

Don't think the "if (a!=b)" is a good idea in many cases.

Isn't the other great advantage of your variable swapping algorithm to avoid a branch instruction which is costly on some architectures?

Re: "throw the outOfShampooException"

[Ocelot Wreak]

And you could also throw an exception on sham poo and instantiate some REAL poo!

-wjc.

Hardcopy and (bent) Starplex diskettes

[Ungrounded Lightning]

Sounds interesting. Got any documentation or source?

I recently found the listings (after losing them for a couple years). They're a bit large to OCR.

I've got two copies of the source on damaged Starplex(tm) diskettes - 8" floppies, NOT in CPM format, with bent envelopes.

If you know anyone in the silicon valley area that can read Starplex diskettes or OCR 8 1/2 x (whatever printer paper was) fanfold listings, let me know. (Or if you're feeling like typing in 50ish pages of stuff... B-) )

1000?

[bill_mcgonigle]

Shouldn't it be the "Top 1024"?

Re:Favorite algorithm?

[Sivar]

Heh, oops, make the line:
if(n1 != 0) n1 = gcd(long n1, long n2);

instead:
if(n1 != 0) n1 = gcd(n2, n1 % n2);

My mistake.

Re:False

[heliocentric]

The halting problem is regarding PROGRAMS, not algorithms.

Programs and algorithms are _not_ the same thing.


You are somewhat correct, but very misguided. The thread here is that if an "idea" doesn't terminate then it's not an alg. I can clearly devise an alg. to test another alg. / program. However, the halting problem states that I can never know for sure if this input ever terminates. Here, the input is a program, it's not a program itself. Infact, when we talk about TMs we often mention "On input which is the encoding of a machine..." thus we are supplying as input what you call a program.

I will stipulate that not all algs. are programs, since I can device a non-deterministic alg. (even using an oracle) that I can not program in the same way (ie, I can't make it poly time on a deterministic machine). However, I would like to know of one program that can not be defined via an alg.

Re:Basic of algorithms

[Hercynium]

D'oh! Yeah, when I was about 15-16. I'm 22 now. :)