CS 252: Algorithms

Fall 2015

Help

Samples

Class Notes

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

• [By 9/23] Read sections 15.2, 15.3, and 15.4 of CLRS, 3rd edition
• [Due 8:30AM 9/28] Problem set 2: dynamic programming

Week 3

Greedy algorithms, shortest paths in graphs

• If you wish, read over my draft correctness proof and running time analysis for the unweighted interval scheduling problem. Have questions or suggestions for improving clarity/brevity/etc.? Bring them to class.
• [By 9/30] Read Chapter 16 introduction and sections 16.1 and 16.2 of CLRS, 3rd edition
• [By 10/2] Read Chapter 24 introduction and sections 24.1 and 24.3 of CLRS, 3rd edition
• [Due 8:30AM 10/5] Problem set 3: greedy algorithms and shortest paths

Week 4

Graph algorithms, recurrences

• [By 9/30] Read Chapter 23 introduction and sections 23.1, and 23.2 of CLRS, 3rd edition
• [By 9/30] Read Chapter 4 introduction and sections 4.3 and 4.5 of CLRS, 3rd edition
• [Due 8:30AM 10/12] Problem set 4: graph algorithm implementations and solving recurrences

Week 5

Midterm exam, starting divide-and-conquer

• [By 9/30] Read Chapter 23 introduction and sections 23.1, and 23.2 of CLRS, 3rd edition
• [By 9/30] Read Chapter 4 introduction and sections 4.3 and 4.5 of CLRS, 3rd edition
• [Due 8:30AM 10/12] Problem set 4: graph algorithm implementations and solving recurrences

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.

• [Due 8:30AM 11/2] Problem set 6: implement seam carving or LZW

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.

• [Due 8:30AM 11/16] Problem set 7: network flows
• [Due 5:00PM 11/23] Takehome exam