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

Re:Ask HN: What's your favorite elegant/beautiful algorithm? by chaoxu on Wednesday October 17, 2018 @02:19AM (#18236556)

Karger's randomized contraction algorithm for finding a min-cut. It's a common algorithm to introduce students into the world of randomized algorithms.

Also a shameless plug. My friend and I came up with this pseudo-polynomial time algorithm for subset sum that can be taught in a single session. It is faster than the standard dynamic programming algorithm. https://arxiv.org/abs/1807.08248

[ Parent | on HN ]

Re:Ask HN: What's your favorite elegant/beautiful algorithm? by GautamGoel on Wednesday October 17, 2018 @04:35AM (#18237231)

I actually read some of this paper! I liked your FFT trick.

[ Parent | on HN ]

Re:Ask HN: What's your favorite elegant/beautiful algorithm? by chaoxu on Wednesday October 17, 2018 @05:34PM (#18244029)

Thanks! Do you use that algorithm for anything in your research?

[ Parent | on HN ]

Re:Ask HN: What's your favorite elegant/beautiful algorithm? by GautamGoel on Thursday October 18, 2018 @06:40AM (#18247250)

Not directly. I briefly thought that a certain computational number theory problem might involve subset sums, but alas, it turned out to be the wrong approach.

[ Parent | on HN ]