Nothing Earth shattering but the algorithm for finding anagrams: just sort by letters and compare resulting strings. It was probably the first elegant algorithm I saw before even seeing a computer.
I still have 70-ish chars long Perl oneliner I wrote nearly 20 years ago, which lists anagrams from the provided wordlist.
Ask HN: What's your favorite elegant/beautiful algorithm?
151–160 of 507 posts
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#152Earlier quoted context omitted.
Isn't this bit: const mid = Math.floor((right + left) / 2); susceptible to overflow? EDIT: Hm, perhaps not (in JS). Number.MAX_SAFE_INTEGER is much greater than I expected.
Indeed, Java's binary search had this bug for a while! It was found through automatic verification, by the way. https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
also some CS books
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#153Viterbi algorithm used in convolutional codes
It is used in DVB-T combined with Reed-Solomon code for example.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#154Surprised nobody's mentioned Hyper Log Log (or its more recent variants). A probabilistic constant-space unique cardinality estimator (i.e. if I see a billion events, how many are unique?) that also supports set operations.
The underlying reasoning behind PCSA/HLL (that if you squint, you can use the zeros and ones from a hash as analogues to coin-flipping, and can use the probability of the rarest event seen to estimate the total number of events seen) is excellent.
Count-min-sketch is also beautifully simple.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#155The (fairly simple) nimber algorithm for optimal nim play which can then be applied to other games e.g. dots and boxes
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#156Fast Fourier Transform. I remember learning about using roots of unity and thinking it was black magic.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#157Burrows-Wheeler transform https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf... Has something of Cantor's diagonal argument about it.
Can you elaborate on how this is related to diagonalization (other than the surface resemblance)?
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#158Union-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).
I like implementing type systems
Could you expand on this? This is something I've just started reading about. I'd be interested in good resources to use to get started. At the moment I've just started reading TAPL.
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#159Binary 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...
Isn't this bit: const mid = Math.floor((right + left) / 2); susceptible to overflow? EDIT: Hm, perhaps not (in JS). Number.MAX_SAFE_INTEGER is much greater than I expected.
Incidentally, as outlined in this Julia FAQ, native machine arithmetic with overflow will deal with this correctly.
mid = (lo + hi) >>> 1
EDIT: legibility
Re: Ask HN: What's your favorite elegant/beautiful algorithm?
#160I like various, older compression algorithms: Huffman, LZ77/LZSS, LZ78/LZW.