CMSC651

Efficiency of algorithms, orders of magnitude, recurrence relations, lower-bound techniques, time and space resources, NP-complete problems, polynomial hierarchies, and approximation algorithms. Sorting, searching, set manipulation, graph theory, matrix multiplication, fast Fourier transform, pattern matching, and integer and polynomial arithmetic.