CAS CS330
Design and Analysis of Algorithms

Summer 2007 - Syllabus

Steve Homer

Room 281 MCS, 353-8927, homer@cs.bu.edu

Office Hours: After class each day for 1 hour, and by appointment

Teaching Assistant: Panagiotis Papapetrou

(panagpap@cs.bu.edu, telephone:353-5227, office: Room MCS 207)

Office Hours: TBA

Text: Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein

Recommended: Algorithmic Design by Kleinberg and Tardos

The most fundamental algorithms and most useful algorithmic methods in computer science will be studied. We will concentrate on learning the most important concepts used in constructing these algorithms and on analyzing their efficiency. Among the methods covered will be: Greedy algorithms, dynamic programming, recursion, graph algorithms, probabilistic algorithms, NP-completeness, and approximations of NP-hard problems. Among the topics covered will be: Network flow, minimum weight spanning trees, transitive closure, shortest paths through graphs, pattern matching, hashing, matrix operations, list processing, integer arithmetic, NP-complete problems and heuristic algorithms. To handle this material you need to know the mathematics covered in MA 293 or CS 113 and the data structures covered in CS 112. The material in MA 242 and MA 294 would also be helpful.

There will be about 5 problem sets, a midterm and a final. The course grade will be based on homework: 40%, midterm: 20% and final: 40%.

Points will be taken off for late homework and incompletes will not be given.