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

[Home] [Logistics] [Schedule and Assignments]

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
[Slides] Reading: BT Sec 1.6
1 09/30 Combinatorics III
  • More on binomial coefficients
  • Binomial Theorem
  • Combinatorial proof of Pascal's identity
  • Basic inclusion-exclusion
[Slides] Reading: BT Sec 1.6
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
[Slides] Reading: BT Sec 1.2.
2 10/7 Probability Basics II
  • More probabilty examples
  • Union / intersection / complement of events
  • Basic properties of probability
[Slides] Reading: BT Sec 1.2.
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
[Slides] Reading: BT Sec 1.5.
3 10/14 Applications: Pairwise-independence
  • Pairwise-independent hashing
[Slides] Reading: Some notes.
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
[Slides] Reading: BT 2.2..
11/6 Chernoff Bounds
  • The Chernoff Bound
  • Distributed Load Balancing
  • 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
[Slides] Reading: BT 4.1
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