Week 1
Complexity review. Stable matching.
- Problem Set #1
- Due on paper by 9:40AM Friday, January 9.
- Reading: Preface, Section 1.1, and Sections 2.1-2.3 from Kleinberg & Tardos.
- Read 2.1-2.3 by Jan 7, and the rest by Jan 9.
Week 2
Stable matching. Graphs.
- Problem Set #2
- Due on paper by 9:40AM Friday, January 16.
- Reading: Chapters 3 and 4 from Kleinberg & Tardos.
- Read Chapter 3 by Jan 14, and Chapter 4 by Jan 19.
Week 3
Graphs. Greedy algorithms.
- Problem Set #3
- Due on paper by 9:40AM Friday, January 23.
- Reading: Chapters 3 and 4 from Kleinberg & Tardos.
- Didn't do this yet? Get to it.
Week 4
Divide-and-conquer.
- Problem Set #4
- Due on paper by 9:50AM Monday, February 2. Submit your
source code for the last problem to your hand-in folder.
- Reading: Sections 5.1-5.5 from Kleinberg & Tardos.
- Do this soon.
Week 5
Exam on Wednesday, Feb 4.
Week 6
Midterm break. A pile of miscellaneous algorithms.
- Reading: Section 6.4 (knapsacks) and pages 727-731
(randomized selection) from Kleinberg & Tardos.
Also, read this
Wikipedia article on selection algorithms.
- By Friday, Feb 13.
- Problem Set #5
- Due on paper by 9:50AM Wednesday, February 18. Submit your
source code for the first problem via HSP or directly to your hand-in folder.
Week 7
Computational geometry.
Week 8
Network flows
- Reading: Sections 7.1, 2, 3, 5, 9, and 10 from Kleinberg & Tardos.
- You'll want to read at least the first three sections by Monday,
Feb 23.
- Do problems 1, 2, 8, 9, 16, and 35 from Chapter 7.
- Due on paper by 9:40AM Friday, February 27.
Week 9
Intractability.
- Reading: Sections 8.1-3
- By early in the week
- Takehome exam
- Due on paper 9:40 AM Friday, March 6.
Finals Week
Wrap-up, and the takehome test.
- Reading: 8.4, 8.10, and others in Chapter 8 as needed.
- Soon
- Takehome exam
- Due 5:00 PM Monday, March 16.