21–30 of 71 posts
http://www.beyond3d.com/content/articles/8/
It's been discussed here before, and no doubt it'll be cited numerous times in the comments of that reddit post, but it was the first time I'd ever seen such trickery. When I got into low level DSP programming I saw many more examples of clever hacks, but this is the one which sticks in my mind above all of those.
Bloom Filters: http://en.wikipedia.org/wiki/Bloom_filter Sort of a probabilistic hash, where you trade space for accuracy. But it's also like a memory function - it can remember if it has seen a piece of data before.
What I love about bloom filters is that when checking to see if something is in a bloom filter, you can only get false positives, not false negatives. That property is just awesome to me.
It lets you search a completely unstructured N-item search space using the square root (!) of N queries, not the N queries you'd think were necessary.
Also, the algorithm is so simple that once you know it's possible, and provided you're very comfortable with basic quantum mechanics, it's almost trivial to find the algorithm.
The entire message is coded into a single number and it approaches the theoretical maximum for compression.
Too bad about software patents!
And the reasons why it blows my mind:
(1) Knuth called it "Algorithm of the year 1973" (possibly because it beat an intuitive lower bound that he had for a problem I can't remember).
(2) It's relatively new for a "core", first-principles algorithm. Ukkonen's algorithm is from 1995, although there are earlier versions.
(3) This BOOK is largely devoted to the many, many applications of suffix trees: http://www.amazon.com/Algorithms-Strings-Trees-Sequences-Com... It should be required reading for anyone interested in advanced algorithms.
(4) Longest common substring in linear time.
(5) Lempel-Ziv decomposition in linear time.
(6) Longest repeated substrings in linear time.
And too many more to list.
My mind is blown by the algorithm for matching with mismatches which I present in the first chapter of my thesis. It shouldn't be, given that I discovered this algorithm -- but somehow "I take the Fourier Transfer of the FreeBSD kernel" sounds more like the punch line to a joke than the first step in an algorithm.
http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen...
At least to me, it seems hard to imagine that multiplying two N-bit integers could be done with less than O(N^2) operations. Schoenage-Strassen lets you do it using O(N log N log log N) operations!
It's a heap supporting merging in log(n). While it's usage might not be very common, it is a beautiful data structure.