Purpose:

Prerequisites:
CMPUT304, an undergraduate course in probability or statistics,, or strong undergraduate background in theoretical computer science and mathematics.

Textbook:
Randomized Algorithms, by Motwani and Raghavan, Cambridge press (1995). The link also includes an errata list.

Further reading: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by Michael Mitzenmacher and Eli Upfal, 2005.

Here is the course information sheet.

• Nov 29: I have posted the take home exam below. Also, the due date for Assignment 3 is extended to Dec 1st.
• Nov 25: Notes for the last lecture have been posted.
• Nov 22: There was a mistake in 2(a) in Assignmen 3 (thanks to Tim for pointing it out): it should have been "...requiring more than k probes...". I posted an updated version.
• Nov 14: Notes for lectures upto 18 are posted.
• Oct 27: Here are some potential presentation topics.
• Oct 26: Assignment 2 has been posted.
• Oct 21: Lecture notes 10 and 11 are posted.
• Oct 14: I have posted some extra notes (see below).
• Oct 11: Lecture notes 8 and 9 have been posted.
• Oct 10: Lecture notes 4,5,6, and 7 have been posted.
• Oct 7: The due date for Assignment 1 has been extended until Thursday Oct 13.
• Sept 27: Assignment 1 has been posted.
• Sept 20: Notes for Lecture 2 and 3 have been posted.
• Sept 14: Notes for Lecture 1 have been posted.

• Lecture 1: Introduction (PS and PDF).
• Lecture 2: Randomized Quicksort, Min-cut (PS and PDF).
• Lecture 3: Simple deviation bounds (Markov's inequality), Complexity classes, Coupon's collector (PS and PDF)
• Lecture 4: Second moment method, Median in linear time (PS and PDF)
• Lecture 5: Chernoff bound, routing in hypercube (PS and PDF)
• Lecture 6: Applications of Chernoff bound (Randomized routing and Randomized rounding) (PS and PDF)
• Lecture 7: Balls and Bins, Power of two choices (PS and PDF)
• Lecture 8: Probabilistic method, derandomizing by conditionall probability, random graphs (PS and PDF)
• Lecture 9: Expanding graphs, Lovasz Local Lemma (PS and PDF)
• Lecture 10: Applications of LLL, packet routing (PS and PDF)
• Lecture 11: Algorithmic versions of LLL (PS and PDF)
• Lecture 12: Random walks, Random 2-sat example (PS and PDF)
• Lecture 13: st-connectivity, Markov chains (PS and PDF)
• Lecture 14: Rapidly mixing Markov chains, coupling (PS and PDF)
• Lecture 15: coupling of Markov chains, a 3SAT algorithm (PS and PDF)
• Lecture 16: Hashing, a 2-universal family, perfect hashing (PS and PDF).
• Lecture 17: Bloom filters, Finger printing, Freivalds technique, Perfect matching in bipartite graphs (PS and PDF).
• Lecture 18: Perfect matchings in bipartite graphs (PS and PDF).
• Lecture 19: Approximate counting, Monte Carlo method, DNF counting.
• Lecture 20: DNF counting, importance sampling, Network reliablity.
• Lecture 21: Network reliability, PCP.
• Lecture 22: PCP, hardness of Clique, Random walks on Expanders. (PS and PDF).

Other notes:

• Here is a short (and not so recent) survey on LLL and its applications.
• Some basic probability tools (prepared by Arthur Czumaj).
• Some other notes on LLL and its application to packet routing (by Aravind Srinivasan).

Assignments:

• Assignment 1 in PS and PDF.
• Assignment 2 in PS and PDF.
• Assignment 3 in PS and PDF.
• Take home exam in PS and PDF.

Grading policy:
There will be 3 assignment sets (for a total of 60%), a take-home final exam or project (for 30%). Also, each participant in the course is required to provide scribe notes for one or two weeks of lectures. This (together with class participation) is worth 10% of your final mark. Scribe notes for each week are due the next Monday at noon. Scribe notes must be typed in LaTeX using the template provided above.

Tentative syllabus:

• Basics: random variables, expectation, complexity classes
• Min-cut algorithm
• Moments and deviations: Markov and Chebyshev inequalities
• Coupon collector's problem
• Occupancy and Hashing, Bloom filters, Universal Hash functions (?)
• Balls and Bins, power of two choices (?)
• Randomized selection
• Chernoff bounds and randomized rounding
• The probabilistic method, method of conditional probability
• The Lovasz Local Lemma, packet routing
• Sampling, Approximate counting
• Random walks and cover time, rapidly mixing Markov chains (?)
• Amplifying probability by random walks on expanders (?)
• Streaming (?)
• Derandomization

• Notes on linear programming, approximation algorithms, and randomized algorithms from home page of Michel X. Goemans ,
• Approximation Algorithms for NP-hard Problems. Dorit Hochbaum (Ed.), PWS Publishers, 1996. Below are links to some of the Chapters of this book that are available online: Hardness of Approximations by Sanjeev Arora and Carsten Lund, Approximation Algorithms for Bin Packing: A Survey by E.G. Coffman, M.R. Garey, and D.S. Johnson , Cut Problems and their application to divide-and-conquer, by David Shmoys . All of these are part of the book "Approximation Algorithms for NP-hard problems" listed above. Copyrights for the material are held by PWS Publishing with all rights reserved.
• A compendium of NP optimization problems , by Pierluigi Crescenzi and Viggo Kann.