101–110 of 507 posts
Karger's randomized contraction algorithm for finding a min-cut. It's a common algorithm to introduce students into the world of randomized algorithms. Also a shameless plug. My friend and I came up with this pseudo-polynomial time algorithm for subset sum that can be taught in a single session. It is faster than the standard dynamic programming algorithm. https://arxiv.org/abs/1807.08248
The "2 watched literal" algorithm used in sat solvers (here is a random blog post I found by googling http://haz-tech.blogspot.com/2010/08/whos-watching-watch-lit... ). The algorithm has many lovely features. It is very efficient -- it is used in basically every SAT solver with minimal modifications. It's not entirely trivial it works, particularly the backtracking part. It is a good example of how there are algorith…
What?: Quite powerful data structure for geographic data.
Why?: I dabbled with geodata for quite a bit before discovering PostGIS and the R*-tree. Operations that took me several seconds before (geojson+ruby) could be computed in well under 100ms directly on the Database.
[1] https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_v...
Euclid's GCD algorithm, and Russian peasant multiplication.
Make a rectangle with side lengths of 2 positive real numbers. Put the biggest square inside (i.e. against a short side) that you can, add as many as fit. If there's still a gap, put the biggest square that fits in that, repeating until filled.. If you never fill the gap, the ratio is irrational. The number of squares of each size used gives the ratio's continued fraction.
AES is beautiful as well. And I love Huffman encoding. hm, what else. Bloom filters are awesome.
I suspect FFT is beautiful, too, but it surpassed my ability to understand.