Description: Lecture, four hours; outside study, eight hours. Requisite: course 180. Background in discrete mathematics helpful. Theoretically sound techniques for dealing with NP-Hard problems. Inability to solve these problems efficiently means algorithmic techniques are based on approximation--finding solution that is near to best possible in efficient running time. Coverage of approximation techniques for number of different problems, with algorithm design techniques that include primal-dual method, linear program rounding, greedy algorithms, and local search. Letter grading.

Units: 4.0