Explore approximation algorithms for NP-hard problems, online algorithms, approximation in P, and other subjects related to approximation algorithms and their limitations. Examine combinatorial algorithms, as well as algorithms based on linear programming and semidefinite programming. Identify the Probabilistically Checkable Proofs (PCP) Theorem, discuss its applications, and prove a weak version of it. Three lecture hours a week for one semester. Computer Science 388E and 395T (Topic: Approximtn Algorthms/Complexty) may not both be counted. Prerequisite: Graduate standing and knowledge of undergraduate-level algorithms and complexity.