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 www.abe.com
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
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