Advanced Algorithms

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.