COMP 599 Advanced Probabilsitic Methods in CS- Winter 2014

Course Info

Time & Place:
Monday and Wednesday 10:00-11:30, McConnell Engineering 320

Bruce Reed . MC301,, Office Hours: Monday 14:00-15:30

Prerequisite: An undergraduate course on graph theory and basic notions of discrete probability ( found in many undergraduate CS and math courses).

When applying a Probabilistic Method, we find or prove the existence of a structure with certain desirable properties by showing that a randomly chosen structure from an appropriate distribution has these properties with positive probability. Such an approach often allows us to resolve optimization problems which have proven impervious to attack by other methods. We will discuss two examples. The first is the application of the probabilistic method in graph colouring. The second is the theory of Rapidly Mixing Markov Chains.


The course mark will be 25% assignments, 75% take home exam,


The text for the first half of the course

* Announcements

The first assignment is available on the assignment page which you can

The second assignment is available on the assignment page which you can access via the announcements page.

Here is an introduction to Rapidly Mixing MMarkov Chains written by Dana Randall.

Here is a chapter on Rapidly Mixing Markov Chains written by Mark Jerrum andAlisdair Sinclair