Network Optimization
Lecture Notes
|
SES # |
TOPICS |
PDF SLIDES |
PPT SLIDES |
|
1 |
Introduction to network models |
(PDF) |
(PPT) |
|
2 |
Computational complexity and data structures |
(PDF) |
|
|
3 |
Graph search algorithms |
(PDF) |
(PPT) |
|
4 |
Transformations and flow decomposition |
(PDF) |
(PPT) |
|
5 |
Shortest paths: label setting algorithms |
(PDF) |
|
|
6 |
The radix heap algorithm |
(PDF) |
(PPT) |
|
7 |
Shortest paths: label correcting algorithms |
(PDF) |
(PPT) |
|
8 |
Algorithm analysis |
(PDF) |
(PPT) |
|
9 |
Basic algorithms for the maximum flow problem |
(PDF) |
|
|
10 |
Midterm 1 (Ses #1-8) |
|
|
|
11 |
Combinatorial applications of maximum flows |
(PDF) |
(PPT) |
|
12 |
Preflow push algorithms |
(PDF) |
(PPT) |
|
13 |
More on preflow push algorithms |
(PDF) |
|
|
14 |
Minimum cost flow: basic algorithms |
(PDF) |
(PPT) |
|
15 |
Minimum cost flow: polynomial time algorithms |
(PDF) |
(PPT) |
|
16 |
Applications of network flows; Linear programming review |
(PDF) |
|
|
17 |
The network simplex algorithm |
(PDF) |
|
|
18 |
NP-completeness |
|
|
|
19 |
Midterm 2 (Ses #9-17) |
|
|
|
20 |
Lagrangian relaxation 1 |
(PDF) |
|
|
21 |
Lagrangian relaxation 2 |
(PDF) |
|
|
22 |
Multicommodity flows 1 |
(PDF) |
(PPT) |
|
23 |
Multicommodity flows 2 |
(PDF) |
(PPT) |
|
24 |
Presentations of class projects |
|
|
|
25 |
Presentations of class projects (cont.) |
|
|
Assignments
|
ASSIGNMENTS |
|
Problem set 1 (PDF) |
|
Problem set 2 (PDF) |
|
Problem set 3 (PDF) |
|
Problem set 4 (PDF) |
|
Problem set 5 (PDF) |
Exams
A selection of exam practice problems are available for Midterm 2. These problems were used for exam preparation in a review session and at home.
|
EXAM MATERIALS |
|
Midterm 2 review problems (PDF) |
|
Midterm 2 practice problems (PDF) |
Animations
Animations are available to illustrate and clarify many of the topics covered in the lecture notes for this course. We recommend you view the Microsoft® PowerPoint® (PPT) versions, if possible, because they include motion.
|
SES # |
TOPICS |
PDFS |
SLIDES |
|
3 |
Breadth first search Depth first search Topological ordering |
(PDF) (PDF) (PDF) |
(PPT) |
|
4 |
Eulerian cycles in directed graphs Flow decomposition |
(PDF) (PDF) |
(PPT) (PPT) |
|
5 |
Dijkstra's algorithm |
(PDF) |
(PPT) |
|
6 |
Dial's algorithm 2-level bucket algorithm Radix heap animation |
(PDF) (PDF) (PDF) |
(PPT) (PPT) |
|
7 |
Label correcting algorithm Modified label correcting algorithm |
(PDF) (PDF) |
(PPT) (PPT) |
|
9 |
Ford-Fulkerson algorithm |
(PDF) |
(PPT) |
|
11 |
Preflow push algorithm |
(PDF) |
|
|
13 |
Negative cycle (cycle canceling) algorithm |
(PDF) |
(PPT) |
|
14 |
Successive shortest path (SSP) algorithm |
(PDF) |
(PPT) |
|
16 |
Network simplex animations |
(PDF) |