Math 466/566 -- Network Optimization (Fall 2008)
Course Description
| Network flow problems is an important class of optimization problems, with applications to several areas including chemistry, computer networking, engineering, public policy, scheduling, telecommunications, transportation, and many others. This course will provide an integrated view of the theory, algorithms, and the applications of key network optimization problems including the shortest path problem, the maximum flow problem, the minimum cost flow problem, the minimum spanning tree problem, and the multi-commodity flow problem. Most of the arguments will be presented from first principles, and we will adopt a network or graphical view point. Limited use of a linear programming approach will be involved, for which the necessary background materials will be reviewed. The only pre-requirement is mathematical intuition! Emphasis will be on powerful algorithm strategies, rigorous analysis of the algorithms, and data structures for their implementation. Apart from problems involving proofs (in homework and exams), the student will produce simple implementations of some of the algorithms (using MATLAB). Animations of algorithms will also be presented in order to help the student in gaining a sound intuition about them. Depending on student interest, we will discuss topics from combinatorial optimization as well. |
Syllabus
Tentative Course Schedule
Errors and typos in the AMO book
Announcements
| Wednesday, Nov 5: | There will be a make-up class this Monday, Nov 10, at 4:10 pm (till 5:25 pm) in the usual room (Webster 11). |
| Thursday, Nov 13: | The project is now due on Tuesday, Nov 18. |
| Thursday, Nov 13: | Scores have been posted against your PassNumbers. Contact me if you do not know your PassNumber. |
| Wednesday, Nov 26: | Hw10 has been posted. Its due on the Thursday after the break (Dec 4). |
| Thursday, Dec 11: | The final exam is posted. Due on the Tuesday, Dec 16, by noon. |
| Wednesday, Dec 17: | Solutions to the final, scores for the course, and grades are posted. |
Handouts
Homeworks
Exams
Project
MATLAB Codes
Software
MATLAB
Tutorial from Mathworks page
Another
guide to MATLAB from UBC CS.
GIDEN