Hacker News new | past | comments | ask | show | jobs | submit login

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




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


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


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.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: