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

[Home] [Logistics] [Schedule and Assignments]

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
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.