Computer Science 308-490B Introduction to the Probabilistic Analysis of Algorithms December 19, 2006 Winter 2007 --- Course Syllabus
Instructor	Luc Devroye Email to luc@cs.mcgill.ca Tel: (514) 398-3738 (office) McConnell Engineering Building, Room 300N Office hours: any time my door is open
Teaching Assistant	Nicolas Broutin Email to nbrout@cs.mcgill.ca McConnell Engineering Building, Room 109 Office hours: Monday, 2-3:30pm
Location	Tuesday, Thursday 16:00-17:30. McConnell Engineering 320N.
Description	This course offers an opportunity for our undergraduate students to learn the tools needed to design and analyze efficient randomized algorithms, an area that has become important in the last few years. McGill has no course in this direction except at the graduate level. Computationally difficult (NP complete) problems can often be solved quickly by using randomization if one is willing to accept answers that are correct with a given probability or degree of accuracy. These randomized algorithms are the methods of choice for a number of important problems. The course will be especially appealing to those students wishing to continue with graduate work or fundamental research.
Contents	Fundamental tools from probability are used to analyze algorithms. Notions covered include independence, generating functions, probability inequalities, random walks and Markov chains. We analyze probabilistic recurrences, Las Vegas algorithms, randomized approximation algorithms, random sampling methods, Monte Carlo techniques, and algorithms for combinatorial search and graph theoretic problems.
Lectures	Lectures 1-3: Review the relevant notions of probability theory, including independence, probability inequalities, and certain distributions. Expected values. Modern concentration inequalities. Lectures 4-6: Simple randomized algorithms. Las Vegas and Monte Carlo. Probabilistic recurrences. Lecture 7: Game-theoretic techniques. Minimax. Lectures 8-12: Markov chains. Random walks. k-SAT. Random walks on graphs. Cover times. Rapid mixing. Markov chain Monte Carlo. Lectures 13-14: Algebraic methods. Fingerprinting and Freivald's technique. Verifying identities. Randomized pattern matching. Lectures 15-16: Data structures. Random binary search trees. Random treaps. Skip lists. Lectures 17-20: Geometric algorithms and linear programming. Convex hulls. Delaunay triangulations. Binary space partitions. Random sampling. Fast expected time linear programming. Lectures 21-26: Applications. (Variable from year to year.) Routing, wiring. Randomized approximation for MAX SAT. Byzantine agreement. Approximate counting. Randomized primality testing.
Evaluation	This is a course in the classical mould, with 3 hours of lectures per week. The evaluation is based on about twelve written homework assignments, each consisting of several problems. The last one of these has a due date on the last day of lectures. The homework problems, which form the core of the course, deal with randomization and probabilistic analysis, and are taken from across the entire spectrum of computer science subjects. There is no in-class test, no midterm, and no formal final examination.
Prerequisites	308-251: Data Structures 189-323: Probability Theory
Textbook	Lecture notes will be handed out. This text can be used as a rough reference, but is by no means necessary to follow the course: R. Motwani, P. Raghavan: "Randomized Algorithms," Cambridge University Press, 1995.