CMPUT675: Randomized Algorithms
Fall 2005, TR 3:30-4:50:, in CSC B10.
Mohammad R. Salavatipour
CMPUT304, an undergraduate course in probability or statistics,,
or strong undergraduate background in theoretical computer
science and mathematics.
Randomized Algorithms, by Motwani and Raghavan, Cambridge press (1995).
The link also includes an errata list.
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
- 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
- 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).
Template for course notes (modified
from the one provided for CSC2401 offered by Micah Adler in 1998 in Univ.
- Here is a short (and not so recent) survey on
LLL and its applications.
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.
- 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.
- 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 (?)
Here are some useful links to more resources (books, course notes by
other people who have taught this course, problems, etc.):
Questions? Send email to me ...
- Notes on linear
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.