primality
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 4.3: Design Methods III
The witness method — randomly hunt an element proving a property: primality (Fermat → Miller–Rabin → Solovay–Strassen), plus witnesses for Boolean matrix products rebuilding all-pairs shortest paths.