Perturbation theory[0] is an algorithmic way to find approximate solutions to problems you don't know how to solve. The idea is to perturb a known solution to a closely related problem. It is pivotal in quantum mechanics.
Ask HN: What's your favorite elegant/beautiful algorithm?
61–70 of 507 posts
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#62Learning Huffman Coding in SICP was an amazing thrill--and all these years later it's still up there in bang-for-the-buck neatoness.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#63Counting sort. It's extremely elegant and has odd complexity properties that make it interesting.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#64Euclid'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. http://mathforum.org/dr.math/faq/faq.peasant.html https://en.wikipedia.org/wiki/Karatsuba_algorithm
Yup. Applying Russian multiplication to matrices is surprisingly effective for evaluating recursive relations (it can evaluate the nth Fibonacci number in O(log n)) Karatsuba is also a nice 'proof-of-concept' algorithm (it shows that it is possible to do better than O(n^2) at multiplication in the simplest way possible) that's also very practical - and it has a nice anecdote behind it :)
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#65Diffie–Hellman. I know that cryptography can get much fancier and more clever, but Diffie–Hellman took a concept my intuition told me was impossible and showed that it's possible in a really simple, elegant way. Learning about it was the first time I realized how beautiful the math behind computer science is. It's also a great insight into just how fundamental the concept of computational complexity is.
> a concept my intuition told me was impossible and showed that it's possible in a really simple, elegant way
I agree but, to be fair, the key ingredient ("discrete logarithms are hard") is not simple at all.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#66Diffie–Hellman. I know that cryptography can get much fancier and more clever, but Diffie–Hellman took a concept my intuition told me was impossible and showed that it's possible in a really simple, elegant way. Learning about it was the first time I realized how beautiful the math behind computer science is. It's also a great insight into just how fundamental the concept of computational complexity is.
So true. Securely exchanging keys is an abstract concept until you see those paint colors mixing!
I love the idea of how essentially we have never met and we're shouting across a crowded room but no one else can understand our conversation.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#67I like Dijkstra's algorithm for finding the shortest path between two nodes in a graph. It's not so much that it is "beautiful", but it is a remarkably simple algorithm that a human can follow manually. The reason it is efficient is easily understood (it's easy to see how we are able to "finalize" nodes because it's obvious there is no shorter path to that node), and it takes what would otherwise be a complicated tas…
What I like about Dijkstra's algorithm is not that you can calculate the shortest path between two nodes, but that you can calculate the shortest path from one node to every other node, and do it one pass in O(n) time. I'm not sure it's at all obvious that it should be possible to do that.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#68I like Dijkstra's algorithm for finding the shortest path between two nodes in a graph. It's not so much that it is "beautiful", but it is a remarkably simple algorithm that a human can follow manually. The reason it is efficient is easily understood (it's easy to see how we are able to "finalize" nodes because it's obvious there is no shorter path to that node), and it takes what would otherwise be a complicated tas…
For similar reasons, I really like the A* pathfinding algorithm. If you implement it on a grid with obstacles, draw the grid on screen, and update it as the algorithm runs, it's both beautiful and very intuitive to watch.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#69Been learning about Hashlife[0] the last few days. It's pretty cool.
[0] http://www.drdobbs.com/jvm/an-algorithm-for-compressing-spac...
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#70Bloom filters are interesting. A bunch of different hashes as kind of fingerprint that make search fast but with caveats: negative answer is negative, positive answer might be negative.