Course Description and Learning Objectives

Many problems arising in computer science are NP-hard and therefore we do not expect efficient algorithms for solving them exactly. This has led to the study of approximation algorithms where algorithms are supposed to run fast but can return approximate solutions. This course provides a broad overview of the main techniques involved in designing and analyzing such algorithms. It also explore connections between algorithms and mathematical fields such as algebra, geometry, and probability.

The learning objectives of the course are:

learn basic techniques of approximation algorithms and analysis techniques
learn new algorithmic paradigms
participate in a "research" project
grow in mathematical maturity

Prerequisites

A first course on algorithms (eg, CS31 at Dartmouth) and mathematical maturity to read and write proofs will be assumed. Knowledge of NP-completeness is recommended. If you can solve 75-80% of these Week 0 problems, then you are probably ready.

Logistics

Lectures: 10A hour (TR, 10:10-12), Cummings 200; X-hour (F, 3:30-420) may be used
Personnel
- Instructor: Deeparnab Chakrabarty (DeepC); OH: Fridays 4:30 - 5:30
- Graduate Teaching Assistant: Ankita Sarkar; OH: [coming soon]
Discussion: via Ed Discussion
Work Submission: via Gradescope
Textbook: There is no required textbook, but there are two excellent textbooks on the subject.
- Approximation Algorithms by Vijay V. Vazirani
- The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys
- Some lecture notes: https://www.cs.dartmouth.edu/~deepc/appx-lecture-notes.htm
Read this: Honor Code vis-a-vis CS 36/236

Evaluation

[The "percentages" are subject to change. Details of the above will be forthcoming hopefully before first day of classes]

Date	Lecture Topic	Relevant Exercise	Other Info
1 Apr (Tue)	Introduction
3 Apr (Thu)	Greedy Algorithms
8 Apr (Tue)	Local Search
10 Apr (Thu)	Approximation Schemes