CS265

Welcome to CS265/CME309!

Randomized Algorithms and Probabilistic Analysis

Stanford University, Autumn 2020.

Course Overview

Instructor: Mary Wootters

CAs: Bryan Cai, Lunjia Hu, Jay Mardia, Mingda Qiao

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: If you are taking this course synchronously (encouraged, if possible), we will meet M/W at 10:00am Pacific Time, on Nooks. See canvas for the link to join (it's in the "Home" tab, and also on the "Syllabus" tab). Taking the course asynchronously is an option; see "Course Structure" below.

Office hours. All office hours will be on our Nooks community page. The link is on Canvas. We will have a "Homework Party" each week for you to work with your teams on HW in an environment where CAs are around to answer questions. The weekly schedule (all times Pacific) is:

  • Homework Party: Mondays, 6-7pm
  • Mary's OH: Mondays, 11:30-1pm (after class)
  • Lunjia's OH: Tuesdays 4:30-6pm
  • Jay's OH: Wednesdays, 11:30-1pm (after class)
  • Bryan's OH: Thursdays, 3-4:30pm
  • Mingda's OH: Thursdays, 4:30-6pm
Deviations from this schedule will be announced on this webpage (in the Announcements box below) and on Canvas.

Course Structure

CS265 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 on Nooks ready to engage and do in-class exercises. Before each class, you will complete a short quiz on the material you were supposed to have digested before class. There will be weekly homework.

Since a large part of learning will happen during active in-class group work, we encourage you to attend class live if possible. However, we understand that this may not always be possible, due to time zones, technology, or other issues. If you are not able to regularly join the class live, you may take this class asynchronously. In that case, you can follow along with the in-class agenda (and sometimes in-class videos, when relevant) and do the in-class exercises either on your own or with a study group of other folks taking the course asynchronously.

If you plan to take this class asynchronously, please reach out to the course staff. We will work with you to develop a plan that works for you.

Announcements

  • (November 8) Mary's OH on November 9 are cancelled. There will still be a HW party on Monday evening.
  • (October 4) Based on student feedback, we have updated the quiz policy, see Quiz Policies below. (tl;dr you can collaborate on quizzes now, but we still encourage you to try them on your own first).
  • (September 18) We have a new CA!! Welcome Bryan Cai to the teaching team.
  • (September 18) If you want help finding teams, please fill out this form by 9/19 at noon Pacific time.
  • (September 18) The first HW assignment is out! Assignment and LaTeX template below.
  • (September 15) Class meet-and-greet event Wednesday September 16, 5-6pm Pacific on Nooks. No agenda, just a time to get to know each other better. Hope to see you there!

Useful Links

Assignments

There are two sorts of graded assignments, Quizzes and Homework.

Homework Policies

Homework Assignments

(More) Course Policies

Assignments and Grading

Your grade is made up of:

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

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.
  • Consulting anyone other than the course staff on the quizzes. (The quizzes are open book, open internet, open whatever, just not open other people).
  • Providing help to others in violation with the bullet points above.

Nooks Etiquette

Please follow these guidelines during class sessions:

  • When you get to class, go to a "small group" room in Nooks. You'll work with the people in this room during class. If you prefer to work alone, there's a room called "Quiet Room" for you to work in.
  • If you have a question, you can either come to the "Teaching Staff" room and ask us, or you can ask it in chat (either privately to the course staff, or else publicly to everyone, your choice).
  • It's fine to leave your camera off or turn it on, whatever you prefer.
  • We encourage you to join new groups and make new friends! And if someone new joins your room, be welcoming!

Note about recordings: In-class sessions in the "Teaching staff" room may be recorded and available on Canvas. These recordings may be viewed by other Stanford students enrolled in the course Canvas page. Individual small-group rooms will not be recorded. If you have any questions please contact the course staff.

Accommodations and flexibility

We understand that remote learning is difficult, and that this difficulty 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-aut2021-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. Lecture notes are lightly modified versions of Greg Valiant's notes from Fall 2019.

Classes that have not happened yet may have broken links and are subject to change.

Monday 9/14. Class 1: Introduction, Polynomial Identity Testing

Wednesday 9/16. Class 2: Karger's algorithm and the Karger-Stein algorithm

Monday 9/21. Class 3: Primality Testing

Wednesday 9/23. Class 4: Markov and Chebyshev inequalities; sampling-based median

Monday 9/28. Class 5: Moment generating functions; Chernoff bound; Randomized routing on the hypercube

Wednesday 9/30. Class 6: Balls and Bins; "Poissonization"; The power of 2 choices

Monday 10/5. Class 7: Metric Embeddings I; Bourgain's embedding

  • Before class:
    • Mini-lecture on metric embeddings
    • Mini-lecture on Bourgain's embedding
    • Mini-lecture on the proof that Bourgain's embedding works
    • Corresponding lecture notes
    • Do the quiz on gradescope.
  • During class: Agenda
  • Further reading:

Wednesday 10/7. Class 8: Metric Embeddings II; Johnson-Lindestrauss Transform

Monday 10/12. Class 9: Dimension reduction and sparsity: Compressed Sensing; the RIP

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

  • Before class:
    • Mini-lecture on the probabilistic method and Ramsey numbers
    • Mini-lecture on independent sets
    • Corresponding lecture notes
    • Do the quiz on gradescope.
  • During class: Agenda
  • Further reading:

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

  • Before class:
    • Mini-lecture on the second-moment method
    • Mini-lecture on the LLL
    • Mini-lecture on the proof of the LLL
    • Corresponding lecture notes
    • Do the quiz on gradescope.
  • During class: Agenda
  • Further reading: Slides with solutions to in-class work (No video for today since it was mostly group work).
  • Optional further reading: excerpt from Mitzenmacher and Upfal proving the more general version of the LLL.

Wednesday 10/21. Class 12: Moser's "Entropic Proof" of the Constructive/Algorithmic Lovasz Local Lemma

  • Before class:
    • Mini-lecture on the Constructive LLL
    • Mini-lecture on the Proof the the constructive LLL
    • Corresponding lecture notes
    • Do the quiz on gradescope.
  • During class: Agenda
  • Further reading: Slides with solutions to in-class work (No video for today, as it was mostly group work)

Monday 10/26. Class 13: Introduction to Markov chains; randomized algorithm for 2SAT

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

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

Tuesday 11/3. Election Day

If you are eligible to vote, VOTE!!!!!

Wednesday 11/4. Class 16: Buffer

  • Before class: nothing.
  • If we are on track, we'll take this class period as a time to do some review. If we aren't on track, we'll take this class period as a time to catch up.

Monday 11/9. Class 17: Martingales; the Doob Martingale; Azuma-Hoeffding tail bounds

Wednesday 11/11. Class 18: The martingale stopping theorem; applications

Monday 11/16. Class 19: A taste of pseudorandomness: expanders and extractors

Wednesday 11/18. Class 20: The last one!

  • Before class:
    • NA
  • We'll use this final class period to review the quarter, answer questions, and talk about future topics to study. If time, Mary will talk about some of her recent (relevantly, randomized) research.