CSC 423

Randomized Algorithms

Units: 1.5, Hours: 3-0

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.

Note: Credit will be granted for only one of 423 and a topics course with similar content.

Prerequisites: A minimum grade of B+ in 225 and third- or fourth-year standing.

Undergraduate course in Computer Science offered by the Department of Computer Science in the Faculty of Engineering.