3 ms·

Randomized algorithms are so damn cool. They really feel like cheating your way out of NP problems. I highly recommend that anyone interested in algorithms stud

• another_twist 10mo ago
  +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.
  • gnull 10mo ago
    Btw, you can make quicksort deterministically O(n log n) if you pick the pivot point with linear median search algorithm. It's impressive how randomness lets you pick a balanced pivot, but even more impressive that you could do the same without randomness.
  • deleted 10mo ago
    [deleted]
  • tmoertel 10mo ago
    Similarly, quickselect with random pivots runs in expected linear time. For a proof of this, see https://github.com/tmoertel/practice/blob/master/dailycodingproblem_com/p661_find_elem_in_sorted_array_with_limited_ops.py#L51 https://github.com/tmoertel/practice/blob/master/dailycoding...
• gnull 10mo ago
  https://www.wisdom.weizmann.ac.il/~oded/PDF/rnd.pdf 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.