Algorithms
Instructor
Distinguished Professor Gabor T. Herman
Rationale
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 worstcase resource requirements and other attractive qualities, such as optimality or approximation guarantees, good performance “in practice,” parallelizability, and simplicity.
Course description
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, divideandconquer, 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, NPcompleteness, and reductions.
Implementation projects might be assigned, applying algorithms to realworld applications.
List of topics
Learning Objectives
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 divideandconquer 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 divideandconquer, 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 NPcomplete
Assessment
The course grade will be determined by homework (and, possibly, inclass) problem sets (which may include programming) (65%) and a final exam (35%).
Textbook
Introduction to Algorithms (latest edition); Cormen, Leiserson, Rivest, and Stein; MIT Press.
References
Algorithm Design (latest edition); Kleinberg and Tardos; Pearson.