Catalog description:

A review of NP-Completeness and poly-time reductions; an introduction to randomized algorithms and the randomized complexity classes PP, RP, and BPP; an introduction to approximation algorithms for solving NP-Hard problems; polynomial-space algorithms and the classes PSPACE and the poly-time hierarchy; Poly-time approximation schemes and approximation algorithms via linear-program rounding.

Prerequisites:

An undergraduate algorithms course

Course Objectives:

• To recognize the most well-known NP-complete problems, and categories of NP-complete problems.
• To perform the most well-known poly-time reductions between NP-hard problems, and able to extend these proofs to similar problems.
• To be able to perform the most well-known poly-time reductions between NP-hard problems, and able to extend these proofs to similar problems.
• To understand the definitions of the complexity classes P, NP, co-NP, RP, PP, BPP, PSPACE, and the poly-time hierarchy, and be able to prove the relationships between them.
• To understand the purpose of approximation algorithms and polynomial-time approximation schemes, be able to derive the approximation factors for well-known examples, and adapt a poly-time approximation algorithm for one problem to another similar problem.
• To analyze the performance characteristics of randomized algorithms, and adapt a randomized algorithm for a canonical problem to work on another similar problem.