261–270 of 507 posts
Levenshtein distance, a dynamic programming algorithm for determining the edit distance between two sequences - the number of insertions, deletions or substitutions required to convert one sequence to the other. https://en.wikipedia.org/wiki/Levenshtein_distance
Quicksort ( especially implemented in a functional language like haskell ). It's a perfect mix of an elegant algorithm and a beautiful implementation. Simple, elegant, beautiful and powerful. What more can you want in an algorithm.
Duff's device. Because you will first look at it in disgust, but then you realize how clever it really is. See: https://en.wikipedia.org/wiki/Duff%27s_device
Even sadder because the same effect can be achieved cleanly (and "optimizably")by using as "switch" followed by a "while".
Euclid's GCD algorithm, and Russian peasant multiplication.
I like this version of the Euclid algorithm: 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.
Earlier quoted context omitted.
Nope. An algorithm has to be effective. You can find pathological cases for k-means such that it will never converge on anything useful. So if you set your termination case to be convergence it will never terminate and if you don't then it will never be effective.
I think you might be in the minority in this opinion. Many algorithms have pathological cases but are still considered algorithms
Fistly, wavelet trees! Wavelet trees with something like RRR encoding for the bit vectors lets you work with massive datasets in positively tiny space and constant time. They're not even expensive to construct! My favorite introduction to the whole space of rank/select-friendly structures is Alex Bowe's tutorial: https://alexbowe.com/wavelet-trees/
I constantly agitate for people to realize that we now have an algorithm for O(n) generalized sorting. It's called discrimination sort, and while it's a complex subject its quite elegant once you internalize the algorithm. There's a talk by Prof. Henglein here: https://www.youtube.com/watch?v=sz9ZlZIRDAg
2017 saw the recommendation of a truly phenomenal approach to indexing data, using simple leaning structures. These indexes are poorly explored, there's still a ton of headroom here, but the paper is an incredibly cool read and very approachable: https://arxiv.org/abs/1712.01208
Another really cool family of algorithms and associated structures in distributed systems is CRDTs. They're poorly understood, but in research they have largely superseded operational transforms. The Wikipedia page branches off into lots of good research: https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
If we slightly broadened the lens of what is an algorithm, my favoriate category-theoretic approaches to solving problems include Recursion Schemes which are a technique to totally separate the specification of recursive algorithms over data structures from both the structures and the code that the algorithm runs to compute a result (Patrick from Github has a great series on them here: https://blog.sumtypeofway.com/). I also love the modern and rapidly growing "Ghosts of Forgotten Proofs" as a way to let the compiler assert you've properly built and/or terminated values: https://github.com/matt-noonan/gdp-paper/releases/download/j...
The (fairly simple) nimber algorithm for optimal nim play which can then be applied to other games e.g. dots and boxes