| Lecture | Topic | Lecture Notes |
|---|---|---|
Lecture 1 |
Introduction, Monty Hall, probability spaces and examples. |
|
Lecture 2 |
More examples of probability spaces, review of sets, probability rules from set theory. |
|
Lecture 3 |
Review of sets (from CS 131), probability rules from set theory. |
|
Lecture 4 |
Review of counting (from CS 131). |
|
Lecture 5 |
Review of counting (from CS 131), continuous probability spaces. |
|
Lecture 6 |
More examples of continuous probability spaces. |
|
Lecture 7 |
Conditional probability. |
|
Lecture 8 |
Why tree diagrams work, product rule for conditional probability, law of total probability. |
|
Lecture 9 |
Independence. |
|
Lecture 10 |
Conditional independence. Probabilities of independent coin flips. |
|
The material covered by the midterm ends here. |
||
Lecture 11 |
Review of asymptotic notation (from CS 131). Introduction to randomized algorithms: testing whether two polynomials are equivalent. |
|
Lecture 12 |
Introduction to discrete random variables. Independence for random variables. |
|
Lecture 13 |
PDF and CDF of a discrete random variable. Discrete distributions: Bernoulli, Uniform, Binomial. |
|
Lecture 14 |
Expectation of a discrete random variable. Conditional expectation and law of total expectation. Geometric distribution. |
|
Lecture 15 |
Geometric distribution: memoryless property, expectation. Linearity of Expectation. |
|
Lecture 16 |
Expectation of a Binomial random variable. Coupon collector problem. Functions of random variables. |
|
Lecture 17 |
Variance and standard deviation. |
|
Lecture 18 |
Variance of discrete distributions. Deviations from the mean: Markov and Chebyshev inequalities. |
|
Lecture 19 |
Applications of Chebyshev: matching birthdays, polling. Estimation by sampling. |
|
Lecture 20 |
Pairwise independent sampling. Chernoff Inequality and application to randomized load balancing. |
|
Lecture 21 |
Continuous random variables. Continuous distributions: Uniform, Exponential. |
|
Lecture 22 |
Expectation, variance, and independence for continuous random variables. Uniform and Exponential distributions continued. |
|
Lecture 23 |
Uniform and Exponential distributions continued. |
|
Lecture 24 |
Normal distribution. |
|
The material covered by the final exam ends here. |
||
Lecture 25 |
Course recap. |