SYST 420 / SYST 521
George Mason University
Instructor: Ursula Morris Class Room: Robinson Hall A 247
Class Time: Fr. 1:30 - 4:10 Office Hours: after class and by appointment
This course introduces network flow problems. These problems arise in many fields like computer networking, engineering, scheduling and routing, transportation, telecommunications. The course provides information about the theory, algorithms, and applications of network flow problems. The focus will be on shortest paths, maximum flow, minimum cost flow, and the network simplex algorithm.
The course begins with network nomenclature and elementary graph theory. This is followed by an introduction into data structures, complexity theory and flow decomposition. Based on these concepts shortest paths algorithms and the maximum flow algorithms are presented. A lecture on minimum spanning trees prepares for the following topics. A minimum cost network flow algorithm and a network simplex algorithm complete the basic topics of the course. As time permits, other topics might be added to the syllabus.
Text: Network Flows: Theory, Algorithms and Applications, by Ravindra K. Ahuja, Thomas L. Magnanti and James B. Orlin, published by Prentice Hall 1993.
Software: During the course, a software package called MPL will be used. A free student version can be obtained by going to http://www.maximalsoftware.com,, downloading the student version, and requesting an activation code asap.
Every student is expected to give two short presentation in class.
Course Topics (tentative)
|1||Introduction and Network Terminology|
|8||Shortest Path Algorithms|
|9||Max Flow Algorithms|
|11||Minimum Spanning Trees|
|12||Minimum Cost Network Flows|
Grading SYST 420: