-
Overview:
-
CO351 is an introductory course on Network Flows,
covering some of the theory, algorithms, and applications.
Networks are pervasive in everyday life:
road-networks connect cities,
electrical and phone networks connect homes,
social networks connect friends, etc.
The course focuses on optimization problems on networks.
A familiar example is the shortest paths problem:
What is the shortest route between cities A and B in a road-network?
Almost all of the problems of interest can be formulated
as linear programming problems (LPs);
moreover, these LPs have special properties
useful for designing algorithms
and for proving theoretical results.
Topics include:
Transshipment problems (TP).
Shortest path problems.
The max-flow min-cut theorem and applications.
Minimum cost flow problems.
Network simplex and primal-dual algorithms.
Applications in transportation, distribution, project planning, assignments, etc.
Prereq: (One of CO 250/350 or 352 or 355 or CM 340) and MATH 239 or
249. Not open to General Mathematics students.
-
Time & Place:
-
10:30-11:20 MWF MC4063
-
Office hours:
-
Instructor
R.Mittal DC 2116 phone x36531 Wed 1:30-3:00
(r3mittal@uwaterloo.ca)
Teaching Assistant:
M.Sharpe MC 6096 phone x36297 Fri 2:00-3:00
(sharpe.malcolm@gmail.com)
Network Flow Theory - C&O 351.
This book is available from the UW Media.doc location in MC 2018.
Final 50%
Midterm 30%
Assignments 20%
To pass the course, a pass in the final exam is required.
Please look up UW ACE for info on the Midterm Exam,
which is on Oct.20
(UW ACE)
The midterm exam is on June 20, Wednesday.
There is one session,
10:30-11:30 in MC 4040/MC 1056
Usually, it is much easier to explain math in person
rather than over email.
Students are welcome to ask questions in class, or just after class,
or during office hours.
Also, if necessary, students may ask instructor/TAs to schedule
meetings outside regular office hours. Send an email to instructor/TA to
fix an appointment.
Assignments will be posted on this website every 1-2 weeks.
All the assignments are REQUIRED (see the policy on INC requests, at
the bottom of this page).
Assignment solutions should be handed in at the start of class on the
due date.
There is a penalty on late submissions.
Acknowledge all outside help and collaboration in the submission
(no need to mention help from instructor/TA or from course material).
FGA (Frequently given answers)
- You have to turn in the assignment on the due date in class or before
class.
- You can give the assignment to the instructor in his office or slide it under his office door.
- You CAN'T email the assignment except in emergency.
The reputation of the University and the integrity of your degree rests
on the assumption that all work submitted is your own.
We encourage students to discuss the course material and
disseminate what they learn.
In this spirit, DISCUSSION related to the assignments
is acceptable and encouraged.
Please acknowledge all collaboration, discussions, and
sources in your submission,
EXCEPT for the course notes, lecture material, and
discussions with the course staff.
You are expected to write up the solutions on your own.
Copying or paraphrasing a solution from a
fellow student or old solutions qualifies as cheating.
In order to maintain a culture of academic integrity,
members of the University of Waterloo community are expected to
promote honesty, trust, fairness, respect and responsibility.
Read
page on academic integrity.
A student who believes that a decision affecting some aspect of his/her
university life has been unfair or unreasonable may have grounds
for initiating a grievance.
Read
Policy #70 Student Petitions and Grievances.
When in doubt please be certain to contact the department's
administrative assistant who will provide further assistance.
A student is expected to know what constitutes academic integrity
(read
page on academic integrity)
to avoid committing an academic offence, and to take responsibility
for his/her actions. A student who is unsure whether an action
constitutes an offence, or who needs help in learning how to avoid
offences (e.g., plagiarism, cheating) or about "rules" for group
work/collaboration should seek guidance from the course instructor,
academic advisor, or the undergraduate Associate Dean.
For information on categories of offences and types of penalties,
students should refer to
Policy #71, Student Academic Discipline.
For typical penalties, read
Guidelines for the Assessment of Penalties.
A decision made or penalty imposed under Policy 70
(Student Petitions and Grievances) or Policy 71 (Student Discipline)
may be appealed if there is a ground. A student who believes he/she has
a ground for an appeal should refer to
Policy 72, Student Appeals.
A grade of INC will be awarded only to students who cannot write the
final exam for "valid reasons" and who are in "good standing" prior to
the final exam. To be in "good standing" a student must have submitted
and passed ALL assignments, written and passed the midterm exam, and
have attended most of the lectures.
Students seeking an INC grade should discuss with the section
instructor. Documentation is required.
The Office for Persons with Disabilities (OPD), located in Needles
Hall, Room 1132, collaborates with all academic departments to arrange
appropriate accommodations for students with disabilities without
compromising the academic integrity of the curriculum. If you require
academic accommodations to lessen the impact of your disability,
please register with the OPD at the beginning of each academic term.
Before using exams from the past, please read
"What is an Exam?"
The university's
Counselling Services
has posted
Exam Preparation Tips.
The following website has exams from the past:
The MathSoc Online Exambank
Optional reading:
Chapters 19 and 20 of the book
`Linear Programming' by
V.Chvatal.
But be aware that Chvatal's notation differs
from that of CO351.
INFORMS OR/MS Resource Collection.
This is a page for pointers to ALL aspects of operations research and
the management sciences.
Lex Schrijver's web page has some notes on advanced material.
Michel Goeman's web page has some notes on advanced material.
R.K.Ahuja, T.L.Magnanti, and J.B.Orlin.
Network Flows: Theory, Algorithms and Applications.
Prentice-Hall, Englewood Cliffs, N.J., 1993.
Call no. T57.85 A37 1993
V.Chvatal,
Linear Programming,
W.H.Freeman and Company, New York, 1983.
Call No.T57.74.C54 1983
EMAIL: course_number AT student DOT math DOT uwaterloo DOT ca