Instructor: Sharan Vaswani
Instructor office hours: Tuesday 11 am - 12 pm (TASC-1 9203)
Teaching Assistants: Yasaman Etesam, Aditya Bhadreshkumar Panchal
TA office hours: Thursday 9 am - 10 am (ASB9808)
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 |
|---|---|---|---|---|
| Tues May 10 | Course logistics, Sets, Sequences, Counting | [L1] | Meyer, Lehman, Leighton (4.1, 4.2, 4.5, 15.1, 15.2) | |
| Fri May 13 | Permutations, Combinations | [L2] | Meyer, Lehman, Leighton (15.3, 15.4, 15.5) | |
| Tues May 17 | Binomial Theorem, Generalization to Multinomials, Pigeonhole principle | [L3] | Meyer, Lehman, Leighton (15.6, 15.8, 15.9, 15.10) | |
| Fri May 20 | Introduction to Probability | [L4] | Ross (3.1, 3.2, 3.3) | [Assignment 1] released |
| Tues May 24 | Axioms and rules of Probability, Birthday Paradox | [L5] | Ross (3.4, 3.5), Meyer, Lehman, Leighton (17.4, 17.5) | |
| Fri May 27 | Introduction to Conditional Probability | [L6] | Ross (3.6), Meyer, Lehman, Leighton (18.2) | Assignment 1 due |
| Tues May 31 | Conditional Probability, Tree Diagrams, Monty Hall problem | [L7] | Ross (3.6), Meyer, Lehman, Leighton (17.1, 17.2, 18.3) | |
| Fri June 3 | Law of Total Probability, Bayes Rule | [L8] | Ross (3.7), Meyer, Lehman, Leighton (18.5) | |
| Tues June 7 | Law of Total Probability, Bayes Rule, Independent Events | [L9] | Ross (3.7, 3.8), Meyer, Lehman, Leighton (18.5, 18.6, 18.7) | [Assignment 2] released |
| Fri June 10 | Frievald's Algorithm | [L10] | O'Donnell (1) | |
| Tues June 14 | Random Variables, Distribution Functions | [L11] | Ross (4.1), Meyer, Lehman, Leighton (19.1, 19.3.1) | |
| Fri June 17 | Discrete Distributions (Bernoulli, Uniform, Binomial, Geometric) | [L12] | Ross (5.1), Meyer, Lehman, Leighton (19.3.1, 19.3.2, 19.3.4) | Assignment 2 due |
| Tues June 21 | Expectation of random variables, Linearity of expectation | [L13] | Ross (4.4, 4.5), Meyer, Lehman, Leighton (19.4.1-19.4.3, 19.5.1-19.5.3) | |
| Fri June 24 (8.30 am - 9.20 am) (AQ 3181) | Midterm | |||
| Tues June 28 | Coupon Collector Problem, Max Cut, Conditional Expectation, Law of Total Expectation, Randomized Quick Select | [L14] | Meyer, Lehman, Leighton (19.5.4, 19.4.5), Harvey (5.1, 4.2) | |
| Fri July 1 | Holiday | |||
| Tues July 5 | Independence of random variables, Joint distributions, Variance | [L15] | Ross (4.3, 4.6), Meyer, Lehman, Leighton (19.2, 20.3.1, 20.3.2) | [Assignment 3] released |
| Fri July 8 | Properties of Variance, Matching Birthdays | [L16] | Meyer, Lehman, Leighton (20.3) | |
| Tues July 12 | Covariance, Correlation, Tail Inequalities (Markov, Chebyshev) | [L17] | Ross (4.7), Meyer, Lehman, Leighton (20.1, 20.2) | |
| Fri July 15 | Voter Poll, Weak Law of Large Numbers | [L18] | Meyer, Lehman, Leighton (20.4) | Assignment 3 due |
| Tues July 19 | Machine Learning 101 | [L19] | Murphy (4.2.1, 4.2.3, 10.2.1, 10.2.3) | |
| Fri July 22 | Randomized QuickSort | [L20] | Harvey (4.3) | [Assignment 4] released |
| Tues July 26 | Chernoff Bound, Randomized Load Balancing | [L21] | Meyer, Lehman, Leighton (20.5) | |
| Fri July 29 | A/B Testing | [L22] | Harvey (10.2.2, 10.2.3) | |
| Tues August 2 | Introduction to Continuous random variables, Uniform, Normal distrubutions | [L23] | O'Donnell (17.1, 17.2, 17.4.2, 17.5.2, 22), Ross (4.2, 5.4, 5.5) | Assignment 4 due |
| Fri August 5 | Central Limit Theorem, Wrapping up | [L24] | O'Donnell (23.4), Ross (6.3) | |
| Sun August 14 (12 pm - 3 pm) (AQ 3005) | Final |