University of Chicago CSPP 55005 - General Information

CSPP 55005: Advanced Algorithms
Winter 2010
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

algorithms for all-pairs shortest paths

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

linear programming, the simplex algorithm, and duality

arithmetic and RSA

polynomials and the Fast Fourier transform

NP-complete problems and reductions

approximation algorithms and local search

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

Course requirements

There will be weekly homework assignments and two in-class written examinations. Homework will count for 1/3 of the course grade, and each examination will count for 1/3 of the total grade. 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.

Algorithms by Dasgupta et al. (ISBN: 9780073523408). Used copies of this book are listed at the following site: DPV