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

Reading: 5.1-5.3
PSet6 Out PSet5 Due
Section 7
(Thu, Nov 7)
Central Limit Theorem
Joint Distributions
materials solutions
(Fri, Nov 8)
Joint Distributions
Tail Bounds: Markov's Inequality
Reading: 5.3-5.4, 6.1
Week 8
Lecture 19
(Mon, Nov 11)
No Lecture: Veterans Day
Lecture 20
(Wed, Nov 13)
Chebyshev's Inequality
Chernoff Bounds
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
Reading: 6.2, 6.3.1
Week 9
Lecture 22
(Mon, Nov 18)
Maximum Likelihood Estimation
Reading: 7.1-7.2
Lecture 23
(Wed, Nov 20)
Maximum Likelihood Estimation
continued
Reading: 7.1-7.2
PSet8 Out PSet7 Due
(Thu, Nov 21)
MLE
materials solutions
(Fri, Nov 22)
Markov Chains
Reading: 9.6
Week 10
Lecture 24
(Mon, Nov 25)
Markov Chains + PageRank
Reading: 9.6
Lecture 25
(Wed, Nov 27)
Differential Privacy
Reading: Dwork-Roth book
PSet9 Out PSet8 Due
Section 9
(Thu, Nov 28)
No Section: Thanksgiving Holiday
Lecture 26
(Fri, Nov 29)
No Lecture: Thanksgiving Holiday
Week 11
Lecture 27
(Mon, Dec 2)
Applications
Lecture 28
(Wed, Dec 4)
Applications
Section 10
(Thu, Dec 5)
Review
materials solutions
Lecture 29
(Fri, Dec 6)
Victory Lap & Review
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.