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

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 notes:
• 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).
Template for course notes (modified from the one provided for CSC2401 offered by Micah Adler in 1998 in Univ. of Toronto).
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.

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