CSE 312: Foundations of Computing II, Autumn 2024

Announcements and Updates

Schedule

For future lectures, this is a tentative schedule. The exact contents are subject to change. Links to future materials may also be broken.

Week 1
Topic
Week 1
Lecture 1
(Wed, Sept 25)
Introduction
So you think you can count?
slides cc
set theory review Reading: 1.1-1.2.1
PSet1 Out
Section 1
(Thu, Sept 26)
Counting practice
materials solutions
Lecture 2
(Fri, Sept 27)
Combinations and Binomial Coefficients
slides cc Reading: 1.2.2-1.3.1
Week 2
Lecture 3
(Mon, Sept 30)
Inclusion-Exclusion, Pigeonhole Principle and More
slides cc Reading: 1.3
Lecture 4
(Wed, Oct 2)
Discrete Probability
slides cc Reading: 2.1
PSet2 Out PSet1 Due
Section 2
(Thu, Oct 3)
Probability problems
materials solutions
Lecture 5
(Fri, Oct 4)
Conditional Probability
Bayes Theorem
slides cc Reading: 2.2
Week 3
Lecture 6
(Mon, Oct 7)
Bayesian Inference & Independence
slides cc Reading: 2.3
Lecture 7
(Wed, Oct 9)
Intro to Random Variables & Expectation
slides cc Reading: 3.1
PSet3 Out PSet2 Due
Section 3
(Thu, Oct 10)
Conditional Probabilities, Chain rule
materials solutions Naive Bayes Slides
Lecture 8
(Fri, Oct 11)
Linearity of Expectation
slides cc Reading: 3.1.3-3.2.1
Week 4
Lecture 9
(Mon, Oct 14)
Variance
Independence of RVs
slides cc Reading: 3.2.2-3.3
Lecture 10
(Wed, Oct 16)
Bloom Filters
slides cc Reading: 3.4, 9.4
PSet3 Due PSet4 Out
Section 4
(Thu, Oct 17)
Discrete Random Variables
materials solutions
Lecture 11
(Fri, Oct 18)
Zoo of Discrete RVs
slides cc Reading: 3.4-3.5, 9.4
Week 5
Lecture 12
(Mon, Oct 21)
Poisson RVs
slides cc Reading: 3.5-3.6
Lecture 13
(Wed, Oct 23)
Continuous RV Basics
Uniform RVs
slides cc Reading: 4.1-4.2.1 PSet4 Due
Section 5
(Thu, Oct 24)
Discrete Zoo Practice
materials solutions
Lecture 14
(Fri, Oct 25)
Expectation & Variance of Continuous RVs
Exponential RVs
slides cc Reading: 4.2.1-4.2.3
Week 6
Lecture 15
(Mon, Oct 28)
Normal Distribution
Central Limit Theorem
slides cc Reading: 4.3, 5.7
Midterm
(Wed, Oct 30)
Midterm
PSet5 Out
Section 6
(Thu, Oct 31)
Continuous RVs
materials solutions
Lecture 16
(Fri, Nov 1)
Application: Polling
slides cc Reading: 5.7
Week 7
Lecture 17
(Mon, Nov 4)
Continuity correction
Application: Distinct Elements
slides cc Reading: 5.7.4, 9.5
Lecture 18
(Wed, Nov 6)
Joint Distributions
slides cc
Reading: 5.1-5.3
PSet6 Out PSet5 Due
Section 7
(Thu, Nov 7)
Central Limit Theorem
Joint Distributions
materials solutions
Lecture 19
(Fri, Nov 8)
Joint Distributions
Tail Bounds: Markov's Inequality
slides cc Reading: 5.3-5.4, 6.1
Week 8
(Mon, Nov 11)
No Lecture: Veterans Day
Lecture 20
(Wed, Nov 13)
Chebyshev's Inequality
Chernoff Bounds
slides cc Reading: 6.1-6.2
PSet6 Due PSet7 Out
Section 8
(Thu, Nov 14)
Tail Bounds
materials solutions
Lecture 21
(Fri, Nov 15)
Chernoff Bound
Union Bound
slides cc Reading: 6.2, 6.3.1
Week 9
Lecture 22
(Mon, Nov 18)
Maximum Likelihood Estimation
slides cc Reading: 7.1-7.2
Lecture 23
(Wed, Nov 20)
Maximum Likelihood Estimation
continued
slides cc Reading: 7.1-7.2
PSet8 Out PSet7 Due
Section 9
(Thu, Nov 21)
MLE
materials solutions
Lecture 24
(Fri, Nov 22)
Markov Chains
slides cc Reading: 9.6
Week 10
Lecture 25
(Mon, Nov 25)
Markov Chains + PageRank
slides cc Reading: 9.6
(Wed, Nov 27)
No Lecture: Thanksgiving Holiday

PSet9 Out PSet8 Due
(Thu, Nov 28)
No Section: Thanksgiving Holiday
Markov Chain practice: materials solutions
(Fri, Nov 29)
No Lecture: Thanksgiving Holiday
Week 11
Lecture 26
(Mon, Dec 2)
Differential Privacy
slides Reading: Dwork-Roth book
Lecture 27
(Wed, Dec 4)
Information Theory
slides
Section 10
(Thu, Dec 5)
Review
materials solutions
Lecture 28
(Fri, Dec 6)
Informtion Theory & Victory Lap
slides slides PSet9 Due
Exam Week
Final Exam
(Mon, Dec 9)
The final exam is scheduled at 2:30-4:20 pm in our regular classroom (ARC 147).

This course website heavily follows the example of the website of CSE373 2019 Spring.