1.16 Randomization
Randomized algorithms use random choices during execution. The output or running time may depend on those choices. Randomization is useful when it simplifies design, avoids adversarial patterns, or gives good expected performance with a small amount of code. A randomized algorithm still needs a correctness contract. The contract must say whether the algorithm is always correct, probably correct, or correct in expectation. Problem You want to use randomness to make...