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:
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.
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.
Please follow the Stanford honor code. In this class, the following will be considered violations of the honor code:
Please follow these guidelines during class sessions:
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.
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.
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.
If you are eligible to vote, VOTE!!!!!