quicksort
Computer science / Coursework / Randomized algorithms
Lecture 1: Introduction
Motivating examples (fingerprinting, Karger min-cut, QuickSort, Freivalds) where a few coin flips replace heavy deterministic work at a tiny, controllable error.
Computer science / Coursework / Randomized algorithms
Lecture 2: Analysis of Randomized Algorithms
The Markov–Chebyshev–Chernoff ladder of tail inequalities (one idea at three strengths), used to prove QuickSort is O(n log n) w.h.p. and R-Select finds the median in 2n + o(n).