CSC423

Randomized Algorithms

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.