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. 