# The Department of Electrical Engineering & Computer Science

## EECS 457 - Advanced Algorithms

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

If you see this button within a description, clicking it will take you to the Instructor's own page for this class.

### Computer Science course tags

 Select a category CS Core Course CS Project Course CS Depth-Theory CS Depth-Systems CS Depth-AI CS Depth-Interfaces CS Depth-Security CS Breadth-Theory CS Breadth-Systems CS Breadth-AI CS Breadth-Interfaces CS Breadth-Software Development

Robert R. McCormick School of Engineering and Applied Science
Electrical Engineering & Computer Science Home | McCormick Home | Northwestern Home
© 2013 Robert R. McCormick School of Engineering and Applied Science, Northwestern University