Computational Complexity and Approximation - 625.690

This course will cover the theory of computational complexity and popular approximation and optimization problems and algorithms. It begins with automata theory, languages, and computation followed by important complexity concepts including Turing machines, Karp and Turing reducibility, basic complexity classes, and the theory of NP-completeness. It then discusses the complexity of well-known approximation and optimization algorithms and introduces approximability properties, with special focus on approximation algorithm and heuristic design. The course will specifically target algorithms with practical significance and techniques that can improve performance in real-world implementations.

Course Prerequisite(s)

Introductory probability theory and/or statistics (such as EN.625.603 Statistical Methods and Data Analysis) and undergraduate-level exposure to algorithms and matrix algebra. Some familiarity with optimization and computing architectures is desirable but not necessary.