University of Chicago CSPP 55005 - General Information

CSPP 55005: Advanced Algorithms
Winter 2011
General Information

Course description

This course is a sequel to CSPP 55001, an introductory course on the design and analysis of efficient algorithms. This course introduces students to advanced techniques for designing and analyzing algorithms, and explores their use in a variety of problem areas. Emphasis is placed on fundamental algorithms and techniques of algorithm design.

Tentative list of topics

all-pairs shortest paths algorithms

network flow, max-flow problem, and min-cut/max-flow theorem

linear programming, the simplex algorithm, and duality

hashing

randomly built binary search trees; balanced binary search trees

NP-complete problems and approximation algorithms

parallel algorithms

online algorithms

Note: The instructors may change the list of topics based on class interest.

Course requirements

There will be weekly homework assignments and an in-class presentation. Presentation topics must be approved by the instructors. Unless explicitly stated otherwise, homework assigned in one class will be due at the beginning of the next class.

Prerequisites

Completion of CSPP 55001 with a grade of B+ or better. There are no programming prerequisites.

Text

Introduction to Algorithms (Third Edition) by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (ISBN: 0-262-03384-4). The Third Edition is available at MIT Press and at amazon. Be sure to get the third edition.