## CSE 312: Foundations of Computing II (Autumn '19)

The following is a tentative schedule, and will be updated after each class to include the exact topics that have been covered.

WkDate 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
1 09/30 Combinatorics III
• More on binomial coefficients
• Binomial Theorem
• Combinatorial proof of Pascal's identity
• Basic inclusion-exclusion
10/2 Combinatorics IV
• General inclusion-exclusion
• Number of derangements
[Slides] - Also see [Notes].
10/4 Probability Basics I
• Combinatorics wrap-up: Pigeonhole Principle
• Probability spaces
• Events
2 10/7 Probability Basics II
• More probabilty examples
• Union / intersection / complement of events
• Basic properties of probability
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
3 10/14 Applications: Pairwise-independence
• Pairwise-independent hashing
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
11/6 Chernoff Bounds
• The Chernoff Bound
• Polling and the Sampling Theorem
[Slides] [Chernoff Bound notes]
11/8 Continuous Distributions I
• Wrap-up 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
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 t-distribution
[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 [Hand-written notes]
12/6 Randomized Algorithms II