COMP 670J -- Fall  2001

Approximation Algorithms

Instructor -- M. J. Golin

T, Th 10:30-11:50-- Room 2407

Course Info


Course description and objective:   Most computer science researchers have given up on the possibility of finding techniques that always yield optimal solutions to NP-hard problems.

This still leaves us with the task of finding  `good' solutions to these problems.  The theory of approximation algorithms is devoted to developing techniques that yield provably good (`approximate') solutions to these problems.

In this course we will learn about the theory and practice of designing such algorithms.

Lecture Notes:



Project Information:   Full Information about the class project is available here.

The Project FAQ will be updated regularly with tips and answers to some of the
common questions being asked.  It is recommended that you check it every few days
or so to see what has been added.

The list of who is doing which project and which projects are fully subscribed can be found here.

Details on the I/O  specifications for each project can be found  here .

Here is a simple random number generating program using system calls.
It can be modified to help generate data for the projects (or you can use
any other random generator you find convenient).



Grade Database:   Updated list of Homework  and Project Grades

You can find the criteria used for project grading and final mark assignment   here

Please doublecheck your grades in the database.
If there are any questions send me email before Dec 31, 2001.
Final Office hours for asking questions and/or reviewing the project will be

  1. Monday,         Dec 31, 2001    10:30-11:30 AM
  2. Wednesday    Jan  2,   2002    10:30-11:30 AM