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. This includes using probability to analyze data sets and algorithms and to prove the correctness of algorithms.
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.
| Name | Email (@ bu . edu) |
|---|---|
| Harry Fu (TF) | chenghao |
| Nicholas Hall (TA) | njhall |
| Dongyue (Eleanor) Xu (TA) | xdy |
| John Bolognino (CA) | jcbolo |
| Vishesh (Vish) Jain (CA) | vjain25 |
| Christine Le (CA) | cnle |
| Cheng-En (Marcus) Tsai (CA) | mrtsai |
| Shengduo Li (CA) | shengdli |
| Eric Wang (CA) | eawang |
| Yuchen Lu (CA) | luyc |
| Noah Barnes (CA) | nebarnes |
Office hours: The office hours schedule will be posted on Piazza.
The readings are from the class textbook. A free copy of the textbook is available here. The schedule is tentative and subject to change.
:| Lecture | Topic | Reading | Instructor |
|---|---|---|---|
| L1 (Tue 9/6) | Introduction | AE | |
| L2 (Thu 9/8) | Probability cast: sample spaces, events, probability function | 17.1, 17.2, 17.3, 17.5 | AE |
| L3 (Tue 9/13) | Probability axioms and rules | AE | |
| L4 (Thu 9/15) | Tree diagrams | AE | |
| L5 (Tue 9/20) | Continuous probability spaces | AE | |
| L6 (Thu 9/23) | Random variables: definition and examples, application of recommender systems. | 19.1, 19.3, MIT notes | JB |
| L7 (Tue 9/27) | Random variables: bitcoin mining example, definition of discrete PDF and CDF. | JB | |
| L8 (Thu 9/29) | Examples of discrete PDFs and CDFs. Definition of continuous PDF and CDF. | JB | |
| L9 (Tue 10/4) | Properties of continuous PDFs and CDFs, examples and applications. | JB | |
| L10 (Thu 10/6) | Conditional probability: motivation, definition. | 18.2, 18.3, 18.4, 18.5 | AE |
| (Tue 10/11) | No lecture (Monday schedule). | ||
| L11 (Thu 10/13) | Conditional probability: tree diagrams, product rule, law of total probability. | AE | |
| L12 (Tue 10/18) | Conditional probability: medical testing example, Bayes theorem. | JB | |
| L13 (Thu 10/20) | Independent events and random variables. | 18.7, 19.2 | JB |
| L14 (Tue 10/25) | Mutual independence. | ||
| (Thu 10/27) | In-class midterm exam | ||
| L15 (Tue 11/1) | Expectation | 19.4, 19.5 | JB |
| L16 (Thu 11/3) | Expectation continued | JB | |
| L17 (Tue 11/8) | Variance | 20.2, 20.3 | JB |
| L18 (Thu 11/10) | Discrete distributions I: uniform, Bernoulli, binomial | 19.3, 19.4, 19.4.3, 19.4.6, 20.3.2, 20.3.4 |
AE |
| L19 (Tue 11/15) | Discrete distributions II: geometric | AE | |
| L20 (Thu 11/17) | Continuous distributions I: uniform, exponential | MIT notes I, MIT notes II | AE |
| L21 (Tue 11/22) | Continuous distributions II: normal | AE | |
| (Thu 11/24) | No lecture (Thanksgiving break) | ||
| L22 (Tue 11/29) | Markov and Chebyshev inequalities, estimation by sampling | 20.1, 20.2, 20.3.5, 20.4 | JB |
| L23 (Thu 12/1) | Chernoff inequality, load balancing | 20.5.2, 20.5.3, 20.5.5 | JB |
| L24 (Tue 12/6) | Random walks, PageRank | 21.1 (optional), 21.2 | JB |
| L25 (Thu 12/8) | Randomized algorithms, reservoir sampling AND/OR Coupon collecting |
19.5.4 |
AE |