COSC 236 Approximation Algorithms

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 explores connections between algorithms and mathematical fields such as algebra, geometry, and probability.

Instructor

Chakrabarty

Prerequisite

A first course on algorithms and mathematical maturity to read and write proofs will be assumed. Prerequisite Courses: COSC 31, COSC 30.