TTH 2-320 TCH M128

Prof. Hai Zhou

haizhou AT northwestern DOT edu

L461 Tech Institute

(847) 491-4155

Office Hours: T 330-5 or by appointment

Mr. Yuankai Chen

yuankaichen2014 AT u DOT northwestern DOT edu

L580 Tech Institute

(847) 491-9925

Office Hours: F 10-12

This course will cover some advanced topics of algorithm design and analysis. From a history starting with Euclid, we will first discuss the three central tasks of algorithm design: correctness, termination, and efficiency. Focusing on algorithm design methods, we will discuss efficient algorithms for a sequence of interesting problems: minimal cycle ratios, maximal network flows, min-cost flows, convex cost flows, and generalized flows. Besides allowing students to understand those data structures and algorithms, a main goal of this course is to improve the problem solving abilities of the students. Therefore, if possible, we will study together how an efficient algorithm is designed.

EECS 336 or any undergraduate algorithms course.

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

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

Late policy: -40% per day

Homework 0 (out 9/27, due 10/2): bioHomework 1 (out 10/2, due 10/11): Stable marriage and shortest paths

Homework 2 (out 10/11, due 10/18): Shortest paths and cycle ratios

Homework 3 (out 10/23, due 10/30): Maximal Flows

Homework 4 (out 11/13, due 11/20): Min-Cost Flows

Week 1 Intro to algorithm design: when Euclid meets TuringWeek 2 Minimal cycle ratio algorithms: Lawler, Howard, Karp, and Burns, Experimental study

Week 3-4 Maximal flow algorithms: from Ford to Goldberg, and Orlin's recent O(mn) algorithm

Week 5-6 Min-cost flow algorithms: push-relabel, capacity-scaling, or cost-scaling

Week 7-8 Convex cost flow algorithms: convex optimization is not that hard

Week 9-10 Generalized flows and combinatorial optimization: limitations of worse-case analysis

Please check back often to this page (www.eecs.northwestern.edu/~haizhou/457) for updates and course material down-loading.