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 other elementary calculus class). We assume good working knowledge of elementary set theory and counting, and elementary calculus (i.e., integration and differentiation).
| Name | Email (@ bu . edu) | Office Hours |
|---|---|---|
| Xingjian Han (TF) | xjhan | Friday 7:15am - 8:45am |
| Iden Kalemaj (TF) | ikalemaj | Thursday 8:30pm - 10pm |
| Yansong Bai (UA) | baibest1 | Tuesday 2pm - 3pm |
| Rachel Lai (UA) | ralai | Wednesday 4pm - 5pm |
| Anna Watson (UA) | ajwatson | Sunday 7pm - 8pm |
The readings are from the class textbook. A free copy of the textbook is available here.
Homeworks are released on Mondays and are due the following week on Monday at midnight. The homework pdf and tex are posted on Piazza.
You can try the Jupyter notebooks in your browser here. You can make changes and run the code in the browser. The changes will not be saved, when you hit refresh all the changes will be gone.
The schedule is tentative and subject to change
| Lecture | Topic | Reading | Slides | Code | Homework |
|---|---|---|---|---|---|
| L1 (Wed 9/2) | Introduction | Slides | dice | ||
| (Mon 9/7) | No class (Labor day) | HW1 out | |||
| L2 (Wed 9/9) | Probability cast: sample spaces, events, probability function | 17.1, 17.2, 17.3, 17.5 | Slides | python intro | |
| L3 (Mon 9/14) | Probability axioms | Slides | HW1 due, HW2 out | ||
| L4 (Wed 9/16) | Probability rules | Slides | |||
| L5 (Mon 9/21) | Tree diagrams | Slides | strange dice | HW2 due, HW3 out | |
| L6 (Wed 9/23) | Continuous probability spaces | Slides | continuous uniform sampling | ||
| L7 (Mon 9/28) | Random variables: definition and examples | 19.1, 19.3, MIT notes | Slides | hot hands | HW3 due, HW4 out |
| L8 (Wed 9/30) | Random variables: pdf and cdf | Slides | |||
| L9 (Mon 10/5) | Random variables: more pdf and cdf | Slides | HW4 due, HW5 out | ||
| L10 (Wed 10/7) | Conditional probability: motivation, definition, examples | 18.2, 18.3, 18.4, 18.5 | Slides | ||
| (Mon 10/12) | No class (Columbus Day). Lecture moved to Tuesday (Monday schedule). | HW5 due, Midterm 1 practice out | |||
| L11 (Tue 10/13) | Conditional probability: tree diagrams, product rule, law of total probability | Slides | |||
| L12 (Wed 10/14) | Conditional probability: Bayes theorem | Slides | |||
| L13 (Mon 10/19) | Midterm exam I | HW6 out | |||
| L14 (Wed 10/21) | Independent events | 18.7, 19.2 | Slides | ||
| L15 (Mon 10/26) | Independent random variables, mutual independence | Slides | HW6 due, HW7 out | ||
| L16 (Wed 10/28) | Mutual independence continued | Slides | |||
| L17 (Mon 11/2) | Expectation: definition, examples | 19.4, 19.5 | Slides | HW7 due, HW8 out | |
| L18 (Wed 11/4) | Linearity of expectation, functions of random variables | Slides | |||
| L19 (Mon 11/9) | Conditional expectation, variance | 20.2, 20.3 | Slides | HW8 due, HW9 out | |
| L20 (Wed 11/11) | Discrete distributions: Bernoulli, binomial, geometric | 19.3, 19.4, 19.4.3, 19.4.6, 20.3.2, 20.3.4 |
Slides | distributions | |
| L21 (Mon 11/16) | Continuous distributions I: exponential, uniform | MIT notes I, MIT notes II | Slides | HW9 due, HW10 out, Midterm 2 practice out | |
| L22 (Wed 11/18) | Continuous distributions II: normal | Slides | |||
| L23 (Mon 11/23) | Markov and Chebyshev inequalities, estimation by sampling | 20.1, 20.2, 20.3.5, 20.4 | Slides | HW10 due | |
| L24 (Mon 11/30) | Midterm exam II | HW11 out | |||
| L25 (Wed 12/2) | Chernoff inequality, load balancing | 20.5.2, 20.5.3, 20.5.5 | Slides | ||
| L26 (Mon 12/7) | Random walks | 21.1 (optional), 21.2 | Slides | HW11 due | |
| L27 (Wed 12/9) | Randomized algorithms, reservoir sampling | Slides | reservoir sampling |