Lectures (beginning September 5): D100: Tuesday (8.30 am - 10.20 am) and Thursday (8.30 am - 9.20 am) (AQ 3005) D200: Tuesday (11.30 am - 1.20 pm) (AQ 3150) and Thursday (11.30 am - 12.20 pm) (C 9002)
Tutorials (beginning September 17): D100: Friday (11.30 am - 12.20 am, 12:30 pm - 1.20 pm) (WMC 2533 & WMC 3511) D200: Tuesday (4.30 pm - 5.20 pm) (WMC 2531 & AQ 5035), 5:30 pm - 6.20 pm (WMC 2501 & AQ 5025)
Instructor: Sharan Vaswani
Instructor office hours: Tuesday, 3 pm - 4 pm (TASC-1 8221)
Teaching Assistant: Kaixuan Hu, Dingdong Yang, Haidan Liu, Harsimran Singh
TA office hours: Monday, 12.30 pm - 1.30 pm (ASB 9810), Wednesday, 1 pm - 2 pm (ASB 9804), Wednesday, 4 pm - 5 pm (ASB 9816), Thursday, 1 pm - 2 pm (ASB 9810)
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 and discussion.
| Date | Topics | Slides | References | |
|---|---|---|---|---|
| Thu September 5 | Course logistics, Sets, Functions | [L1] | LLM (4.1, 4.2, 4.5) | |
| Tue September 10 | Sequences, Counting, Permutations | [L2] | LLM (14.1 - 14.4) | |
| Thu September 12 | Combinations, Binomial Theorem | [L3] | LLM (14.5) | |
| Tue September 17 | Generalization to Multinomials, Inclusion Exclusion | [L4] | LLM (14.6-14.10) | |
| Thu September 19 | Pigeonhole principle, Introduction to Probability | [L5] | R (3.1-3.5), LLM (16.5) | |
| Mon September 23 | Assignment 1 released | |||
| Tue September 24 | Axioms and Rules of Probability | [L6] | R (3.6), LLM (16.4, 17.2) | |
| Thu September 26 | Birthday Paradox, Introduction to Conditional Probability | [L7] | R (3.6), LLM (17.2) | |
| Mon September 30 | Assignment 1 due | |||
| Tue October 1 | Conditional Probability, Monty Hall Problem, Tree Diagrams | [L8] | LLM (16.1-16.3, 17.1, 17.3, 17.4) | |
| Thu October 3 | Tree Diagrams, Bayes Rule | [L9] | R (3.7, 3.8), LLM (17.5, 17.6) | |
| Mon October 7 | Assignment 2 released | |||
| Tue October 8 | Law of Total Probability, Independent Events, Frievald's Algorithm | [L10] | LLM (17.7) | |
| Thu October 10 | Frievald's Algorithm | [L11] | O'Donnell (1) | |
| Mon October 14 | Assignment 2 due | |||
| Tue October 15 | Holiday | |||
| Thu October 17 | Probability Amplification, Random Variables | [L12] | R (4.1), LLM (18.1) | |
| Tue October 22 | Midterm | |||
| Thu October 24 | Random Variables, Distribution Functions | [L13] | R (5.1), LLM (18.1, 18.3) | Tue October 29 | Discrete Distributions | [L14] |
| Thu October 31 | Expectation of random variables | [L15] | R (4.4, 4.5), LLM (18.4.1-18.4.3) | |
| Mon November 4 | Assignment 3 released | |||
| Tue November 5 | Expectation of random variables, Linearity of expectation, Coupon Collector Problem | [L16] | LLM (18.5.1-18.5.4) | |
| Thu November 7 | Conditional Expectation, Law of Total Expectation, Independence of random variables | [L17] | LLM (18.4.5, 18.2) | |
| Tue November 12 | Max Cut, Randomized Quick Select | [L18] | H (5.2), H (16.1) | |
| Wed November 13 | Assignment 3 due | |||
| Thu November 14 | Variance | [L19] | R (4.6), LLM (19.3.1) | |
| Mon November 18 | Assignment 4 released | |||
| Tue November 19 | Properties of Variance | [L20] | LLM (19.3.2 19.3) | |
| Thu November 21 | Covariance, Correlation, Matching Birthdays | [L21] | R (4.7), LLM (19.4.2) | |
| Mon November 25 | Assignment 4 due | |||
| Tue November 26 | Tail Inequalities (Markov, Chebyshev) | [L22] | LLM (19.1, 19.2) | |
| Thu November 28 | Voter Poll, Weak Law of Large Numbers | [L23] | LLM (19.4, 19.6) | |
| Tue December 3 | Chernoff Bound, Randomized Load Balancing | [L24] | LLM (19.6) | |
| Thu December 5 (WMC 3520) (12 pm - 3 pm) |
Final | |||