CSE 312: Foundations of Computing II

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.

Wk	Date	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	[SEC 0] [SEC 0 Solutions]
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].	[HW 1]
	10/4	Probability Basics I Combinatorics wrap-up: Pigeonhole Principle Probability spaces Events [Slides] Reading: BT Sec 1.2.	[SEC 1] [SEC 1 Solutions]
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.	[HW 2]
	10/11	Conditional Probability II Bayes Rule and examples Pairwise independence Independence of several events Conditional independence [Slides] Reading: BT Sec 1.5.	[SEC 2] [SEC 2 Solutions]
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	[HW 3]
	10/18	Expectation I Probability Mass Functions Expectation Examples of expectation Multiple random variables [Slides] Reading: BT 2.1 + 2.2	[SEC 3] [SEC 3 Solutions]
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	[HW 4]
	10/25	Markov's and Chebyshev's Inequality Markov's inequality Chebyshev's inequality Conditional expectation [Slides] Reading: BT 7.2 + 2.6	[SEC 4] [SEC 4 Solutions]
5	10/28	Midterm Q&A	[Practice Midterm 1] [Solutions] [Practice Midterm 2] [Solutions]
	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]	[HW 5]
	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	[SEC 6] [SEC 6 Solutions]
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	[HW 6]
	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	[SEC 7] [SEC 7 Solutions]
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.)	[HW 7]
	11/22	Estimation II MLE estimators for Gaussians (Un)biased and consistent estimators Unbiased estimator for the variance MLE estimators are consistent [Slides]	[SEC 8] [SEC 8 Solutions]
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]	[HW 8]
	11/29	No class: Thanksgiving	[SEC 9] [SEC 9 Solutions]
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 Polynomials and the Schwartz-Zippel Lemma Fingerprinting for Large Files Exam info [Slides]	[Practice Final 1] [Practice Final 2] [Solutions Practice Final 1] [Solutions Practice Final 2]