Randomized Algorithms

An introduction to randomized algorithms: a private coin the adversary cannot see turns one exploitable fixed behavior into a distribution over deterministic algorithms, so no single input is bad for all of them. The Las Vegas (always correct, random running time) versus Monte Carlo (fixed time, probably correct) split, why boosting confidence is nearly free (k independent runs fail with probability at most 2 to the minus k), a first tail bound (Markov's inequality) with linearity of expectation and indicator variables, and how the whole series is the mirror image of the online, streaming, and approximation series: randomness as a resource whose worth is exactly what it hides from the adversary, with Yao's principle as the hinge.