Mommy, you know you have to be real good at coloring inside the lines when you are in college.

Elliot, 5 years old

Class Meetings

Lectures: Tue, Thu 9:30-10:45 MCS B23

Instructor: Peter Gács

Office Hours: Tuesday 2-3:30, Fri 2:-3:30 or by appointment.

Coordinates: gacs@bu.edu, MCS-277, 617-353-2015

Textbooks

Required: Cormen et al: Algorithms, third edition. MIT Press. ISBN-13: 978-0262033848
Recommended:

• Kleinberg-Tardos: Algorithm Design
• Gilber Strang: Introduction to Linear Algebra, Fourth Edition. Wellesley Cambridge Press, ISBN 0980232716.
• Carl D. Meyer: Matrix Analysis and Applied Linear Algebra. SIAM Press, ISBN 0-89871-454-0.

General description

The course treats advanced algorithm design and analysis ideas, demonstrated on mostly algebraic and optimization examples.
Some of the topics: Section 26 (Network flow), parts of Chapter VII (Selected Topics) of the textbook---in particular, matrix operations and linear programming.
Some material on handouts on the ellipsoid algorithm and convex programming. NP-completeness. Randomized algorithms. Approximation algorithms.

Prerequisites: an undergraduate course on linear algebra (like CS132), and an undergraduate course on the analysis of algorithms (like CS332, which has prerequisites CS112, CS131). Some topics assumed:

• Data structure and search concepts and techniques.
• Algorithm analysis concepts (rates of growth) and basic techniques (resolve a recursive inequality).
• Graph concepts and basic algorithms (like shortest path).
• Dynamic programming.
• Basic combinatorics, probability and linear algebra.
• NP-completeness (basic notion and examples).

If your preparation is missing some of these topics, you will need to invest more time in studying them on your own. If you are missing too many then you should take a lower-level course before this one.