CSE 522, Autumn 2009: Approximation Algorithms

Expectations

This is a graduate course, so my primary expectation is that you will attend class, ask questions, and generally help create an engaging, educational and fun experience in the classroom.

In addition, each student will be expected to do the following:

• Scribe one lecture.
• Provide written feedback and comments for the authors on one section of the Williamson/Shmoys book each week. These comments should include typos, suggestions for places where the exposition could be improved, pointers to writing that is difficult to understand, etc. These are due on Mondays, starting October 12 (email your comments to Anna).
• Each student will do a 45 minute presentation during the last two weeks of the quarter. More details forthcoming, but, roughly speaking, two types of presentations are possible:
  • A presentation on some section(s) of the book that I didn't cover in class.
  • A presentation of your thoughts on an open problem in approximation algorithms. The presentation should include an overview of what's known about the problem and then a discussion of your insights about the problem, approaches to the problem, why they are likely or unlikely to work, and the stumbling blocks. I will be posting some ideas for this type of project soon.

For your own edification, I also recommend that you try some problems from the Williamson/Shmoys book, but I will not be grading them.