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

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.

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

- Gradescope: for homework. Entry code: B225KD.
- YouTube Playlist: for finding mini-lecture videos.
- Ed:
for asking questions and interacting with your peers, as well as for receiving announcements. To join our Ed page: join here.
**NOTE:**The first time you have to log on to Ed you have to click the second "join here" link. After that you can click the "Ed" link above. - Class-by-class assignments and resources
- cs265-aut2324-staff@lists.stanford.edu: staff email address. Please use this for logistics only; please use Ed for any questions about the course material.

- Homework will be done in small groups (up to three people). Please turn in
**one assignment per group.**Make sure to put all your names on the assignment, and to use the "group assignment" feature in Gradescope. - Homework will be turned in on Gradescope. Entry code: B225KD.
- Please
**type your homework.**Overleaf is a great option for group LaTeX-ing. - Homeworks will not be accepted after the due date, though your lowest homework grade will be dropped. (We will, of course, make exceptions for exceptional circumstances---please email staff list at cs265-aut2324-staff@lists.stanford.edu if anything comes up, or just Greg if it's sensitive in nature.)

- Homework 1: The basics. Latex Template. Due Friday 10/6. Sample Solutions
- Homework 2: Primality testing; Markov and Chebyshev. Latex Template. Due Friday 10/13. Sample Solutions
- Homework 3: Chernoff bounds; balls and bins. Latex Template. Due Friday 10/20. Sample Solutions
- Homework 4: Homework 4: Metric Embeddings! Latex Template. Due Friday 10/27. Sample Solutions
- Homework 5: Sparsity, Probabilistic Method. Latex Template. Due Friday 11/3. Sample Solutions
- Homework 6: More Probabilistic Method. Latex Template. Due Friday 11/10. Sample Solutions
- Homework 7: Markov Chains. Latex Template. Due Friday 12/1. Sample Solutions
- Homework 8: Martingales. Latex Template. Due Friday 12/8. Sample Solutions

Here are the homework due dates. The homeworks will be posted here as they become available.
Homeworks are due **on Fridays at 11:59pm** on Gradescope. We will post homework at least a week in advance, and we will shoot for the Wednesday 9 days before they are due.

Homeworks will mostly cover material from the preceding week (eg, HW1 is due in Week 2 and will cover material from Week 1), but may reach further back or have some hints of what's to come later. Likely topics are listed below, but are not binding.

- Quizzes are due by
**1:00pm Tuesdays/Thursdays**before the start of every class (except the first class and last two classes). The quizzes are short and meant to be a lightweight way to check your understanding of the material in the mini-lecture videos. - Quizzes can be found on Gradescope. Entry code: B225KD.
- Quizzes are open book, open notes. You are allowed to discuss them with your classmates, but since they are meant as a check-your-understanding please make sure that your understanding is checked!
- All of the quizzes are posted already (or will be by the start of the quarter) in case you want to get a head-start!
- Late quizzes will not be accepted. In the case of extreme circumstances where you would have to miss several classes/quizzes, or if you join the class late and have already missed quizzes, please contact the course staff to work out an alternative plan.

- We will have an
**in-person**Final Exam**Tuesday, December 12**, 3:30-6:30pm, in Room 420-041. - If you cannot make the in-person exam, reach out to Greg ASAP (ideally by the end of Week 3) to discuss options. We may be able to accommodate this, but only if we know well in advance.
- The exam is
**not**collaborative. - We will provide a reference sheet with some useful theorems and bounds on it; you will also be allowed to prepare and bring your own reference sheet(s) consisting of up to three double-sided sheets of standard-sized paper, with anything you want written on them. Other than that, the exam is closed-notes.
- The exam covers all the material in Weeks 1-9. (Including mini-lectures, HW, and in-class material). The Week 10 material will not be on the exam.
- A practice exam (along with a sample reference sheet) will be released before the final exam, probably early in Week 10.
- Here is a
**practice exam**to help you study. The practice exam has a reference sheet at the back, which will be the same as the reference sheet that you will get with the actual exam. (We'll make an announcement if there are any changes). See the note on the first page for how best to use this practice exam in your studying. [Exam][Solutions].

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.

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.

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.

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.

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.

- Before class: N/A
- During class: Agenda
- Further reading/watching:
- Lecture Notes
- Minilecture about our model of computation (in case we don't get to it in class).

- Before class:
- Mini-lecture on Linearity of Expectation.
- Mini-lecture on Karger's algorithm
- Corresponding lecture notes
- Do the quiz on gradescope.

- During class: Agenda
- Further reading:
- Agenda with solutions to in-class work
- Further (optional) reading:
- A new approach to the minimum cut problem (Karger and Stein, 1996).
- Minimum Cuts in Near-Linear Time (Karger 1998).

- Before class:
- Mini-lecture on Groups
- Mini-lecture on Primality Testing and Fermat's Test
- Corresponding lecture notes
- Do the quiz on gradescope.

- During class: Agenda
- Further reading:
- Agenda with solutions to in-class work
- Further (optional) reading: [Agrawal-Biswas: another randomized primality test], [Agrawal-Kayal-Saxena: Primes is in P].

- Before class:
- Mini-lecture on Markov and Chebyshev's inequalities
- Mini-lecture on Markov and Chebyshev in Action
- Corresponding lecture notes
- Do the quiz on gradescope.

- During class:
- Further reading:

- Before class:
- Mini-lecture on Moment Generating Functions
- Mini-lecture on Chernoff Bounds
- Corresponding lecture notes
- Do the quiz on gradescope.

- During class: Agenda
- Further reading:
- Further (optional) reading:

- Before class:
- Mini-lecture on balls and bins
- Mini-lecture on Poissonization (Heads up, there are two small errors in this video, pointed out in the description on YouTube. Sorry about that!)
- Corresponding lecture notes
- Do the quiz on gradescope.

- During class: Agenda
- Further reading:
- Agenda with solutions to in-class work
- Optional Further Reading: A survey on the power of two choices and related phenomenon

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

- Before class:
- Mini-lecture on the Johnson-Lindenstrauss Lemma
- Mini-lecture on Intro to Nearest Neighbors
- Corresponding lecture notes
- Do the quiz on gradescope.

- During class: Agenda
- Further reading:

- Before class:
- Mini-lecture on Compressed Sensing and the RIP
- Mini-lecture showing that Gaussian matrices have the RIP whp
- Corresponding lecture notes
- Do the quiz on gradescope.

- During class: Agenda
- Further reading:
- Further (optional) reading:
- Paper about the relationship between the RIP and JL: [Krahmer, Ward, 2010]
- Paper establishing the RIP for sub-sampled Fourier matrices: [Rudelson, Vershynin, 2008]

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

- 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: Agenda with solutions to in-class work

- 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: Agenda with solutions to in-class work

No class.

- Before class:
- Mini-lecture on Markov Chains
- Mini-lecture on Randomized 2-SAT
- Corresponding lecture notes
- Do the quiz on gradescope.

- During class: Agenda
- Further reading: Agenda with solutions to in-class work
- Optional further reading: More about spectral analysis of random walks: Excerpt from Arora and Barak (behind a Stanford login wall). In particular, Section 21.1 relates the second eigenvalue of the transition matrix to how fast a random walk on a regular graph approaches the uniform distribution (see Lemma 21.3).

- Before class:
- Mini-lecture on some Markov Chain Definitions
- Mini-lecture on the fundamental Theorem of Markov Chains
- Mini-lecture on MCMC
- Corresponding lecture notes
- Do the quiz on gradescope.

- During class: Agenda
- Further reading: Agenda with solutions to in-class work
- Further (optional) reading: A survey of using Markov chains to sample random colorings

- Before class:
- Mini-lecture on TV distance
- Mini-lecture on Mixing times
- Mini-lecture on couplings
- Corresponding lecture notes
- Do the quiz on gradescope.

- During class: Agenda
- Further reading: Agenda with solutions to in-class work
- More further reading: "Shuffing Cards and Stopping Times" by Aldous and Diaconis.

No class.

- Before class:
- Mini-lecture on Martingales
- Mini-lecture on Azuma-Hoeffding bound
- Corresponding lecture notes
- Do the quiz on gradescope.

- During class: Agenda
- Further reading: Agenda with solutions to in-class work

- Before class:
- Mini-lecture on stopping times and the martingale stopping theorem
- Mini-lecture on hitting times for random walks
- Corresponding lecture notes
- Do the quiz on gradescope.

- During class: Agenda
- Further reading: Agenda with solutions to in-class work