CSc 80030: Probabilistic Analysis & Randomized Algorithms
Instructor: Hoeteck Wee (hoeteck at cs·qc·cuny·edu)
Office Hours: by appointment
Lectures: Wed 4.15-6.15 PM, GC 3209

Course Description
This is a course about randomization and computation. We will study the use of randomization in the following contexts:
  1. design of efficient algorithms: e.g. load-balancing algorithms, namely how to assign jobs to machines so as to minimize the maximum load; Bloom filters and hashing techniques for identifying duplicates and popular items in massive and/or streaming data sets (e.g. human genome sequences and Internet traffic).
  2. modeling and quantifying certain "natural processes": e.g. the "birthday paradox" -- in any group of 23 people, it's quite likely that two will have the same birthday; random graph models used in explaining the structure of the Internet and large social networks.

Course Policies
Textbook. The text for the class is Probability and Computing: Randomized Algorithms and Probabilistic Analysis, by Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005.

Collaboration. You are encouraged to work on homework problems in study groups; however, you must write up the solutions on your own, and you must never read or copy the solutions of other students. Similarly, you may use books or online resources to help solve homework problems, but you must credit all such sources in your writeup and you must never copy material verbatim. You are also required to comply with the university's policy on academic integrity.

Homework
  1. Homework 1 (pdf) : Solutions (pdf)
  2. Homework 2 (pdf)
  3. Homework 3 (pdf) : Solutions (pdf)
  4. Homework 4 (pdf) : Solutions (pdf)
  5. Homework 5 (pdf)
  6. Programming Assignment : due Mar 25

Lecture Schedule (tentative)
Date Topic Readings Handout
1/28 Introduction; identity testing   [pdf]
2/4 Randomized min-cut; Binomial, geometric distributions; Coupon collecting MU 1.4, 2.1-4
   [pdf]
2/11 Quicksort; Markov's, Chebyshev's inequality, Chernoff Bound MU 2.5, 3.1-3
   [pdf]
2/18 Randomized median finding; birthday problem; balls & bins MU 3.3-4, 5.1-2
   [pdf]
2/25 Random graphs; probabilistic method MU 5.1-2
   [pdf]
3/4 Probabilistic method & derandomization MU 5.6.1, 6.4
   [pdf]
3/11 Power of two random choices MU 14.1
   [pdf]
3/18 (no class due to TCC 2009)    
3/25 Randomized 2-SAT, random walks MU 7.1,7.4
   [pdf]
4/1 Sublinear-time algorithms survey pp 1-3   [pdf]
4/8, 4/15 Spring recess    
4/22 Expander graphs     [pdf]
4/29 cancelled in lieu of Sanjeev Arora's talk
 
5/6 student presentations I (topics)    
5/13 student presentations II