CSC2421 Home Page (Spring 2005)

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. Please send any comments or questions to the instructor:

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 , David Shmoy's survey papers , Yuval Rabani's course notes and CSC2421 course notes from 2003 . The course meets Thursdays 1-3. The course is related to the highly recommended course CSC2411 Linear Programming and Combinatorial Optimization being taught by Avner Magen.

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%.

Problem Sets, Tests and Other Handouts will be posted here.
  • Problem set 1 in ps format
  • Problem set 1 continuation in ps format
  • Problem set 2 in ps format
  • Problem set 3 in ps format

    • 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