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

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 (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

Homework schedule

Homeworks are released on Monday and they are due the following Monday at 10pm. The homework pdf and LaTex source are posted on Piazza. The homework due dates are as follows:
• HW1: due at Gradescope on Monday, September 13, at 10pm.
• HW2: due at Gradescope on Monday, September 20, at 10pm.
• HW3: due at Gradescope on Monday, September 27, at 10pm.
• HW4: due at Gradescope on Monday, October 4, at 10pm.
• HW5: due at Gradescope on Tuesday, October 12, at 10pm (note the day change due to the Monday schedule).
• HW6: due at Gradescope on Tuesday, October 19, at 10pm.
• HW7: due at Gradescope on Tuesday, November 2, at 10pm.
• HW8: due at Gradescope on Monday, November 8, at 10pm.
• HW9: due at Gradescope on Monday, November 15, at 10pm.
• HW10: due at Gradescope on Monday, November 22, at 10pm.
• HW11: due at Gradescope on Monday, December 6, at 10pm.