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:
- 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).
- 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
- Homework 1 (pdf) : Solutions (pdf)
- Homework 2 (pdf)
- Homework 3 (pdf) : Solutions (pdf)
- Homework 4 (pdf) : Solutions (pdf)
- Homework 5 (pdf)
- 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 |
|
|
|