CS 237: Probability in Computing (Spring 2023)

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 CDS 1028
Prof. Tiago Januario See Piazza CDS 911
Teaching fellows: Wonyl Choi, Debanuj Nayak, Konstantinos Sotiropoulos See Piazza
Teaching assistants: Vishesh Jain, Cheng-En (Marcus) Tsai, Dongyue (Eleanor) Xu See Piazza
Course Assistants: Noah Barnes, Osama Dabbousi, Aiden Fockens, Max Greenspan, Isaac Hu, Shengduo Li, Yuchen Lu, Maysen Pagan, Muniruddin Siddiqui, Eric Wang See Piazza

Syllabus, Lecture Slides, Reading

Reading chapters are from the first textbook (LLM) or from the second 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) Topics Reading and exercises Handouts/Homework Instructor
1 Th, Jan 19 Introduction
Slides with notes 		General Course Information, Collaboration and Honesty Policy, Instructions for Setting up for programming assignments, HW1 out SR+TJ
2 Tu, Jan 24 Probability cast: sample spaces, events, probability function.
Slides with notes 		LLM 17.1-17.2, P 1.1-1.2 SR
3 Th, Jan 26 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 TJ
4 Tu, Jan 31 Tree diagrams.
Slides with notes 		SR
5 Th, Feb 2 Continuous probability spaces
Slides with notes 		HW2 due, HW3 out SR
6 Tu, Feb 7 Different kinds of sample spaces. Random variables: definition and examples.
Slides with notes 		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		 TJ
7 Th, Feb 9 PMF, CDF and PDF.
Slides with notes 		HW3 due, HW4 out TJ
8 Tu, Feb 14 Conditional probability: motivation, definition.
Slides with notes 		LMM 18.2-18.5, 18.7;
P 1.4.0-1.4.1,1.4.5		 TJ
9 Th, Feb 16 Conditional probability: tree diagrams, product rule, law of total probability. Independent events.
Slides with notes 		HW4 due, HW5 out TJ
Tu, Feb 21 Monday Schedule
10 Th, Feb 23 Independent events, Bayes' Rule
Slides with notes 		LLM 18.7, 18.9, P 1.4 HW5 due, HW6 out TJ
11 Tu, Feb 28 Bayes' Rule. Review.
Slides with notes		 LLM 18.8, 19.2, P 1.4.1, 3.1.4 SR
12 Th, Mar 2 Pairwise and Mutual Independence
Slides with notes		 HW6 due, practice midterm problems out. Practice midterm solutions are posted (on Friday) SR
March 4-12 Spring Recess
13 Tu, Mar 14 Review: Presentation of practice midterm solutions
 TJ
Wed, Mar 15 Evening Midterm Exam: 6:30pm-8:30pm in CGS 129
14 Th, Mar 16 Independence of random variables
Slides with notes		 HW7 out SR
15 Tu, Mar 21 Finish independence of random variables. Expectation
Slides with notes		 LLM 19.4-19.5, P 3.2.2 SR
16 Th, Mar 23 Expectation and infinite sums. Linearity of Expectation.
Slides with notes		 HW7 due, HW8 out SR
17 Tu, Mar 28 Expectation of continuous random variables. Conditional expectation. Law of Total Expectation.
Slides with notes 		LLM 20.2, 20.3 TJ
18 Th, Mar 30 Linearity of conditional expectation. Variance. Standard deviation. Variance properties
Slides with notes
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 TJ
19 Tu, Apr 4 Discrete distributions: Bernoulli, Uniform, Binomial, Geometric, Negative Binomial
Slides with notes
Discrete distributions - Python code 		LLM 19.4.6, P 3.1.5 TJ
20 Th, Apr 6 Coupon Collector. Reservoir Sampling.
Slides with notes		 LLM 19.5.4 HW09 due, HW10 out SR
21 Tu, Apr 11 Markov and Chebyshev inequalities, estimation by sampling
Slides with notes		 LLM 20.1, 20.2, 20.3.5, 20.4 SR
22 Th, Apr 13 Applications of Markov and Chebyshev's inequalities
Slides with notes		 HW10 due, HW11 out SR
23 Tu, Apr 18 Continuous distributions I: Uniform, Normal
Slides with notes 		P 4.2.3 TJ
24 Th, Apr 20 Continuous distributions II: Exponential and Poisson Process
Slides with notes 		P 4.2.2; P 11.1.2 HW11 due, HW 12 out TJ
25 Tu, Apr 25 Probability in algorithms (Bucket Sort)
Slides with notes 		SR
26 Th, Apr 27 Probabalistic Data Structures: Hash Tables and Bloom Filters; Sublinear-time Algorithms
Slides with notes 		HW12 due SR
27 Tu, May 2 Review TJ
May 8-12 Final Exams: Mon, May 8, 3pm-5pm (for Section A1) and Wed, May 10, 3pm-5pm (for Section B1)

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