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:
Homeworks:
- Solution
- Solution updated October 31, 2001
- Solution
Project Information: Full Information about the class project is available here.
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).
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