Random sampling, searching, and sorting (Fundamental Algorithms, Spring 2022, Lecture 21)
Kent Quanrud · 75:47
This lecture introduces randomized algorithms by building probability from first principles, then fully analyzing Karger’s random-contraction min-cut algorithm (success probability \(1/\binom{n}{2}\)) and randomized q...