CSIS8601 Advanced Topics in Theoretical Computer Science:
Probabilistic Method & Randomized Algorithms, Fall 2009
- Instructor: Hubert Chan
- TA: Simon Zhang
- Time: Wed 2:00-4:05pm
- Place: Theatre B, Chow Yei Ching Building
- Instructor's Office Hours: after each class
- TA Consultation Hours: Friday 4-6pm
This is a graduate level course that covers probability techniques in the design and the
analysis of randomized algorithms. Topics include measure
concentration results such as Chernoff Bound, Hoeffding's Inequality
and martingale inequalities. We also cover classical results such as
the Johnson-Lindenstrauss Lemma and the Lovasz Local Lemma. This
course puts emphasis on understanding how the various techniques work.
However, we would explain the proofs from the computer scientist's
viewpoint and avoid the pedantic axiomatic approach.
have a basic knowledge of probability and algorithms. For example,
probability space, discrete and continuous random variables, expectation,
probability density function, normal (Gaussian) distribution.
However, we would also recall the necessary concepts as the course proceeds.
Method of Assessment: There will be 4 or 5 homeworks (25%), a mid-term exam
(25%) and a final exam (50%).
Textbook: There is no compulsory text, but here are some suggested
Tentative List of Topics
The list of topics is subject to change
according to the pace and interests of students.
Markov's inequality, Chebyshev's inequality, probabilistic method
Approximate Sampling and Counting
Dimension reduction, Johnson-Lindenstrauss Lemma
Lovasz Local Lemma
VC dimension, epsilon nets, epsilon samples
Lecture Slides and Notes
- 2 Sep. Course info, basics of probability, probabilistic method.
- Slides. (Course admin, Probability basics)
- Notes. (Probabilistic Method, Markov's Inequality, Chebyshev's Inequality)
- 9 Sep. Derandomization by Conditional Expectation, Graphs with No Short Cycles (Method of Alteration)
- 16 Sep. Chernoff Bound, Measure Concentration
- 23 Sep. More Measure Concentration: Counting DNF Satisfying Assignments, Hoeffding's Inequality.
- 30 Sep. Johnson-Lindenstrauss Lemma: Dimension Reduction
- 7 Oct. Locality Sensitive Hashing: Nearest Neighbor Search
- 14 Oct. Reading Week. No Class
- 21 Oct. Midterm
- 28 Oct. Review of Materials from midterm, homework, past lectures.
- 4 Nov. epsilon-Nets, VC-Dimension
- 11 Nov. epsilon-Nets, epsilon-Samples, VC-Dimension (Part 2)
- 18 Nov. Lovasz Local Lemma, Job Shop Scheduling.
- 25 Nov. Lovasz Local Lemma (Part 2): Asymptotically Optimal Job Shop Scheduling
- Homework 1, due 16 Sep.
- Homework 2, due 7 Oct.
- Homeworks 3+4, due 25 Nov.