Wk  Date  Lecture contents 

1  03/30 
Introduction
 Welcome / organizational details
 How we conduct our lectures, sections, and office hours
online


 04/01 
Introduction + Combinatorics I
 Welcome / organizational details
 Introduction to combinatorics: The product rule
Reading: BT Sec 1.1, 1.6


 04/03 
Combinatorics II
 More on the product rule
 Permutations and the factorial function
 Subsets / combination and binomial coefficients
Reading: BT Sec 1.6


2  4/6 
Combinatorics III
 More on binomial coefficients
 Binomial Theorem
 Combinatorial proof of Pascal's identity
 Basic inclusionexclusion
Reading: BT Sec 1.6


 4/8 
Combinatorics IV
 General inclusionexclusion
 Number of derangements
Reading: [Notes]


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


3  4/13 
Probability Basics II
 More probabilty examples
 Union / intersection / complement of events
 Basic properties of probability
Reading: BT Sec 1.2.


 4/15 
Conditional Probability
 Definition and Examples
 Independence
 Chain rule and sequential processes
Reading: BT Sec 1.3  1.4


 4/17 
Conditional Probability II
 Bayes Rule and examples
 Pairwise independence
 Independence of several events
 Conditional independence
Reading: BT Sec 1.5.


4  4/20 
Applications: Pairwiseindependence
 Pairwiseindependent hashing
Reading: Some notes.


 4/22 
Application: Naive Bayes Classifiers + Intro Random
Variables
 Naive Bayes Classifiers
 Definition of (discrete) random variables
Reading: BT 2.1 + 2.2


 4/24 
Expectation I
 Probability Mass Functions
 Expectation
 Examples of expectation
 Multiple random variables
Reading: BT 2.1 + 2.2


5  4/27 
Expectation II
 Multiple random variables and joint PMFs
 Linearity of expectation
 Examples: Binomial Distribution and Coupon Collector


 4/29 
Variance and Independence
 Expectation of functions of random variables
 Variance
 Independent Random Variables
Reading: BT 2.3, 2.4, 2.7


 5/1 
Markov's and Chebyshev's Inequality
 Markov's inequality
 Chebyshev's inequality
 Conditional expectation
Reading: BT 7.2 + 2.6


6  5/4 
Midterm Q&A 

 5/6 
Detour: Entropy and Information
 The data compression problem
 Entropy
 Shannon's source coding theorem
[Shannon's
paper]


 5/8 
Midterm 9:30  10:20am (online)
 Important: Detailed instruction about online exam will be
posted on edstem later.


7  5/11 
Poisson Distribution + Intro to Chernoff Bounds
 The Poisson Distribution and its properties
 Concentration for Binomial Random Variables
 Chernoff bound, first statement
Reading: BT 2.2. 

 5/13 
Chernoff Bounds
 The Chernoff Bound
 Distributed Load Balancing
 Polling and the Sampling Theorem
[Chernoff
Bound notes] 

 5/15 
Continuous Distributions I
 Wrapup tail bounds/concentration
 Definition of countinuous RVs
 Probability Density Functions and Cumulative Density Funtions
Reading: BT 3.1 + 3.2 

8  5/18 
Continuous Distributions II
 The uniform distribution
 The exponential distribution
 Intro to the normal distribution
Reading: BT 3.1 + 3.2 

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


 5/22 
Moments and Moments Generating Functions
 Moment Generating Functions
 Sum of independent Random Variables
 Proof sketch of CLT
Reading: BT 4.1 

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


 5/27 
Estimation II
 MLE estimators for Gaussians
 (Un)biased and consistent estimators
 Unbiased estimator for the variance
 MLE estimators are consistent


 5/29 
Estimation III
 MLE estimators and consistency
 Confidence intervals
 Student's tdistribution


10  6/1 
Application: Differential Privacy
 Privacy Attacks
 Definition of Differential Privacy and Properties
 Laplace Mechanism
 Randomized Response
[A textbook]


 6/3 
Randomized Algorithms I
 Las Vegas vs Monte Carlo
 Randomized Quicksort
 Primality Testing


 6/5 
Exam review


11  6/10 
Final Exam 8:30  10:20am (Online)
 Important: Detailed instruction about online exam will be
posted on edstem later.

