CSE 312: Foundations of Computing II, Winter 2023

Announcements and Updates

  • Huge thanks to all prior instructors of this course at UW, the staff of Berkeley CS 70, Mor Harchol-Balter and Ryan O'Donnell. I have borrowed ideas, problems, and presentation ideas from all of the above.

Schedule

Week 1
Topic
Materials
Assignments
Week 1
Lecture 1
(Wed, Jan 4)
Introduction
So you think you can count?
slides annotated
1.1, 1.2 Berkeley 1
cc solns
Pset 1 out
Pset 1 PDF Pset 1 LaTeX Template
Section 1
(Thurs, Jan 5)
Counting Problems
slides
problems solutions
Lecture 2
(Fri, Jan 6)
More Counting
slides annotated
1.2, 1.3
cc
Week 2
Lecture 3
(Mon, Jan 9)
No More Counting Please!
slides annotated
1.3
cc
Lecture 4
(Wed, Jan 11)
Discrete Probability
slides annotated
2.1 Berkeley 2
Birthday Paradox
cc
Pset1 Due 11:59pm PDT
Pset2 Out
Pset 2 PDF Pset 2 LaTeX Template
Section 2
(Thurs, Jan 12)
Probability problems
slides
problems solutions
Lecture 5
(Fri, Jan 13)
Conditional Probability
Bayes Theorem
Law of Total Probability
slides annotated
2.2 Berkeley 3
cc
Week 3
Holiday
(Mon, Jan 16)
Martin Luther King Jr Holiday
Lecture 6
(Wed, Jan 18)
Independence
Chain Rule
slides annotated
2.2 2.3
cc
Pset2 Due 11:59pm PDT
Pset 3 Out
Pset 3 PDF Pset 3 LaTeX Template
Section 3
(Thurs, Jan 19)
Naive Bayes Classifier
slides
9.3
problems solutions
Lecture 7
(Fri, Jan 20)
More independence
Intro Random Variables
slides annotated
3.1 Berkeley 4
NO cc
Week 4
Lecture 8
(Mon, Jan 23)
More Random Variables
Expectation
Intro Linearity of Expectation
slides annotated
3.2
cc
Lecture 9
(Wed, Jan 25)
More linearity of expectation
LOTUS
slides annotated
3.2.2
cc
  • Pset3 Due 11:59pm PDT
 Pset4 Out
Pset 4 PDF Pset 4 LaTeX Template
Section 4
(Thurs, Jan 26)
Random variables
slides
problems solutions
Lecture 10
(Fri, Jan 27)
Variance
Independence of R.V.s
slides annotated
3.3 Berkeley 5
cc
Week 5
Lecture 11
(Mon, Jan 30)
More Independence of r.v.s
Application: Bloom Filters
slides annotated
3.4.1 9.4
cc
Lecture 12
(Wed, Feb 1)
Zoo of Discrete RVs
slides annotated
3.4-3.5 Berkeley 6
cc
  • Pset4 Due 11:59pm PDT
 Pset5 Out
Pset 5 PDF Pset 5 LaTeX Template
Section 5
(Thu, Feb 2)
The zoo
slides
problems solutions
Lecture 13
(Fri, Feb 3)
Poisson R.V.s
slides annotated
3.6
cc
Week 6
Lecture 14
(Mon, Feb 6)
Continuous R.V.s
slides annotated
4.1-4.2 Berkeley 7
cc
Lecture 15
(Wed, Feb 8)
Exponential and Intro to Normal R.V.s
slides annotated
4.2-4.3
cc
Section 6
(Thurs, Feb 9)
Continuous random variables
slides
problems solutions
Lecture 16
(Fri, Feb 10)
Review for midterm
annotated
NO cc
Week 7
Lecture 17
(Mon, Feb 13)
Midterm
Lecture 18
(Wed, Feb 15)
Normal distributions
Central Limit Theorem
slides annotated
4.3,5.7.3
cc
  • Pset5 Due 11:59pm PDT
 Pset6 Out
Pset 6 PDF Pset 6 LaTeX Template
Section 7
(Thurs, Feb 16)
Normal distns, Continuity correction, CLT
slides
5.7.4
problems solutions
Lecture 19
(Fri, Feb 17)
Application: Polling
Intro to Confidence Intervals
slides annotated
Polling 5.7.4, 8.1
cc
Week 8
Holiday
(Mon, Feb 20)
President's Day Holiday
Lecture 20
(Wed, Feb 22)
Joint distributions
Recap polling
slides annotated
5.1-5.2
cc
  • Pset6 Due 11:59pm PDT
 Pset 7 out
Pset 7 PDF Pset 7 LaTeX Template

Section 8
(Thu, Feb 23)
Joint distns
slides
problems solutions
Lecture 21
(Fri, Feb 24)
Conditional Expectation
Law of Total Expectation
slides annotated
MIT notes 5.3.3
cc
Week 9
Lecture 22
(Mon, Feb 27)
Distinct Elements and the MinHash Algorithm
slides annotated
9.5
cc
Lecture 23
(Wed, Mar 1)
Maximum Likelihood Estimation
slides annotated
7.1-7.2, 7.6.1, 7.7.1
cc
  • Pset7 Due 11:59pm PDT
 Pset 8 out
Pset 8 PDF Pset 8 LaTeX Template
Pset 8 Extra Credit LaTeX Template

Section 9
(Thurs, Mar 2)
Law of Total Expectation, MLE
slides
problems solutions
Lecture 24
(Fri, Mar 3)
Finish MLE, Markov chains
slides annotated
9.6 Berkeley 8
cc
Week 10
Lecture 25
(Mon, Mar 6)
Finish Markov chains + applications
slides annotated
NO more concept checks
Lecture 26
(Wed, Mar 8)
A glimpse of auction theory
See 3/6
Chap 14
  • Pset8 Due 11:59pm PDT
Section 10
(Thurs, Mar 9)
Practice for final
problems solutions
Lecture 27
(Fri, Mar 10)
Victory lap!
slides annotated
(Sat, Mar 11)
  • Extra Credit (MCMC for Knapsack) Due 11:59pm PDT
Finals Week
Our final is scheduled for Wednesday, March 15, from 8:30am - 10:20am

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