ASSIGNMENTs are due at 11:59PM on the listed date. Submissions via Moodle. Note that problem sets will also have a check-in submission date on the Sunday before the overall due date.
Read/watch the READ/VIDEO items and do the TASK items before class on the date where they appear.
M Sep 12
- [TASK] Slack setup
- [READ] Course information. (No really, read this!) (No reading reaction required for this one, but you are welcome to post questions on Slack.)
- [READ] Preface from Kleinberg & Tardos (reading reaction tag #reading1)
- Class notes
W Sep 14
- [READ] Sections 2.1, 2.2, and 2.4 from Kleinberg & Tardos (#reading2)
- Class notes
F Sep 16
- I have posted a LaTeX resource page with a couple templates and a bunch of tutorial and reference links. You can get to this page via the "Resources" link in the top menu on this page.
- Our example from class today: source and pdf
- Class notes
M Sep 19
- [READ] Sections 1.1 and 2.3 of Kleinberg & Tardos (#reading3 by Tuesday night)
- Class notes
W Sep 21
- [ASSIGNMENT] Problem set #1 (here's the LaTeX source in case you're interested)
- Class notes
F Sep 23
- [READ] Section 3.1 of Kleinberg & Tardos (#reading4)
- Class notes
M Sep 26
- [READ] Sections 3.2 and 3.3 of Kleinberg & Tardos (#reading5)
- Class notes
W Sep 28
- [ASSIGNMENT] Problem set #2
- [READ] Section 3.6 of Kleinberg & Tardos (no reaction required) (LaTeX source)
- Class notes
F Sep 30
- [READ] Sections 1.2 (especially "Interval Scheduling") and 4.1, plus the Chapter 4 preamble. Kleinberg & Tardos (#reading6)
- Class notes
M Oct 3
W Oct 5
- [ASSIGNMENT] Problem set #3 (Here's the improved version I produced after our class discussions of problem 2.)
- Class notes
F Oct 7
- [EXAM] 1 hour, closed-book, closed-notes. We'll discuss this in class starting on Sep 30.
M Oct 10
- [READ] Section 4.2 of Kleinberg & Tardos (#reading7)
- Class notes
W Oct 12
- [READ] Sections 4.4 and 4.5 of Kleinberg & Tardos (#reading8)
F Oct 14
- [ASSIGNMENT 10/14] a little graph coding
- [INFO] Solutions for the big-O and Ω arguments in problem 1 of problem set 2, plus a debriefing on those kinds of arguments in general. PDF version or .tex version, as you wish.
- Class notes
M Oct 17
- Midterm break! Woohoo!
W Oct 19
- [READ] Sections 5.1 and 5.2 of Kleinberg & Tardos (#reading9)
- [ASSIGNMENT] There will be an assignment posted, due Oct 26, by Tuesday 10/18
F Oct 21
- [READ] Section 5.3 of Kleinberg & Tardos (#reading10)
- Class notes
M Oct 24
- [READ] Theorem 6.21 of David Liben-Nowell's Connecting Discrete Mathematics and Computer Science
W Oct 26
- [ASSIGNMENT] Problem set #4 (.tex file)
F Oct 28
- In-class exam
M Oct 31
- [READ] Sections 6.1 and 6.2 of Kleinberg & Tardos (#reading11)
- Class notes
W Nov 2
- [READ] Sections 6.3 and 6.4 of Kleinberg & Tardos (#reading12)
- Class notes
- [VIDEO] (22:09) Video on dynamic programming. At the moment, this is just a slightly slower version of the knapsack problem from today's class, but I'm planning to add a couple more problems to it tomorrow.
F Nov 4
- [SLIDES] Dynamic programming slides from today, with a few new annotations
M Nov 7
- [ASSIGNMENT 11/8] Problem set #5 (.tex file)
- the network flow example from class
- Class notes
W Nov 9
- [READ] Sections 7.1 and 7.2 of Kleinberg & Tardos (#reading13)
- Class notes
F Nov 11
- [EXAM] Takehome final, due 5:00PM Monday, November 21
- Class notes
M Nov 14
W Nov 16
F Nov 18
- [Th 11/17] Office hours 9:30-11:00
- [Fr 11/18] Office hours 9:30-12:00