Distinguished Professor Gabor T. Herman
Analysis of algorithms involves characterizing the amount of resources consumed by an algorithm, measured as a function of input length, and typically bounded in the worst case. The most common resources considered are running time and space used, but others may be considered as well, such as number of random bits used or number of blocks read from secondary storage. In algorithm design, we seek algorithms that have good worst-case resource requirements and other attractive qualities, such as optimality or approximation guarantees, good performance “in practice,” parallelizability, and simplicity.
This course covers the design and analysis of algorithms for a number of fundamental problems, such as sorting, order statistics, minimum spanning trees, shortest paths, matching, maximum flow, minimum cut, satisfiability, knapsack, set covering, and linear programming. Common algorithm design techniques will be emphasized, including greedy, divide-and-conquer, and dynamic programming, as well as formulating problems as linear programs and the use of randomness. Some efficient data structures will also be examined, primarily hash tables, but also heaps and binary search trees. Finally, we will briefly discuss the halting problem, NP-completeness, and reductions.
Implementation projects might be assigned, applying algorithms to real-world applications.
List of topics
The student should be able to:
Explain and analyze the performance guarantees (in terms of optimality and efficiency) of standard algorithms for sorting, minimum spanning trees, shortest paths, maximum flow, hashing, and knapsack
Understand and program divide-and-conquer algorithms and the use of search trees
Understand the principles of greedy algorithms and matroids
Know the mathematical definitions needed for the specification of minimum spanning trees and be able to analyze and program algorithms for finding such trees
Seek solutions to newly encountered problems by applying basic algorithm design techniques, such as divide-and-conquer, greedy, dynamic programming; and judge which approaches are most appropriate or promising for the problem at hand
Formulate problems as (possibly integer) linear programs
Investigate or make informed judgments about whether a given problem is likely to be NP-complete
The course grade will be determined by homework (and, possibly, in-class) problem sets (which may include programming) (65%) and a final exam (35%).
Introduction to Algorithms (latest edition); Cormen, Leiserson, Rivest, and Stein; MIT Press.
Algorithm Design (latest edition); Kleinberg and Tardos; Pearson.