Instructor: Sharan Vaswani
Instructor office hours: Tuesday 11.30 am - 12.30 pm (TASC-1 8221)
Teaching Assistant: Anh Dang, Matin Aghaei
TA office hours: Wednesday 2.30 pm - 3.30 pm (ASB 9814), Thursday 2.30 pm - 3.30 pm (ASB 9814)
Course Objective: The course introduces the foundational concepts in probability as required by many modern applications in computing. It will give the students in Computing Science experience in: 1. Understanding the combinatorial nature of many computational problems. 2. Working knowledge of probability theory, with applications to computing (algorithms, machine learning, data analysis, etc.)
Prerequisites: MACM 101, MATH 152 and MATH 232/MATH 240
Textbook: There is no required textbook. We will use the following resources:
Piazza for course-related questions.
| Date | Topics | Slides | References | Homework |
|---|---|---|---|---|
| Tue Jan 9 | Course logistics, Sets, Functions | [L1] | Meyer, Lehman, Leighton (4.1, 4.2, 4.5) | |
| Thu Jan 11 | Sequences, Counting, Permutations | [L2] | Meyer, Lehman, Leighton (14.1 - 14.4) | |
| Tue Jan 16 | Combinations, Binomial Theorem | [L3] | Meyer, Lehman, Leighton (14.5) | |
| Thu Jan 18 | Generalization to Multinomials, Inclusion Exclusion, Pigeonhole principle | [L4] | Meyer, Lehman, Leighton (14.6-14.10) | |
| Tue Jan 23 | Introduction to Probability, Axioms of Probability | [L5] | Ross (3.1-3.5), Meyer, Lehman, Leighton (16.5) | Assignment 1 released |
| Thu Jan 25 | Rules of Probability, Birthday Paradox | [L6] | Ross (3.6), Meyer, Lehman, Leighton (16.4, 17.2) | |
| Tue Jan 30 | Introduction to Conditional Probability | [L7] | Ross (3.6), Meyer, Lehman, Leighton (17.2) | Assignment 1 due |
| Thu Feb 1 | Conditional Probability, Monty Hall Problem, Tree Diagrams | [L8] | Meyer, Lehman, Leighton (16.1-16.3, 17.1, 17.3, 17.4) | |
| Tue Feb 6 | Tree Diagrams, Bayes Rule | [L9] | Ross (3.7, 3.8), Meyer, Lehman, Leighton (17.5, 17.6) | |
| Thu Feb 8 | Law of Total Probability, Independent Events | [L10] | Meyer, Lehman, Leighton (17.7) | Assignment 2 released |
| Tue Feb 13 | Frievald's Algorithm | [L11] | O'Donnell (1) | |
| Thu Feb 15 | Probability Amplification, Random Variables, Distribution Functions | [L12] | Ross (4.1), Meyer, Lehman, Leighton (18.1) | Assignment 2 due |
| Tue Feb 20 | Holiday | |||
| Thu Feb 22 | Holiday | |||
| Tue Feb 27 | Discrete Distributions | [L13] | Ross (5.1), Meyer, Lehman, Leighton (18.3) | |
| Thu Feb 29 (9.30 am - 11.15 am) (EDB 9618) | Midterm | Tue March 5 | Discrete Distributions | [L14] | Ross (5.1), Meyer, Lehman, Leighton (18.3) |
| Thu March 7 | Expectation of random variables, Linearity of expectation, Coupon Collector Problem | [L15] | Ross (4.4, 4.5), Meyer, Lehman, Leighton (18.4.1-18.4.3, 18.5.1-18.5.4) | |
| Tue March 12 | Max Cut, Conditional Expectation | [L16] | Meyer, Lehman, Leighton (18.4.5), Harvey (16.1) | |
| Thu March 14 | Law of Total Expectation, Randomized Quick Select, Independence of random variables | [L17] | Meyer, Lehman, Leighton (18.2), Harvey (5.2) | |
| Tue March 19 | Joint distributions, Variance | [L18] | Ross (4.3, 4.6), Meyer, Lehman, Leighton (19.3.1, 19.3.2) | Assignment 3 released |
| Thu March 21 | Properties of Variance, Matching Birthdays | [L19] | Meyer, Lehman, Leighton (19.3, 19.4.2) | |
| Tue March 26 | Covariance, Correlation, Tail Inequalities | [L20] | Ross (4.7), Meyer, Lehman, Leighton (19.1) | Assignment 3 due |
| Thu March 28 | Tail Inequalities (Markov, Chebyshev), Voter Poll | [L21] | Meyer, Lehman, Leighton (19.1, 19.2, 19.4) | |
| Tue April 2 | Weak Law of Large Numbers, Chernoff Bound | [L22] | Meyer, Lehman, Leighton (19.6) | Assignment 4 released |
| Thu April 4 | Chernoff Bound | [L23] | Meyer, Lehman, Leighton (19.6) | |
| Tue April 9 | Randomized Load Balancing | [L24] | Meyer, Lehman, Leighton (19.6) | Assignment 4 due |
| Thu April 11 | Course Review | [L25] | ||
| Sun April 14 (7 pm - 10 pm) (SWH10041) | Final |