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:
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.
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.
Your grade is made up of:
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.
You must do the final exam on your own, without consulting other humans. Consulting course materials or the internet is okay. See here for more about the policies on the final exam.
Please follow the Stanford honor code. In this class, the following will be considered violations of the honor code:
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.
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.
No class.
No class.
