Modern computational applications often involve massive data sets. In this setting, it is crucial to employ asymptotically efficient algorithms. This course presents techniques for the design and analysis of polynomial-time algorithms. Unfortunately, many optimization problems that arise in practice are unlikely to be polynomial-time solvable. This course presents techniques for establishing evidence of such computational intractability, especially NP-hardness. Even if a given optimization problem is NP-hard, it may be possible to compute near-optimal solutions efficiently. This course presents techniques for the design and analysis of efficient approximation algorithms.
Topics include growth of functions, divide-and-conquer algorithms, dynamic programming, greedy algorithms, basic graph algorithms, network flow, minimum-cost matching, linear program-ming, randomized algorithms, data structures (hashing, amortized analysis, splay trees, union-find, and Fibonacci heaps), online algorithms for paging, P, NP, NP-completeness, and approximation algorithms.