What algorithm blows your mind? (Reddit compsci)
1–10 of 71 posts
Re: What algorithm blows your mind? (Reddit compsci)
#2For 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
Re: What algorithm blows your mind? (Reddit compsci)
#3How is generation of the Mandelbrot Set not on this list? That something so simple could produce something so indescribably beautiful...
Re: What algorithm blows your mind? (Reddit compsci)
#4Kruskal, Prims and reverse-delete algorithms to find the Minimum Spanning Tree in a graph, are fun, not that hard, and very practical.
http://en.wikipedia.org/wiki/Minimum_spanning_tree
Think about it, every time you get a google map direction/route, one of them is in play.
Re: What algorithm blows your mind? (Reddit compsci)
#5In heuristics, I like Asynchronous teams [ http://www.cs.cmu.edu/afs/cs/project/edrc-22/project/ateams/... ]
In multi-robot coordination I like the free market system [ http://www.frc.ri.cmu.edu/projects/colony/architecture.shtml ]
And regarding machine learning I like neural nets (MLP), however the algorithms that currently blow my mind are convoluted neural networks (CNNs) and deep belief networks trained with auto-encoders. http://www.youtube.com/watch?v=AyzOUbkUf3M on the 21-minute mark to see it in action.
Re: What algorithm blows your mind? (Reddit compsci)
#6Ok, 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.
Re: What algorithm blows your mind? (Reddit compsci)
#7How is generation of the Mandelbrot Set not on this list? That something so simple could produce something so indescribably beautiful...
Agreed, but while the notation's simple, the iterative effect is hard to follow -
it's like a spinning rod, angle doubled and length squared each iteration, with a rod of fixed length and angle added to it each iteration (if the spinner is facing away, it gets shorter, but if towards, it gets longer). Iterate til it goes over 2. If it doesn't then it's in the Set (or maybe you need to iterate more...). [that's my current understanding]
It's pretty clear to me that I can't visualize what it will do over a few iterations (apart from simple cases) - and I sure can't see how it would produce self-similar (ie fractal) shapes. Agreed that that's amazing.
Re: What algorithm blows your mind? (Reddit compsci)
#8The heapsort. It sounds very strange.
Re: What algorithm blows your mind? (Reddit compsci)
#9It surprised me that matching is not NP-complete.
Re: What algorithm blows your mind? (Reddit compsci)
#10Compressed 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)