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
