3.0

credits

Average Course Rating

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.