This course will cover the theory of computational complexity, with a focus on popular approximation and optimization problems and algorithms. It begins with 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 impact of emerging computing techniques, such as massive parallelism and quantum computing, will also be discussed. The course will specifically target algorithms with practical significance and techniques that can improve performance in real-world implementations.
Introductory probability theory and/or statistics (such as 625.403 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.