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 inclusion-exclusion
Reading: BT Sec 1.6
|
|
| 4/8 |
Combinatorics IV
General inclusion-exclusion
Number of derangements
Reading: [Notes]
|
|
| 4/10 |
Probability Basics I
Combinatorics wrap-up: 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: Pairwise-independence
Pairwise-independent 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
Wrap-up 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 t-distribution
|
|
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.
|
|