Algorithm II

13. Randomization

WU Xiaokun 吴晓堃

Randomization

Algorithmic design patterns.

  • Greedy. Divide-and-conquer. Dynamic programming. Network flow.
  • Randomization.

Randomization. Allow fair coin flip in unit time.

  1. Efficient deterministic algorithms that always yield correct answer;
  2. Efficient randomized algorithms that yield correct answer with high probability;
  3. Randomized algorithms that always correct, and run efficiently in expectation.

Why randomize? Can lead to simplest, fastest, or only known algorithm for a particular problem.

Ex. Symmetry-breaking protocols, graph algorithms, quicksort, hashing, load balancing, closest pair, Monte Carlo integration, cryptography, etc.

Contention resolution

Global min cut

Linearity of expectation

Max 3-satisfiability

Universal hashing

Chernoff bounds

Load balancing