Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

111–120 of 507 posts

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

#111

Post by failsafe »

avinassh wrote: post #88

K - means clustering, which I learned about recently. For non-machine learning folks, this algorithms helps in grouping relevant items together. As a practical, using this algorithm you can segment your customers based on their purchase history and interests. The actual algorithm is very simple, imagine a lot of points on the 2D plane and each of them represent customers, whom you want to segment/cluster. Now, chose…

The interesting part is solving the "closest pair problem" which is a part of the clustering algorithm. Hurts my head just thinking about it, god knows how someone came up with a solution like this. https://www.geeksforgeeks.org/closest-pair-of-points-using-d...

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

#112

Post by utopcell »

utopcell wrote: post #107

The Boyer–Moore majority algorithm [1] which allows you to find the majority element (if one exists) in an unsorted array in linear time and constant space. [1] https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_v...

..and its generalization [2], which finds the (at most) k elements whose frequency is more than 1/(k+1) in the unsorted stream (k=1 being the majority algorithm in [1].)

[2] https://www.cs.bgu.ac.il/~dinitz/Course/SS-12/Karp-frequent-...

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

#113

Post by Tepix »

I love many of those posted already (in particular FFT and DH) I just wanted to add DHT, for example Kademlia. I also like RC4 for its simplicity, unfortunately it's no longer considered secure.

PID controllers are also a great invention, does that count as an algorithm?

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

#114

Post by n4r9 »

jacknews wrote: post #93
avinassh wrote: post #88

K - means clustering, which I learned about recently. For non-machine learning folks, this algorithms helps in grouping relevant items together. As a practical, using this algorithm you can segment your customers based on their purchase history and interests. The actual algorithm is very simple, imagine a lot of points on the 2D plane and each of them represent customers, whom you want to segment/cluster. Now, chose…

I prefer mean-shift for it's simplicity, as it even creates it's own clusters.

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 determine how many clusters to use in the first place?

Having looked at the that page I also definitely don't think it's simpler than K-means!

Edit: This article gives a much more accessible descriptions than wikipedia:

https://spin.atomicobject.com/2015/05/26/mean-shift-clusteri...

To answer my own questions, the number of clusters is determined by the number of max points of the kernel density function, but the kernel bandwidth does have to be specified.

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

#115

Post by catears »

I personally enjoy the Fenwick Tree: https://en.m.wikipedia.org/wiki/Fenwick_tree

What is it used for? It allows one to both query and update prefix sums in O(log n), for a normal array this would be O(n)/O(1) respectively.

The cool thing is that it can be emulated with an array and as such it takes just the same amount of space as an array.

The best part is that they can be implemented (simple version) in about 10 lines of C++ code.

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

#116

Post by n4r9 »

failsafe wrote: post #111
avinassh wrote: post #88

K - means clustering, which I learned about recently. For non-machine learning folks, this algorithms helps in grouping relevant items together. As a practical, using this algorithm you can segment your customers based on their purchase history and interests. The actual algorithm is very simple, imagine a lot of points on the 2D plane and each of them represent customers, whom you want to segment/cluster. Now, chose…

The interesting part is solving the "closest pair problem" which is a part of the clustering algorithm. Hurts my head just thinking about it, god knows how someone came up with a solution like this. https://www.geeksforgeeks.org/closest-pair-of-points-using-d...

The closest-pair algorithm is something you might use in single-linkage clustering, not K-means clustering:

https://en.wikipedia.org/wiki/Single-linkage_clustering

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

#117

Post by emmanueloga_ »

KerrickStaley wrote: post #53

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

I was gonna mention this one as well! So simple and clever.

I like the explanation in the case study in Sedgewick's Algorithms [1].

Compare its simplicity to connected-components [2], another elegant algorithm but with a perhaps a bit more involved implementation.

1: https://algs4.cs.princeton.edu/15uf/

2: https://algs4.cs.princeton.edu/41graph/CC.java.html

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

#120

Post by ChrisRackauckas »

High order algorithms for stochastic differential equations.

https://epubs.siam.org/doi/abs/10.1137/09076636X

Somehow, even when things are almost surely not differentiable anywhere, you can develop algorithms which to a higher order (matching some idea of non-differentiable Taylor series) approximate the function. This is a beautiful idea since when you first do deterministic numerical analysis, all of the derivations require differentiability, but now this really expands your idea of what differentiable means.

Post reply on HN