Crtedit points: 2.0
Approximation algorithms offer a robust way to cope with NP-hard problems arising in many areas of computer science and beyond. In addition to being directly useful in applications, approximation algorithms allow us to explore the structure of intractable problems and distinguish between the different levels of difficulty these problems exhibit in theory and practice. The course will cover a mix of basic and advanced topics through a range of problems.
Grading Policy:
We will post three home assignments. HW1 should be submitted in pairs and will be 15% of the final grade. HW2 and HW3 are not for submission.
There will be two 2-hour quizzes:
- Quiz 1: 45–85% of the final grade, depending on whether the MAGEN applies. The quiz will be based on HW2 and the related lecture material (more details in class).
- Quiz 2: 40% MAGEN of the final grade. The quiz will be based on HW3 and the related lecture material (more details in class).