Basic techniques in design and analysis of randomized algorithms: moments and deviations, Markov chains and random walks, martingales, and algebraic techniques. Other topics include: the probabilistic method, random structures and complexity. Applications are selected from: parallel algorithm, routing networks, combinatorial optimization, data structure, approximate solutions to intractable problems, cryptography, pattern matching, and computational geometry.
- CSC 226 with a minimum grade of B+; and
- minimum third-year standing.