CMPUT675: Randomized Algorithms

Fall 2005, TR 3:30-4:50:, in CSC B10.

Instructor: Mohammad R. Salavatipour

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.

Annoucnements:

- 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).

Here is a sample and its source file.

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

Useful Links:

Here are some useful links to more resources (books, course notes by other people who have taught this course, problems, etc.):

- 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.