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.

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) Topics	Reading and exercises	Handouts/Homework	Instructor
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.	LMM 18.2-18.5, 18.7; P 1.4.0-1.4.1,1.4.5	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.	LLM 18.8, 19.2, P 1.4.1, 3.1.4	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.	LLM 19.4-19.5, P 3.2.2	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.	LLM 20.1, 20.2, 20.3.5, 20.4	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