Wk  Date  Lecture contents 
Assignments / Sections 
0  09/25 
Introduction + Combinatorics I
 Welcome / organizational details
 Introduction to combinatorics: The product rule
[Slides] Reading: BT Sec 1.1 + 1.6


 09/27 
Combinatorics II
 More on the product rule
 Permutations and the factorial function
 Subsets / combination and binomial coefficients
[Slides] Reading: BT Sec 1.6


1  09/30 
Combinatorics III
 More on binomial coefficients
 Binomial Theorem
 Combinatorial proof of Pascal's identity
 Basic inclusionexclusion
[Slides] Reading: BT Sec 1.6


 10/2 
Combinatorics IV
 General inclusionexclusion
 Number of derangements
[Slides]  Also see [Notes].


 10/4 
Probability Basics I
 Combinatorics wrapup: Pigeonhole Principle
 Probability spaces
 Events
[Slides] Reading: BT Sec 1.2.


2  10/7 
Probability Basics II
 More probabilty examples
 Union / intersection / complement of events
 Basic properties of probability
[Slides] Reading: BT Sec 1.2. 

 10/9 
Conditional Probability
 Definition and Examples
 Independence
 Chain rule and sequential processes
[Slides] Reading: BT Sec 1.3  1.4. 

 10/11 
Conditional Probability II
 Bayes Rule and examples
 Pairwise independence
 Independence of several events
 Conditional independence
[Slides] Reading: BT Sec 1.5. 

3  10/14 
Applications: Pairwiseindependence
 Pairwiseindependent hashing
[Slides] Reading: Some notes.


 10/16 
Application: Naive Bayes Classifiers + Intro Random
Variables
 Naive Bayes Classifiers
 Definition of (discrete) random variables
[Slides] Reading: BT 2.1 + 2.2


 10/18 
Expectation I
 Probability Mass Functions
 Expectation
 Examples of expectation
 Multiple random variables
[Slides] Reading: BT 2.1 + 2.2 

4  10/21 
Expectation II
 Multiple random variables and joint PMFs
 Linearity of expectation
 Examples: Binomial Distribution and Coupon Collector
[Slides] Reading: BT 2.4 + 2.2 +
2.5 

 10/23 
Variance and Independence
 Expectation of functions of random variables
 Variance
 Independent Random Variables
[Slides] Reading: BT 2.3, 2.4, 2.7 

 10/25 
Markov's and Chebyshev's Inequality
 Markov's inequality
 Chebyshev's inequality
 Conditional expectation
[Slides] Reading: BT 7.2 + 2.6


5  10/28 
Midterm Q&A 

 10/30 
Detour: Entropy and Information
 The data compression problem
 Entropy
 Shannon's source coding theorem
[Slides] [Shannon's
paper] 

 11/1 
Midterm (in class)
 Important: Check the edstem Q&A section for detailed
instructions

 SEC 5: See practice MTs (+ solutions)

6  11/4 
Poisson Distribution + Intro to Chernoff Bounds
 The Poisson Distribution and its properties
 Concentration for Binomial Random Variables
 Chernoff bound, first statement
[Slides] Reading: BT 2.2.. 

 11/6 
Chernoff Bounds
 The Chernoff Bound
 Distributed Load Balancing
 Polling and the Sampling Theorem
[Slides] [Chernoff
Bound notes] 

 11/8 
Continuous Distributions I
 Wrapup tail bounds/concentration
 Definition of countinuous RVs
 Probability Density Functions and Cumulative Density Funtions
[Slides]. Reading: BT 3.1 + 3.2 

7  11/11 
No class: Veterans Day 

 11/13 
Continuous Distributions II
 The uniform distribution
 The exponential distribution
 Intro to the normal distribution
[Slides] Reading: BT 3.1 + 3.2 

 11/15 
The Normal Distribution
 Basic Properties
 The standard normal distribution
 The Central Limit Theorem
[Slides] [Table of normal distribution] Reading: BT 3.3 + 7.4


8  11/18 
Moments and Moments Generating Functions
 Moment Generating Functions
 Sum of independent Random Variables
 Proof sketch of CLT
[Slides] Reading: BT 4.1 

 11/20 
Estimation I
 CLT and the Continuity Correction
 Introduction to MLE
 MLE for Bernoulli Random Variables
[Slides] Reading: Some
notes from Penn (These cover all three classes on estimation,
but note that we covered less than in these notes.)


 11/22 
Estimation II
 MLE estimators for Gaussians
 (Un)biased and consistent estimators
 Unbiased estimator for the variance
 MLE estimators are consistent
[Slides]


9  11/25 
Estimation III
 MLE estimators and consistency
 Confidence intervals
 Student's tdistribution
[Slides]


 11/27 
Application: Differential Privacy
 Privacy Attacks
 Definition of Differential Privacy and Properties
 Laplace Mechanism
 Randomized Response
[Slides] [A textbook]


 11/29 
No class: Thanksgiving 

10  12/2 
Randomized Algorithms I
 Las Vegas vs Monte Carlo
 Randomized Quicksort
 Primality Testing
[Slides]


 12/4 
Exam review
[Handwritten notes] 

 12/6 
Randomized Algorithms II

