Lecturer	James Worrell
Degrees	Schedule C1 — Computer Science Schedule C1 — Mathematics and Computer Science Schedule C — MSc in Advanced Computer Science MSc in Mathematics and Foundations of Computer Science
Term	Michaelmas Term 2010  (20 lectures)

Overview

Randomisation and probabilistic techniques play a key role in modern computer science, with applications ranging from communication protocols, combinatorial optimisation, computational geometry, data structures, networks and machine learning. In particular, randomised algorithms, which typically guarantee a correct result only with high probability, are often simpler and faster than corresponding deterministic algorithms. In this course we study fundamental applications of probabilistic techniques to computer science, focusing on randomised algorithms and the probabilistic analysis of algorithms.

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 at the level of the first year of the undergraduate Computer Science course at Oxford will be assumed. However 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-7 and 13 of the required text "Probability and Computing", by Mitzenmacher and Upfal. Supplementary material may also be taken from the book "Randomized Algorithms" by Motwani and Raghavan.  It is expected that the following will be covered:

Lectures 1--3: Probability and Events. Verifying matrix multiplication, min-cut algorithm, Schwartz-Zippel lemma, bipartite matching, isolating lemma.

Lectures 4--5: Random Variables and Moments.  Expectation and variance, the coupon collector's problem, the stable marriage problem,
randomised quicksort, median finding.

Lectures 6---8: Chernoff Bounds. Las Vegas and Monte Carlo algorithms, set balancing, facility location, random rounding and permutation routing.

Lectures 9---13: Balls and Bins. Poisson approximation, hashing, Bloom filters, Hamiltonian paths in random graphs.

Lectures 14---17:  Markov Chains and Random Walks.  Random-walk algorithms for 2-SAT, 3-SAT, undirected reachability, sampling.

Lectures 17---18:  Pairwise Independence and Universal Hash Functions.  Sampling, derandomization, perfect hashing and count-min filters.

Lectures 19---20: The Probabilistic Method. Lovasz local lemma and application to propositional satisfiability; derandomization through conditional expectation.

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; bloom filters and count-min 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.

                

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.