IE512: Course Information

Lecture

Lecture is on Tuesdays and Thursdays, 9:30pm-10:45am, 101 Transportation building.

Textbook and optional references

There is no existing text that perfectly matches the content of IE512. However, the following references contain useful additional details and insights.

• Kleinberg and Tardos, Algorithm Design

• Ahuja, Magnanti, and Orlin, Network Flows

• Lovasz, Pelikan, and Vesztergombi, Discrete Mathematics

• van Lint and Wilson, A Course in Combinatorics

You really won't need these books; we list them just in case you want to consult some other references.

Course requirements and grading

Requirements:

• Attendance.

• Homework assignments. There will be approximately 6 problem sets. Working through (and, yes, often struggling with at length!) the homework is a crucial part of the learning process and will invariably have a major impact on your understanding of the material. In understanding the problems sets, collaboration with your peers in small groups are allowed, even encouraged, but you must write up your own homework to hand in.

• Two exams: a midterm and a final. Dates will be announced later.

Grading

• Homework 30%, midterm 30%, final 40%. These weights are approximate; we reserve the right to change them later.

Prerequisites

The course is introductory but at a graduate level. It assumes mathematical maturity, which means that familiarity with elementary undergraduate mathematics and and a level of comfort with reading and writing proofs. An undergradudate course in algorithms is not a prerequisite, only familiarity with basics in linear algebra at the level of MATH415 or MATH 416 and knowledge of basic probability at the level of IE410, MATH461, or ECE534. Exposure to programming language (Matlab) is required.

Course description

In this course, we study algorithms for combinatorial optimization problems with focus on networked systems. These algorithms solve problems that arise in various practical scenarios, including airline companies scheduling their flights, large companies deciding what and where to stock in their warehouses, delivery companies choosing the routes, Google ranking search results, and Netflix choosing which movies to recommend.

We study general combinatorial problems on graphs, each modeling various practical problems of interest. We focus on general and powerful algorithmic techniques for each problem. We learn proof techniques to give guarantees on the quality of the solution found using these algorithms. We apply those algorithms in stylized examples, sometime using MATLAB.

Topics

• Cycles and Trees

• Network Flow

• Matching Problems

• Spectral Methods

• Linear Programming

• Online Algorithms

Other courses in algorithms

• CS473/MATH473. Fundamental Algorithms

• CS571/MATH580. Combinatorial Mathematics

• CS573. Graduate Algorithms

• CS574. Randomized Algorithms

• CS575/MATH584. Methods of Combinatorics

• CS583. Approximation Algorithms

• ECE526. Distributed Algorithms

• CS579/ECE579. Computational Complexity

• MATH412. Introduction to Graph Theory

Course objective

I hope you will enjoy the beauty of algorithms on graphs and networks discussed in this course.