for me simplex (george-dantzig) is very very cool.
What algorithm blows your mind? (Reddit compsci)
31–40 of 71 posts
Re: What algorithm blows your mind? (Reddit compsci)
#32Earlier quoted context omitted.
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.
Also the fact that you can use more bits per element and reduce the error rate for false positives. Using around 3 bytes per element, can bring the error rate down to 0.001%.
also the fact that you can use multiple hash functions to reduce the error rate even further is pretty nice. this is of course without incurring the overhead of extra storage space...
Re: What algorithm blows your mind? (Reddit compsci)
#33Lenstra-Lenstra-Lovasz:
http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%9...
High dimensional work is bloody hard, and this algorithm works amazingly well. I've spoken with Lenstra (one of them) and he's amazingly insightful on these things. He helped to crystalise my understanding of why high-dimensional spheres should be thought of as "spikey," rather than "round."
Re: What algorithm blows your mind? (Reddit compsci)
#34I've always found error detecting/correcting codes to be lovely. A great example, that's easy to understand, is the Hamming(7,4) code. http://en.wikipedia.org/wiki/Hamming(7,4) I got interested in these codes because of the problems involved with deep space communication. http://en.wikipedia.org/wiki/Error_detection_and_correction#...
Also, compression. Wikipedia got real good about error detection and correction and compression algorithms past few years http://en.wikipedia.org/wiki/Category:Error_detection_and_co...
Re: What algorithm blows your mind? (Reddit compsci)
#35Ok, not quite an algorithm, but the PCP theory ( http://en.wikipedia.org/wiki/PCP_theorem ) is easily the most mind-blowing result in comp sci in the past 20 years.
PCPs are true magic. I once learned how to construct a PCP-proof with verification using just 7 bits, but it still feels like magic to me. The 3-bit variants are just crazy.
Re: What algorithm blows your mind? (Reddit compsci)
#36My 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.
Link?
Re: What algorithm blows your mind? (Reddit compsci)
#37I've always found error detecting/correcting codes to be lovely. A great example, that's easy to understand, is the Hamming(7,4) code. http://en.wikipedia.org/wiki/Hamming(7,4) I got interested in these codes because of the problems involved with deep space communication. http://en.wikipedia.org/wiki/Error_detection_and_correction#...
I learned Hamming code in school this summer (digital systems) .It was probably the single most magical thing (even more than flipflops! Loops make memory!) I was exposed to that class.
I remember upon learning it someone went "wow, who came up with that". The prof answered dryly "some genius named Hamming".
Re: What algorithm blows your mind? (Reddit compsci)
#38I'd go with Tarjan and Hopcroft's planarity testing algorithm, whose runtime is linear in the number of vertices.
Re: What algorithm blows your mind? (Reddit compsci)
#39More of a complexity result than an algorithm, but it is a really fun result anyway. In complexity class we were given the problem to simulate an n-tape non-deterministic Turing machine with a 2-tape non-deterministic Turing machine with just a constant slow-down (which turned out to be 3). It really gave an insight into the power of non-deterministic choice.
Re: What algorithm blows your mind? (Reddit compsci)
#40Singular value decomposition. It continually amazes me how many problems -- from noise reduction to Netflix prediction -- SVD can be usefully applied to. http://en.wikipedia.org/wiki/Singular_value_decomposition
The core ideas behind SVD and eigen values are very rich and profound. It has always fascinated me when I studying maths in undergrad.
Someone else already mentioned compressed sensing, which expands on some of those ideas. Terrence Tao had a pretty good presentation on the topic: http://terrytao.files.wordpress.com/2009/08/compressed-sensi...