Welcome to CS265/CME309!

Randomized Algorithms and Probabilistic Analysis

Stanford University, Fall 2023.

Course Overview

Instructor: Greg Valiant

CAs: Chirag Pabbaraju, Hans Hanley, Vijaykrishna Gurunathan, Ivan Villa-Renteria

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.

When/Where: We will meet in-person T/Th 1:30-2:50pm in Shriram 104. SCPD students: see the ``SCPD Students'' box below for how to participate in this course remotely.

Office hours. Starting in Week 2, the weekly schedule (all times Pacific) is:

  • Greg: Tuesdays, 3-4pm in Gates 162.
  • Chirag: Wednesdays, 10am-12 in Huang Basement.
  • Hans: Wednesdays, 5-7pm, via zoom: Zoom link HERE, with password 974742.
  • Vijaykrishna: Thursdays, 3-5pm in Huang Basement.
  • Ivan: Fridays, noon-2pm in Huang Basement.

Deviations from this schedule will be announced on our Ed discussion page.

NOTE: Office hours start in Week 2. There are no OH in Week 1, but please ask on Ed if you have a question or want to meet with a member of the course staff.

Course Structure

CS265/CME309 will be a "flipped class." This means that before class you will read lecture notes and/or watch the short recorded mini-lectures that Mary Wooters (who often co-teaches this class) has put together, 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.

For SCPD Students

Because this is a flipped class, all of the lecture material is recorded and available at the links below, so SCPD students can follow along just like in-person students. That is, before each class, you should watch the mini-lecture videos and/or read the lecture notes, and do the short pre-class quiz on gradescope. (No quiz before the first class).

The main class session -- which will be mostly group-work -- will not be recorded. You can do the in-class work on your own or asynchronously with other remote students. All in-class work and solutions will be posted below in the "class-by-class resources" section on the website.

We will also have at least one session of zoom office hours (see the OH schedule above). In addition to any questions about the material, you can also use these OH to work on the in-class problems there with a CA.

We will email all the SCPD students at the beginning of the quarter to connect you to each other to form study groups; you can also find study groups on Ed.


  • Course announcements will be posted on our Ed discussion page, so please join that (and sign up for email notifications if it suits you).

Useful Links


This course will have weekly homework, quizzes, and a final in-person exam.

Homework Assignments

Quiz Policies

Exam Policies/Info

(More) Course Policies

Assignments and Grading

Your grade is made up of:

  • 54% of your grade: HW. We will drop the lowest HW score.
  • 16% of your grade: Pre-class quizzes.
  • 30% of your grade: Final exam.

Note that even though each HW may have a different number of total points, they will be rescaled so that they are out of 100 before averaging them; so all HW count for the same amount. Same goes for the quizzes.

There will be several options throughout the quarter for you to go above and beyond. (For example, bonus "might be fun to think about" problems, links to further reading, etc). These things do not factor directly into your grade, but they will factor into your learning! The course staff will be happy to give you feedback on any of these sorts of things, but we won't officially grade them.

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 your own words and should be something you understand.

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.

There is no collaboration on the final exam.

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 or quizzes. This includes posting homework questions on online forums, or searching 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 during the final exam.
  • Providing help to others in violation of the bullet points above.

Accommodations and flexibility

We understand that Covid is still circulating, 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 cs265-aut2324-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.

Tuesday 9/26. Class 1: Introduction, Polynomial Identity Testing

Thursday 9/28. Class 2: Karger's algorithm and the Karger-Stein algorithm

Tuesday 10/3. Class 3: Primality Testing

Thursday 10/5. Class 4: Markov and Chebyshev inequalities; sampling-based median

Tuesday 10/10. Class 5: Moment generating functions; Chernoff bound; Randomized routing on the hypercube

Thursday 10/12. Class 6: Balls and Bins; "Poissonization"; The power of 2 choices

Tuesday 10/17. Class 7: Metric Embeddings I; Bourgain's embedding

Thursday 10/19. Class 8: Metric Embeddings II; Johnson-Lindestrauss Transform

Tuesday 10/24. Class 9: Dimension reduction and sparsity: Compressed Sensing; the RIP

Thursday 10/26. Class 10: The probabilistic method I: bounding Ramsey numbers, derandomization via conditional expectations

Tuesday 10/31. Class 11: The probabilistic method II: Second-moment method and the Lovasz Local Lemma

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

Tuesday 11/7. Democracy Day

No class.

Thursday 11/9. Class 13: Introduction to Markov chains; randomized algorithm for 2SAT

Tuesday 11/14. Class 14: Fundamental theorem of Markov chains; stationary distributions; Markov Chain Monte Carlo

Thursday 11/16. Class 15: Mixing times; strong stationary times; coupling

Tuesday 11/21 and Thursday 11/23. Thanksgiving Break!!

No class.

Tuesday 11/28. Class 16: Martingales; the Doob Martingale; Azuma-Hoeffding tail bounds

Thursday 11/30. Class 17: The martingale stopping theorem; applications

Tuesday 12/5. Class 18: A taste of pseudorandomness: expanders and extractors

Thursday 12/7. Class 19: The research frontier!