University of Chicago CSPP 55001 - General Information
CSPP 55001: Algorithms
Autumn 2011
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 (ISBN 978-0-262-03384-8),
available at
MIT Press and at
amazon.
Recommended text: Algorithm Design by Jon Kleinberg and Eva Tardos, at
Addison-Wesley and
amazon.
Lectures
The following schedule is tentative and subject to change.
| Week | Topics
|
| 1 | Analysis of algorithms: insertion sort & mergesort
|
| Divide & conquer
|
| 2 | Randomized algorithms: quicksort
|
| Priority queues; heapsort
|
| 3 | Dynamic programming
|
| 4 | Medians and order statistics
|
|
|
| 5 | Graph searching:
|
| Breadth-first search & Depth-first search
|
| 6 | Midterm exam
|
| Greedy algorithms
|
| 7 | Shortest paths:
|
| Dijkstra's algorithm, Bellman-Ford, DAG shortest paths
|
| 8 | Minimum spanning trees:
|
| Prim's and Kruskal's algorithms
|
| 9 | NP complete problems:
|
| approximation algorithms
|
| 10 | Number-theoretic algorithms
|
|
|
| 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