## CSE 312: Foundations of Computing II (Spring '20)

The following is a tentative schedule, following the schedule of 312 taught in Autumn 2019 by Professor Stefano Tessaro. We will modify the schedule along the quarter depending on the pace of the class, and adjustment to the material. However, this tentative schedule only serves as an initial reference and will not be updated during the quarter. Instead, we will upload all lecture slides, section handouts, homeworks, and reading material on Edstem.

WkDate 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
04/03 Combinatorics II
• More on the product rule
• Permutations and the factorial function
• Subsets / combination and binomial coefficients
2 4/6 Combinatorics III
• More on binomial coefficients
• Binomial Theorem
• Combinatorial proof of Pascal's identity
• Basic inclusion-exclusion
4/8 Combinatorics IV
• General inclusion-exclusion
• Number of derangements
4/10 Probability Basics I
• Combinatorics wrap-up: Pigeonhole Principle
• Probability spaces
• Events
3 4/13 Probability Basics II
• More probabilty examples
• Union / intersection / complement of events
• Basic properties of probability
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
4 4/20 Applications: Pairwise-independence
• Pairwise-independent hashing
4/22 Application: Naive Bayes Classifiers + Intro Random Variables
• Naive Bayes Classifiers
• Definition of (discrete) random variables
4/24 Expectation I
• Probability Mass Functions
• Expectation
• Examples of expectation
• Multiple random variables
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
5/1 Markov's and Chebyshev's Inequality
• Markov's inequality
• Chebyshev's inequality
• Conditional expectation
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
5/13 Chernoff Bounds
• The Chernoff Bound
• 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
8 5/18 Continuous Distributions II
• The uniform distribution
• The exponential distribution
• Intro to the normal distribution
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
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.