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. |
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 |
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. |
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) |