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

11–20 of 71 posts

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

#11

Post by Figs »

endtime wrote: post #2

For me, it's boosting. Basically, if you make the assumption that your weak classifier can achieve X% correct on any random distribution over a data set, then you can create an ensemble of weak learners that together get Y% correct on the same set, where Y > X. Question 3 here will walk you through the proof: http://bit.ly/cQ03na

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/handouts/cs221-ps2.pdf

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

#12

Post by jgrahamc »

I'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#...

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

#13

Post by thalur »

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?

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

#14

Post by benmccann »

Figs wrote: post #11
endtime wrote: post #2

For me, it's boosting. Basically, if you make the assumption that your weak classifier can achieve X% correct on any random distribution over a data set, then you can create an ensemble of weak learners that together get Y% correct on the same set, where Y > X. Question 3 here will walk you through the proof: http://bit.ly/cQ03na

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.

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

#15

Post by elblanco »

Some of the sorting algorithms, as somebody learning them, it's almost entirely opaque how somebody could come up with those.

It seems like they must have sprung forth wholecloth to the inventor in the shower...it's almost impossible to have iteratively developed some of them because even small changes in the algorithms produce terrible results. I remember thinking over and over again, "how the hell could somebody come up with this?"

Searching in comparison looks very engineered, very studied, something that most people could come up with given need, motivation and time.

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

#18

Post by daeken »

nl wrote: post #16

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.
Post reply on HN