Winter 2012-13, Stanford University

Tue, Thurs 11:00 AM - 12:15 PM

Building 200, Room 305

- Staff, office hours, and contact information

- Course outline, pre-requisites, and textbooks

- Grading
- Handouts
- Reading
- Additional reading

Teaching Assistant: David Lee, Office hours: Wed 4pm - 5pm. Location: 420-286. Email: davidtlee AT stanford DOT edu

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.

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.

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.

Prerequisites: Basic 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 and Measure, John Wiley and Sons, 1986.

The text-book material may be
supplemented with assigned reading from recent publications.

- Class outline, pre-requisites, and textbooks (1/8)
- 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

- Finished counting distinct elements
- Started Buy-at-Bulk Network Design and Simultaneous tree approximations

- Finished Buy-at-bulk
- Derandomization example
- Separation Oracles for LP

- 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.