The subject is the design and analysis of efficient algorithms and the data structures supporting them. The algorithms will be stated in terms of mathematical models of computation and will be described in (often strikingly elegant) pseudocode. The analysis will consist of rigorous mathematical arguments; this is a proof-based class. The results of the analysis are mathematical theorems that estimate the running time or other resources used by the algorithm as a function of the length n of the input. The typical result is asymptotic as n → ∞. We shall also discuss the subject of computational intractability, rigorously formalized in the concept of NP-compleness.

The class will focus on a small number of algorithmic topics central to both the theory and the practice of computing (sorting in a variety of models, shortest paths, optimal spanning trees, fast multiplication and...