Basic information:
The class meets every weekday from 9:30-10:50am in CSIC 1122 between July 14 and August 8/22. The instructor is Tom DuBois . For detailed course information see the syllabus.
Welcome to CMSC 451.
Tuesday, August 19: There has been a slight modification in homework 5 (it is in red). The desired graph coloring approximation factor in some cases worked out to be less than 1 (which is impossible). I have changed it to be the max of 1 and the previously given expression.
Thursday, August 14: Homework 4 solutions are available.
Wednesday, August 13: Homework 5 is out today and due on Thursday, August 21.
Thursday, August 7: Homework 4 is out today and due on Thursday, August 14. I have made one change from the copy handed out in class, it is in red. Homework 3 solutions are also available. Tuesday, August 5: Midterm Today! Midterm solutions are here.
Class today (8/1/08) is cancelled. Sorry for the late notice. I suggest that you look at the subset sum section in the book as well as the longest common subsequence section from last spring's lecture notes. I will hold extra office hours monday for anyone who wants to hear the lecture (in groups or individually). Since longest common subsequence is related to the edit distance problem on the homework, and I meant to, but won't get around to covering that, I'm making that problem optional (but highly recommended).
Tuesday July 29: Homework 2 solutions are available, with the tex file as well.
Monday July 28: Homework 3 is released, it is due Monday, August 4.
Thursday July 24: Homework 2 is updated (all changes make it easier), a new file has been posted with updates in red.
Monday July 21: Homework 2 is released.
Tuesday July 15: Homework 1 is released, it is due Tuesday, July 22.