Lecture: Devorah Kletenik
Analysis of algorithms involves characterizing the amount of resources con-
sumed by an algorithm, measured as a function of input length, and typ-
ically 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,
2 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 ow, minimum cut, satisability,
knapsack, set covering, and linear programming. Common algorithm design
techniques will be emphasized, including greedy, divide-and-conquer, and dy-
namic programming, as well as formulating problems as linear programs and
the use of randomness. Some ecient data structures will also be examined,
primarily hash tables, but also heaps and binary search trees. Finally, we
will briey discuss the halting problem, NP-completeness, and reductions.
Implementation projects might be assigned, applying algorithms to real-
3 Topic List
Growth of Functions
- Asymptotic Notation
- Recurrence Equation
- Median and other Order Statistics
- Activity Selection
- Minimum Spanning Tree: Prim, Kruskal, Borvka
- Set Covering
- Page Rank
- Steepest Descent
- Longest Common Subsequence
- Independent Set
- Dijkstra Algorithm for Shortest Paths
- Binary Search Trees
- Hash Tables
- Disjoint Sets
- Bipartite Matching
- Maximum Flow and Minimum Cut
Linear Programming (and Integer Programming):
- Standard and Other Forms
Computability and Complexity:
- Halting Problem
- Polynomial Time
- Complexity Classes P and NP
4 Learning Goals
The student should be able to:
--Explain and analyze the performance guarantees (in terms of optimality
and eciency) of standard algorithms for sorting, minimum spanning
trees, shortest paths, maximum ow, hashing, and knapsack.
--Understand and program divide-and-conquer algorithms and the use of
--Understand the principles of greedy algorithms and matroids.
Know the mathematical denitions needed for the specication of min-
imum spanning trees and be able to analyze and program algorithms
for nding such trees.
--Seek solutions to newly encountered problems by applying basic algo-
rithm 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) problems (which may include programming): 65
- Final exam: 35
Introduction to Algorithms, (latest edition); Cormen, Leiserson, Rivest, and
Stein; MIT Press.
7 Reference Text
Algorithm Design (latest edition); Kleinberg and Tardos; Pearson.