Randomized Algorithms, CME 309/CS 365


Winter 2012-13, Stanford University
Tue, Thurs 11:00 AM - 12:15 PM
Building 200, Room 305

STAFF

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

COURSE OUTLINE

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.

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.

  1. Motwani and Raghavan. Randomized Algorithms, Cambridge University Press, 1995. (free online version for Stanford students)
  2. Mitzenmacher and Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 1995.
  3. William Feller. An introduction to Probability Theory and Its Applications, Volumes I and II, John Wiley, New York, 1968.
  4. Patrick Billingsley. Probability and Measure, John Wiley and Sons, 1986.
The text-book material may be supplemented with assigned reading from recent publications.

GRADING

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

HANDOUTS

  1. Class outline, pre-requisites, and textbooks (1/8)
  2. Tell us about yourself (1/8 - 1/10)
  3. HW 1 (1/22 - 1/31 11:00am) [mean = 86.2, stdev = 10.2, median = 88]
  4. Project List (1/24)
  5. HW 2 (2/5 - 2/14 11:00am) [mean = 74.4, stdev = 14.7, median = 80]
  6. HW 3 (2/21 - 3/1 5:00pm) [mean = 86.8, stdev = 13.4, median = 88]
  7. Final Exam (3/17 - 3/21 5:00pm)

LECTURE RELATED READING

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.

1/8

  1. Intro to Randomized Algorithms (MR, Preface)
  2. Randomized Quicksort (MR, 1.0)
  3. Independence of variables (MR, Appendix C)
  4. Linearity of Expectations (MR, Appendix C)
  5. Harmonic numbers (MR, Appendix B)

1/10

  1. Drunken sailors (MR, 1.5)
  2. Coupon collector (MR, 3.6)
  3. Union bound (MR, Appendix C)
  4. Geometric variables (MR, Appendix C)
  5. Markov inequality (MR, 3.2)
  6. Started Randomized Min-cut (MR, 1.1)

1/15

  1. Probabilistic Method and Randomized Min-cut (MR, 5, 10.2)
  2. Chebyshev inequality (MR, 3.2)
  3. Started Randomized select (MR, 3.3)

1/17

  1. Chernoff bound (MR, 4.1)
  2. Analyzed Randomized select with Chebyshev (see previous readings)

1/22

  1. More Chernoff bound intuitions (see previous readings)
  2. Started Randomized Rounding: Steiner Tree (MR, 4.3)

1/24

  1. Randomized Rounding: Min-Congestion Multicommodity Flow (see previous readings)
  2. Las Vegas and Monte Carlo (MR, 1.2)
  3. Started Yao's Minimax Theorem (MR, 2.2.2)

1/29

  1. von Neumann's theorem for Zero Sum games (MR, 2.2.1)
  2. Yao's Minimax Theorem (see previous readings)

1/31

  1. List of Projects: Group Steiner Tree, Feige's Conjecture, Applying Yao's Minimax theorem to Stochastic Decision Making (contact Ashish for more details)
  2. Game Tree Evaluation (MR, 2.1)

2/5

  1. Moment estimation of frequencies in streams (AMDM Lecture Notes 4)
  2. p-stable distributions: Normal distribution (see above)
  3. Johnson-Lindenstrauss dimensionality reduction (AMDM Lecture Notes 9)

2/7

  1. p-stable distributions: Cauchy distribution (see above)
  2. Concentration of the median of a distribution (AMDM Lecture Notes 3)
  3. Moment estimation of frequencies in streams (continued)
  4. Johnson-Lindenstrauss dimensionality reduction (continued)
  5. Started counting distinct elements

2/12

  1. Fakcharoenphol-Rao-Talwar Tree Embeddings

2/14

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

2/19

  1. Finished Buy-at-bulk
  2. Derandomization example
  3. Separation Oracles for LP

2/21

  1. Started Group Steiner Tree and Martingale Rounding

2/26

  1. Martingales, Doob Martingales, Azuma's Inequality (MR, 4.4)

2/28

  1. Finished Group Steiner Tree and Martingale Rounding

3/5

  1. Markov Chains and Random Walks (MR, 6)

3/7

  1. Continued Markov Chains and Random Walks

3/12

  1. Connection between hitting time and resistance of electrical networks
  2. Started perfect matchings using random walks

Upcoming

  1. Bourgain's Embedding
  2. Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs

ADDITIONAL READING

  1. S. Muthukrishnan. Data Streams: Algorithms and Applications. Also available as a free download.
  2. 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.
  3. Goemans and Williamson. The Primal-Dual Method for Approximation Algorithms and Its Application to Network Design Problems.