Instructor: Mary Wootters
CAs: Spencer Compton, Dorsa Fathollahi
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 117/118, or equivalents and instructor consent.
When/Where: Class is M/W, 10:30am-11:50pm in CoDa B90.
Office hours.
NOTE: Office hours start in Week 2. There are no OH in Week 1, but please ask on Ed if you have a question.
Deviations from this schedule will be announced on Canvas.
CS265/CME309 is 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. 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.
Exception: Please do not come to class if you are sick.
Here are the homework due dates. The homeworks will be posted here as they become available. Homeworks are due on (most) Fridays at 11:59pm on Gradescope. We will post HW at least a week before the due date.
The homework schedule is listed below. The topics are estimates; in particular, previous material is always fair game :)
Solutions will be posted on Canvas.
We will have two in-person, proctored exams:
Your grade is made up of:
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.
Homework: 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.
Quizzes: 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.
Exams: There is no collaboration on the exams.
We view LLMs like ChatGPT, Copilot, Claude, etc as knowledgeable (if fallible) friends who are not in your homework group. Thus, you are allowed to interact with them the same way as you would with such friends. It's fine to interact with them to build your intuition, get ideas, etc. This can even be a great way to learn, and we encourage that! But you should not have them do or write up your homework for you, just as you should not ask your friends outside of your homework group to do or write up your homework for you.
Please follow the Stanford honor code. In this class, the following will be considered violations of the honor code:
If you are in a situation that makes the format of this class especially difficult for you, please reach out. We will work with you to make the course work for you as well as we can, while being fair to all students.
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-win2526-staff@lists.stanford.edu.
IMPORTANT OAE DEADLINES: If you plan to use your OAE-approved exam accommodations for a specific assessment, students must provide their letter and inform the instructor by:
Below, find class-by-class resources, including lecture notes, in-class agendas and exercises, and further reading. All videos can be found Canvas, or also 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.
We won't have time this year to get to this (thanks, Monday holidays!), and you aren't responsible for it for this class. However, if you are curious, the videos are available on YouTube for your perusal :)
IMPORTANT! The exam is 9am-11:50am. You will have 2 hours and 30 minutes to take the exam, and then we have scheduled 20 minutes to collect exams at the end. LET US KNOW ASAP IF YOU CANNOT MAKE (all of) THE EXAM!!!!!
No class.