Probability and Computing: 20132014
Lecturer 

Degrees 
Schedule C1 — Computer Science Schedule C1 — Mathematics and Computer Science 
Term 
Michaelmas Term 2013 (20 lectures) 
Overview
In this course we study applications of probabilistic techniques to computer science, focusing on randomised algorithms and the probabilistic analysis of algorithms. Randomisation and probabilistic techniques have applications ranging from communication protocols, combinatorial optimisation, computational geometry, data structures, networks and machine learning. Randomised algorithms, which typically guarantee a correct result only with high probability, are often simpler and faster than corresponding deterministic algorithms. Randomisation can also be used to break symmetry and achieve load balancing in parallel and distributed computing. This course introduces students to those ideas in probability that most are most relevant to computer science. This background theory is motivated and illustrated by a wideranging series of applications.Learning outcomes
At the end of the course students are expected to
 Understand basic concepts and tools in probability theory that are relevant to computing, including random variables, independence, moments and deviations, tail inequalities, occupancy problems, the probabilistic method, derandomisation and Markov chains.
 Be able to use the above tools to devise and analyse randomised algorithms and carry out the probabilistic analysis of deterministic algorithms.
 Understand some of the main paradigms in the design of randomised algorithms, including random sampling, random walks, random rounding, algebraic techniques, foiling the adversary and amplification.
Prerequisites
Exposure to probability theory, discrete mathematics, algorithms and linear algebra will be assumed. Specific concepts that will be assumed include discrete probability spaces, the principle of inclusionexclusion, conditional probability, random variables, expectation, basic graph theory, the binomial theorem, finite fields, power series, sorting algorithms, asymptotic notation, vector spaces, linear transformations, matrices and determinants. Graduate students who have not taken a course in algorithms will not be at a significant disadvantage. Diligent students lacking some of the required background but willing to acquaint themselves with the necessary material are encouraged to contact the lecturer to discuss their situation prior to registering for this course.
Synopsis
The material will be mostly drawn from Chapters 1  5, 7, 10, 11 and 13 of the course text "Probability and Computing",
by Mitzenmacher and Upfal. Supplementary material is also taken from the book "Randomized Algorithms" by Motwani and Raghavan.
It is expected that the following will be covered:
Events and Probability (2 lectures): Verifying matrix multiplication,
mincut algorithm, longpath algorithm.
Polynomial Identity Testing (1 lecture): SchwartzZippel lemma, isolating
lemma, bipartite matching.
Random Variables and Expectation (1 lecture): Coupon collector, randomised Quicksort.
Moments and Deviations (1 lecture): Chebyshev, median finding.
Stable Marriage Problem (1 lecture).
Luby's Algorithm (1 lecture).
Chernoff Bounds (2 lectures): Las Vegas and Monte Carlo algorithms, set balancing,
facility location, random rounding, permutation routing.
Markov Chains (34 lectures): Randomwalk algorithms for
2SAT, 3SAT, randomwalks on graphs.
Balls and Bins (12 lectures): Poisson approximation, occupancy problems,
Bloom filters.
The Monte Carlo Method (1 lecture): DNF counting, importance sampling.
Pairwise Independence
(1 lecture): finding cuts, derandomisation, sampling.
Universal Hashing (1 lecture): universal hash functions,
perfect hashing, countmin filters.
The Probabilistic Method (12 lectures): Derandomisation, lower bounds for
set balancing, Lovasz local lemma.
Markov Chain Coupling (2 lectures): Metropolis Algorithm, variation distance,
mixing times.
Syllabus
Tools and Techniques: random variables; conditional expectation; moment bounds; tail inequalities; independence; coupon collection and occupancy problems; the probabilistic method; Markov chains and random walks; algebraic techniques; probability amplification and derandomisation.
Applications: Sorting and searching; graph algorithms; combinatorial optimisation; propositional satisfiability; hashing; routing; random sampling; DNFcounting; bloom filters, countmin filters.
Reading list
Required text:
 Probability and Computing, by Michael Mitzenmacher and Eli Upfal, Cambridge University Press.
Also useful:
 Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press.
 Design and Analysis of Randomized Algorithms, by Juraj Hromkovic, Springer.