CATALOG DESCRIPTION: Design and analysis of advanced algorithms: graph algorithms; maximal network flows; min-cost flow algorithms; convex cost flows.

REQUIRED TEXT: R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993

COURSE DIRECTOR: Hai Zhou

COURSE GOALS: This course will cover the theoretical aspects of algorithm design and analysis. Starting with a matching problem, we will first discuss the three central tasks of algorithm design: correctness, termination, and efficiency. Following a similar design process, we will design efficient algorithms for a sequence of problems: shortest paths, minimal cycle ratios, maximal network flows, min-cost flows, and convex cost flows. Besides allowing students to understand those data structures and algorithms, a main goal of this course is to improve the problem solving capabilities of the students. Therefore, if possible, we will study together how each efficient algorithm is designed.

PREREQUISITES BY COURSES: EECS 336 or any algorithms course

PREREQUISITES BY TOPICS: Data structures, Introduction to Algorithms.

DETAILED COURSE TOPICS:

Week 1 Intro to algorithm design: stable marriage

Week 2 Shortest path algorithms

Week 3 Minimal cycle ratio algorithms

Week 4-5 Maximal flow algorithms

Week 6-8 Min-cost flow algorithms

Week 9-10 Convex cost flow algorithms

COMPUTER USAGE: None.

HOMEWORK ASSIGNMENTS: Five problem sets and one take-home exam.

LABORATORY PROJECTS: None.

GRADES: 40% Homework     30% Take-home exam     30% Final exam