CSC2421 Home Page (Spring 2003)

This page provides general information and WWW access to various documents concerning csc2421. Many of these documents are electronic versions of handouts given in class. Announcements will also be made on this page. We are aware that the text has not arrived even though it was ordered in November. We are trying to expedite the matter and/or make zerox copies of some of the beginning chapters (if we get permission). There are a couple of used copies that were listed on

The the final grades are now available. The final assignment can be obtained from Professor rackoff.

Please send any comments or questions to the instructors:

This version of CSC2421 aims to be mainly a research oriented course on the topic of approximation algorithms for combinatorial optimization problems. The text is ``Approximation Algorithms'' by Vijay Vazirani. Another highly recommended sourse of material is the text ``Approximation Algorithms for NP-Hard Problems'' edited by Dorit Hochbaum. In addition, there are several good sets of lecture notes and surveys that you may want to consider. In particular, I recommend the notes that can be found on David Williamson's home page , Madhu Sudan's notes , and David Shmoy's survey papers . The course meets Tuesday 1-3.

It is expected that we will have students taking lecture notes and that the quality of these notes will be used as part of the grading scheme (25%). We also plan to have three assignments each worth 25%.

Here follows the tentative syllabus.


  • Syllabus
  • Problem sets
  • Problem Set 1
  • Problem Set 2
  • Problem Set 3
  • Here follows the class lecture notes.
  • Lecture 1
  • Lecture 2
  • Lecture 3
  • Lecture 4
  • Lecture 5
  • Lecture 6
  • Lecture 7
  • Lecture 8
  • Lecture 9
  • Lecture 10
  • Lecture 11
  • Lecture 12
  • Lecture 13