CSE 312: Foundations of Computing II, Winter 2024

Announcements and Updates

  • [1/1] Welcome to CSE 312! The below is a tentative schedule that is subject to change, make sure to check it for the most up-to-date plan for the course!
  • In the readings below "T" refers to the book by Alex Tsun and "H" refers to the book by Mor Harchol-Balter.
  • 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 3)
Introduction
So you think you can count?
slides annotated
T 1.1, 1.2 Berkeley 1
H 1.5
cc
Pset 1 out
Pset 1 PDF Pset 1 LaTeX Template
Section 1
(Thurs, Jan 4)
Counting Problems
slides
problems solutions
Lecture 2
(Fri, Jan 5)
More Counting
slides annotated
T 1.2, 1.3
cc
Week 2
Lecture 3
(Mon, Jan 8)
No More Counting Please!
slides annotated
T 1.3
cc
Lecture 4
(Wed, Jan 10)
Discrete Probability
slides annotated
T 2.1 H 2.1-2.2
Berkeley 2
Birthday Paradox
cc
Pset1 Due 11:59pm PDT
Pset2 Out
Pset 2 PDF Pset 2 LaTeX Template
Section 2
(Thurs, Jan 11)
Probability problems
slides
problems solutions
Lecture 5
(Fri, Jan 12)
Conditional Probability
Bayes Theorem
Law of Total Probability
slides annotated
T 2.2 H 2.3-2.6 Berkeley 3
cc
Week 3
Holiday
(Mon, Jan 15)
Martin Luther King Jr Holiday
Lecture 6
(Wed, Jan 17)
Independence
Chain Rule
slides annotated
T 2.2-2.3
cc
Pset2 Due 11:59pm PDT
Pset 3 Out
Pset 3 PDF Pset 3 LaTeX Template
Section 3
(Thurs, Jan 18)
Conditional probability, Bayes Thm
slides
9.3
problems solutions
Lecture 7
(Fri, Jan 19)
More independence
Intro Random Variables
slides annotated
T 3.1 Berkeley 4 H 3.1-3.2
cc
Week 4
Lecture 8
(Mon, Jan 22)
More Random Variables
Expectation
Intro Linearity of Expectation
slides annotated
T 3.2 H 4.1-4.2
cc
Lecture 9
(Wed, Jan 24)
More linearity of expectation
LOTUS
slides annotated
T 3.2.2
cc
  • Pset3 Due 11:59pm PDT
 Pset4 Out
Pset 4 PDF Pset 4 LaTeX Template
Section 4
(Thurs, Jan 25)
Random variables
slides
problems solutions
Lecture 10
(Fri, Jan 26)
Variance
Independence of R.V.s
slides annotated
T 3.3 Berkeley 5
cc
Week 5
Lecture 11
(Mon, Jan 29)
Independence of r.v.s
Zoo of Discrete RVs
slides annotated
T 3.4-3.5 H chap 3
Berkeley 4
cc
Lecture 12
(Wed, Jan 31)
Continue zoo: Geometric and Poisson
slides annotated
T 3.6 Berkeley 6
cc
  • Pset4 Due 11:59pm PDT
 Pset5 Out
Pset 5 PDF Pset 5 LaTeX Template
Section 5
(Thu, Feb 1)
The zoo
slides
problems solutions
Lecture 13
(Fri, Feb 2)
Finish Poisson
Application: Bloom Filters
slides annotated
T 9.4
cc
Week 6
Lecture 14
(Mon, Feb 5)
Finish Bloom Filters
slides annotated
NO cc
Lecture 15
(Wed, Feb 7)
Continuous random variables
slides annotated
T 4.1-4.3 H 7.1-7.3
Berkeley 7
cc
  • Pset5 Due 11:59pm PDT
Section 6
(Thurs, Feb 8)
Continuous random variables
slides
problems tablet version
solutions
Lecture 16
(Fri, Feb 9)
Review for midterm
slides annotated
cc (due Feb 14)
  • Pset5 Task 7 Due 11:59pm PDT
Week 7
Lecture 17
(Mon, Feb 12)
Midterm
Lecture 18
(Wed, Feb 14)
Normal distribution
Central Limit Theorem
slides annotated
T 4.3, 5.7.4 H chap 9
Berkeley 7- Secs 3-5
cc
Pset6 Out
Pset 6 PDF Pset 6 LaTeX Template
Section 7
(Thurs, Feb 15)
Normal distn, Continuity correction, CLT
slides 5.7.4
problems tablet version
solutions
Lecture 19
(Fri, Feb 16)
Application: Polling
Intro to Confidence Intervals
slides annotated
Polling 5.7.4, 8.1
cc
Week 8
Holiday
(Mon, Feb 19)
President's Day Holiday
Lecture 20
(Wed, Feb 21)
Joint distributions
slides annotated
T 5.1-5.2
H Sect 3.3
H Chap 8
cc
  • Pset6 Due 11:59pm PDT
 Pset 7 out
Pset 7 PDF Pset 7 LaTeX Template

Section 8
(Thu, Feb 22)
CLT and joint distributions
slides
problems solutions
Lecture 21
(Fri, Feb 23)
Conditional Expectation
Law of Total Expectation
slides annotated
MIT notes
5.3.3
H 4.3-4.4 H 7.3-7.5
cc
Week 9
Lecture 22
(Mon, Feb 26)
Maximum Likelihood Estimation
slides annotated
T 7.1-7.2, 7.6.1, 7.7.1
H 16.1-16.2
cc
Lecture 23
(Wed, Feb 28)
Finish MLE
Distinct Elements and the MinHash Algorithm
slides annotated
T. 9.5
cc
  • Pset7 Due 11:59pm PDT
 Pset 8 out
Pset 8 PDF Pset 8 LaTeX Template

Section 9
(Thurs, Feb 29)
Law of Total Expectation, MLE
slides
problems solutions
Lecture 24
(Fri, Mar 1)
Markov chains
slides annotated
H chap 24
9.6 Berkeley 8
cc
Week 10
Lecture 25
(Mon, Mar 4)
Pagerank + A glimpse of auction theory
slides annotated
Chap 14
NO more concept checks
Lecture 26
(Wed, Mar 6)
Finale
slides
  • Pset8 Due 11:59pm PDT
Section 10
(Thurs, Mar 7)
Practice for final
slides
problems solutions
Lecture 27
(Fri, Mar 8)
Victory lap!
  • Pset8 Task 9 Due 11:59pm PDT
Finals Week
Our final is scheduled for Monday, March 11, from 2:30pm - 4:20pm

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