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

### Course Staff

Instructors:

Prof. John Byers
Homepage: cs.bu.edu/fac/byers/
Email: (@ bu . edu) byers

Prof. Alina Ene
Homepage: cs-people.bu.edu/aene/
Email: (@ bu . edu) aene

Teaching Assistants:

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.

### Lectures

The readings are from the class textbook. A free copy of the textbook is available here. The schedule is tentative and subject to change.

:
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. AE, John traveling
(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

### Homework schedule:

Homeworks are released on Monday and they are due the following Monday at 10pm. On the weeks where Monday is a holiday, the homework will be due on Tuesday. The homework pdf and LaTex source are posted on Piazza.