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

Hmmm...

[42forty-two42]

Well, compiler alrogithms are important :)

Re:Hmmm...

[DJPenguin]

I seem to remember having a write various everyday tasks (getting up, walking to school) in psuedo-code at school.

I imagine the pseudo-code "algorithm" for making a cup of coffee would be one of the most important in CS! :)

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?

[G0SP0DAR]

hehe! I have to agree with you there. Clearly, it is less efficient than the almighty quick sort routine. At least on paper. There are a few CS teachers who insist that bubble has some practical advantages over QS. If anyone finds out what these are, please post them, I have yet to figure it out! ;)

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?

[PD]

If you're sorting a very short list, like 10 items, a bubble sort will be all done by the time a quicksort is just getting set up.

Re:Bubble Sort?

[Gary Yngve]

We all know that Bubble Sort is O(n^2) while Quick Sort is O(n log n) average case [and O(n^2) worst case].

But remember that Big-O is for asymptotic behavior. When you have to swap small amounts of elements, bubble sort is by far faster. Why? For one, Quick Sort is recursive. In fact, a good quick sort implementation will do quick sort until the chunks get small enough and then do bubble sort on those.

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.

Re:Bubble Sort?

[Phil Wilkins]

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

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

Re:Bubble Sort?

[Garin]

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

The moral of the story is to always think about the reality of your data structures, and optimize for the most important and most relevant cases that you're dealing with, not to go with the slickest and coolest algorithms. Yes, Abrash is one of my heroes. :)

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?

[Hater's Leaving, The]

People do code mimicked stacks though. I do, if I need to (though I'm more of a merge or heap man myself). Register windowing, and branch prediction have made recusion less of a pain too.

So I certainly shouldn't say that there's no overhead, but the overhead is _really small_ compared with the rest of the job that needs to be done. O(n ln(n)) kicks in really quickly for sorts. I'll heap 20 things if there's a chance it might baloon to 30, say.

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.

Having said that, they probably said that about some bignum algorithms, and look at what GIMPS are playing with currently.

THL.

Re:Bubble Sort?

[r00tarded]

i wouldnt omit it. its a great introduction to how not to sort. people seem to sort using bubble sort naturally. so its a great way to introduce the entire science behind sorting, by doing a bubble and then showing a quick or merge.

Re:Bubble Sort?

[compwiz3688]

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

And figuring out the differences (features, [dis]advantages)between all the other sorting algorithms. I had an algorithm exam (sorting was one of the sections) 3 months ago, and now I can't remember what the difference is between insertion and selection (again).

Also, bubble sort is the first algorithm anybody would learn (except maybe those advanced kids), and probably the most "memorized".

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?

[rope]

You should consider that you can build infinite number of stupid alghorithms that will be best in some situations. Etc. swap 1st and last element, look if data is sorted and then perform some sort algorithm. This will be the best method if only this two elements are on wrong positions. And it should be used sometimes. And if someone ask you: "Do you sometimes need this stupid sort?" and you answer:"No" you will not get job?!

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?

[Mr Z]

All sort algorithms can be made stable by putting the original positions into the keys you are sorting.

Thanks, I was just about to say that. It's an oft overlooked property, too. I generally feel that a sorting algorithm's stability is overrated, since you can easily tack it onto any sort, usually for a low cost. If you're sorting an array, all you need to do is compare the two pointers to break ties. It's that simple. It *does* get more complicated if you're sorting some other structure, such as a linked-list -- then you're stuck with an O(N) assignment phase before the sort, potentially, and that brings with it extra storage requirements.

--Joe

Re:Bubble Sort?

[erc]

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 "who cares?" When's the last time you had to figure something like that out? An interview isn't a trivia contest, maybe you ought to re-evaluate your interviewing style. I personally never ask this sort of nonsense in an interview, it's completely irrelevent to modern day business programming.

Re:Bubble Sort?

[erc]

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.

And there are many cases where you really can't easily get away from recusion. Searching n-levels of directories, for example.

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?

[a random streaker]

Actually, there are other N2 sort algorithms that are better than bubble sort, so you wouldn't even use that on the small arrays at the end of quicksort.

As a TA once told my class, "Don't use bubble sort. It's dumb."

It is, though, not the worst sorting method. The worst was permutation sort, where you permuted the items, checked if they were sorted, then permuted them again and again until they were sorted.

Re:Bubble Sort?

[a random streaker]

Actually, since you have to run through all the items to make sure they're sorted, you can't do better than O(n).

Even where the cardinal value of the keys are the ordinal value in the sort (e.g. key translates directly to position in an array), you're still at O(n).

Besides, I can define a faster lightning sort as long as you rely on side effects rather than on return value.

#define lightning_Flash_wins_over_Superman_sort(x)

That's the old Barry Allen flash, by the way.

Re:Bubble Sort?

[a random streaker]

I've always found selection sort to be easier to program and understand than bubble sort.

You are right, though, about time not being much of an issue anymore. Why even bother with linked lists when you can just load all the stuff into a giant array? For $200 you can get a Gig of RAM.

I've even used gigantic arrays for database storage in a CE device. They are, after all, identical to a random access file of fixed record size, one of the cornerstones of computer science as data processing.

Re:Bubble Sort?

[a random streaker]

OMG did I have a problem with qsort once.

About 10 years ago when C++ was still fairly new, I had a project at grad school where I had to sort something. The compiler compiled but the program crashed. I checked and checked and checked, but there was nothing wrong with my program.

Not one damned thing.

It turns out the qsort was a C library, but I was calling it from a .cpp file. Thus the C function in the .cpp file was C++ call stack oriented, and the callback from qsort choked.

The compiler was too stupid to recognize this for some reason.

It's several incidents like that that have made me a brutish, hulking figure who swears, drinks beer, and loathes "God" the way Mark Twain used to.

Re:Bubble Sort?

[a random streaker]

> Do you implement an efficient sorting
> algorithm? No. You type in the quickest thing
> possible to get the job done.

Exactly! That's why you'd program selection sort or extraction sort instead of bubble sort.

Hell, I don't even remember any of them exactly. I'd write a double loop that pulled the highest key out on each decreasing n value. Which one was that now?

Re:Bubble Sort?

[vocaro]

If you're building software for a desktop, I agree with you. But I build embedded devices. Here, the argument is not simply a matter of speed. You also have to consider the size of the temporary memory needed for the algorithm, and the size of the algorithm's code itself.

What if you had to build an embedded device with, say, 4KB of RAM and 1KB of ROM (for executable code)? This type of device wouldn't even have an operating system, and with such limited amounts of memory, you'd want to save every byte. With the recursive quicksort, you'd have to implement a stack (very unsafe in this example!). Other very fast sort algorithms might require large amounts of extra scrath memory (such as the bucketsort). In the end, the bubblesort, with its very small implementation size, simple design, and limited memory requirements, might actually be one of the best choices when memory efficiency is far more important than speed.

(Never say never!)

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?

[magnusk]

For lists of N items with a *constant* number of out-of-order items, both insertion sort and bubble sort are O(N), not O(N^2). IIRC, the runtime of bubble sort is typically better in this situation.

Re:Bubble Sort?

[zoon0]

Him: This is a standard interview question for me, when I interview programmers. "In what case would you want to use a bubble sort?"
You: And the correct answer is: never.
Me: Never say never.

Aren't you assuming that programmer time has insignficant cost compared to program run time?

And didn't someone famous say 'Premature optimization is the root of all evil'? Aren't they half right?

Re:Bubble Sort?

[sir99]

If you're using C++, Stroustrup claims that STL sort() is faster than qsort(), because it gives the compiler a chance to optimize your code. Of course, it also bloats your program for the same reason.

Re:Bubble Sort?

[Matthaeus]

Actually, since in bubble sort you have to compare each element to all the others after it, it's O(n^2). (k*n(*n-1))/2 if you wanna be specific, where k is the number of primitive operations in the innermost loop.

Re:Bubble Sort?

[Matthaeus]

All of the following criteria would have to be met for me to use bubble sort:

1. I don't have any code handy to implement a different type of sort.
2. n 50 (depending on the machine)
3. The program is due in 5 minutes.

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

Re:Bubble Sort?

[sir99]

Thanks for the explanation of my rather quick comment. I should clarify that I meant using sort() will bloat your code more than qsort() would, not necessarily that sort() would bloat the code unacceptably. I actually haven't had the opportunity to use either, since as one other poster said, it's not often necessary to sort anything in most programs.

Binary Search

[G0SP0DAR]

Without binary search, life as we know it would not exist.

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:Binary Search

[G0SP0DAR]

True. I suppose the binary search would be more or less directly dependent on the quick sort for any reasonable amount of efficiency

Re:Binary Search

[Hater's Leaving, The]

Funnily enough that list was just the /small/ set of algorithms that I come in contact with almost every day (I'm a softie & mathematician). I live in my own small world.
I was hoping to see lots of other lists from people who work and think in other fields. I'm sure there are a vast number of Chemists, Physicists, and Engineers, for example, who could open my eyes when it comes to algoritms. (Applied maths was never my strong point)

Ditto with more high-tech Comp-Sci algorithms.

Thanks for posting those, it's a shame you're sitting there at Score 0, as I nearly missed your reply. I shall look them up (and snarf the papers for fun future bus-journey reads).

THL.

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

[halfpastgone]

on a somewhat similar note: Cayley-Purser algorithm

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

[Traxton1]

It's got nothing on rot13 ;)

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?

Are sorting algorithms "deep"?

[sh4de]

Quicksort is my personal favourite, and while I haven't ever implemented it in C (not reinventing the wheel etc.), I did code a MC68k assembly version in late 80s.

Radixsort looked a lot like magic at first sight. It was very common on the Amiga, mainly for sorting the Z buffer in one's l33t 3D routines. :)

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.

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

[Hater's Leaving, The]

"
Then it sends finer ones, and finally the last comb is the same as the 'exchange consecutive elements only' step in ...
"

bubblesort.

Not
"
quicksort.
"

Ooops.
I hope it was obvious that was a simple braino.

THL.

Mandelbrot set fractal generation

[PyroJimmy]

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

Re:Mandelbrot set fractal generation

[sir99]

Of course it terminates. It terminates when you reach the desired accuracy (just like Newton-Raphson iteration).

Miller-Rabin

[entrager]

My vote goes to Miller-Rabin.

Prime numbers = fun for the whole family.

Sounds like a poll .....

[binaryDigit]

And therefore I choose:

Cowboy Neal Bubble Butt Algorithm

Oh... I can see the poll already...

[Cothol]

...What is your favorite algorithm?

Important Algorithms

[Anonymous Coward]

Dijkstra's Single Source Shortest Path Algorithm
Boyer-Moore Fast String Searching Algorithm

Re:Important Algorithms

[crevette]

I love Dijkstra (sp?) algo, it gets my vote too! Any algo with a complexity N is great to me.

Re:Important Algorithms

[Gary Yngve]

Actually Dijkstra's Algorithm is O(E log V) or O(V^2), depending on implementation. E is the number of edges and V is the number of vertices.

Basic of algorithms

[reflexreaction]

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.

Re:Basic of algorithms

[halo8]

Ya... like pythagorums theory, is that like an Algorithm? how about some post a quick point form crash course on Algorithms?

THANX =)

Re:Basic of algorithms

[nickynicky9doors]

Author: David Berlinski

Title: The Advent of the Algortihm

Publisher: Harcourt

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

Re:Basic of algorithms

[Hercynium]

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

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

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

Re:Basic of algorithms

[SpryGuy]

To be finite, the process must end after a predictable number of steps.

I disagree with that definition. Can't something be both finite AND unpredictable? You know it will terminate, but you're not sure exactly when? I'm thinking of algorithms like "Find me the next prime number after X". You can't predict the exact number of steps for that one, at least in the simple implementations of that algorithm.

Re:Basic of algorithms

[Broccolist]

If you just had a program that calculated the digits of pi and outputted them to the screen forever, no, that wouldn't be an algorithm. AFAIK, algorithms that don't terminate are called computational methods. But since computational methods can usually be trivially terminated at some arbitrary point (e.g. in the case of pi, stop after one million digits), their study intersects with the study of algorithms.

Re:Basic of algorithms

[Gary Yngve]

But in this case you can place an upper bound on the number of steps. The next prime number after p (p>2) is guaranteed to occur before p!.

Re:Basic of algorithms

[jcast]

So you're telling me my Haskell compiler allows me to implement non-algorithms that nevertheless return a useful result?

And, for that matter, you're saying the xinetd program running on my computer does not implement any algorithm?

If algorithms fall so short of describing what we can actually do with computing machines, why do CS people spend so much time on them?

Re:Basic of algorithms

[_Knots]

AFAIK, there is no known formula for the n-th decimal digit of pi. However, there is one for the n-th base sixteenth (hexadecimal) digit.

D = (1/16^n)[(1/(2n+1)) + (1/(2n+3)) + [two other similar terms]].

I'm not sure the first two terms are right, but the formula has a (1/16^n) term multiplied by four 1/(an+b) terms, where a and b are constants and n is the n'th digit of Pi.

-knots

Re:Basic of algorithms

[leifw]

The Ackermann function is the simplest example of a well-defined total function which is computable but not primitive recursive. See the article "A function to end all functions" by Gunter Dötzel, Algorithm 2.4, Oct 1991, Pg 16. The function f(x) = A(x, x) grows much faster than polynomials or exponentials. The definition is:

1. If x = 0 then A(x, y) = y + 1
2. If y = 0 then A(x, y) = A(x-1, 1)
3. Otherwise, A(x, y) = A(x-1, A(x, y-1))

(stolen from http://pw1.netcom.com/~hjsmith/Ackerman/AckeWhat.h tml)

Re:Basic of algorithms

[leifw]

Doh, should've included this before. Here's a page that has values for Ackermann's function. It grows fast. The reason that it's so hard to compute is because of the depth of recursion that it requires to solve even a low order problem.

Re:Basic of algorithms

[rabidcow]

What's so great about the Sieve of Eratosthenes?

Re:Basic of algorithms

[delong]

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

I would say this statement indicates you are STILL a kid. When I was a kid, computers took up whole buildings, and you handed a computer operator a stack of punch cards and breathlessly waited the next morning (if lucky) for the results of your program. You showed your age, in other words.

:P

Derek

Re:Basic of algorithms

[GreenPhreak]

I just think it is impressive that an ancient Greek came up with a very elegant way of finding all prime numbers over 2k years ago. I know it doesn't rank up there as a deep algorithm, but I think it is a fundamental algorithm.

Re:Basic of algorithms

[Hercynium]

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

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

[LastToKnow]

Well certainly. Those with youngun's frequently have to pass references to other things to dress.

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

[Mr Z]

Much too long. You want:

$0&$0

Does almost the same thing, only faster. If you still want the pipes, go a character longer: $0|$0&

--Joe

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

[Fulcrum of Evil]

a Java Virtual Machine isn't an algorithm

Well yeah, a JVM is a piece of software.

HIBT?

Re:My favorite algorithm

[dsoltesz]

Actually, I've recently used this very algorithm to illustrate while loops to my niece, as follows:

do {
lather () ;
rinse () ;
} while (hairIsDirty == true)

On the shampoo bottle, the condition is implied but nonetheless there, meeting the requirement for termination after a finite number of steps...

btw, my niece, once a computer-phobic literary snob, has discovered the joys of qbasic: colorful blinking text, ascii art decorations, and being the only girl in class. At one time she used "geek" as an insult, but now proclaims herself a Geek Goddess. There's nothing quite like having all the boys gather 'round with jaws dropped ogling yer bodacious GUI :-D

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.

Re:My favorite algorithm

[blazin]

Like the other reply to your message, I was trying to leave it a little open ended where you could potentially have the need to dress someone else, or for someone else to dress you.

Would you agree that it'd be important to have the ability to pass in a reference to the "undress" method?

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?

Re:Rank alg: Anyone know the name of this one?

[Improper Gesture]

Yeah, I run that all the time. It's SockSort.

while(!basket1.empty()) {
similarity1 = 0;
sock1 = basket.pick(1);

sock2 = basket.pick(1);
similarity2 = compare(sock1, sock2);
if (similarity

Re:Rank alg: Anyone know the name of this one?

[Matthaeus]

You didn't finish your code, but I'm hoping that you'd either implement basket as a queue or put discarded socks in a different basket if they don't match. Otherwise, you could be continually picking the same sock out of the basket to compare with a sock it doesn't match.

Quick sort

[Ripsnorter]

My fav is the Quick Sort. Its simple, effective and something I'd like to think I'd come up with myself, but know I couldn't.

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.

Al-Gore-ithm

[Anonymous Coward]

My favorite Al-Gore-ithm was when he invented the Internet.

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?

[FortKnox]

touche. Good point.

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

Re:Algorithms?

[hargettp]

I respectfully disagree: it's *still* all about algorithms! And, BTW, what comes next I do not wish to aim at you personnaly. Just ignore the rest of this if I'm taking you (and me!) too seriously. ;)

<rant>

I've been in IT for over 10 years, and it seems so many times you find people in IT who will happily blather on about the "Visitor" pattern or another such topic (a useful pattern, to be sure), but who for the life of them can't remember any of the basic sort algorithms. It kills me; algorithms are still fundamental component of our toolkit. We can't ignore them

</rant>

<useful_contribution>
Are patterns nothing more than new algorithms expressed more conceptually, with natural language instead of a programming language? Sure, a pattern does not have the same strict criteria of finite number of steps, complete in finite time, must have output, etc., but just as algorithms (and Donald Knuth's work) are guides to implementation, are patterns not also guides?

Typically, one can express an algorithm in some form of pseudo-programming language. By choosing a programming language, we are choosing a form of expression with deep mathematical roots (think Godel, Turing, Church, etc.). What are patterns, but guides that we simply have not translated into a pseudo-language template for implementation? The Visitor pattern is a great example: one can express the pattern in a number of languages, quite simply.

So, perhaps we incorrectly differentiate between patterns and algorithms based purely on the language of expression. Perhaps instead we should look for that new language, or expand an old programming language, that can capture the ideas of patterns more precisely and inline in the same code as those code artifacts we have traditionally called algorithms.

And with the expressive power of this new language, what would programming be like?
</useful_contribution>

Re:Algorithms?

[t]

Yes yes yes. They should also put on every exam, "What is the definition of a scientist." I have feeling most people would fail. Especially those who insist it should be implemented in Java.

t.

Re:Algorithms?

[russellh]

Patterns have more to do with programming than computer science.

You're right, but not in the way you think you are. You're thinking of the software industry popularization of Alexander's patterns, which is of course all about programming and not computer science. However, they have dumbed down the concept significantly. If you read Alexander's A Pattern Language, and compare it with the gang of four book, there's just no comparison - Alexander's is deep, probing, and almost alive; the GoF's book is shallow and dead. The comparison between patterns and computer science is like biology to physics: biology is about life, whereas physics is about the structure of matter. We have a new field here - nobody's recognized it yet.

Re:Algorithms?

[pkiguruman]

hmmmm....I thought that it's all ball bearings nowadays.

Re:Algorithms?

[FortKnox]

ROFL!!

I think it was the bypass line....

What's your name?
Fletch
Your FULL Name?
Fletch F Fletch
Occupation?
I'm a shepard...

Re:Algorithms?

[Rob Riggs]

I've been in IT for over 10 years, and it seems so many times you find people in IT who will happily blather on about the "Visitor" pattern or another such topic (a useful pattern, to be sure), but who for the life of them can't remember any of the basic sort algorithms. It kills me; algorithms are still fundamental component of our toolkit. We can't ignore them

Oh horsepucky! It's important to know these things if one is writing libraries. Application programmers have little need for this knowledge. Their tools should provide it for them. You don't need to be a scientist to build a car (or even an automobile engine) these days. Software engineering has long since advanced past the point that one need be a computer scientist to write computer applications.

Re:Algorithms?

[jcast]

I should probably mention that, according to the Curry-Howard isomorphism, Computer Science (actually that subset of CS that studies algorithms) and (constructive) proof theory are interchangeable.

Re:Algorithms?

[sawanv]

I am inclined to agree with your prog. Most of us are really programmers not computer scientists.

Recursion?

[gatekeep]

I'm not sure if it'd be an 'algorithm' per se, but I've always found the concept of recursion/mathematic induction to be extremely useful. I don't know how much use it is to true programmers, but for writing useful shell scripts and administrative tools it's something I rely on quite a bit.

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

[kippy]

Skip list are a data structure, not an algorithm.

FFT, right on.

My favorates are:

huffman coding
heap sort
merge sort

Re:Off the top of my head

[cpeterso]

I like bubble sort.

Re:Off the top of my head

[jasha]

How about bogo-sort? I especially like the variant where "... Implementation of step 2 is left as an exercise for the reader"

Re:Off the top of my head

[Sangui5]

Ah, the skiplist. Every time algorithms come up, the skiplist is not paid nearly enough attention.

I know that I've posted this URL once to this article aready, but skiplists are practically ignored, compared to how nifty they are. No balanced tree has a right to exist (except perhaps B-trees because the mesh nice with hardware) with skiplists around:

ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

And I'd like to add 2 more nifty and somewhat ignored algorithms: the Burrows-Wheeler Transform and the Discreet Cosine Transform. Burrows-Wheeler is what gives us bzip, and Discreet Cosine is what gives us JPEG and MPEG. Heck, while I'm on a compression kick, lets add MTF (move-to-front) and Huffman Codes.

Re:Off the top of my head

[discstickers]

Hurray for Lemepel-Ziz! The decompression is simply beautiful, especially compared to the hell that is compression. I stared at my decompress for well over six hours, and I never got it quite right working with a trie. When I switched to an array of Strings, it took five minutes. Like I said, beautiful. =)

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

[marcelk]

I think you missed creative loop unrolling.

Re:Off the top of my head

[Woodie]

I'd add the following, if they can be considered algorithms:

Genetic Algorithms/Programming
Neural Networks
Fuzzy Logic

While these may appear focused on AI - they have had real application in a lot of areas.

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

[Accelerated Joe]

Knuth-Morris-Pratt string matching

The KMP algorithm is the only algorithm I've ever seen that shocked me when I first saw it. It is so simple, and yet I probably never would have thought it up on my own. It's just beautiful!

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.

Re:Off the top of my head

[powderfinger]

Is it really! that ! Tom Duff.
I think we should be told.

Diffie-Hellman, too

[paulschreiber]

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

Paul

Re:Diffie-Hellman, too

[3am]

That's not really an algorithm...

Re:Diffie-Hellman, too

[Grit]

Hmph! Just because us distributed computation people have to count messages in addition to everything else doesn't mean it's not an algorithm!

I admit the line between algorithm and protocol is fuzzy at best. It's say that Diffie-Hellman is an algorithm, but a specific use of it is a protocol. Just like BGP (the Internet routing protocol) is a (distributed) implementation of the Bellman-Ford algorithm.

Re:Diffie-Hellman, too

[3am]

I'll buy that - I think it's just the mathematician in me is much more comforted by the words 'instance of an algorithm' or 'implementation of an algorithm' in this case.

Maybe you should read the interview again

[Pussy Is Money]

In the interview, Knuth also repeatedly remarks on the importance of the "individual bricks" over "milestones" and top-ten lists. So maybe you should read the interview again.

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

Re:An important algorithm I use everyday...

[Requiem]

Yes, yes, but what is the time complexity?

Re:An important algorithm I use everyday...

[AutumnLeaf]

Shouldn't that middle bit be:

ready, fire, aim? I know that's my mode of operation when the alarm is going off...

Re:My favorite algorythm

[Capt. DrunkenBum]

Well, that is one to my personal favorites.. Although I use "x" instead of "a"...

Classy. :)

Hello World

[Wolfier]

One of the most important algorithms ever invented.

Seriously, how about Simulated Annealing or Genetic Algorithm?

Re:Hello World

[rlotun]

Yes, lest we forget the biologically inspired algorithms in areas such as:

1) Evolutionary Computing: Genetic Algorithms, etc.
2) Function of the brain: Neural Networks (more specifically, backpropogation)
3) Machine Learning

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

Re:simplex method

[mike_g]

I took a linear programming class a while back, and the professor stated that more computing time has been spent running the simplex method than any other algorithm in history. Definitely an important one, but my favorite is still the FFT.

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

Very Deep Algorithm

[stinkydog]

dim accounttotal 'Total number of accounts
dim myaccount 'my account

for count=1 to accountotal
myaccount=myaccount+(100*account(coun t)-100*int(ac count(count)))/100
account(count)=int(account(cou nt)*100)/100
next

Run once a week for a healthy balance
SD

Re:Very Deep Algorithm

[DiS[EnDeR]]

Yummy, VB....
"waiter, my programming language is not verbose, send it back"

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

Euler's Totient Theorem

[alanw]

Elegant, deep, and the foundation of public
key cryptography.

The best

[Snuffleupagus]

I personally have a love hate relationship with B+ trees.

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

Fibinacci Number Algorithm.... Very fun

[taya0001]

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

Re:Fibinacci Number Algorithm.... Very fun

[getch();]

Ah, yes. The above implementation is the textbook example of situations in which one shouldn't use recursion.

Re:Fibinacci Number Algorithm.... Very fun

[RazorJ_2000]

That IS the meaning of life: "don't use recursion". Pretty deep, eh.

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); }

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

Use this one everyday

[ill_conditioned]

I'm a big fan of the Ostrich Algorithm...

Re:Use this one everyday

[Matthaeus]

I remember the first time I heard about the Ostrich Algorithm. I was taking an OS class from a short little feisty Vietnamese guy, and the Ostrich Algorithm was actually on the syllabus and the tests as being the best way to avoid resource deadlock. Then again, that was for a Software Engineering degree. Now that I'm in Computer Science (and have to take OS all over again), I fully expect to have to deal with resource deadlock in its entirety.

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

Re:Prune your betas!

[gregbaker]

"is be horrible" isn't be what I meant.

DeCSS

[mikeee]

Clearly, the most important algorythm. ;)

Re:DeCSS

[iceburn]

Oh yeah, that thing that takes cascading style sheets out of web pages. I think I have a copy of it on my drive. Very useful.

There are always new problems

[Anonymous Coward]

'Companions the Creator seeks, not corpses, not herds and believers. Fellow creators the Creator seeks, those who write new values on new tablets. Companions the Creator seeks, and fellow harvesters, for everything about him is ripe for the harvest.'

(Friedrich Nietzche)

Algorithm to understand what's an algorithm.

[locoluis]

1. For all the comments on this article.
2. See which ones show a list of actions to do, especially those who specify conditions (if/then/else), or control flow (repeat,for each,while,until...)
3. Study the selected examples.
4. Reload and repeat until understood.

I *so* have a future in CS teaching.

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?

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?

What is your favorite algorithm?

[Conspiracy_Of_Doves]

Ok, this is one for everybody who as ever posted the phrase "Is this really news for nerds?"
.
.
Give me a nice recursive function any day. :)

My favorite

[SGDarkKnight]

Experienced COMPUTER PROGRAMMERS modify Algorithm A by placing a known elephant in Cairo to ensure that the algorithm will terminate.

Assembly language programmers prefer to execute Algorithm on their hands and knees.

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

[sdowney]

How in hell did this idiot get modded up to insightful.

I can only hope that he's not employed by anyone who cares about the quality of the work done for them.

Apparently he'd prefer to waste their money reimplementing linked lists, mostly likely incorrectly.

The best developers steal shamelessly from people like Knuth, Sedgewick and Hoare. There's no need to reinvent bicycle wheels, especially when there are high performance race car wheels free for the taking.

Besides, the fundementals are HARD. There are thousands of ways of screwing up a linked list implementation. Most of them subtle. And that's supposed to be an easy one. String matching, hash tables, red-black trees, quicksort, etc, are even subtler.

Implementing them in college, in a CS course, is so you gain a deeper understanding of how they work. It's not so that you go out and reinvent them whenever you need one.

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

[t]

Unfortunately, sometimes progress in the "correct" direction can only be made when you disregard what came before you. e.g., the Earth is the center of the universe.

Personally I feel that string theory is an obstacle to progress.

And probability based speech recognition algorithms have to get thrown the fuck out. It's a dead-end method.

t.

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:But smart people won't ignore the topic...

[jovhl]

but real progress is NEVER made when you disregard what came before you

Never is a strong word. Fresnel tried, and succeded, in formulating a correct theory of diffraction precisely because he didn't know all that had been done before him.
As it was, Fresnel provided conclusive proof that Newtons view of light as particles was incorrect, and that diffraction was a direct result of the wavelike properties of light. Huygens, a contemporary of Newton, held a similar view, but was considered a quack by most since his theory went against Newtons. Fresnel proved Huygens had the right idea all along, but he didn't know that when he did his experiments and formulated his theory. If he had, he wouldn't have "wasted" all that time making his own experiments and theories. Maybe he still would have cracked the problem, but most probably he wouldn't. Many had tried to stand on the shoulders of Newton and Huygens, but that didn't help them solve the problem.

Game playing algo...

[KaiserSoze]

I was always partial to the minimax game playing algo with alpha-beta pruning. I think it is rather cool that you just start lopping off whole chunks of the tree, and you're always searching for that one branch that fits you best and your opponent worst.

Pardon me...

[SSJ_Ramon]

...but did you say Al Gore rhythms?

Re:My favorite algorythm

[Gary Yngve]

If all algorithms, by definition, terminate, then the Halting Problem is easily decidable.

Dr. Fun cartoon

[PD]

This cartoon is about Knuth

What about the

[graphicartist82]

CowboyNeal algorithm? CowboyNeal = SQR(CowboyNeal * CowboyNeal)

Re:What about the

[sacherjj]

I always wondered why CowboyNeal was so positive about everything...

Re:What about the

[t]

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

If you have to ask

[sinserve]

"What is your favorite algorithm", then you have no idea what an algorithm is.

Let me put it in common english, so Joe-Six-Pack can understand:

"Hey slashdot readers, what your favorite way of solving problems".

Yessir, we have "a" favorite way to solve problem*s*.

A new low slashdot, a fucking new low.

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

random

[brondsem]

random number generators
I don't know any names, but they're used in lots of applications

how about breaking RSA?

[vladkrupin]

or breaking this. Or this (a few others come to mind too).

Heck, just with crypto breaking you can probably find over a hundred different algorithms that are utilized in breaking crypto only. This way we can get to a thousand in no time, we just need more paranoid developers... ;)

CiSE Top 10

[Vireo]

The Computing in Science and Engineering magazine published in Jan/Feb 2000 a "Top 10 Algorithms of the Century" article by Jack Dongarra and Francis Sullivan. Their choices for the most important / useful algorithms are:

Metropolis algorithm for Monte Carlo

Simplex Method for Linear Programming

Krylov Subspace Iteration Methods

The Decompositionnal Approach to Matrix Computations

The Fortran Optimizing Compiler

QR Algorithm for Computing Eigenvalues

Quicksort Algorithm

Fast Fourier Transform

Integer Relation Detection

Fast Multipole Method

Re:CiSE Top 10

[Inthewire]

Remember the header that preceded this thread? The thing where they introduce the story? There was a link to a previous thread...a thread discussing that same top ten list. Amazing, isn't it?

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 .

Re:My favorite algorythm

[Gary Yngve]

There are many common randomized algorithms that have an expected running time that is linear but could potentially run forever. A simple example is the rejection method.

For example, suppose I had two coins and had to pick a random number from {1,2,3}. I could do the following scheme:
Flip the two coins. If I got:
HH I picked 1.
HT I picked 2.
TH I picked 3.
TT Flip again.

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:algorithm example: long division

[jcast]

Would you like to inform us what you think the Halting Problem is all about?

"You'll be strung-up by your toenails...

[CheapScott]

...if you do this on the school's mainframe!"

--A Serious Warning from my Freshmen Comp Sci Instructor (14 years ago).

main() {
while(1)
fork();
}

Re:"You'll be strung-up by your toenails...

[JacobO]

I thought you were supposed to add a malloc(1024) in that loop too...

Sheesh!

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.

Swap!

[FernandoValenzuela]

The Greatest Algorithm Ever Created:

swap (int* a, int* b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}

Re:Swap!

[ChicagoFan]

The Greatest Algorithm Ever Created:

swap (int* a, int* b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}

Bah. Long live C++!

template &lt class Visa>
swap(Visa& a, Visa& b)
{
Visa tmp;
tmp = a;
a = b;
b = tmp;
}

"Visa. It's every type you want (it) to be."

ChicagoFan

(this crap here only to get past the "too few characters per line" filter)

Re:Swap!

[FernandoValenzuela]

oh sure, if you want to overload operator = for every class...

Re:Swap!

[ChicagoFan]

oh sure, if you want to overload operator = for every class...

1) Without operator=, I couldn't swap two elements of a class even if I wrote a swap function specifically for that class instead of using a template. (unless you had a member swap(), I guess, but then you have to write a member swap() instead of a member operator=).

2) Operator= exists automatically for all classes. You only need to overload it if you are specifically allocating dynamic memory or using other such resources, and often you can just make your member variables objects (instead of pointers to objects) and let their functions do the dirty work.

So it's not as much work as you think.

ChicagoFan, probably IHBT

Re:Swap!

[iangoldby]

Nah! Save 4 bytes:

swap (int *a, int *b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}

The sad thing is I had to look up the C operator for exclusive-or.

Re:Swap!

[GMontag451]

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

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

Al Gore Rhythm?

[ctp]

Ever seen that man dance? He has no rhythm!!! What's all the fuss about???

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.

I dunno...

[locoluis]

I didn't mean to make sense. :)

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?

Re:Best texts on algorithms

[CrayzyJ]

Introduction to Algorithms - Cormen, Leiserson, and Rivest - is the defacto standard. It can be a hard read, but it has *everything*.

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.

Re:Finite Element

[Gary Yngve]

Finite elements are really more of a modeling technique. The interesting algorithms are then how to solve the differential equations over the finite elements.

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

[Gary Yngve]

And most processors these days have a single machine instruction to do a swap for you. Of course their main motivation is atomicity for concurrency. But these days it may be better just to code swaps the old-fashioned way (with the temp variable). Besides having it being easier to read, the compiler would have a better chance figuring out exactly what you are doing and optimizing it for you. The compiler is your friend and you should not try to outsmart it.

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'

Re:In place swap of two variables

[jakew]

Wish I had mod points. I was just about to type this very thing. So nice to know that not everyone is x86-centric.

Of course, the xor version is more efficient on sensible ISAs if you take register allocation into account.

Re:In place swap of two variables

[Ironpoint]

xor ecx,edx
xor edx,ecx
xor ecx,edx

Same opcode count PLUS one more register is free for something else. If one operand is a memory address, then it uses only one register.

And if we are swapping 32-bit floats, we don't have to use the fpu.

Re:In place swap of two variables

[epine]

xor r4, r4, r5

This is supposed to be sane? I know of many human languages with the grammatical structure:

verb subject object indirect-object

Not.

Re:In place swap of two variables

[epine]

The floating point unit doesn't have an xor capability in any modern chip I've seen, unless the IA-64 bit slicing facilities for floating point manipulation include this.

Re:In place swap of two variables

[epine]

The xor swap only makes sense if you use it to swap a bit field within the integral value.

Off the tip of my fingers I think it goes like this:

b ^= a;
a ^= (b & bitmask);
b ^= a;

Yes, that should be right since if the second statement is rendered idempotent by a zero bit in the bitmask it boils down to this:

b ^= a;
b ^= a;

And we are back to the beginning again.

There's no good reason a compiler couldn't be coded to recognize this sequence of steps and apply instruction level optimizations, such as on x86 if your constant bitmask is just swapping the low byte. The single byte swap instruction could be substituted mechanically.

The program code:

uint32 a, b;
b ^= a;
a ^= (b & 0xFF);
b ^= a;

Would be generated by the compiler as:

swap al, bl

Of course I'm joking that anyone would implement this optimization in a real compiler. But then take a look at recent developments to automate the generation of SIMD instructions for conventionally coded loops.

I think the boundary between what helps and what hinders the compiler is becoming extremely blurry.

Re:In place swap of two variables

[Fulcrum of Evil]

Very sane.Instructions are by and large OP DST SRC SRC

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

Re:Quantum Algorithms

[NoBeardPete]

I think it's worth going into more detail on these, because I suspect most people don't know much about them. I won't try to explain Shor's factoring algorithm, because I never really managed to get it all in my head at once. It might have helped if I wasn't trying to carry 4 technical classes on top of my brutal physics lab when I was trying to understand it.

Grover's search algorithm, though, I remember quite well. It's beautiful in its simplicity and elegance (which is a large part of why I still remember it), yet quite powerful. Here's what it does:

We have some function F returns 1 on exactly one out of its n inputs. Grover's search algorithm lets us find the value x such that F(x) = 1, and it lets us do that in order sqrt(n) time. Classically you can't do any better than just searching through the space of inputs, trying each one, which takes order n time.

Damn.

So, having covered the fact that it is mighty powerful, I'll say a little about how it works. First, we construct an input x which is a superposition of all possible inputs. In particular, this means it is fractionally 1/n the right answer, but is (n-1)/n some wrong answer. We pump this x through f (and a few other operations) and then combine the output with the input. Each wrong answer suffers a little bit of destructive interference, while the right answer undergoes constructive interference. Rather, rinse, repeat, and after a number of steps that goes like sqrt(n), all of the wrong answers have completely cancelled out, and all that is left is the right answer!

Yeah, so I know this is hard to get across in this kind of short text dohickey, but this is such a cool algorithm, I had to try anyway. My success... well, I guess that depends on how cool you think the Grover algorithm is now.

How about Genetic Algorithms?

[Ipsilon]

They can solve a large set of optimization problems and the basic idea is very simple.

Re:How about Genetic Algorithms?

[Ipsilon]

Interesting opinion, but I've used Genetic Algorithms for different kind of problems like optimization, machine learning, etc. Yes, they are damn slow, but in many problems there is no other feasible solution.

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

[deadtreerus]

Tipper throws her hat over Al's deep ALGorythm probe.

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.

Re:Djikstra's Communicating Semaphores

[CvD]

The name's Dijkstra, not Djikstra. :-) The Dutch 'ij' is somewhat equivalent to the english 'y', although we have the 'y' too. The 'ij' is actually one letter "unit" in a word.

And yeah, semaphores are cool!

Cheers!

Re:Djikstra's Communicating Semaphores

[jakew]

Sounds interesting. Got any documentation or source?

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

Say no to algorithms in CS!

[NicolaiBSD]

algorithms in CS? I can't say this often enough: You don't want none of them fancy-schmanzy algorithms in your Counterstrike, they'll ruin your ping for sure.

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:Bresenham Line Algorithm

[RoadWarriorX]

Yes! Without Bresenham, I could not have spent a good portion of my life playing Quake... ;-)

The most obvious

[compass46]

#include

main()
{
for(;;)
{
printf ("Hello World!\n");
}
}

Square Root Algorithm

[CTalkobt]

A simple and somewhat efficient algorithm for finding the square root of a number goes as follows:

n = # ( say 25 ).
Count the number of sucessive odd numbers that add up but not over the target number.
eg: 1+3+5+7+9 = 25
....1.2.3.4.5 so 5^2 = 25.

Who knows what this is really called?

Re:Square Root Algorithm

[Utopia]

Thanks for the algorithm.
I never realized that
1 + 3 + ... + (2n-1) = n^2

Re:Square Root Algorithm

[knulleke]

No, he's not saying that. You add where you should count.

cute algorithms

[Gary Yngve]

the quadratic algorithm for solving the Stable Marriage problem... I've been wanting to run it on a bunch of friends to see what bizarre matches came up... (run it twice, to be both male-optimistic and female-optimistic).

Sweepline algorithm for Voronoi diagrams.
The sweepline (directrix) creates parabolas around the points (foci). If illustrated right, these look like breats and make for a humorous lecture.

OT - What are the most common ones in use

[wrinkledshirt]

Sorry, this stuff is all super-Greek to me. I thought I was pretty smart for finally getting the Quicksort algorithm, but even then I needed the pretty Java applet to show how it worked.

What I'm wondering is, what sorts of algorithms are in use all the time that we don't really know about? That article about the top-ten algorithms of all time listing some pretty exotic-sounding things, claimed that many of those algorithms were probably in use on the computer right now. Is that really the case? Are there many algorithms in use for the Linux kernel, for instance?

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

[FatHogByTheAss]

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.

It is far more important that someone know when to apply a particular tool to solve a problem, rather than knowing the detail of the tool itself.

I would much rather have developers that know when to apply a given algorithm, even if they can't describe the detail from memory. Most true CS algorithm problems have been solved a zillion times.

Productive engineers apply those tools to their problems, rather than build those tools themselves.

I can't tell you what makes the blade in my circular saw go round and round, but I know what to use if I have to cut wood.

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

Re:One Vote for Newton!

[Gary Yngve]

Newton's Method is slick, but remember that it does not guarantee convergence at all, especially in the presence of zero second derivatives. For 1-D, you can couple Newton with Regula Falsi. For higher dimensions, Levenberg-Marquardt works surprisingly well given that it heuristically chooses whether to behave more like Newton or more like gradient descent.

Re:One Vote for Newton!

[jat2]

Generally speaking, one really means "Gauss-Newton" when referring to "Newton methods." The GN algorithm (which I mentioned in my original post) works by "dampening" the Newton step via a 1-dimensional optimization subproblem called a line search (e.g. Armijo), thus avoiding "overshooting" the root.

Most professional implementations use damped Newton methods (like GN), which are globally superlinearly convergent. In practice, GN is only merely superlinearly convergent for the first few iterations before moving close enough to the root to converge quadratically.

The Levenberg-Marquardt algorithm is a quasi-Newton algorithm (which I also mentioned in my original post) because it estimates the Jacobian matrix of the nonlinear function instead of always using the exact Jacobian. In this way, there are less function evaluations required per iteration at the cost of superlinear convergence instead of quadratic.

As far as nonlinear programming is concerned, no algorithm beats the class of Newton-like algorithms for their generality, efficiency and elegance. There are even a few different flavors of Newton algorithms that can be used to solve nonsmooth equations and their ilk! (The Bouligand differentiable Newton algorithm can solve systems of variational inequalities and complementarity problems.)

For an excellent reference, see Numerical Methods for Unconstrained Optimization and Nonlinear Equations by Dennis and Schnabel.

Sorts

[Anonymous Coward]

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?

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

[compwiz3688]

They'll probably have more terms, like "Working 9 to 5" for 2000, "Retired" for 4000, and say "Old and gray" for 8000? :)

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

[NinjaGaidenIIIcuts]

Most of these 500 algorythms were just been added for the needs of specific applications, CS is biased in the direction of "numbers that make money" and simply doesn't extend research "for fun", meaning hard research for things that appearantly don't give financial return.

Re:1000 is too naive

[epine]

The maturity threshhold is not put forward in terms of the computer science field, but in terms of human intellectual limits. Mature fields have the characteristic that 90% of all progress comes from people who are highly specialized within their niche with completely unexpected connections popping up between subjects that were thought to be unrelated.

A field is mature when much of the work concerns the relationships of things already known. CS isn't there yet.

The single most important algorithm....EVER

[MJN222]

Seeing as to how I just had an Algorithms assignment due today and spent a decent chunk of time solving the following problem to produce an algorithm, I'm gonna say its important. :-)

Let G = (V,E) be a flow network with source s, sink t, and integer capacities. Suppose we are given a maximum flow in G.

Now suppose that the capacity of a single edge (u,v) in E is decreased by 1. Give an O(V + E) time algorithm to update the maximum flow.

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! :-) )

Kollige

[farmerzebra]

One of the algorithms that was impressed onto me as one for a rainy day, was the radix sort. One variant of it can do some real magic. wish I could find my old notes on that...
The other memorable one was Dykstra's shortest path alogorithm. The prof was Romanian, she spoke 12 languages, none of them english. I couln't undertand a word that woman said.
I guess the CS field needs a comprehensive, but simple book on those 500 canonaical algorithms.
Most CS books I've read seem to have been written to impress colleagues.

Re:What's the definition of "deep"?

[marktwen]

I.e., it's not the type of question that comes with a multiple-choice answer. Viz., modern university education can't even come close to teaching it.

Yeah every algorythm will be important

[NinjaGaidenIIIcuts]

But developers need a bit more of computer education to code applications using 80-bit floating-point format instead of double-precision.

People still believe that SSE2 and its 64-bit precision will keep up with science applications, but that's not true.

Is interesting that cpus like Itanium support 40-bit integer format and a lot of registers, packing a single 80-bit operation plus a 40-bit integer instruction (128-bit pack, a 8-bit header, 120-bit free) is easy using explicit paralelism and should be a big win for many scientific applications.

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!

-

The Scientific Method...

[RazorJ_2000]

Why are so many people thinking of algorithms in terms of precise computations and, more literally, formulas? How about the Scientific Method as an algorithm? Without it, much of modern technology and science would be lost.

Re:My favorite algorythm

[Gary Yngve]

That's the definition I go by. Basically the Church-Turing Thesis. Algorithm == Turing Machine.

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

Self-contained recursive algorithm

[Rui del-Negro]

recursive (ri kur'siv), adj. see 'recursive'.

Re:My favorite algorythm

[Doppler00]

I wrote a program like that on an Apple II in 3rd grade. I asked the class go guess how long it would take the computer to count to a million. Unfortunately, it took several hours.

Computer science is the study of Algorithms

[Meech]

In my first computer science course, I was taught that computer science was the study of algorithms.

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

ROT13

[Rui del-Negro]

CSS is just a bad imitation of the ROT13 algorithm.

Re:ROT13

[JonWan]

Well I said it was important *not good*. It was really a serious nomination, just the part about the law made it funny (Well maybe not). If you think about it the studios wrangeled over the DVD format for a long time and only agreed to release movies after they were told that it was safe. It turned out to be a case of "Don't count your money before the DVD is hacked" and now they are stuck with it because of the sucessfull media blitz they have given DVDs. They make so much money now it will be hard to stop releasing movies on DVD. That is why they will spend so much money in Congress and the courts to get their way.

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.

Lempel-Ziv?? [Re:Off the top of my head]

[glyph42]

Lempel-Ziv compression is one of the most clunky, arbitrary, wasteful, inefficient, and widely-used compression algorithms available today. Get a clue about compression before you talk about it like that.

I'd much sooner vote for LZP (for its sheer elegance) or the latest block-sort methods for their efficiency and speed.

See compression.ca for some real numbers

Re:Lempel-Ziv?? [Re:Off the top of my head]

[Hater's Leaving, The]

The Lempel-Ziv family is a large one.
Clunky - dunno what you're refering to here. LZ77 was poop in my book. That might count as clunky in your book.

Arbitrary - Oh god yes. Several parameters to chose from, and then evolution such the the parameters would adapt themselves to the problem-size in question.

Wasteful, inefficient - really? That's probably bad parametrisation, and a cheap and nasty entropy compressor as the back end. Throw it away, bolt on a decent entropy compressor. If you use the right kind of LZ variant, then you wont be more than 5-10% off the more high-tech modern ones.

Maybe LZP is such a variant - I don't know of it, or not by that name - what's the particular twist that LZP has?

Pretty please - URL will do.

However, like you - I just love the BWT technique. Here's a great way to compress data - shuffle the tokens around! My jaw dropped when I first read their paper. Hmmm, I had some potential improvements to their transform, I must try them out some time. (They've probably been done already I'm sure).

THL

Re:Lempel-Ziv?? [Re:Off the top of my head]

[glyph42]

URL for LZP:

www.cbloom.com/papers/lzp.html

Enjoy! Also be sure to check out the compression.ca site that I mentioned before.

- GLYPH

Re:Lempel-Ziv?? [Re:Off the top of my head]

[Hater's Leaving, The]

Ah, Bloom. OK, I seem to remember that last time I was told to go look there my bloody PS viewer didn't work, and I gave up.

You're a dude for posting that link - you'll get my eternal gratitude if you can post a good review of the PP* family. From teh one-line I've heard it doesn't seem like it's anything new at all, it's just an dynamic adaptive-depth modeller. And great for thrashing caches.

THL.

Re:Lempel-Ziv?? [Re:Off the top of my head]

[Hater's Leaving, The]

Holy Baloney - I invented LZP in about 1990. I needed a quick hack scheme to compress some text, and decided that the 1-bit guess was the way to go, as long as about 50% of the time the guess was correct, which is a simple matter of modelling well enough...

It's funny - being nothing more than an amateur and hobbyist, you get to invent all kinds of things and never have a clue whether they're in the academic literature or not.

THL.

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.

Re:Skip list problems

[charmer]

In IPDPS 2001 conference, there is a paper on Concurrent Priority Queues based on SkipLists by Shavit of Sun Micro. That demonstrates exactly the opposite of what you are saying.

Re:Skip list problems

[Sangui5]

Could you post a link? I know I've seen ways to make skiplists nicely concurrently accessed, but it is nice to have a reference, rather than just saying "Is so!".

Re:Skip list problems

[charmer]

I searched google for skiplists, when I came across this presentation. I dont have a link handy.

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.

Re:What, no else if SO?

[The Man]

How about: ... else if SO assert (get_temperature (HELL) 10); endif Why imagine something that will never happen? And hey, I'm 23. If you haven't woken to a lover's voice by 23, you never will. Pathetic? *shrug* C'est la vie.

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

Re:Actually he invented Spam

[compwiz3688]

His wire-all-the-schools-for-internet was also a trojan horse.

So that's where the spam is coming from. :)

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.

Databases

[Dr_Cornholio]

Where would the world be without the Prof. Nijissen Algorithm. It is a complex algorithm but once you've used it a couple of times, you can create the most complex databases without even working up a sweat!

physical simulation, collision detection

[NFW]

My $0.02: LCP, penalty method, lagrange multiply, impluse method... some such physical simulation algorithm will belong in the list eventually (or maybe a few of them will). Probably a collision detection algorithm too, maybe nice fast polygon soup algorithm.

This stuff is pretty niche right now (mostly just games and high-end simulations), but I think it will get find more widespread application as computing power increases.

a cool LCP implementation

a fun toy (yes, I'm biased) that uses the above

The Illegal Infinite Knowledge Algorithm

[Anonymous Coward]

The following must be *the* most important algorithm known. ;-) It --- if run sufficiently long enough, say, oh, a few forevers --- generates a representation of all possible knowledge that can be represented:

(let ((y 0))
(define knowitall
(lambda (x)
(begin
(if (= x 0) (write-char #\.))
(write x)
(knowitall (+ 1 x)))))
(knowitall y))

Why? This algorithm generates (a decimal representation of) Champernowne's Constant, which is a / the (only known?) string that contains within it every possible substring of arbitrary length drawn from the same alphabet of characters. Warning: this algorithm is probably illegal, because it contains within it / will eventually generate DeCSS, the complete source code to every version of Microsoft Windows ever, the complete collection of all Mariah Carey's songs in MP3 format, the complete set of all the documents that Anderson shredded on behalf of Enron, the exact GPS coordinates of Osama Bin Laden at every moment for the rest of his life, George Bush's complete DNA sequence, etc. Enjoy! :-)

Re:The Illegal Infinite Knowledge Algorithm

[Xoro]

Bah!

Your cheesy scheme is no match for an infinite number of typing monkeys.

The one algorithm of all time...

[Subcarrier]

The one algorithm of all time that I remember most fondly has got to be the Infocom parser. At the tender age of 14 I spend countless of hours trying to duplicate it in early BASIC. This, in retrospect, might not have been such a great idea...

Obviously...

[Pig Hogger]

... 42!!!

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

Wavelets

[michael_cain]

In particular, the "lifting scheme" for constructing transforms -- it's fast, it's invertable, and it generalizes more easily to a variety of conditions.

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?

Re:Everyday life needs algorithms

[Fulcrum of Evil]

Perhaps an exponential growth algorithm for our bank accounts.

Oh, that one's easy. It's called compounded interest.

Re:Everyday life needs algorithms

[daveman_1]

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

If you figure out how to optimize this one in a way that works every time, you will have solved all the important problems in the universe.

AI

[ZaneMcAuley]

I think the next important algorithm would be a good "Fitness" test algorithm for AI.

Cool algorithms

[flonker]

One of my favourite algorithms is one I found in Programming Pearls. Basically, using a bitfield to sort numbers in constant time, O(n), given that the numbers are unique. Something like:

for i=MIN to MAX
aout[ i ] = 0
for i=0 to n
aout[ ain[i] ] = 1
for i=MIN to MAX
if aout[i] == 1
Do whatever with the now sorted output

Re:Cool algorithms

[Accelerated Joe]

Yeah, bucket sorting sure is cool! Radix sort would probably be more efficient here, unless your range is too small for the sorting method to matter.

Normalization

[Blackheart2]

Since this is a blatant popularity contest, I will submit my own, very biased, favorites. These are all ways of normalizing lambda-calculi.

1. call-by-name evaluation
2. call-by-need evaluation
3. call-by-value evaluation

Lambda-calculi are abstract models of computation which lie at the heart of functional programming languages. Terms of the lambda-calculus are programs, and present computable functions. A normalization algorithm lets you decide whether two terms (programs, basically) are equivalent---not merely syntactically (which is trivial), but semantically, i.e., whether or not they give the same results on the same inputs. This is an extremely important problem in the field of programming languages because it affects program reliability.

The normalization methods mentioned below are important because they are decision procedures on closed terms of typed lambda-calculus, i.e., terms without any free variables. Call-by-name (cbn) is also a "semi"-decision procedure for untyped lambda-calculus (dynamically typed functional languages). This means that if two programs terminate, then they will reduce to the same thing using cbn.

To put this in context: When you program in ML or Scheme or, more or less, LISP, you are using the call-by-value evaluation procedure, since arguments are evaluated before calls. When you program in Haskell (or Scheme with suspensions), you are using the call-by-need procedure, since arguments are evaluated on demand. And, if you are using Algol 60, you are using call-by-name, since arguments are evaluated every time they are demanded.

Other candidates for `deep algorithms' in this vein are Gentzen's "Hauptsatz", or cut elimination procedure and the Hindley-Milner type inference algorithms.

Another Exception

[restless_ne'erdowell]

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

yeah

[Trepidity]

I have one particular computer science professor who can barely program worth a damn. But he sure is good at discrete math.

Drunkard's Walk

[JLester]

Drunkard's Walk of course!

Jason

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.

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!

Graph algorithms

[pauljlucas]

Reachability, closure, minimum spanning trees, finite state automata minimization, etc., have lots of uses and are some of my favorites.

I vote for "One Click Shopping"

[LM741N]

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

My Private /. Webpage

[litewoheat]

function onFilterShashdotArticles(articles)
{
len = articles.length;
for(i=0;i<len;i++)
{
if(articles[i].from == "Anonymous Coward" || articles[i].score < 1)
{
articles[i].filter = true;
}
}
}

Re:My favorite algorythm

[germanbirdman]

Completely offtopic, nice effect though which I always ran on my ZX Spectrum 20 years ago:

for n=1 TO 80:CIRCLE n,n,n: NEXT n

going ontopic again, a circle just would be too slow to draw without the BRESENHAM algorithm for slow processors.

Mathematics are also very important. Think taylor rows (correct translation? "Taylorreihen"). Without it we wouldn't have many of the mathematical functions.

But before you even use taylor, you need to have efficient multiplication and division algorithms for floating point numbers.

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

BSP trees

[ncoder]

BSP trees, for fast visibility testing.

Hey, without them, bye bye Doom, Quake, Unreal, Half-life, etc...

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.

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

Re:My favorite algorithm...

[DaCool42]

but bubble sort is one of the slower ways of sorting

Re:My favorite algorithm...

[epine]

Bubble sort gets a bad rap being the butt of every joke. Bubble sort was invented as the optimal sorting algorithm for a Turing machine.

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.

Nitpicks

[greenrd]

You have them mixed up. O(N) (which that algorithm is, technically, if you ignore the range) isn't constant time, it's linear time. O(1) is constant time.

However, this is one case in which the "constant" factor (the range) is likely to outweigh the actual O(N) factor, so the O(N) notation is misleading. (The range isn't really constant of course - if you wanted to include that you could call it O(N+M)).

Thanks for the algorithm though!

Re:Theoretically interesting/Practically irrelevan

[khuber]

I disagree. Like the other guy in a second level post said, you need to know -when- to apply various common algorithms. Beyond that, programmers write algorithms all the time to carry out particular tasks. Just because I didn't write quick sort, doesn't make my algorithm unnecessary. Maybe there isn't a common algorithm for doing my task.

Suppose I knew binary search was a fast way to find something in a sorted array, in O(log n). Of course I'd put all my strings in an array and use binary search, right? No, a better solution is probably to use a hash table, which is O(1). But by not understanding data structures and algorithms, you're not going to realize that problems can be transformed like that. It's the when all you have is a hammer, everything looks like a nail problem.

I really believe that the world does not need more ignorant programmers producing junk code because they don't understand basic CS principles. And you don't need a CS degree either, just some fairly basic knowledge of algorithms, complexity, data structures, and when they apply.

-Kevin

Quine-McCluskey optimization method

[WEFUNK]

...You may remember me from such algorithmic steps as "Expand my MinTerms and Don't Cares", "Group by Ones", "Compare the Pairs and Cover the Set", and "Find the Prime Implicants".

...oh wait that's the Troy-McClure method...

Guess my prof didn't pronounce it quite right (or I wasn't quite listening).

Great for minimizing the number of logic gates in a circuit, but we had to do it by hand for electrical engineering exams - so tedious! Certainly gave proof to why we now use computers for such mindless monkey-work.

Re:My pick goes for RSA ... NOT!

[Traa]

recently it has been shown that RSA is not that great of an algorithm after all. New theories have shown that 1024-bit keys are not safe enough. The complexity of number factoring (though full of cool deep algorithms like the "Number Field Sieve") are not yet fully understood and seem to be easier computable then was previeously thought.

Time will tell if this is going to lead to some form of world chaos becuase certain powers will be capable of cracking the worlds secrets (HTTPS, SSH, IPSec, S/MIME, PGP).

Apparently

[greenrd]

B-W is used by the bzip2 compression program (which is used by kernel.org to compress kernel sources to a higher ratio than gzip does).

My New Sorting Algorithm!

[Enonu]

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

My Favorite Algorithm is...

[fizban]

...the one that instructs my Mandrake 8.2 installation to show 25 minutes remaining for the last 15 minutes...

how about this one?

[Anonymous Coward]

1-click shopping

Re:My favorite algorythm

[jezreel]

Thank you for making my day :-)))))))))))))))

Re:My favorite algorythm

[Jagunco]

Probably faster than a Sun E10000 running this [much simpler] equivalent program in java:

class basic {
public static void main(string args[]) {
long x = 0;
try {
while (true) System.out.println(x++);
} catch (Exception e) {
System.out.println("An exception ocurred :)");
}
}
}

What the heck is ROT13 ?

[Rui del-Negro]

I'm guessing you don't know what ROT13 is. ROT13 is an "encrypting" algorithm used in e-mail and newsgroups that simply adds 13 to each letter (ie, it "rotates the alphabet by 180 degrees"). Most e-mail clients and news readers still have an "apply ROT13" option. I meant it as a joke, of course.

Re:What the heck is ROT13 ?

[Rui del-Negro]

Just say Microsoft is evil and CowboyNeal rules. That gets you two points minimum (usually for "Informative" and "Insightful", although it should actually be for "Redundant" and "Funny").

If you want more, just add a signature that says "I'll probably be modded down as a Troll, but who cares?".

And don't feel bad; no-one got my joke about recursive algorithms, either. There should be a way to add canned laughs to the posts.

oldie but goodie

[MikeyO]

My all time favorite algorithm would have to be the first one i learned:

10 print hello;

20 goto 10

Re:oldie but goodie

[Ziviyr]

My all time favorite algorithm would have to be the first one i learned:

10 print hello;

20 goto 10

The computer I learned on would probably fill the screen with zeros if you did that on it. ;-)

Two Phase Random Routing

[panck]

I like this algorithm because it's non-intuitive. I think we learned about this in Parallel Programming class.
Basically, if you have a lot of network-linked boxes that you want to use for performing some parallel task, you run into network bottlenecks sometimes depending on how the network is structured. Esp. if you have a couple nodes which are doing a lot of communication, they can tie up a segment of the network, and all the other nodes get hurt.

Two Phase Random Routing simply says, if you want to send data to some node, don't send it straight there. First send it to a random other node, who will forward it on.

Amazingly, this fixes the problem.

I don't remember if this was more effective for some networks/applications than others, but I thought it was cool.

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.

de Casteljau Algorithm

[braeden]

I nominate the de Casteljau algorithm for frame independent generation of curves and surfaces from control points by interpolation between the points.

The algorithm sits on a mathematically rigorous foundation in affine (i.e. "frame independent" or "not based in a particular coordinate system") geometry, the study of which is quite fascinating (and complex) and highly recommended. (Book plug: Curves and Surfaces in Geometric Modeling by Jean Gallier. ISBN 1-55860-599-1. Heavy theory-- this is a math book. However, it directly applies to computer graphics.)

Implementation of the algorithm and its extensions (such as the progressive version known as the de Boor algorithm) gives us polynomial and Bézier (spline) curves and surfaces and subdivision (which gives the CS implementor control over level of detail).

Perhaps a reader can help elaborate on this and other algorithms in the curves and surfaces domain?

Shor's Algorithm

[Lank]

How about Shor's algorithm? As useful quantum computing gets closer to reality every day, undoubtedly quantum algorithms such as Shor's will become increasingly more important.

Dynamic nodes?

[Sangui5]

How is it that the nodes are dynamically resizable? Once a node is created, it has a fixed size. If you use sentinals for head and tail they may need to change size, but not very often. Saying that the nodes are changing size during runtime is flat out wrong.

And as for locking, a skiplist is fast enough that locking the whole thing isn't much of a penalty. Besides, if you're clever enough about it you can lock just a portion of the list and not the whole thing (lock top-down, and pre-decide how high the new node will be). True, that makes the code somewhat more complex, but that's nothing compared to any of the tree structures.

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.

fave algorithms

[adminispheroid]

Some biggies I use all the time, but haven't seen mentioned here, are Levenberg-Marquardt (sp?) (non-linear model fitting through chi-squared minimization) and Powell's direction set method (optimization). And biconjugate gradient methods for solving large sparse linear systems. Also we shouldn't take for granted Tchebychev methods, which are the magic behind fast accurate implementation of special functions like exp and sin.

This may be a bit of a stretch -- but I have to mention the Beowulf algorithm: fill a room with cheap PCs, string together with scrounged network hardware, add Linux and MPI/PVM, and poof, you have a supercomputer.

That original list of 10 certainly hit the war-horses -- Monte-Carlo, matrix decomposition, FFT -- without which life would be nasty, brutish, and short.

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.

Ah, but it DOES terminate.

[Mr Z]

This is a BASIC program running on a real computer, and therefore it accepts inputs that are not explicitly written in the program.

One of these inputs is the BREAK keystroke (exact key depends on the type of computer). That input causes the program to halt. Another is the power connection. If this is removed, the algorithm halts as well. ;-)

It would seem that all real computers are subject to the latter constraint. Thus it would seem that all physically realizable programs (meaning, you can write them and run them on a machine, rather than just talk about them in broad terms) halt. Thus, in the grand scheme of things, they're ultimately eligible to be algorithms on this point due to artifacts of the implementation. :-)

--Joe

Did any of them actually test it?

[Sycraft-fu]

:)

I had some fun at the expense of my TA in an intro CS course I took. It was a Java course (yuck) and the TA was a real condecending jerk (which is funny bacuse the professor was a nice guy). Now this course was for people with zero programming experence. I had a fair amount, but had to take it anyways because that is just how you did things in the CS major. The combination of that and the TA made me look for ways to make trouble. Soooooo...

We had a homework assignment that required us to do some various thigns, I don't remember all of it, but one of them was to sort a pretty large list of things. The type of sort wasn't specified. I assume we were supposed to use qucik sort since we had learned it and the code for it was on the course page. However the professor told us that what counted with our programs was having clean, readable code and getting the job done, we could do things our own way to a large degree.

So I wrote the most inefficient sort (short of something like this) I could think of. It was a recursive, bubble sort. It started at the beginning of the list and checked to see if the two items it was looking at were in order. If so, it incrimented it's counter, if not it switched the order. Then it called itself.

As you can imagine this lead to rather a lot of memory usage, and apparently it ran like crap on the TA's computer since it was old, slow and didn't have a lot of memory to start with. I got a kick out of it since when talked to the professor about it, he decided I deserved full credit, since it DID work, just not optimally.

1 one-thousand, 2 one-thousand, ....

[Mr Z]

Unfortunately, it took several hours.

The guessing, the program, or both?

--Joe

Re:1 one-thousand, 2 one-thousand, ....

[Eccles]

The guessing, the program, or both?

The original asking. He's got a stutter that would make Porky Pig envious...

Re:1 one-thousand, 2 one-thousand, ....

[Doppler00]

The counting. Actually, I'm sure most of the time is spent processing the PRINT statement. It is also an interpretted language so that further slows it down.

Taylor rows?

[Mr Z]

I think the translation you want is Taylor Series. Those infinitely long algebraic series for expressing transcendental functions line sine, cosine, etc. Right?

--Joe

Will CS ever be a "science"

[sielwolf]

As one of my profs loves to put it "No real science has the word 'science' in it". Physics, Chemistry as compared to Social Science or Dropping Mad Science.

And then there is Dijkstra's ubiquous quote/Attrition header "Computer Science is no more about computers than astronomy is about telescopes."

I know this is OT but what would you call CS if you couldn't use the S? Computers? Algorithmics? Fingering Finite State Machines? Gasp, Information Technology? (BTW I think Technology is about as appropriate as Science is as a root noun).

Re:Will CS ever be a "science"

[thirty-seven]

There is already another name for Computer Science - Informatics. According to the introduction of the Computer Science section of the University of Waterloo Undergrad Calendar, "Computer Science is centred around the study of information. It is concerned with the nature and properties of information, its structure and classification, its storage and retrieval, and the various types of processing to which it can be subjected. It is also concerned with the physical machines that perform these operations, with the elemental units of which these machines are composed, with the organization of these units into efficient information processing systems, and with the exploration of the limits of the abilities of these machines."

The source of recursion is useful...

[Jagasian]

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

What about BLAST?

[dnaboy]

For those who are unfamiliar with the DNA sequencing and analysis world, BLAST is an algorithm for finding similarities in DNA sequence. For example, I find a gene that codes for nerdiness, and sequence it. I can then run the sequence through BLAST and not only find out where in the genome (~3 billion G,C,A, and Ts) the sequence is, but also what other genes are similar or whether the same or a similar gene is in another species, such as mouse. Without a highly efficient homology algorithm, it's safe to say that the genome would be far from complete. I'm more of a bio guy than a CS guy, so I'm not really qualified to say whether it is as elegant as it appears from the outside, but hey, it got the job done either way

If nothing else, 3 or 4 months ago Steve Jobs was glowing on stage at some conference touting how much the Mac kicks the butt of the PC in BLAST speed. No one, of course, bothered to mention that you'd be crazy to try to run BLAST with even a bacterial genome on a personal computer of any sort. It's efficient, but come on.

Tree algorithms

[Anonymous Coward]

The most important algorithm I have used in the last 10 years.

Threaded AVL trees.

It is amazing how much code I have "fixed" or
improved by dumping a:

List with a sort function
binary trees
simple AVL trees
loading data and then sorting it.

This is the most underused yet best bang for the
buck algorithm/data structure out there.

I have used it for directed , undirected graphs,
user interfaces, event handling, cacheing algorithms, data flow algorithms, searchs user information etc. The overhead is minimal and
a known runtime is so important. The automatic
reblancing has known points to make it thread
safe and the ability to linear process through
the tree makes it a replacement for any list were
someone is searching for data.

Leslie Donaldson

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

Learning algorithms

[Hobbes_2100]

'nuff said. Well, not really. Some of these include:

1. Genetic algorithms.
2. Neural networks.
3. Rule learning / Inductive logic programming algorithms.
4. Reinforcement learning.
5. Bayesian learning systems.

Admittedly, many of these are actually "classes" of algorithms. There are fairly canonical examples of each though. It is also very important to note that all learning can be phrased as a search process. Hence, all searching techiniques [best first, depth first, A*, etc.] have a very important role in all of learning ... and in fact, in all of computer science. Herb Simon (love him or hate him) said that all AI is "heuristic search" (apologies if it was Newell that said this).

Since I work with them everyday, I have to support them.

Seriously though, they are very important (and for more things then just good game AI).

Regards,
Mark

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

Dictionary of Algorithms and Data Structures

[sjpotenza]

Check out a dictionary of algorithms and data structures at:

http://www.nist.gov/dads

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.

There is no such thing as "matured" science.

[Anonymous Coward]

When science "matures", it becomes technology and engineering. Science, by definition, is the eternal process of charting the unknown, and re-examinating the known.

If you want to try it out safely

[roystgnr]

Try limiting the number of processes it can spawn first: "ulimit -u 100" or something like that on bash. Then you start up top in another window to watch the results.

I tried it on my machine (after syncing the disks) and didn't have to hard boot, but it took literally minutes to kill the damn thing off. Linux tries to split CPU time between processes rather than between users, it seems, and so one root login seems a thousandth as important the scheduler as 1000 spinning forkbombs.

I don't suppose there's any kernel patches like the O(1) scheduler, but which implement a "be fair to multiple users" scheduler instead?

traditional marriage algorithm?

[ftdohist]

this was one of the first that i learned - i used it just the other day to explain to some art grad students what an algorithm is.

Favorite Algorithms

[This Is Ridiculous]

I haven't had much formal compsci training (yet) but I've always loved the way bottom-up parsers work. It's so counterintuitive at first glance, but when you finally grok it it's so simple.

Simplest of the Simple

[Cheese Man]

While this may not quite fit, my favorite implementation of an algorithm has to be strcpy in C, whose hart is:

while (*src++ = *dst++);

If you fully understand this single line, you've past the "beginner" stage...

Also, a more-esoteric (though applicable) algorithm is the infamouse (and cool) swap of two variables without a third. Also a one-liner in C:

a ^= b ^= a ^= b;

or for the nit-picky:

if (a != b) a ^= b ^= a ^= b;

Anywho, these are the elegant examples that made me stick with Comp Sci long enough to learn RSA, et. al.

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:Simplest of the Simple

[epine]

The xor concept applied with bit masks leads to a very efficient method of performing an 8x8 bit block transpose in 3 passes over a pair of 32 bit integers (with shifting).

Re:Cayley-Purser is broken

[halfpastgone]

yeah you're right. Sarah Flannery actually cracked it herself. link here.

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.

Knapsack packing algorithms!

[wdr1]

I mean really, what other algorithm also helps you move and pack a truck?

-Bill

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?

Depth-First search

[TimoT]

I'd argue that depth-first search is even more fundamental (topological sort is based on it). You can also compute strongly connected components using 2 DFS passes. Another fundamental graph algorithm would be the breadth-first search. I guess it depends on how you define fundamental, but I'd say a simple algorithm that is used to build simple algorithms.

Unpublished

[Anonymous Coward]

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

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

Al Gore Rhythm

[Alien Being]

chown -R gore /net

Simple and Fast

[ZeldorBlat]

I've used this on several of my assignments in my algorithms class. And the beauty is, it solves any problem!

Assume there exists an optimal solution O. Then we have:

Opt()
return O
end

Proof of Correctness:
O is the optimal solution.
The algorithm returns O.
Therefore, the algorithm returns the optimal solution.

Running Time Analysis:
The algorithm returns O, which can be done in constant time. Therefore, the entire algorithm is O(1).

This answer generally recieves minimum credit.

Johnia Machine!

[Tazzy531]

Johnia Machine is definitely the way to go...

Genetic Algorithms

[sireenmalik]

Why doesnot anyone mention GAs?

I had heard a lot about GAs ( initial work by John Holland) before and was fascinated by the natural appeal of the idea: evoluation and "survuval of the fittest" strategy. Intrigued, i recently used a GA to solve a complex problem and was truly amazed by its efficiency. On the same kind of problems the classical solutions take longer(much longer) time.

But GAs face their share of criticism. For example a strong solution/chromosome in a population can lead the entire population to follow(just like real life), or when after some iterations the difference between the best and worst solutions is not too much... the algorithm stops. The trick is then to have "Diversity" in the chromosome population( think about the Immigration schemes by the developed countries) and simultaneously allowing the solution to "Converge". It would be wrong not to mention R.B Holstein whose Selection Criteria are of trumendous value for handling both Diversity and Convergance at the same time.

Given everything, i think GAs should be ranked in the top 10 algorithms.

Re:#1 missed algorithm from 1950s

[MjDascombe]

Do either of you even know what an algorythm is?

Most important cs algorithm

[Nicodemus713]

Without a doubt (illustrated in C):

int main (char** argv)
{
printf("Hello World\n");
exit(0);
}

Appearantly it is the fundemental building block upon which all programming languages are based.

Here are my picks ...

[Anonymous Coward]

- A* algorithm (generic AI problem solving algorithm.)

- Dijstra's minimum path (and other graph algothms.)

- Risch algorithm (Maple uses this to integrate arbitrary expressions.)

- Toom-Cook/FFT, Montgomery's algorithm (big number multiplies.)

- Introspective sort. (Hybrid of Quick sort and Heap sort which gives great average and worst time complexity.)

- Various pseudo-prime/factoring tests. There are a number of "random trial" algorithms that work unusually/unexpectedly well.

- Karmarkar's algorithm (fast average and worst time complexity Linear program solver.)

- Arithmetic encoding, PPMD, BWT (state of the art in compression algorithms which are pretty damn good.)

- The DCT/iDCT algorithm (video/image compression.)

- Peterson's Critical Section algorithm (great for multitasking.)

- "Dynamic Programming".

- Good Hashing algorithms.

Not funny you jerk

[fungai]

Who is this mister Knuth to say that computer science is not yet mature? If CS brought us UNIX, and even a CS student can program something as wonderful as Linux, then I say Computer Science is as mature as I want it to be, thank you very much. And to this Mr. Knuth I ask, do you even know anything about Computer Science?

And an even more irrelevant side note... I once addressed Noam Chomsky as "Mr Chomsky", and when I realized my mistake and apologized he said "That's not a problem. Only my enemies call me "Professor Chomsky".

Re: "throw the outOfShampooException"

[Ocelot Wreak]

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

-wjc.

Patanjali's Yoga Sutra

[adimanava]

the algorithm par excellence to realise the Self, knowing which everything else is known!

QuickSort vs. HeapSort

[rpiaggio]

I've seen QuickSort mentioned several times in the discussions. Do people still use QuickSort?

Why not use HeapSort always, which has the same time complexity but lower space complexity (O(n))?

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.