syllabus

The lectures and animations on this web site will also are available on MIT’s Open Courseware site as of the fall 2004.
All material is subject to the terms of use and copyright given on the OCR website.

All lecture notes are intended to be viewed in Slide Show mode in Powerpoint. Much of the lecture material is animated.

Lecture	Topic	Animation	Readings in AMO
1	Introduction to network models.		1-22, 53-63
2	Computational complexity and data structures		23-38, 765-773
3	Graph search algorithms	Breadth First Search, Depth First Search, Topological Sort	38-47, 66-79
4	Transformations and flow decomposition	Flow Decomposition	79-86
5	Shortest paths: label setting algorithms	Dijkstra’s Algorithm Dial’s Algorithm	93-114
6	The radix heap algorithm	Radix Heap Algorithm	115-124
7	Shortest paths: label correcting algorithms	Label Correcting Algorithm, Modified Label Correcting	133-147, 149-150,154-157
8	Basic Algorithms for the Maximum Flow Problem	Augmenting Path Algorithm	166-187
9	Combinatorial applications of maximum flows	Shortest Augmenting Path Algorithm	188-198 and 207-223
10	Preflow push algorithms	Preflow Push Algorithm	223-237
11	More on preflow push algorithms		238-242
12	The global min cut algorithm	Global Min Cut Algorithm	Class Handout
13	Minimum cost flows: basic algorithms	Cycle Canceling	294-319
14	The successive shortest path algorithm	Successive Shortest Paths	320-326
15	The network simplex algorithm	Network Simplex	402-453
16	Minimum Cost spanning trees	Spanning Tree Algorithms	510-536
17	Review of linear programming		802-820
18	Generalized Flows		Generalized Flows	566-592
19	Lagrangian Relaxation 1		598-615
20	Lagrangian Relaxation 2		615-638
21	Multicommodity Flows 1		649-671
22	Multicommodity Flows 2		671-683
23	Very Large Scale Neighborhood Search		class handout