The FFT algorithm is perhaps the most elegant and useful work of the 20th century. Modern communications would probably not be possible with out it but it's utility isn't limited to electronics It is used across the list of scientific disciplines and even in finance and economics. Next time you make a call on your smart phone, hoist a beer to Cooley, Tukey, and Carl Gauss
Ask HN: What's your favorite elegant/beautiful algorithm?
321–330 of 507 posts
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#322Tarjan's strongly connected components algorithm. It finds strongly connected components in a graph (read: cyclic dependencies), while doing a topological sort (read: you could use it for a package manager to determine which packages to install first). It is proof of a very deep understanding of the nature of graphs. Edit: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_...
At my work, we have a simulation system that uses Tarjan's algorithm to determine the order that update's need to be applied in order to properly propagate to all downstream nodes. Thought it was pretty neat when I realized our connected components code could do that for us.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#323The FFT algorithm is perhaps the most elegant and useful work of the 20th century. Modern communications would probably not be possible with out it but it's utility isn't limited to electronics It is used across the list of scientific disciplines and even in finance and economics. Next time you make a call on your smart phone, hoist a beer to Cooley, Tukey, and Carl Gauss
It's also critical for factoring prime numbers and SETI signal intelligence processing. Truly a gem.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#324There's something fundamentally appealing about Genetic Algorithms to me. Even though they don't apply everywhere, and even though "hill climbing with random restart" can be just as effective in many cases, there's just something awe inspiring about the idea of mimicking evolution.
I also really like other related "nature inspired algorithms"[1] like Ant Colony Optimization, Particle Swarm Optimization, etc.
[1]: http://www.cleveralgorithms.com/nature-inspired/index.html
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#325The Gale-Shapley Algorithm to solve the "Stable Marriage" problem. 2012 Nobel Prize in Economic Sciences for its wide-ranging use in medicine, education, and resource allocation. It's fairly easy to implement a basic version of it, feels intuitively obvious once explained, and has been applied to everything from organ transplants to student placement in elementary schools. Really, any place you have two groups where…
Interesting! I knew that med school applicants were accepted on some sort of ranking and matching process but didn't realize there was a real algorithm behind it. This, or one similar, seems to be what's behind it.
There's no matching process at the beginning of medical school, but there is for assigning med school graduates to residencies. This variant of the problem is NP-hard, so there's no exact solution, but matching still works pretty well. https://web.stanford.edu/~alroth/papers/rothperansonaer.PDF has all the details.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#326Extremely simple one, but my favorite is an algorithm for determining if two words are anagrams of each other: The Fundamental Theorem of Arithmetic states: "every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors."[1] So to determine that two words are anagrams of…
Nice in theory, but in practice you wouldn't implement it like that, especially if the words can be longer than your machine integer allows. Sorting and comparing is more elegant than invoking a BigNum library, imho (and has smaller footprint). This shows that theoretical elegance != implementation elegance.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#327Leslie Lamports Paxos protocol has to be in to top 5 algorithms/protocols (https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf). This enabled so much progress in computing its unreal.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#328Extremely simple one, but my favorite is an algorithm for determining if two words are anagrams of each other: The Fundamental Theorem of Arithmetic states: "every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors."[1] So to determine that two words are anagrams of…
Nice in theory, but in practice you wouldn't implement it like that, especially if the words can be longer than your machine integer allows. Sorting and comparing is more elegant than invoking a BigNum library, imho (and has smaller footprint). This shows that theoretical elegance != implementation elegance.
Or, for better time complexity (with a bit of extra space) making a map of char -> frequency and comparing the results.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#329Extremely simple one, but my favorite is an algorithm for determining if two words are anagrams of each other: The Fundamental Theorem of Arithmetic states: "every integer greater than 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors."[1] So to determine that two words are anagrams of…
[deleted]
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#330The FFT algorithm is perhaps the most elegant and useful work of the 20th century. Modern communications would probably not be possible with out it but it's utility isn't limited to electronics It is used across the list of scientific disciplines and even in finance and economics. Next time you make a call on your smart phone, hoist a beer to Cooley, Tukey, and Carl Gauss
Even after working with it for 15 years I still find new and interesting things about it.