Introduction: data structures, algorithms, correctness criteria, non-existence result. Complexity classes – L, NL, P, NP, PSPACE, EXPTIME, EXPSPACE, DECIDABLE, UNDECIDABLE. The class P, and examples of analysis of worst- and expected-case efficiency. Optimization vs. decision problems, the class NP, Cooke and Karp reductions, the polynomial hierarchy. Recognizing optimal substructure, dynamic programming, when not to be naive. Reconciling NP- completeness – NP as an upper-bound, reduction to SAT and SAT solvers. Reconciling PSPACE- completeness – model checking, PSPACE as an upper-bound. The class of counting problems in NP, #P. Approximation algorithms for NP-complete problems – gap preserving reductions.