alt Hacker NewsRandomized algorithms are so damn cool. They really feel like cheating your way out of NP problems. I highly recommend that anyone interested in algorithms studies them.
Replies
another_twist • today at 7:02 AM
+1. My favourite bit is when pivots are chosen randomly in quicksort, we get linearithmic expected complexity. The CLRS proof using indicator random vars was a oh-shit moment.
➕ show 3 replies
https://www.wisdom.weizmann.ac.il/~oded/PDF/rnd.pdf
Then you reach derandomization and it hits you once again, it shows you that maybe you can "cheat" in the same way without randomness. Not for free, you usually trade randomness for a bit more running time, but your algorithms stay deterministic. Some believe all probabilistic algorithms can be derandomized (BPP = P), which would be a huge miracle if true.