Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

What algorithm blows your mind? (Reddit compsci)

reddit.com

Post reply on HN
Print view View original

41–50 of 71 posts

Re: What algorithm blows your mind? (Reddit compsci)

#41

Post by cdavid »

thalur wrote: post #13
jefffoster wrote: post #10

Compressed Sensing is exciting - using a sequence of low res images to obtain a higher resolution sample. It was discussed in Wired ( http://www.wired.com/magazine/2010/02/ff_algorithm/all/1 ) together with a compelling example (minimizing the time of a young patient in an MRI machine)

That sounds far too good to be true. I guess if you don't care about the fine details then its a decent technique, but to take the MRI example, what if the thing that was wrong was only visible in those small details?

There are other things which sound too good to be true and yet are true (the sampling theorem for exact reconstruction of periodic signals is pretty unintuitive IMO, and even more "magic")

Re: What algorithm blows your mind? (Reddit compsci)

#42

Post by cperciva »

jules wrote: post #36
cperciva wrote: post #27

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.

Link?

http://www.daemonology.net/papers/thesis.pdf

Re: What algorithm blows your mind? (Reddit compsci)

#43

Post by anamax »

jefffoster wrote: post #10

Compressed Sensing is exciting - using a sequence of low res images to obtain a higher resolution sample. It was discussed in Wired ( http://www.wired.com/magazine/2010/02/ff_algorithm/all/1 ) together with a compelling example (minimizing the time of a young patient in an MRI machine)

Compressed sensing was the subject of a recent talk which can be viewed at ee380.stanford.edu as well as via itunes and youtube.

Re: What algorithm blows your mind? (Reddit compsci)

#44

Post by jules »

RiderOfGiraffes wrote: post #33

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

Why are high dimensional spheres spikey?

Re: What algorithm blows your mind? (Reddit compsci)

#45

Post by [deleted] »

benmccann wrote: post #14
Figs wrote: post #11

Earlier quoted context omitted.

Please don't post links through bit.ly and other URL indirection sites. It hurts the web by making it much more difficult to follow the link in the case that an intermediary goes out of business. Hacker News and your post will probably be around in a few years, but will bit.ly? (What's their business model, exactly...?) For future reference, the unshortened version of his link is: http://www.stanford.edu/class/cs221/…

Not to mention the real URL shows that the link is going to Stanford whereas I have no clue whether the shortened link is going to Stanford, an XXX site, or rick rolling me.

[deleted]

Re: What algorithm blows your mind? (Reddit compsci)

#46

Post by hxa7241 »

joe_bleau wrote: post #23

CORDIC ( http://en.wikipedia.org/wiki/Cordic ), used to efficiently calculate trig functions with only very basic hardware requirements (add, sub, shift, and table lookup).

. . . relatedly, from Jim Blinn, from Marvin Minsky -- drawing a circle (near enough), or doing incremental rotation, using just integer add, sub, and two shifts:

   N = 128 * 3.14159
   X = 1000
   Y = 0

   MOVE(X,Y)
   FOR I = 1 TO N
      X = X - (Y >> 6)
      Y = Y + (X >> 6)
      DRAW(X,Y)

Re: What algorithm blows your mind? (Reddit compsci)

#47

Post by cosbynator »

Welzl's algorithm for minimum enclosing disk does it for me. Pick a point, recursively see if it is in the disk without the point - if not, it is part of the definition the minimum enclosing disk (forced to be on the boundary). Randomized, simple, clean and expected O(n).

Not enough people know about it! http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.46....

Re: What algorithm blows your mind? (Reddit compsci)

#48

Post by RiderOfGiraffes »

jules wrote: post #44
RiderOfGiraffes wrote: post #33

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

Why are high dimensional spheres spikey?

Ah. I really should write that up. Far too long to explain in a comment here, far to interesting (to me!) to forget or ignore.

I'll write it up and submit it. Anyone who cares to email me can get an early version to read, and your feedback would be useful.

Please.

Thanks.

Re: What algorithm blows your mind? (Reddit compsci)

#49

Post by rhettinger »

The Burrows-Wheeler transform used in bzip2 is truly mind-blowing.

Many algorithms are ordinary genius (eventually you would have come up with it because the problem space dictates the solution), but this one is extraordinary genius (mind-blowingly original and non-obvious). Every time I see it, I'm amazed that it works.

Re: What algorithm blows your mind? (Reddit compsci)

#50

Post by Retric »

cdavid wrote: post #41
thalur wrote: post #13

Earlier quoted context omitted.

That sounds far too good to be true. I guess if you don't care about the fine details then its a decent technique, but to take the MRI example, what if the thing that was wrong was only visible in those small details?

There are other things which sound too good to be true and yet are true (the sampling theorem for exact reconstruction of periodic signals is pretty unintuitive IMO, and even more "magic")

Filling in missing information with a reasonable guess is vary different from having accurate information. Looking at a low res impressionist painting you are going to fill in based on reasonable estimates for the real world not what is actually there.
Post reply on HN