16: Randomized Algorithms

Coming soon.

Topics

• Las Vegas vs. Monte Carlo
• Randomized quicksort
• Randomized min-cut (Karger’s algorithm)
• Hashing (universal, perfect)
• Probabilistic analysis
• Expected runtime analysis