Raft, because it's designed to be easy to understand.
Ask HN: What's your favorite elegant/beautiful algorithm?
141–150 of 507 posts
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#142Dancing Links (Knuth's paper: https://arxiv.org/pdf/cs/0011047.pdf ) > In computer science, dancing links is the technique suggested by Donald Knuth to efficiently implement his Algorithm X. Algorithm X is a recursive, nondeterministic, depth-first, backtracking algorithm that finds all solutions to the exact cover problem. Some of the better-known exact cover problems include tiling, the n queens problem, and Sudoku…
+1 Dancing Link. Donald Knuth rules !
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#143Fortune's algorithm for generating Voronoi diagrams from a set of points on a plane is a beautifully elegant algorithm with a unique visual component.
Check the external links on the wikipedia page for an excellent implementation that you can run in your browser.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#144Union-find data structure: https://en.wikipedia.org/wiki/Disjoint-set_data_structure
I love this algorithm (I like implementing type systems) but I always feel a bit naughty when I implement it, as AFAIK it can't be implemented with immutable data structures (not efficiently, at least).
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#145Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#146K - means clustering, which I learned about recently. For non-machine learning folks, this algorithms helps in grouping relevant items together. As a practical, using this algorithm you can segment your customers based on their purchase history and interests. The actual algorithm is very simple, imagine a lot of points on the 2D plane and each of them represent customers, whom you want to segment/cluster. Now, chose…
K-means is not an algorithm, it's a heuristic for an Np-hard problem.
Isn't a method that gives an approximate or best-fit estimate to a problem still an algorithm, if it terminates?
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#147Diffie–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.
I am so glad that I took Cryptography as an elective in college even though the course brought down my grades :)
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#148cps transformation (continuation passing style). Transform any control flow patterns (loops, calls, non-tail recursion, exceptions, coroutines) into nothing but closures and tail calls!
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#149K - means clustering, which I learned about recently. For non-machine learning folks, this algorithms helps in grouping relevant items together. As a practical, using this algorithm you can segment your customers based on their purchase history and interests. The actual algorithm is very simple, imagine a lot of points on the 2D plane and each of them represent customers, whom you want to segment/cluster. Now, chose…
K-means is not an algorithm, it's a heuristic for an Np-hard problem.
It is absolutely an algorithm in the sense of "a set of rules to be followed". I think you mean that it doesn't guarantee an optimal solution. That just means it's a heuristic algorithm, same as simulated annealing is a heuristic algorithm for solving optimisation problems.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#150cps transformation (continuation passing style). Transform any control flow patterns (loops, calls, non-tail recursion, exceptions, coroutines) into nothing but closures and tail calls!
Also a step into non determinism and some logic programming.