CS237: Probability in Computing

Course Description

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

Course Staff

Prof. Alina Ene
Homepage: cs-people.bu.edu/aene/
Email: aene @ bu . edu
Office Hours: Wed 4 - 5:30pm, in MCS 291

Teaching Fellow: Erasmo Tani
Email: etani @ bu . edu
Office Hours: Tue 5:30 - 7pm, in MCS 135B (note: the room is on the 1st floor, not the basement)

Undergraduate Assistants: Sam Harrison, Yue Yu
Office Hours: Th 5:30 - 7pm, in the undergraduate lab


The readings are from the class textbook. A free copy of the textbook is available here.
Homeworks are released on Thursdays and are due the following week on Thursday 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 (1/22) Introduction Slides dice
L2 (1/24) Probability cast: sample spaces, events, probability function 17.1, 17.2, 17.3, 17.5 Slides HW1 out
D1 (1/25) Discussion week 1 Slides python intro
L3 (1/29) Probability axioms Slides
L4 (1/31) Probability rules Slides HW1 due, HW2 out
L5 (2/5) A guessing game, tree diagrams Slides
L6 (2/7) More tree diagrams, continuous probability spaces Slides strange dice; continuous uniform sampling HW2 due, HW3 out
L7 (2/12) Random variables: definition and examples 19.1, 19.3, MIT notes Slides hot hands
L8 (2/14) Random variables: pdf and cdf Slides HW3 due, HW4 out
L9 (2/19) No class (Monday schedule)
L10 (2/21) More pdf/cdf (slides included in L8 slide deck above). Conditional probability: motivation, definition 18.2, 18.3, 18.4, 18.5 Slides HW4 due, HW5 out
D5 (2/22) Discussion week 5 Notes
L11 (2/26) Conditional probability: examples, tree diagrams, product rule Slides
L12 (2/28) More conditional probability: more examples, law of total probability, Bayes theorem Slides HW5 due, HW6 out
L13 (3/5) Independent events and random variables 18.7, 19.2 Slides
L14 (3/7) Mutual independence Slides HW6 due, HW7 out, midterm practice problems out
L15 (3/19) Midterm review Slides
L16 (3/21) Midterm
L17 (3/26) Expectation 19.4, 19.5 Slides
L18 (3/28) Variance 20.2, 20.3 Slides HW7 due, HW8 out
L19 (4/2) Discrete distributions I: uniform, Bernoulli, binomial 19.3, 19.4, 19.4.3,
19.4.6, 20.3.2, 20.3.4
Slides distributions, double sixes (L20)
L20 (4/4) Discrete distributions II: geometric Slides HW8 due, HW9 out
L21 (4/9) Continuous distributions I: uniform, exponential MIT notes I, MIT notes II Slides
L22 (4/11) Continuous distributions II: normal Slides HW9 due, HW10 out
L23 (4/16) Markov and Chebyshev inequalities, estimation by sampling 20.1, 20.2, 20.3.5, 20.4 Slides
L24 (4/18) Chernoff inequality, load balancing 20.5.2, 20.5.3, 20.5.5 Slides HW10 due, final practice problems out
L25 (4/23) Random walks 21.1 (optional), 21.2 Slides
L26 (4/25) Randomized algorithms, reservoir sampling Slides reservoir sampling
L27 (4/30) Final exam review
L28 (5/2) Course recap