University of Chicago CSPP 55001 - General Information
CSPP 55001: Algorithms
Spring 2008
General Information
Goal
This course is an introduction to the design and analysis of efficient
algorithms. Topics include asymptotic notation, evaluation of recurrences,
and basic algorithm design techniques such as divide-and-conquer methods,
dynamic programming, greedy algorithms, and graph searching. Sorting and
searching algorithms are studied, as well as graph algorithms such as
graph search, minimal spanning trees, and shortest paths.
Prerequisites
Completion of CSPP 50102 or CSPP 50201 and 50202 or equivalent coursework in
discrete mathematics. There are no programming prerequisites.
Textbook
The required text is
Introduction to Algorithms
(Second Edition)
by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, available in
paperback (ISBN: 0262531968) and in
hardcover (ISBN: 0262032937).
Used copies of the text at reduced prices are listed at the sites:
paperback and
hardcover.
Be sure to get the second edition.
Syllabus
| week | Topics
|
| 1 | Analysis of sorting algorithms: insertion sort
and mergesort
|
| divide-and-conquer algorithms
|
| 2 | Quicksort
|
| randomized algorithms
|
| 3 | Heapsort
|
| binary trees
|
| 4 | Lower bound for comparison-based sorting
|
| Sorting in linear time
|
| 5 | Midterm examination
|
| Medians and order statistics
|
| 6 | Greedy algorithms
|
| 7 | Dynamic programming
|
| 8 | Graph searching algorithms:
|
| Breadth-first search and depth-first search
|
| 9 | Shortest-path algorithms:
|
| Dijkstra's algorithm
|
| 10 | Minimum spanning trees:
|
| Prim's algorithm
|
| 11 | Final examination
|
Note: The detailed structure of the syllabus may change, based on class progress.
Unless explicitly stated otherwise, homework assigned in one class will be
due at the beginning of the next one.
brady at cs dot uchicago dot edu