Week 1
Start-up, review, and dynamic programming
- [By 9/16] Read the Course Information
- [By 9/16] Read the Asymptotics Overview and Data Structures Review documents posted on Moodle.
Bring questions to class on Wednesday.
(Note that all material written by David Liben-Nowell and used in this course will be posted on Moodle
instead of here.)
- [By 9/18] Read Chapter 15 introduction and section 15.1 of CLRS, 3rd edition
- [Due 8:30AM 9/21] Problem set 1: rod cutting, etc.
Week 2
Dynamic programming, greedy algorithms
Week 3
Greedy algorithms, shortest paths in graphs
Week 4
Graph algorithms, recurrences
Week 5
Midterm exam, starting divide-and-conquer
Week 6
Midterm break. "Magic 5" selection algorithm. Seam carving.
- [By 10/23] Read sections 9.0, 9.1, and 9.3 in CLRS on the Selection problem.
- [By 10/23] Read DLN's handout, Analysis of the “Magic Five” select algorithm. Posted on Moodle.
- [By 10/23] Read "Seam Carving for Content-Aware Image Resizing," by Shai Avidan and Ariel Shamir. I have
posted a copy on Moodle. It's also readily available by searching for its title, and via the
ACM Digital Library, for which Carleton has an institutional membership.
- You might find this seam-carving tutorial easier to get started with than the Avidan and Shamir article.
- [Due 9:00AM 10/27] Problem set 5: selection and more
Week 7
Seam carving, compression, stable marriage.
Week 8
Network flows, midterm takehome.
- [Due 8:30AM 11/9] Takehome exam
- [Sometime in the next week] Read sections 26.1-3 (flow networks, etc.) of CLRS.
Weeks 9, 10
Network flows, a little computational geometry, routing algorithms.