Ask HN: What's your favorite elegant/beautiful algorithm? • Hacker News Board

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#51

Post by sandreas » Wed, Oct 17, 2018, 7:13 AM UTC

The Sauvola adaptive thresholding algorithm did a great job as i tried to clean up scanned text images before OCR processing. It's quick, quite easy to implement and produced great results. Here is a sample: http://scikit-image.org/docs/dev/auto_examples/segmentation/...

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#52

Post by IvyMike » Wed, Oct 17, 2018, 7:13 AM UTC

skrebbel wrote: post #34

Long division, because it shows that you don't need computers to run algorithms and that, in fact, any kid can do it.

And it was amazing the feeling of power that gave him. https://urbigenous.net/library/power.html

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#53

Post by KerrickStaley » Wed, Oct 17, 2018, 7:14 AM UTC

Union-find data structure: https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#54

Post by edoo » Wed, Oct 17, 2018, 7:15 AM UTC

A properly implemented queue that utilizes the CPU compare and swap instructions on the pointers for nearly overhead-free, mutex free concurrency.

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#55

Post by josephg » Wed, Oct 17, 2018, 7:15 AM UTC

JonathanMerklin wrote: post #48

netgusto wrote: post #20

Binary 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.

Not in Javascript, where everything is a double precision float. You would lose precision at about 2^51, but that’s not a limit that will meaningfully affect us for good while.

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#56

Post by calciphus » Wed, Oct 17, 2018, 7:15 AM UTC

The 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 individual members have a preferential ranking of the other.

https://en.wikipedia.org/wiki/Stable_marriage_problem#Soluti...

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#57

Post by moviuro » Wed, Oct 17, 2018, 7:16 AM UTC

dvh wrote: post #35

Bash fork bomb

  :(){ :|:& };: #Don't run this at home

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#58

Post by 0n34n7 » Wed, Oct 17, 2018, 7:17 AM UTC

Kalman Filter - Smoothed out all the outliers on a location tracking project I worked on - https://en.m.wikipedia.org/wiki/Kalman_filter

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#59

Post by motiw » Wed, Oct 17, 2018, 7:19 AM UTC

Hash functions are so powerful in so many algorithms and optimizations

Re: Ask HN: What's your favorite elegant/beautiful algorithm?

#60

Post by marcodave » Wed, Oct 17, 2018, 7:20 AM UTC

I remember having my mind blown studying the Ukkonen algorithm, for string search prefix trees. Especially the fact that was built from the naïve implementation O(N^3) brought down to O(N)