Randomized Algorithms, CME 309/CS 365
Winter 2012-13, Stanford University
Tue, Thurs 11:00 AM - 12:15 PM
Building 200, Room 305
Instructor: Ashish Goel, Office
hours: Mon 4pm - 5pm. Location: Huang 359. Email: ashishg AT stanford DOT edu,
Phone: 650 eight-hundred-fourteen 1478
Teaching Assistant: David Lee,
Office hours: Wed 4pm - 5pm. Location: 420-286. Email: davidtlee AT stanford
Staff email address: cme309-win1213-staff AT lists DOT stanford DOT edu; please use this address except when you need to contact the
instructor or the TA very specifically.
Auditors/guests: Please make sure you sign on to cme309-win1213-guests
The last twenty five years have
witnessed a tremendous growth in the area of randomized algorithms.
During this period, randomized algorithms have gone from being a tool
in computational number theory to a mainstream set of tools and
techniques with widespread application. Three benefits of randomization
have spearheaded this growth: simplicity, speed, and robustness to
input parameters. This course presents the basic concepts in the design
and analysis of randomized algorithms at a level accessible to advanced
undergraduates and to graduate students.
The course will be organized into two interleaved parts. The first
thread will develop basic probabilistic tools that are recurrent in
algorithmic applications. The second thread will focus on specific
areas of application. Applications will be given along with each tool
to illustrate it in concrete settings.
The following is a tentative outline of the course.
Tools and Techniques: Basic
probability theory; randomized complexity theory; game-theoretic
techniques; Markov, Chebyshev, and moment inequalities; limited
independence; coupon collection and occupancy problems; tail
inequalities and Chernoff bounds; conditional expectation and
martingales; Markov chains and random walks; stable distributions;
probability amplification and derandomization.
Applications: sorting and
searching; data structures; combinatorial optimization and graph
algorithms; metric embeddings; online and streaming algorithms;
algorithms for massive data sets including similarity search, nearest
neighbors, and clustering; number-theoretic algorithms.
undergraduate courses in Algorithms and Probability Theory.
Text-books: The first book
below is a required text-book for this course. The other two books are
recommended as good introductions to probability theory.
- Motwani and Raghavan. Randomized
Algorithms, Cambridge University Press, 1995. (free online version for Stanford students)
- Mitzenmacher and Upfal. Probability
and Computing: Randomized Algorithms and Probabilistic Analysis,
Cambridge University Press, 1995.
- William Feller. An
introduction to Probability Theory and Its Applications, Volumes I and
II, John Wiley, New York, 1968.
- Patrick Billingsley. Probability
Measure, John Wiley and Sons, 1986.
The text-book material may be
supplemented with assigned reading from recent publications.
There will be three homework assignments, each of which is worth 23.5% of the final
grade. The assignments will be posted every other Tuesday after class and due the Thursday
of the following week at 11:00am. The final exam will be take home and worth 29.5% of
the final grade.
will post the average and standard deviation of each homework and the final exam. Interested
students can ask for a class project, which will typically be an open research problem.
A list of projects will be available on 1/24 and interested students should let us know by 1/31.
- Class outline, pre-requisites, and
- Tell us about yourself (1/8 - 1/10)
- HW 1 (1/22 - 1/31 11:00am) [mean = 86.2, stdev = 10.2, median = 88]
- Project List (1/24)
- HW 2 (2/5 - 2/14 11:00am) [mean = 74.4, stdev = 14.7, median = 80]
- HW 3 (2/21 - 3/1 5:00pm) [mean = 86.8, stdev = 13.4, median = 88]
- Final Exam (3/17 - 3/21 5:00pm)
Concepts for each lecture (or concepts that are assumed to be already known) and their corresponding readings will be posted here. This list will be updated with at least the next week's reading (and should not be interpreted as the full list of readings for the class). Most will come from Randomized Algorithms by Motwani and Raghavan (denoted MR). I will denote text in the intro of a chapter (before section 1) as section 0. For the material not contained in the textbook, relevant papers or notes will be posted.
- Intro to Randomized Algorithms (MR, Preface)
- Randomized Quicksort (MR, 1.0)
- Independence of variables (MR, Appendix C)
- Linearity of Expectations (MR, Appendix C)
- Harmonic numbers (MR, Appendix B)
- Drunken sailors (MR, 1.5)
- Coupon collector (MR, 3.6)
- Union bound (MR, Appendix C)
- Geometric variables (MR, Appendix C)
- Markov inequality (MR, 3.2)
- Started Randomized Min-cut (MR, 1.1)
- Probabilistic Method and Randomized Min-cut (MR, 5, 10.2)
- Chebyshev inequality (MR, 3.2)
- Started Randomized select (MR, 3.3)
- Chernoff bound (MR, 4.1)
- Analyzed Randomized select with Chebyshev (see previous readings)
- More Chernoff bound intuitions (see previous readings)
- Started Randomized Rounding: Steiner Tree (MR, 4.3)
- Randomized Rounding: Min-Congestion Multicommodity Flow (see previous readings)
- Las Vegas and Monte Carlo (MR, 1.2)
- Started Yao's Minimax Theorem (MR, 2.2.2)
- von Neumann's theorem for Zero Sum games (MR, 2.2.1)
- Yao's Minimax Theorem (see previous readings)
- List of Projects: Group Steiner Tree, Feige's Conjecture, Applying Yao's Minimax theorem to Stochastic Decision Making (contact Ashish for more details)
- Game Tree Evaluation (MR, 2.1)
- Moment estimation of frequencies in streams (AMDM Lecture Notes 4)
- p-stable distributions: Normal distribution (see above)
- Johnson-Lindenstrauss dimensionality reduction (AMDM Lecture Notes 9)
- p-stable distributions: Cauchy distribution (see above)
- Concentration of the median of a distribution (AMDM Lecture Notes 3)
- Moment estimation of frequencies in streams (continued)
- Johnson-Lindenstrauss dimensionality reduction (continued)
- Started counting distinct elements
- Fakcharoenphol-Rao-Talwar Tree Embeddings
- Finished counting distinct elements
- Started Buy-at-Bulk Network Design and Simultaneous tree approximations
- Finished Buy-at-bulk
- Derandomization example
- Separation Oracles for LP
- Started Group Steiner Tree and Martingale Rounding
- Martingales, Doob Martingales, Azuma's Inequality (MR, 4.4)
- Finished Group Steiner Tree and Martingale Rounding
- Markov Chains and Random Walks (MR, 6)
- Continued Markov Chains and Random Walks
- Connection between hitting time and resistance of electrical networks
- Started perfect matchings using random walks
- Bourgain's Embedding
- Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs
- S. Muthukrishnan. Data Streams: Algorithms and Applications.
Also available as a free download.
- Linial, London, and Rabinovich. The geometry of graphs and some of its
algorithmic applications. For insight into (and sometimes
simpler proofs of) Bourgain's theorem, Johnson-Lindenstrauss
dimensionality reduction, and sparsest cut approximation.
- Goemans and Williamson. The Primal-Dual Method for Approximation Algorithms and
Its Application to Network Design Problems.