CS265

Welcome to CS265/CME309!

Randomized Algorithms and Probabilistic Analysis

Stanford University, Winter 2022.

Course Overview

Instructors: Greg Valiant and Mary Wootters

CAs: Yeganeh Alimohammadi, Margalit Glasgow, Ben Heller, Bryan Zhu.

Course Description: Randomness pervades the natural processes around us, from the formation of networks, to genetic recombination, to quantum physics. Randomness is also a powerful tool that can be leveraged to create algorithms and data structures which, in many cases, are more efficient and simpler than their deterministic counterparts. This course covers the key tools of probabilistic analysis, and application of these tools to understand the behaviors of random processes and algorithms. Emphasis is on theoretical foundations, though we will apply this theory broadly, discussing applications in machine learning and data analysis, networking, and systems. Topics include tail bounds, the probabilistic method, Markov chains, and martingales, with applications to analyzing random graphs, metric embeddings, random walks, and a host of powerful and elegant randomized algorithms.

Prerequisites: Prerequisites: CS 161 and STAT 116, or equivalents and instructor consent.

How to attend: We will meet Monday/Wednesday 11:30am-1pm. Starting Monday January 24, we will meet at the tree-pit in the engineering quad closest to Huang. See the map here.

Office hours.

The weekly schedule (all times Pacific) is:

  • Mary's OH: Monday 2-4pm
  • Greg's OH: Friday 2-3pm
  • Yeganeh's OH: Wednesday 6-8pm
  • Margalit's OH: Tuesday 6-8pm
  • Ben's OH: Monday 4-6pm
  • Bryan's OH: Thursday 2-4pm

For the moment, OH will be remote, held on our OhYay page, at ohyay.co/s/cs265. If you are enrolled, you can get the password by clicking here. (If you aren't enrolled, email the staff email list for the password).

Deviations from this schedule will be announced on this webpage (in the Announcements box below) and on our Ed discussion page.

Course Structure

CS265/CME309 will be a "flipped class." This means that you will watch short recorded mini-lectures and/or read lecture notes before class, and come to class ready to engage. In class, we will do active learning to practice and further develop the material from the mini-lectures. The agendas for each class (exercises and solutions) will be posted on this website (in the class-by-class resources below).

Since a large part of learning will happen during active in-class group work, we encourage you to attend class if possible. However, if you can't attend regularly, it is still possible to take this course, as all of the graded material can be done asynchronously. If you must do this, we encourage you to find other students in a similar situation to do the in-class work with asynchronously; Ed is a good place to find others.

Announcements

  • 1/23/22: Starting Monday January 24, we will be meeting in-person, outside in the engineering quad, at the tree-pit closest to Huang. There's a map here.
  • 1/17/22: Mary's OH are canceled on MLK day. If you'd like to meet another time this week, please reach out.
  • There is an issue with the enrollment system and it is not currently letting anyone enroll. Don't worry, you will be able to enroll in this course! Please try again once the quarter has started, hopefully it will be fixed by then. UPDATE: this should be fixed now!
  • We are looking forward to seeing you on the first class on OhYay! The link is here.

Useful Links

Assignments

This course will have weekly homework, quizzes, and a final take-home exam.

Homework Assignments

    Here are the homework due dates. The homeworks will be posted here as they become available. Homeworks are due on Wednesdays by 11am on Gradescope. We will try to post homeworks nine days before they are due (on Mondays), and certainly at least a week in advance.

Quiz Policies

(More) Course Policies

Assignments and Grading

Your grade is made up of:

  • 60% of your grade: HW.
  • 16% of your grade: Pre-class quizzes.
  • 24% of your grade: Final.

Collaboration Policy

We encourage collaboration with your classmates in class and on homework! Please acknowledge your collaborators. Note that plagiarism is never okay; anything you or your group hands in should be in y'all's own words.

It's fine to chat with your classmates about the quizzes, but each person should submit their own, and you should (of course) make sure you understand your answers.

Please do the final exam on your own, without consulting other humans. Consulting course materials or the internet is okay.

Academic Honesty

Please follow the Stanford honor code. In this class, the following will be considered violations of the honor code:

  • Consulting anyone outside this course for help on the homework. This includes posting homework questions on online forums, or searching either online or in your social networks for solutions to past years' CS265 homeworks. (Searching online for general background knowledge is fine and good).
  • Consulting anyone other than the course staff on the exam. (Again, searching online for general background knowledge is fine; the exam is open-book, open-internet).
  • Providing help to others in violation of the bullet points above.

Accommodations and flexibility

We understand that there is an ongoing pandemic, among other things, and that this disparately impacts different people. If you are in a situation that makes the format of this class especially difficult for you, please reach out. We will do everything we can to make sure that the course works for you.

Students who may need academic accommodations based on the impact of a disability should initiate the request with the Office of Accessible Education (OAE) and notify us as soon as possible at cs256-win2122-staff@lists.stanford.edu.

Class-by-class Schedule and Assignments

Below, find class-by-class resources, including videos, lecture notes, in-class agendas and exercises, and further reading. All videos can be found on the YouTube playlist here.

Classes that have not happened yet may have broken links or links to draft (last year's) materials, and are subject to change.

Monday 1/3. Class 1: Introduction, Polynomial Identity Testing

Wednesday 1/5. Class 2: Karger's algorithm and the Karger-Stein algorithm

Monday 1/10. Class 3: Primality Testing

Wednesday 1/13. Class 4: Markov and Chebyshev inequalities; sampling-based median

Monday 1/17. MLK Day

No class.

Wednesday 1/19. Class 5: Moment generating functions; Chernoff bound; Randomized routing on the hypercube

Monday 1/24. Class 6: Balls and Bins; "Poissonization"; The power of 2 choices

Wednesday 1/26. Class 7: Metric Embeddings I; Bourgain's embedding

Monday 1/31. Class 8: Metric Embeddings II; Johnson-Lindestrauss Transform

Wednesday 2/2. Class 9: Dimension reduction and sparsity: Compressed Sensing; the RIP

Monday 2/7. Class 10: The probabilistic method I: bounding Ramsey numbers, derandomization via conditional expectations

Wednesday 2/9. Class 11: The probabilistic method II: Second-moment method and the Lovasz Local Lemma

Monday 2/14. Class 12: Moser's "Entropic Proof" of the Constructive/Algorithmic Lovasz Local Lemma

Wednesday 2/16. Class 13: Introduction to Markov chains; randomized algorithm for 2SAT

Monday 2/21. Presidents Day

No class.

Wednesday 2/23. Class 14: Fundamental theorem of Markov chains; stationary distributions; Markov Chain Monte Carlo

Monday 2/28. Class 15: Mixing times; strong stationary times; coupling

Wednesday 3/2. Class 16: Martingales; the Doob Martingale; Azuma-Hoeffding tail bounds

Monday 3/7. Class 17: The martingale stopping theorem; applications

Wednesday 3/9. Class 18: The research frontier!

  • Before class:
    • Nothing!
  • During class: Greg and/or Mary will give short research talks.
  • Further reading: [To be posted]