Course Number
CMPSC 230
Internal Course Number
230
Level
Graduate
Units
4
Faculty
Teofilo F. Gonzalez
Course Description

Prerequisite: Computer Science 130A-B.
Epsilon approximations, PTAS and FPTAS. Techniques for the design of approximation algrorithms. P, NP, NP-complete problems, polynomial transformations, Turing reductions, strong NP-completeness, NP-hardness and inapproximability results. Topics in algorithms include: amortized analysis, advanced graph algorithms and data structures.