CS 237: Probability in Computing (Fall 2026)

Course Overview

Introduction to basic probabilistic concepts and methods used in computer science. Develops an understanding of the crucial role played by randomness in computing, both as a powerful tool and as a challenge to confront and analyze. Emphasis on rigorous reasoning, analysis, and algorithmic thinking. (Counts as a Group B course for the CS major and a background course for the CS minor.)

More specifically, we focus on basic probability theory and applications and uses of probability theory in computer science. Randomness is used in designing efficient algorithms and has numerous applications in learning, cryptography, distributed systems, networking, data mining, data privacy, complexity theory and other areas of computer science. You will learn fundamental tools from probability and see some applications of randomness in computing.

Prerequisites: CS 131 and MA 123 (or equivalent elementary calculus class) and CS 111 (or equivalent Python programming experience). We assume good working knowledge of elementary set theory and counting, elementary calculus (i.e., integration and differentiation), and programming in Python. 		Randomness in computing picture

Quick Links: Office Hours · Piazza · Gradescope · Lecture slides and reading · Course information · Collaboration Policy· Additional Resources

Course Staff

Office Hours Office
Prof. Sofya Raskhodnikova Th 3:30-5:30pm CDS 1028
Teaching fellow: Anatoly Zavyalov Wed 4:30-6:30pm CDS 10th floor
Teaching fellow: Debanuj Nayak Tues 5-6pm CDS 10th floor
Course Assistant: Bivan Prajapati Mon noon-1pm CDS 10th floor

Office Hours Calendar

Lecture Slides and Reading

Reading chapters are from the first textbook (P) or from the second textbook (LLM), referred to by the acronyms of the author names.
Warning: Some of the material in lectures is covered on the board.

Lec. Date (Tentative) Topics Reading and exercises Handouts/Homework
1 Th, Sep 3 Introduction. Probability cast: sample spaces, events, probability function.
Slides with notes
General Course Information, Collaboration and Honesty Policy, HW1 out
2 Tu, Sep 8 Probability function. Probabillity axioms and rules. Computing probabilities.
Slides with notes
LLM 17.1-17.2, P 1.1-1.2
3 Th, Sep 10 Pobability rules. Tree diagrams. Monty Hall.
Slides with notes
 LLM 17.3,17.5, P 1.3,2 HW1 due, HW2 out
4 Tu, Sep 15 Monty Hall variants. The dice game. Discrete probability spaces.
Slides with notes
5 Th, Sep 17 Continuous probability spaces. Geometric method.
Slides with notes
 HW2 due, HW3 out
6 Tu, Sep 22 Random variables: definition and examples. LLM 19.1, 19.3,
P 3.1.1-3.1.3,3.1.6,
P 3.2.1, 4.0-4.1 MIT notes
7 Th, Sep 24 PMF, CDF and PDF. HW3 due, HW4 out
8 Tu, Sep 29 Conditional probability: motivation, definition. LMM 18.2-18.5, 18.7;
P 1.4.0-1.4.1,1.4.5
9 Th, Oct 1 Conditional probability: tree diagrams, product rule, law of total probability. Independent events. HW4 due, HW5 out
Tu, Oct 13 Substitute Monday Schedule
10 Tu, Oct 6 Independent events, Bayes' Rule LLM 18.7, 18.9, P 1.4 HW5 due, HW6 out
11 Th, Oct 8 Bayes' Rule. Review. LLM 18.8, 19.2, P 1.4.1, 3.1.4
12 Th, Oct 15 Pairwise and Mutual Independence HW6 due, practice midterm problems out. Practice midterm solutions are distributed in discussions (on Friday)
13 Tu, Oct 20 Review: Presentation of practice midterm solutions
Wed, Oct 21 Evening Midterm Exam: date Wednesday, October 21; time and location TBD
14 Th, Oct 22 Independence of random variables
Slides with notes		 HW7 out
15 Tu, Oct 27 Finish independence of random variables. Expectation LLM 19.4-19.5, P 3.2.2
16 Th, Oct 29 Expectation and infinite sums. Linearity of Expectation. HW7 due, HW8 out
17 Tu, Nov 3 Expectation of continuous random variables. Conditional expectation. Law of Total Expectation. LLM 20.2, 20.3
18 Th, Nov 5 Linearity of conditional expectation. Variance. Standard deviation. Variance properties
Let's play a game - Python codes 		LLM 19.3.1, 19.3.2, 19.3.4, P 3.1.5 HW8 due, HW9 out
19 Tu, Nov 10 Discrete distributions: Bernoulli, Uniform, Binomial, Geometric, Negative Binomial
Discrete distributions - Python code 		LLM 19.4.6, P 3.1.5
20 Th, Nov 12 Coupon Collector. Reservoir Sampling. LLM 19.5.4 HW09 due, HW10 out
21 Tu, Nov 17 Markov and Chebyshev inequalities, estimation by sampling LLM 20.1, 20.2, 20.3.5, 20.4
22 Th, Nov 19 Applications of Markov and Chebyshev's inequalities HW10 due, HW11 out
23 Tu, Nov 24 Continuous distributions I: Uniform, Normal P 4.2.3
Nov 25-29 Thanksgiving Recess
24 Tu, Dec 1 Continuous distributions II: Exponential and Poisson Process
Slides with notes 		P 4.2.2; P 11.1.2 HW11 due, HW 12 out
25 Th, Dec 3 Probability in algorithms (Bucket Sort)
26 Tu, Dec 8 Probabalistic Data Structures: Hash Tables and Bloom Filters; Sublinear-time Algorithms HW12 due
27 Th, Dec 10 Review
Dec 15 and Dec 17 Final Exams: Tue, Dec 15, 12pm-2pm (for Section A1, TR 11:00am-12:15pm) and Thu, Dec 17, 9am-11am (for Section A2, TR 9:30am-10:45am)

Resources

Sample nameplate
Change the name to yours in this PPTX file, print it, and bring to class.
LaTeX resources
Overleaf is a web-based LaTeX editor that requires no installation. For an introduction to LaTeX, see Learn LaTeX or Overleaf's Learn LaTeX in 30 minutes.
Homework template files: tex, pdf, jpg.
Sofya Raskhodnikova