CMPT 210 - Probability and Computing
Course overview
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
Topics
- Combinatorics: Permutations, Binomial coefficients, Inclusion-Exclusion
- Basic probability theory: Independence, Conditional probability, Bayes' Theorem
- Basic probability theory: Random variables, Expectation, Linearity of Expectation, Variance
- Discrete distributions: Binomial and Geometric, Joint distributions
- Tail inequalities: Markov’s Inequality, Chebyshev’s Inequality, Chernoff Bound
- Applications: Verifying matrix multiplication, Max-Cut, Machine Learning, Randomized QuickSelect, Voter Poll
Lecture slides and readings
| Topic | Slides | References |
|---|---|---|
| Sets, Functions | Lecture 1 | LLM (4.1, 4.2, 4.5) |
| Sequences, Counting, Permutations | Lecture 2 | LLM (14.1 - 14.4) |
| Combinations, Binomial Theorem | Lecture 3 | LLM (14.5) |
| Generalization to Multinomials, Inclusion Exclusion | Lecture 4 | LLM (14.6-14.10) |
| Pigeonhole principle, Introduction to Probability | Lecture 5 | R (3.1-3.5), LLM (16.5) |
| Axioms and Rules of Probability | Lecture 6 | R (3.6), LLM (16.4, 17.2) |
| Birthday Paradox, Introduction to Conditional Probability | Lecture 7 | R (3.6), LLM (17.2) |
| Conditional Probability, Monty Hall Problem, Tree Diagrams | Lecture 8 | LLM (16.1-16.3, 17.1, 17.3, 17.4) |
| Tree Diagrams, Bayes Rule | Lecture 9 | R (3.7, 3.8), LLM (17.5, 17.6) |
| Law of Total Probability, Independent Events, Frievald's Algorithm | Lecture 10 | LLM (17.7) |
| Frievald's Algorithm | Lecture 11 | O'Donnell (1) |
| Probability Amplification, Random Variables | Lecture 12 | R (4.1), LLM (18.1) |
| Random Variables, Distribution Functions | Lecture 13 | R (5.1), LLM (18.1, 18.3) |
| Discrete Distributions | Lecture 14 | |
| Expectation of random variables | Lecture 15 | R (4.4, 4.5), LLM (18.4.1-18.4.3) |
| Expectation of random variables, Linearity of expectation, Coupon Collector Problem | Lecture 16 | LLM (18.5.1-18.5.4) |
| Conditional Expectation, Law of Total Expectation, Independence of random variables | Lecture 17 | LLM (18.4.5, 18.2) |
| Max Cut, Randomized Quick Select | Lecture 18 | H (5.2), H (16.1) |
| Variance | Lecture 19 | R (4.6), LLM (19.3.1) |
| Properties of Variance | Lecture 20 | LLM (19.3.2 19.3) |
| Covariance, Correlation, Matching Birthdays | Lecture 21 | R (4.7), LLM (19.4.2) |
| Tail Inequalities (Markov, Chebyshev) | Lecture 22 | LLM (19.1, 19.2) |
| Voter Poll, Weak Law of Large Numbers | Lecture 23 | LLM (19.4, 19.6) |
| Chernoff Bound, Randomized Load Balancing | Lecture 24 | LLM (19.6) |
Books and references
- Introduction to Probability and Statistics for Engineers and Scientists, Sheldon M. R, Fifth Edition. [R]
- Mathematics for Computer Science (Lehman, Leighton, Meyer) [LLM]
- CMU Lecture Notes for Probability and Computing (O'Donnell) [D]
- Randomized Algorithms, Nick Harvey [H]
- Probabilistic Machine Learning: An Introduction, Kevin Murphy [M]