CS 530

Spring 2007

Design and Analysis of Algorithms

Syllabus

Steven Homer (homer@cs)

Office: MCS 281

Phone: 353-8927

Office hours: Monday and Wednesday 11-12:30

Prerequisites: CS 330 or consent of instructor.

Text: Algorithms by Cormen, Rivest and Leiserson

CS530 is the graduate-level continuation of CS330. The course will cover some of the core topics already studied in CS330 (or in some equivalent course at another university), but with more details and rigor. In addition, we will present a selection of advanced topics and additional tools for analyzing algorithms.

The background material covered in CS 330 is assumed. That which is not known already can be learned without the instructor's help. This includes the basic algorithms concerning sorting and searching, recursion, NP completeness, and approximation and heuristic algorithms for NP problems, and graphs. It also includes the basic algorithm types such as exhaustive search algorithms, greedy algorithms, recursion, and dynamic programming. Also assumed is the background necessary to analyze the efficiency of these algorithms and basic discrete mathematics, probability and linear algebra. If this material is unfamiliar to you, you will have to spend some time doing background reading.

Some of the topics planned for the class this year include include the fast Fourier transform, linear programming and its generalizations, branch and bound, maximum flow, pattern matching and integer and matrix arithmetic. One advanced topic will be covered in depth during the last month of the course.

There will be about six homework assignments a midterm and a final exam. The grade will be determined by: homework 40%, midterm 20%, and final 40%. No incompletes will be given.