BOGO sort! /s
I really like backtracing algorithms used to solve huge graphs without actually visiting all nodes. Pretty elegant IMO.
Ask HN: What's your favorite elegant/beautiful algorithm?
11–20 of 507 posts
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#12Sleep sort :)
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#13I think Krylov subspace methods are particularly sophisticated and elegant, and they come with the added advantage of being best-in-class.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#14SimHash is beautiful once you understand how it nudges apparent randomness into useful order.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#15Hello World! in python
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#16The "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 algorithms which are extremely hard to do functionally (the whole algorithm is about moving pointers around).
It's also a good example of practical Vs theoretical efficiency. In the worst case it is no more efficient than the algorithm it replaced, in practice it is hundreds of times more efficient. The "not moving back" feels like it should save at most half the time, it on fact speeds things up by often 10 times (this is because watches are often moved around until they reach some "boring" variables, where they lay undisturbed).
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#17Karger'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
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#18Shor's Algorithm blew my mind after getting the slightest grasp of it thanks to Scott Aaronson: https://www.scottaaronson.com/blog/?p=208
The LLL lattice basis reduction algorithm and the Coppersmith method are also jaw-dropping
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#19Euclid's GCD algorithm, and Russian peasant multiplication.
I never heard about "Russian peasant multiplication" before.
When I read it, I thought you were referring to Karatsuba multiplication. As it turns out, you didn't.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#20Binary search. Very simple, incredibly powerful; can search on data or math function.
It's the basis for other CS concepts.
JS implementation: https://gist.github.com/netgusto/90c8e0e7019a832cbf95eac58e1...