University of Chicago CSPP 55001 - General Information
CSPP 55001: Algorithms
Autumn 2009
General Information
Goal
This course is an introduction to the design and analysis of efficient
algorithms. Topics include basic algorithm design techniques such as
divide-and-conquer methods, dynamic programming, greedy choice, 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 (Third Edition)
by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. The Third
Edition is available at
MIT Press and at
amazon.
The Second Edition is available at
amazon (ISBN: 0262032937). The course
will support both the Third and Second Editions of the textbook.
Lectures
The following schedule is tentative and subject to change.
| Week | Topics
|
| 1 | Analysis of algorithms: insertion sort & mergesort
|
| Divide & conquer; recurrences
|
| 2 | Randomized algorithms: quicksort
|
| Priority queues; heapsort
|
| 3 | Dynamic programming
|
| 4 | Medians and order statistics
|
| Hashing; binary search trees
|
| 5 | Midterm examination
|
|
|
| 6 |
Graph searching algorithms:
|
| Breadth-first search & Depth-first search
|
| 7 | Shortest-path algorithms:
|
| Dijkstra's algorithm and Bellman-Ford algorithm
|
| 8 | Minimum spanning tree algorithms:
|
| Prim's and Kruskal's algorithms
|
| 9 | NP completeness
|
| 10 | tba
|
| 11 | Final examination
|
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