EECS 457 Advanced Algorithms

Time & Place

TTH 2-320 TCH M128

Instructor

Prof. Hai Zhou
haizhou AT northwestern DOT edu
L461 Tech Institute
(847) 491-4155
Office Hours: T 330-5 or by appointment

We have a TT

Mr. Yuankai Chen
yuankaichen2014 AT u DOT northwestern DOT edu
L580 Tech Institute
(847) 491-9925
Office Hours: F 10-12

Overview

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.

Prerequisites

EECS 336 or any undergraduate algorithms course.

Required Text

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

Policies

Grading: 40% Homework     30% Take-home exam     30% Final exam
Late policy: -40% per day

Homeworks

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

Lecture schedule

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.