CS49/149: Approximation Algorithms, Spring 2017

Instructor: Deeparnab Chakrabarty (Office hours: Wed 3:30pm - 5pm, or by appointment @Sudikoff 216)
Time: 10A (TR: 10:10am - 12noon)
Venue: Sudikoff 214



Course Description
Many problems arising in computer science are NP-hard and we do not expect polynomial time algorithms solving them exactly. This has led to the study of approximation algorithms where one relaxes the goal to return approximate solutions. Over the past three decades, a beautiful theory of approximation algorithms has emerged. This course provides a broad overview of the main techniques in the area.

Background
A first course on algorithms and the ability to read and write mathematical proofs will be required. Prerequisite course: CS 31 or equivalent. Desirable: CS 30, CS 231.

Recommended Books
There is no required textbook but the following books are highly recommended.

Evaluation
Assignments (70%), Endterm or Project (30%)

Assignments

Tentative Schedule
Each week will be devoted to one or two techniques illustrated on a few problems.

Grading
There will be weekly assignments with 3-4 problems which will serve as a revision and reinforcement for the material covered in class. Students are highly encouraged to start early. Each point will be worth 7 points and we will follow Amit Chakrabarti's excellent and detailed grading policy.. Please refer to the "Working Together and Honor Priniciple" in the same page as well.