Deep Algorithms? 596
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.
Bubble Sort? (Score:2, Funny)
Re:Bubble Sort? (Score:3, Funny)
You're damn right it's important.
Re:Bubble Sort? (Score:2)
Re:Bubble Sort? (Score:2, Insightful)
Re:Bubble Sort? (Score:5, Insightful)
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? (Score:3, Insightful)
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? (Score:3, Insightful)
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? (Score:3, Interesting)
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? (Score:3, Interesting)
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? (Score:5, Interesting)
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? (Score:2, Informative)
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? (Score:3, Interesting)
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
My pick goes for RSA (Score:4, Interesting)
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.
Diffie-Hellman, too (Score:5, Interesting)
Paul
Re:My pick goes for RSA (Score:3, Insightful)
:-)
Re:My pick goes for RSA (Score:3, Insightful)
Mandelbrot set fractal generation (Score:2, Interesting)
Purely to add a little bit of the aesthetic to the list. [Check it out] [bu.edu]
My favorite algorithm (Score:3, Funny)
Lather. Rinse. Repeat.
Re:My favorite algorithm (Score:5, Funny)
This fails the first requirement of an algorithm, according to Knuth:
You know there's some guy still in the shower...
Re:My favorite algorithm (Score:4, Funny)
Assuming everything shuts down correctly, the destructor or finalization method should be something along the lines of
getOutofShower();
self.dry(self);
self.dress(
Heh...heh (Score:3, Funny)
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
Rank alg: Anyone know the name of this one? (Score:2, Interesting)
You start with 2 sets of items that are related in some way. Next, you identify possible matching relationships. You then rank each relationship pair with some metric, sort the relationship list, and remove all lower ranking relationships. This leaves you with a list of the highest ranking relationships, with items appearing only once in the relationship list.
This was a trivial exercise in Lisp (where I first implemented it), but I've used it quite a few times in various other languages. Anyone know the name of this?
Well, technically a data structure (Score:5, Interesting)
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) [umd.edu]PDF [umd.edu]
Skip list problems (Score:4, Insightful)
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.
Topological Sort (Score:5, Interesting)
Algorithms? (Score:4, Interesting)
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? (Score:4, Funny)
Re:Algorithms? (Score:3, Insightful)
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? (Score:4, Interesting)
It depends on what field you're working in. Patterns are all the rage in OOP, and especially in Java. No doubt about that. Alas, they alone do not encompass all that is technology.
But, more to the point, patterns are a component of software engineering. Similiar to patterns, algorithms are a component of computer science. (Although it's probably safe to to say algorithms play a *much* larger compontent in CS, than patterns are in S.E.).
What's the difference between software engineering and computer science? Hard to explain, but it's a little bit akin to the difference between Physics and Engineering. The former tends to deal with matters more theoritcal, the latter, matters more pratical.
It worth noting that both algorithms and patterns feed into being a good software engineer, as least IMHO.
-Bill
Boyer-Moore String Searching (Score:5, Informative)
Re:Boyer-Moore String Searching (Score:4, Informative)
For some reason, I like string searching algorithms too. Check out this monster list of thirty or so different exact string searching algorithms [univ-mlv.fr], 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 (Score:5, Insightful)
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 (Score:3, Funny)
I like bubble sort.
An important algorithm I use everyday... (Score:5, Funny)
while alarm ringing
cover head with blankets
mprecate the onerous noisemaker softly
consider turning the damn thing off
if feeling remarkably hyperactive
then
lethargically slither out of blankets
sinuously stretch out arm
sigh
bang it to kingdom come
else
go back to sleep sweet sleep
endif
if hear name being called
then
see who it is
if kid brother/sister
then
ready
aim
fire
watch baneful clock execute a parabolic trajectory
in approximate direction of youngster
if target intercepted
then
ignore howls for Amnesty International
else
swear a thousand maledictions
endif
else if father
then
get out of bed hyper-quickly
if feeling watched
then
turn alarm off gently
else
kick alarm off gently
endif
else if mother
then
scan her for arms, especially those prohibited by
Geneva Convention
if result is affirmative
then
begin negotiations
else
pretend not to have seen her
increase snoring intensity
endif
endif
if feel something cold and wet being sloshed onto
blankets
then
yell blue murder
get out
endif
endwhile
end
Dinoj Surendran @ 1995 - no rights reserved
Hello World (Score:4, Interesting)
Seriously, how about Simulated Annealing or Genetic Algorithm?
Fast routing agorithm (Score:2)
simplex method (Score:5, Interesting)
linear programming, minimax game searches, network flow, primal-dual techniques for approximation algorithms......
Three favorite algorithms (Score:2, Insightful)
* 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 (Score:2)
Paul
Favorite algorithms (Score:2, Interesting)
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 (Score:2)
How about CSS? (Score:4, Funny)
discrete fast fourier transform (Score:2)
Fast Fourier Transform (Score:5, Interesting)
Shallow algorithms (Score:2, Funny)
2) Sue
3) PROFIT!!
confusing theory with engineering? (Score:2, Insightful)
The CORDIC Algorithm (Score:4, Informative)
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.
The pr0n algorithm (Score:2)
Prune your betas! (Score:5, Interesting)
DeCSS (Score:2)
MD5 Checksum (Score:2)
Top 10 (Numerical) Algorithm Papers online (Score:2, Informative)
Deep vs. important (Score:5, Interesting)
Deep and important: fast fourier transform, simplex method, LLL lattice point algorithm,
Schoof algorithm for elliptic curve point counting, etc.
Deep and unimportant: interior-point linear programming (everyone uses the simplex method in practice despite its theoretically exponential worst case running time)
Incredibly deep: Number Field Sieve. But whether it's important to practitioners is sort of a paradox.
Shallow and important: ordinary arithmetic
Shallow and unimportant: Slashdot moderation algorithm
Google's Page Rank (Score:2, Interesting)
Paul.
Huffman encoding (Score:2)
Re:Huffman encoding (Score:2)
Data compression is the area with plenty of interesting algorithms. Look, for example, at Burrows-Wheeler Transform [dogma.net]. Amazing stuff.
Compiler/Architecture Algorithms (Score:5, Interesting)
Hash tables and sort algorithms (Score:2)
Just think about it, how many times the hash tables and sort algorithms were used to render this very page?
van Jacobson's congestion avoidance and control (Score:2, Interesting)
Dr. Fun cartoon (Score:4, Funny)
Lewis Caroll's day of the week algorithm (Score:2, Funny)
Personally, I find it interesting that this algorithm was developed by the same guy who wrote Alice's Adventures in Wonderland [bibliomania.com]. 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
Best texts on algorithms (Score:2, Interesting)
The Knuth books? Or is there something better?
Finite Element (Score:2, Interesting)
In place swap of two variables (Score:2, Interesting)
No temporary storage needed!
Jono
Re:In place swap of two variables (Score:3, Informative)
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
Quantum Algorithms (Score:2)
(Even if this doesn't happen, the following algorithms still deserve honorable mention for being the first to make use of quantum parallelism to give results unattainable thus far by classical algorithms):
- Shor's algorithm for factoring and discrete log
- Grover's search algorithm
My favorite AlGoreithm (Score:5, Funny)
The funniest algorithm (Score:4, Interesting)
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.
Douglas Adams was right (Score:2, Interesting)
Djikstra's Communicating Semaphores (Score:3, Interesting)
With Mark Weiser's addition of the "T" primative (more commonly called "non-blocking P" i.e. "Try to P but if that would block return an error flag instead.") you have a fantastically powerful tool in a tiny amount of code.
For instance: I was able to implement a kernel for an actor-based, real-time, prioritized, preemptive multitasking system, including initialization code, an idle task, and a minimal startup task table (i.e. everything but the application tasks and device drivers):
- In under 512 bytes of code and initialization data.
- On an 8080.
Communicating P, V, and T, (along with a flavor of "V" doubling as a return-from-interrupt) are a complete set of primitives for such work.
For those not familiar, an "actor" in this context is a class such that each instance of that class or any subclass of it is a separate thread of execution. Messages are exchanged between threads via queues on semaphores rather than C++ member function calls / Smalltalk message sends, but otherwise all the object-oriented concepts apply directly.
Communicating Semaphores handle locking (like normal semaphores), message queueing, and resource allocation (by holding a queue of messages, each of which represents, or actually is, a resource).
"T" lets interrupt routines run initially as parasites on the interrupted task, then "T" a free-message-buffer queue, fill in the message, and "V" it to the incoming-work semaphore of the actual service routine as the interrupt exits - provoking a context switch if the service routine is higher priority than whatever was running. The interrupt routine can punt and return to the interrupted task if no buffers are available.
Parsing, interpreration and game theory (Score:2)
There's some good ones (like QuickSort) that should be #1, but here's a random collection of some algorithms I find interesting:
Bresenham Line Algorithm (Score:2)
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.
1000 is too naive (Score:5, Interesting)
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 (Score:3, Funny)
My Personal Favorite (Score:4, Funny)
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:
(Ducks)
Elevator Awareness Algorithm (Score:3, Funny)
Where x is the number of people in the elevator and y is the number of people who know for sure who farted.
What is a deep algorithm? (Score:4, Insightful)
Pessimal Algorithms and Simplexity Analysis (Score:3, Interesting)
Re:My favorite algorythm (Score:2)
Re:My favorite algorythm (Score:2, Informative)
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.
Re:My favorite algorythm (Score:3, Funny)
(I hated to lose the ability to mod, but I couldn't resist!
Re:Basic of algorithms (Score:2)
Author: David Berlinski
Title: The Advent of the Algortihm
Publisher: Harcourt
Re:Basic of algorithms (Score:5, Informative)
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 (Score:5, Informative)
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 item2. 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?
algorithm example: long division (Score:2, Informative)
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 to understand what's an algorithm. (Score:2)
Re:Basic of algorithms (Score:4, Informative)
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 (Score:4, Interesting)
A little side note: as a kid I used to crash both web servers and browsers by implementing this as a CGI script!
Re:Theoretically interesting/Practically irrelevan (Score:2, Insightful)
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?
But smart people won't ignore the topic... (Score:4, Insightful)
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.
Not all answers are in Knuth (Score:2)
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.
Re:But smart people won't ignore the topic... (Score:4, Insightful)
Re:Theoretically interesting/Practically irrelevan (Score:2, Insightful)
You're kidding yourself (Score:4, Insightful)
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.
Re:Are sorting algorithms "deep"? (Score:2, Funny)
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"? (Score:2)
Re:Are sorting algorithms "deep"? (Score:3, Interesting)
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:Binary Search (Score:5, Informative)
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:If you have to ask (Score:2)
But I will execute Jessus's favorite algorithm, and turn the other cheek.
.solution:
mov eax, [input]
cmp eax, bitchslap
jz
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 ;
out dl, ah ; write to the cheek port
return
Re:Euclid's Algorithm? (Score:3, Interesting)
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?