$\DeclareMathOperator{\p}{Pr}$ $\DeclareMathOperator{\P}{Pr}$ $\DeclareMathOperator{\c}{^C}$ $\DeclareMathOperator{\or}{ or}$ $\DeclareMathOperator{\and}{ and}$ $\DeclareMathOperator{\var}{Var}$ $\DeclareMathOperator{\E}{E}$ $\DeclareMathOperator{\std}{Std}$ $\DeclareMathOperator{\Ber}{Bern}$ $\DeclareMathOperator{\Bin}{Bin}$ $\DeclareMathOperator{\Poi}{Poi}$ $\DeclareMathOperator{\Uni}{Uni}$ $\DeclareMathOperator{\Exp}{Exp}$ $\DeclareMathOperator{\N}{N}$ $\DeclareMathOperator{\R}{\mathbb{R}}$ $\newcommand{\d}{\, d}$

CS109 Course Overview

Updated 2021040417

If you have any questions after reading this overview, head on over to our FAQ page, post on our discussion forum, or email us at our mailing list: cs109 @ cs.stanford.edu.

CS109: Probability for Computer Scientists starts by providing a fundamental grounding in combinatorics, and then quickly moves into the basics of probability theory. We will then cover many essential concepts in probability theory, including particular probability distributions, properties of probabilities, and mathematical tools for analyzing probabilities. Finally, the last third of the class will focus on data analysis and machine learning as a means for seeing direct applications of probability in this exciting and quickly growing subfield of computer science. Read more here to learn what CS109 is all about. This is going to be a great quarter and we are looking forward to the chance to teach you.

Teaching Team

Jerry Cain

Lecturer: Jerry Cain
jerry @ cs.stanford.edu
OH Online
Fridays, 11:00am - noon


Our superstar Course Assistants (CAs):

Jerry Cain
Tim Gianitsos
Georgia Sampaio
Suzy Lou
Derek McCreight
Lucy Lu
Anand Shankar
Havin Hosgur
Emma Spellman
Jackson Eilers

Teaching and Learning Statement

We fully recognize that this experience cannot replace what we normally have on campus, and that many of you have personal situations that may change throughout the quarter. That being said, we are determined to reach the following course teaching goals to the best of our ability:

  1. To maintain the intellectual rigor of the CS109 curriculum while providing flexible ways for you to learn.
  2. To foster and maintain human connections and a sense of community throughout this online course.

Many of these changes that we are making are designed to help foster intellectual nourishment, social connection, and personal accommodation—through accessible, asynchronous content for diverse access, time zones, and contexts, and synchronous discussion to learn together and combat isolation. Please bear in mind that all of us are experiencing remote, online classrooms in an unprecedented time of turmoil, and we will have to adapt throughout this quarter together. Everyone needs support and understanding in this unprecedented moment, and we are here to listen to you. If you need something, please ask us. Thanks and welcome to CS109. (Credit for this wording goes to Prof. Brandon Bayne from UNC - Chapel Hill.)

Building Class Community

One of our big course teaching goals is establishing community: We will strive to create an inclusive and equitable class. Coming into CS109, students have greatly varying previous exposure to probability and higher-level math. Regardless of your background, you are welcome and well-prepared to succeed in CS109. We encourage you to succeed, and to help your peers succeed as well.

Asking questions: We are happy to answer any questions you may have through various course support channels (office hours, Edstem, etc.)! During lecture, we request that any questions that you ask be clarifications for yourself or others of the course material being discussed, rather than a question or comment intended to demonstrate additional knowledge beyond the scope of the current topic or the course, which may intimidate or discourage other students. If you do have such questions or comments, we are more than happy to discuss them during office hours, online, or before/after any lecture!

I. Course Overview

Prerequisites

The prerequisites for this course are CS103, CS106B or X, and Math 51 (or equivalent courses). Probability involves a fair bit of mathematics (set theory, calculus, and familiarity with linear algebra), and we'll be considering several applications of probability in CS that require familiarity with algorithms and data structures covered in CS106B/X. Here is a quick rundown of some of the mathematical tools from CS103 and Math 51 that we'll be using in this class: multivariate calculus (integration and differentiation), linear algebra (basic operations on vectors and matrices), an understanding of the basics of set theory (subsets, complements, unions, intersections, cardinality, etc.), and familiarity with basic proof techniques. We'll also do combinatorics in the class, but we'll be covering a fair bit of that material ourselves in the first week. Past students have managed to take CS106B concurrently with CS109 and have done just fine. CS103 is the pre-requisite that we rely on the least. See our FAQ for more information.

Learning Goals

After you're finished with CS109, we hope you'll have achieved the following learning goals:

  • Reason about situations using probabilities, expectation, and variance.
  • Feel comfortable learning about new probability concepts beyond the scope of this class (e.g., through one's own research, studies, or interests).
  • Write programs to simulate random experiments and to test experiment hypotheses.
  • Understand and implement simple machine learning algorithms like Naive Bayes and Logistic Regression.

Course Topics

Here are the broad strokes of the course (in approximate order). We cover a very broad set of topics so that you are equipped with the probability and statistics you will see in your future CS studies!

  • Counting and probability fundamentals
  • Single-dimensional random variables
  • Probabilistic models
  • Uncertainty theory
  • Parameter estimation
  • Introduction to machine learning

II. Course Structure

Units

If you are an undergraduate, you are required to take CS109 for 5 units of credit (this is by department and university policy, no exceptions). If you are a graduate student, you may enroll in CS109 for 3 or 4 units if it is necessary for you to reduce your units for administrative reasons. Taking the course for reduced units does not imply any change in the course requirements.

Lectures

We will be holding live lectures remotely via Zoom at 10:00am-10:50am Pacific Time. Come to learn the material, engage in interesting problems collectively with the class. While lecture attendance isn't mandatory it is correlated with doing well in the course and mastering the material! If you can't make lecture time, you can watch the lecture on canvas. We will typically have lecture posted within 6 hours of the live showing.

Sections

Active participation plays an important role in making you a master of probability for computer science. It has also been observed over many quarters that keeping up with the material highly correlates with improved class performance.

Each week for 50 minutes you will meet in a small group with one of our outstanding CAs (section leaders) and work through problems. If you have taken any of the CS106 classes, our sections will be very similar—except with more probability.

Section attendance and participation is required of all students.

Grading

The grade for the course will be determined according to the following breakdown:

ComponentFinal grade
Problem Sets (6 x 7%) 42%
Quizzes (3 x 14%) 42%
Concept Checks 10%
Section participation 6%

Concept Checks

In CS109 you will learn a large amount of content. The class moves as a consistent pace and staying on top of the material is key to success in the class and mastering the material. To help you keep pace, we rely on concept checks for every lecture. Concept checks will be posted at least two days before lecture and are due just as lecture begin begins. The concept checks will exercise material taught in prior lectures and any pre-lecture videos. You can submit an unlimited number of times up to and including the deadline; we will only grade the final submission. Concept checks will make up 10% of your final course grade.

Late Policy (Concept Checks)

After the initial deadline on Gradescope, you can submit your concept check up to a week later (also via Gradescope) for partial credit (capped at 50%). We will be lenient with the Week 1 deadlines, because we understand student schedules aren't stable during shopping period. But after Week 1, no other extensions will be granted for concept checks.

Problem Sets

During the course, there will be six problem sets assigned. Each student is to submit individual work on the problem sets. You may discuss with other students and course staff, but you must cite all discussion on your individually written final write-up of the problem set. All homework assignments should be turned in at the beginning of class (10:00am Pacific) on the respective due date.

Late Policy (Problem Sets)

We anticipate that—more than ever—during this quarter, there may be unforeseen circumstances that make it difficult to turn in homework assignments on time.

  • All problem sets are due at 10:00am Pacific on the on-time deadline listed on the assignment writeup. If you submit an assignment by the on-time deadline listed on the assignment writeup, you receive a small extra credit on-time bonus, typically 1% of your final problem set grade. Of course being on time has other benefits—when you do your work is closer to when you learned the material.
  • All students will be granted a penalty-free "grace period" for submission on all problem sets (except the final assignment). The grace period is one full class day and allows you to submit the assignment after the original deadline, with no impact on the final grade. As an example, a problem set due on Monday may be turned in on Wednesday before 10:00am Pacific to submit for full credit; a problem set due on Friday may be turned in on the following Monday before 10:00am Pacific to submit for full credit. This grace period is meant to give built-in flexibility for any unexpected snags—however, we strongly recommend that students submit by the original deadline if possible, in order to avoid falling behind on the class cadence.

Quizzes

In addition to the assignments, there will three quizzes, each weighted equally:

  • Week 4: Wednesday, Apr 21 - Friday Apr 23
  • Week 7: Wednesday, May 12 - Friday May 14
  • Week 10: Wednesday, Jun 02 - Friday June 04

Each quiz is a take-home, open-notes exam that approximates about 3-5 hours of active work and should be completed individually. Quizzes are released at 11:00am Pacific after class and due at 10:00am Pacific before the next class. This 47-hour window is intended to reduce time pressure and accommodate any difficulties accessing resources during the quiz itself. If you have an exceptional circumstances before or during the quiz, please inform Jerry or Tim as soon as you are able.

Quiz material will cover the material you have learned in the class lectures, class handouts, and assignments.

Extra Credit Contest

CS109 has traditionally held an extra credit contest, where students apply the principles in this class to explore a topic of their own choice. Participation in the contest is completely optional and prizes involve extra credit to your final course grade. More details about the contest to be posted midway through the quarter.

III. Course Resources

Optional Textbook

Sheldon Ross, A First Course in Probability (10th Ed.), Pearson Prentice Hall, 2018.

This is an optional textbook, meaning that the text is not required material, but students may find Ross offers a different and useful perspective on the important concepts of the class. Suggested, optional reading assignments from the textbook (10th Ed.) are in the schedule on the course website. The 8th, 9th, and 10th editions of the textbook are all fine for this class.

Borrowing the textbook online: HathiTrust, a library archive of which Stanford is a member, has granted the university online access to the 8th edition (2010) for the duration of the Fall quarter. The "check out" system works similarly to print reserves: A user can check out the book an hour at a time as long as they are actively using it. Access guidelines are on the HathiTrust How To Use It webpage. Once you're logged in, the book is at this link.

All students should retain receipts for books and other course-related expenses, as these may be qualified educational expenses for tax purposes. If you are an undergraduate receiving financial aid, you may be eligible for additional financial aid for required books and course materials if these expenses exceed the aid amount in your award letter. For more information, review your award letter or visit the Student Budget website.

"Working" Office Hours

To help make you more successful in this class , the course staff will hold "working" office hours. The idea is to encourage you to work on your problem sets at these office hours, so you can immediately ask any questions that come up while working on your problem sets. While you are certainly not required to attend any of these working office hours, they are simply meant to encourage you to interact with the course staff more often in order to help you better understand the course material. Besides, our job is to help everyone learn the material for this class, and being more accessible to you when you are actually working on your assignments (rather than when you just have a problem) will help the course go more smoothly for you (and it'll be more fun for us).

Accommodations

Students who may need an academic accommodation based on the impact of a disability must initiate the request with the Office of Accessible Education (OAE). Professional staff will evaluate the request with required documentation, recommend reasonable accommodations, and prepare an Accommodation Letter for faculty. For students who have disabilities that don't typically change appreciably over time, the letter from the OAE will be for the entire academic year; other letters will be for the current quarter only. Students should contact the OAE as soon as possible since timely notice (for example, at least a week before an exam) is needed to coordinate accommodations. Students should also send your accommodation letter to instructors as soon as possible. If you require additional, or different, accommodations specific to the Fall 2020 learning environment, please contact your disability adviser directly.

IV. Honor Code

Each student is expected to do their own work on the problem sets and exams in CS109. Students may discuss problem sets with each other as well as the course staff. Any discussion of problem set questions with others should be noted on a student's final write-up of the problem set answers. Each student must turn in their own write-up of the problem set solutions. Excessive collaboration (i.e., beyond discussing problem set questions) can result in honor code violations. Questions regarding acceptable collaboration should be directed to the class instructor prior to the collaboration.

It is a violation of the honor code to copy problem set or exam question solutions from others, or to copy or derive them from solutions found online or in textbooks, previous instances of this course, or other courses covering the same topics (e.g., STATS 116 or probability courses at other schools).Copying of solutions from students who previously took this or a similar course is also a violation of the honor code. Finally, a good point to keep in mind is that you must be able to explain and/or re-derive anything that you submit.

Please read our full Honor Code Policy, which specifically prohibits you from soliciting or taking solutions from other students or websites like Stack Overflow and Chegg.

Looking Forward to a Great Quarter

Genuinely, teaching CS109 is a profound joy. Thanks for coming to learn with us. We can't wait 🌱.