Monday
Introduction to randomized algorithms
Randomization on inputs versus algorithms.
Analysis by linearity of expectation and indicator variables.
Las Vegas and Monte Carlo algorithms.
MR 1-1.2

Thursday
Chernoff bounds and randomized rounding
Markov's inequality
Chernoff Bound: The sum of independent indicator variables is distributed closely around the expectation.
Randomised rounding: Good approximate solutions to hard combinatorial problems.
MR 3.2, 4.1, 4.3

Monday
Algebraic techniques in randomization
Fingerprinting for result checking.
Schwarz-Zippel theorem.
Application to perfect matching.
MR 7-7.3

Thursday
Hashing
Universal hashing and dynamic dictionaries.
MR 8.4

Monday
Introduction to randomized algorithms (cont.)
Another example of a Las Vegas algorithm and analysis by linearity of expectation.
Proof of existence by the probabilistic method.
MR 1.3

Thursday
Chernoff bounds (cont.)
Application to analysis of a routing algorithm.
MR 4.2

Monday
Algebraic techniques (cont.)
Distributed equality test.
(On-line) pattern matching.
MR 7.4-7.6

Thursday
Hashing (cont.)
2-level hashing and static dictionaries.
MR 8.5

Monday
Proving lower bounds
von Neumann's minimax principle
Yao's techniques for proving lower bounds
Average case time usage for best deterministic algorithm relative to a known worst case input distribution equals expected time usage of best randomized algorithm on worst case input
MR 2.2 - 2.2.2

Thursday
Example: Game Tree Evaluation
A Las Vegas algorithm that beats any deterministic strategy
MR 2.1, 2.2.3

Monday
Competitive analysis of on-line algorithms
Competitiveness: Comparison of on-line solution to best off-line solution.
Paging algorithms: deterministic and randomised solutions.
MR 13-13.3

Thursday
Complexity classes
The complexity classes RP, BPP.
Trading randomness for nonuniformity.
MR 1.5, 2.3

Friday
Deadline for project hand-in

Monday
To be announced

Thursday
Multiple choice test