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


Instructor

Prof. Alina Ene
Homepage: cs-people.bu.edu/aene/
Email: (@ bu . edu) aene
Office Hours: Monday 9:30am - 11am

Teaching Fellows and Undergraduate Assistants

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

Lectures

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