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

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

#241

Post by n4r9 » Wed, Oct 17, 2018, 2:03 PM UTC

vanderZwan wrote: post #234

n4r9 wrote: post #114

Earlier quoted context omitted.

Could you explain what you mean by that a little more? I looked at the Clustering section of the Wikipedia page for Mean-Shift: https://en.wikipedia.org/wiki/Mean_shift#Clustering but I don't get how C and r are chosen, nor how the method is supposed to be "non-parametric" given that you need such parameters to begin with. Also, how are you supposed to assign all points to separate clusters, and how would you determi…

Thanks for not just looking for an answer to your own question but also sharing it! > So how does mean shift come into the picture? Mean shift exploits this KDE idea by imagining what the points would do if they all climbed up hill to the nearest peak on the KDE surface. It does so by iteratively shifting each point uphill until it reaches a peak. I wonder if this would still work with high-dimensional data. Distance…

Without looking much further into it, I can't imagine it going very wrong. My intuition says that the density function will be bounded, since you're working with a finite number of points, therefore you'll always be able to climb to a local maximum.

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

#242

Post by jansan » Wed, Oct 17, 2018, 2:03 PM UTC

The Euclidean algorithm to compute the greatest common divisor of two numbers.

In Javascript, if you have two numbers x and y that are both greater than zero, you compute the greatest common divisor xyGcd in one beautiful line of code:

  var xyGcd = function gcd(a,b){ return b ? gcd(b, a%b) : a; }(x, y);

In my opinion this is the greatest one-liner ever.

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

#243

Post by spmurrayzzz » Wed, Oct 17, 2018, 2:07 PM UTC

dvirsky wrote: post #181

I'm surprised no one mentioned PageRank (or maybe I missed it). Another favorite is RAFT, simply because of how elegant and simple it is and how easy it is to understand. Also - I used to work in a company that did P2P video streaming (pre WebRTC) and the way the protocol leveraged Reed Solomon Coding was just awesome. https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor...

Seconding this. Its super easy to understand and explain to others (albeit implementation I have found to be somewhat more challenging when you dig into the details)

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

#244

Post by n4r9 » Wed, Oct 17, 2018, 2:08 PM UTC

another-cuppa wrote: post #197

n4r9 wrote: post #149

Earlier quoted context omitted.

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.

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.

As far as I can tell you're only arguing against poor implementations of K-means. If you demand that the score strictly improves at each iteration then the algorithm must terminate.

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

#245

Post by vanderZwan » Wed, Oct 17, 2018, 2:08 PM UTC

TomasHubelbauer wrote: post #103

I've always appreciated the Bresenham's line algorithm. It's a very simple algorithm and has been "superseded" by Xiaolin Wu's line which can also do antialiasing, but ever since I learnt about it, I've been very fond of it. Also the fact that it's an algorithm for use in computer graphics helps, because for me it's very easy to get excited about visual stuff as opposed to the more abstract CS stuff, which I have dee…

> It's a very simple algorithm and has been "superseded" by Xiaolin Wu's line which can also do antialiasing

Actually, not really! Bresenham's Line Algorithm secretly has a very useful generic low-level algorithm at its core. It just happened to be created for drawing lines first.

The thing most people miss is that it describes a way to do error-free repeated addition of a fraction using only integers and addition. In fact, you can add many different fractions, as long as they all share a denominator.

That is hugely powerful in the right context: imagine an embedded context where you have to add fractions to a counter, but the counter should be an integer value at all times. Maybe you must add different fractions in different situations. For example, an embedded device with two non-matching frequencies to keep track of over longer periods of time. With this method you're guaranteed that no matter how long you keep adding, the sum will always be correct.

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

#246

Post by jhallenworld » Wed, Oct 17, 2018, 2:09 PM UTC

I like skip lists (technically a data structure, but with associated algorithms). I love the simplicity vs. other balanced tree algorithms. Also I'm a fan because it's a relatively recent development that shows that progress is still possible in fundamental areas.

https://en.wikipedia.org/wiki/Skip_list

Some runners up: Gosling's dynamic programming algorithm for optimizing text editor screen updates and gap buffers.

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

#247

Post by ThomasBHickey » Wed, Oct 17, 2018, 2:12 PM UTC

gwbas1c wrote: post #225

Exponential backoff: I don't know if this is a published algorithm. Basically, background processes need to keep retrying an operation until it succeeds. (Make an API call to a server, upload a file, ect, ect.) If the retry interval is too small, you can DOS the remote server. (Server returns a 5xx error because there's a corner case that hits a defect.) But, if the retry interval is too large, your background proces…

Reminds me of the original Ethernet algorithm to deal with collisions on coax.

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

#248

Post by jansan » Wed, Oct 17, 2018, 2:13 PM UTC

dvirsky wrote: post #181

I'm surprised no one mentioned PageRank (or maybe I missed it). Another favorite is RAFT, simply because of how elegant and simple it is and how easy it is to understand. Also - I used to work in a company that did P2P video streaming (pre WebRTC) and the way the protocol leveraged Reed Solomon Coding was just awesome. https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor...

Probably the most commercially successful algorithm ever invented.

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

#249

Post by thekdude » Wed, Oct 17, 2018, 2:14 PM UTC

jhallenworld wrote: post #246

I like skip lists (technically a data structure, but with associated algorithms). I love the simplicity vs. other balanced tree algorithms. Also I'm a fan because it's a relatively recent development that shows that progress is still possible in fundamental areas. https://en.wikipedia.org/wiki/Skip_list Some runners up: Gosling's dynamic programming algorithm for optimizing text editor screen updates and gap buffers.

I had an assignment where I needed to implement generic Skip lists in Java, I had a great time doing it, I really enjoy them as a data structure

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

#250

Post by vanderZwan » Wed, Oct 17, 2018, 2:17 PM UTC

n4r9 wrote: post #241

vanderZwan wrote: post #234

Earlier quoted context omitted.

Thanks for not just looking for an answer to your own question but also sharing it! > So how does mean shift come into the picture? Mean shift exploits this KDE idea by imagining what the points would do if they all climbed up hill to the nearest peak on the KDE surface. It does so by iteratively shifting each point uphill until it reaches a peak. I wonder if this would still work with high-dimensional data. Distance…

Without looking much further into it, I can't imagine it going very wrong. My intuition says that the density function will be bounded, since you're working with a finite number of points, therefore you'll always be able to climb to a local maximum.

The problem I see is the word "near" in "climb to nearest peak". To quote the curse of dimensionality wiki page:

> The common theme of these problems is that when the dimensionality increases, the volume of the space increases so fast that the available data become sparse. This sparsity is problematic for any method that requires statistical significance.

https://en.wikipedia.org/wiki/Curse_of_dimensionality