University of Chicago CSPP 55001—General Information
CSPP 55001: Algorithms
Autumn 2013
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 50103 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.
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, order
statistics
|
| Priority queues; heapsort
|
|
|
| 3 | Dynamic programming
|
| 4 | Dynamic programming
|
| Greedy algorithms
|
| 5 | Graph searching:
|
| Breadth-first search
|
| 6 | Midterm exam
|
| Hashing
|
| 7 | Graph searching:
|
| Depth-first search
|
| 8 | Shortest paths:
|
| Dijkstra's algorithm; Bellman-Ford algorithm
|
| 9 | Minimum spanning trees:
|
| Prim's and Kruskal's algorithms
|
| 10 | NP-complete problems
|
|
|
| 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