Unit 7: Randomization Basics

This unit covers

• probability theory recap
• models of computation with randomization
• Las Vegas and Monte Carlo algorithms

Material

• slides

• lecture notes

• Video 7-1 (2025-06-10): Randomization motivation

• Video 7-2 (2025-06-10): Randomized selection by rank (deterministic adversary lower bound, Floyd-Rivest algorithm)

• Video 7-3 (2025-06-11): Probability theory recap

• Video 7-3 (2025-06-11): Probability theory recap

---

Unit 6  ⋅  Syllabus  ⋅  Unit 8