Randomized searching and sorting
Kent Quanrud · 100:34
Randomized algorithms add coin flips *inside* the algorithm (not over random inputs) and are still judged on worst-case instances; the lecture shows that a totally oblivious random 3SAT assignment is a 7/8-approximati...