CS 237: Probability in Computing (Spring 2022)

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

Course Staff

Office Hours Office
Prof. Sofya Raskhodnikova TTh 5-6pm MCS 112, but office hours moved to MCS B21
Prof. Wayne Snyder See Piazza
TF Ante Bing See Piazza
TA Eren Budur See Piazza
TF Wonyl Choi See Piazza

Syllabus, Lecture Slides, Reading

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

Lec.Date(Tentative) TopicsReading and exercisesHandouts/HomeworkInstructor
1 Th, Jan 20 Introduction General Course Information, Collaboration and Honesty Policy, HW1 out SR+WS
2 Tu, Jan 25 Probability cast: sample spaces, events, probability function.
Slides with notes.
LLM 17.1-17.2, P 1.1-1.2 SR
3 Th, Jan 27 Probability axioms and rules. Computing probabilities.
Slides with notes.
LLM 17.3,17.5, P 1.3,2 HW1 due, HW2 out; watch the video about non-transitive dice before discussions SR
4 Tu, Feb 1 Tree diagrams.
Slides with notes.
SR
5 Th, Feb 3 Continuous probability spaces HW2 due, HW3 out WS
6 Tu, Feb 8 Different kinds of sample spaces. 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
WS
7 Th, Feb 10 Discrete and continuous PDF and CDF. HW3 due, HW4 out WS
8 Tu, Feb 15 Conditional probability: motivation, definition.
Slides with notes.
LMM 18.2-18.5, 18.7;
P 1.4.0-1.4.1,1.4.5
SR
9 Th, Feb 17 Conditional probability: tree diagrams, product rule, law of total probability. Independent events.
Slides with notes.
HW4 due, HW5 out SR
Tu, Feb 22 Monday Schedule
10 Th, Feb 24 Independent events, Bayes theorem.
Slides
LLM 18.7, 18.9, P 1.4
HW5 due, practice midterm problems out WS
11 Tu, Mar 1 Review: Presentation of practice midterm solutions Practice midterm solutions are posted (on Friday) WS
12 Th, Mar 3 No Lecture HW6 out WS
Th, Mar 3 Evening Midterm Exam: 6:30pm-8:30pm in CGS 129
March 5-13 Spring Recess
13 Tu, Mar 15 Independence of random variables. Mutual independence.
Slides with notes.
LLM 18.8, 19.2, P 1.4.1, 3.1.4 SR
14 Th, Mar 17 Mutual Independence.
Slides with notes.
HW6 due, HW7 out SR
15 Tu, Mar 22 Expectation.
Slides with notes.
LLM 19.4-19.5, P 3.2.2 SR
16 Th, Mar 24 Expectation of continuous random variables. Linearity of Expectation.
Slides with notes.
HW7 due, HW8 out SR
17 Tu, Mar 29 Conditional expectation. Law of Total Expectation. Variance.
Slides with notes.
LLM 20.2, 20.3 WS
18 Th, Mar 31 Variance concluded; Discrete distributions I: Bernoulli, Uniform, Binomial
Slides with notes.
LLM 19.3.1, 19.3.2, 19.3.4, P 3.1.5 HW8 due, HW9 out WS
19 Tu, Apr 5 Discrete distributions II: Binomial concluded, Geometric, Negative Binomial
Slides with notes.
LLM 19.4.6, P 3.1.5 WS
20 Th, Apr 7 Coupon Collector. Reservoir Sampling.
Slides with notes.
LLM 19.5.4 HW09 due, HW10 out SR
21 Tu, Apr 12 Markov and Chebyshev inequalities, estimation by sampling
Slides with notes.
LLM 20.1, 20.2, 20.3.5, 20.4 SR
22 Th, Apr 14 Applications of Markov and Chebyshev's inequalities
Slides with notes.
HW10 due, HW11 out SR
23 Tu, Apr 19 Continuous distributions I: Uniform, Normal
Slides
P 4.2.3 WS
24 Th, Apr 21 Continuous distributions II: Exponential and Poisson Process
Slides
P 4.2.2; P 11.1.2 HW11 due, HW 12 out WS
25 Tu, Apr 26 Poisson distribution, probability in algorithms (Bucket Sort)
Slides with notes.
SR
26 Th, Apr 28 Probabalistic Data Structures, Hash Tables and Bloom Filters
Slides
HW12 due WS
27 Tu, May 3 Review WS
May 9-11 Final Exams: Mon, May 9, 3pm-5pm (STO B50) and Wed, May 11, 3pm-5pm (CAS 522)

Miscellaneous

Sample nameplate
Change the name to yours in this PPTX file, print it, and bring to class.
LaTeX resources
TexShop is a latex editor for the Mac platform; TexNiCenter is a tex editor for Windows; Overleaf is a web-based latex system (allows you to avoid latex installation on your machine).
Not so short intro to latex; a latex tutorial.
Homework template files: tex, pdf, jpg.

Sofya Raskhodnikova