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) |
|---|---|
| Jeremy Feininger (TA) | jlf77 |
| Eren Budur (TA) | ebudur |
| Yang (Alex) Yu (CA) | yuyang00 |
| Waner Zhou (CA) | zwe |
| Cassie Huang (CA) | chuang18 |
| Ji (Anna) Zhang (CA) | annajz |
| John Bolognino (CA) | jcbolo |
| Marco Raigoza (CA) | mraigoza |
Office hours: The office hours schedule has been 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 (Thu 9/2) | Introduction | AE | |
| L2 (Tue 9/7) | Probability cast: sample spaces, events, probability function | 17.1, 17.2, 17.3, 17.5 | AE |
| L3 (Thu 9/9) | Probability axioms and rules | AE | |
| L4 (Tue 9/14) | Tree diagrams | AE | |
| L5 (Thu 9/16) | Continuous probability spaces | AE | |
| L6 (Tue 9/21) | Random variables: definition and examples, application of recommender systems. | 19.1, 19.3, MIT notes | JB |
| L7 (Thu 9/23) | Random variables: bitcoin mining example, definition of discrete PDF and CDF. | JB | |
| L8 (Tue 9/28) | Examples of discrete PDFs and CDFs. Definition of continuous PDF and CDF. | JB | |
| L9 (Thu 9/30) | Properties of continuous PDFs and CDFs, examples and applications. | JB | |
| L10 (Tue 10/5) | Conditional probability: motivation, definition. | 18.2, 18.3, 18.4, 18.5 | AE |
| L11 (Thu 10/7) | Conditional probability: tree diagrams, product rule, law of total probability. | AE | |
| (Tue 10/12) | No lecture (Monday schedule). | ||
| L12 (Thu 10/14) | Conditional probability: medical testing example, Bayes theorem. | JB | |
| L13 (Tue 10/19) | Independent events and random variables. | 18.7, 19.2 | JB |
| L14 (Thu 10/21) | Mutual independence. | JB | |
| L15 (Tue 10/26) | In-class midterm exam | ||
| L16 (Thu 10/28) | Expectation | 19.4, 19.5 | JB |
| L17 (Tue 11/2) | Expectation continued | JB | |
| L18 (Thu 11/4) | Variance | 20.2, 20.3 | JB |
| L19 (Tue 11/9) | Discrete distributions I: uniform, Bernoulli, binomial | 19.3, 19.4, 19.4.3, 19.4.6, 20.3.2, 20.3.4 |
AE |
| L20 (Thu 11/11) | Discrete distributions II: geometric | AE | |
| L21 (Tue 11/16) | Continuous distributions I: uniform, exponential | MIT notes I, MIT notes II | AE |
| L22 (Thu 11/18) | Continuous distributions II: normal | AE | |
| L23 (Tue 11/23) | Markov and Chebyshev inequalities, estimation by sampling | 20.1, 20.2, 20.3.5, 20.4 | AE |
| (Thu 11/25) | No lecture (Thanksgiving break) | ||
| L24 (Tue 11/30) | Chernoff inequality, load balancing | 20.5.2, 20.5.3, 20.5.5 | JB |
| L25 (Thu 12/2) | Random walks, PageRank | 21.1 (optional), 21.2 | JB |
| L26 (Tue 12/7) | Randomized algorithms, reservoir sampling | JB | |
| L27 (Thu 12/9) | Coupon collecting | 19.5.4 | AE |