Class Meetings

Lectures: Mon, Wed 1-2:30 MCS B33

Instructor: Peter Gács

Office Hours: Mon 12-1, Fri 10:40-12:40 or by appointment.
Coordinates: gacs@bu.edu, MCS-277, 617-353-2015

Textbooks

Required:

Cormen et al: Algorithms, second edition. MIT Press. ISBN 0-262-03293-7.

Recommended:

Carl D. Meyer: Matrix Analysis and Applied Linear Algebra. SIAM Press, ISBN 0-89871-454-0. (Many students asked me for a good book on linear algebra. This is my recommendation.)

General description

Prerequisites: an undergraduate course on linear algebra, and an undergraduate course on the analysis of algorithms.

Advanced algorithm design and analysis ideas, demonstrated on mostly algebraic and optimization examples.
Topics: Parts of Chapter VII (Selected Topics) of the textbook on matrix operations and linear programming.
Some material on handouts on the ellipsoid algorithm and convex programming. NP-completeness. Approximation algorithms.