TTH 2-320 TCH M128
Prof. Hai Zhou
haizhou AT northwestern DOT edu
L461 Tech Institute
Office Hours: T 330-5 or by appointment
Mr. Yuankai Chen
yuankaichen2014 AT u DOT northwestern DOT edu
L580 Tech Institute
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): bio
Homework 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 Turing
Week 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.