Topic  Readings  Lecture notes  
Lecture #1 (08/20)  Introduction Events & Probability Application: Verifying Polynomial Identities Axioms of Probability 
MU Sections 1.11.2 

Lecture #2 (08/22) 
Axioms of Probability Application: Verifying Matrix Multiplication 
MU Sections 1.2 and 1.3 
lec2.pdf 
Lecture #3 (08/27) 
Bayes' Law Application: A Randomized MinCut Algorithm 
MU Sections 1.3 and 1.4 
lec3.pdf 
Lecture #4 (08/29) 
Discrete Random Variables & Expectation Linearity of Expectations Jensen's Inequality 
MU Section 2.1 
lec4.pdf 
Lecture #5 (09/05) 
The Bernoulli and Binomial Random Variables Conditional Expectation 
MU Sections 2.2 and 2.3 

Lecture #6 (09/17) 
Conditional Expectation The Geometric Distribution 
MU Sections 2.3 and 2.4 

Lecture #7 (09/19) 
Coupon's Collector Problem The Expected RunTime of Quicksort 
MU Sections 2.4 and 2.5 

Lecture #8 (09/21) 
The Expected RunTime of Quicksort Moments and Deviations Markov's Inequality Variance and Moments of a Random Variable 
MU Sections 2.5, 3.1, and 3.2 

Lecture #9 (09/24) 
Variance and Moments of a Random Variable Chebyshev's Inequality 
MU Sections 3.2 and 3.3 

Lecture #10 (09/26) 
Chebyshev's Inequality Coupon Collector's Problem A Randomized Algorithm for Computing the Median 
MU Sections 3.3 and 3.4 

Lecture #11 (09/26) 
A Randomized Algorithm for Computing the Median 
MU Section 4.1 

Lecture #12 (09/29) 
Chernoff Bounds Moment Generating Functions Deriving and Applying Chernoff Bounds 
MU Sections 4.1 and 4.2 

Lecture #13 (10/08)  Deriving and Applying Chernoff Bounds 
MU Section 4.2 

Lecture #14 (10/10) 
Better Bounds for Symmetric Random Variables Application: Set Balancing 
MU Sections 4.3 and 4.4 

Lecture #15 (10/15) 
Balls, Bins, and Random Graphs Example: The Birthday Paradox Balls into Bins (the ballsandbins model, bucketsort) 
MU Sections 5.1 and 5.2 

Lecture #16 (10/17) 
Balls into Bins (the ballsandbins model, bucketsort) The Poisson distribution 
MU Section 5.3 

Lecture #17 (10/19) 
The Poisson distribution (Chernoff bounds) The Poisson distribution as the limit of the Binomial distribution 
MU Section 5.3 

Lecture #18 (10/22) 
The Poisson Approximation 
MU Section 5.4 

Lecture #19 (10/24) 
Model for Random Graphs Algorithm for Finding Hamiltonian Cycles in Random Graphs 
MU Section 5.6 

Lecture #20 (10/26)  Analysis of the Algorithm 
MU Section 5.6 

Lecture #21 (10/31) 
The Probabilistic Method The Basic Counting Argument The Expectation Argument Derandomization Using Conditional Expectations 
MU Sections 6.16.3 