Lectures:
MWF
2:30 to 3:20 pm, Room:
MC 2035
Office hours: check
here
Lectures | Homework | Exams | Marks |
Announcement:
Dec. 21: The solutions to the final and the grade statistics have been posted on the exam and the mark pages, respectively. You may check your grade in the course on Quest.
If you wish to know your mark in the final exam, please email me. If you wish to look at your graded final exam, please make an appointment with me between January 17 and 30, 2008. After that, your exam will be available at the MUO.
Past announcements are available here.
Instructor:
Ashwin Nayak
Combinatorics and Optimization, U. Waterloo
and
Perimeter Institute for Theoretical Physics
Email:
anayak
[at] math
Office:
MC 4034
Phone extension:
33601
Teaching Assistant:
Irene Pivotto
, ipivotto
[at]
math.uwaterloo.ca,
DC 3145, x 37815
Combinatorics and Optimization, U. Waterloo
Outline
The course offers a comprehensive introduction to the theory and applications of network flows. In a network flow problem we wish to route traffic (cars, commodities, email, utilities, etc.) through a network subject to line capacities. Network flow problems can be viewed as linear programs, though we often require that the variables take integer values. We develop algorithms to solve these problems, and use linear programming duality to show that the algorithms terminate with an optimal solution.
The course is divided into roughly three equal parts: shortest path
problems, maximum flow problems, and minimum cost flow problem.
A weekly lecture schedule is available here.
Text book
Network Flows: Course Notes for CO 351, Fall 2007
This book is available from a university Graphics Department location such as MC 2018.
The text is not a substitute
for the lectures. The lectures may present the material covered in the
text in a different manner, or deviate from it entirely. You are
advised
to take your own notes in class.
Evaluation
The final mark in the course will be based on one quiz, homework, one midterm, and the final exam. The weight given to the different components is as follows
Quiz: | 4% |
Homework: | 16% |
Midterm: | 30% |
Final: | 50% |
Being regular in attending the lectures and completing
the homework will help you do well in the exams and the course as a whole.
If you are falling behind, you should seek help from your TA and
instructor
immediately. We will try our best to help you catch up.
Homework
There will be nine graded homework assignments in all. The best seven of these will be counted towards your final mark in the course.
There will be a homework assignment essentially every week, and will be posted on Mondays. The homework will be based on the material covered until that Monday, and it will be due on the following Friday, before 2:25 pm, in CS drop box no. 3, slot 7 in the North-East corner of MC on the third floor. Late submissions will not be accepted. Graded homework will be returned to you the next week.
You should be able to solve most of the problems in the homework on
your own if you have understood the lectures. However you can expect an
odd question that will require additional thought. You may consult your
TA or the instructor during their office hours about the homework.
You are also welcome to discuss the homework amongst yourselves.
However, you should write up the solutions on your own and
mention all sources of help. Solutions will be posted on the web after
the homework is collected.
Office hours
We will make ourselves available to help you with the course one
hour
every week (check here).
You are advised to see us during that time (or during the tutorial) if
you have any difficulty with the lectures, homework, or any other
aspect
of the course. Please use email only in special circumstances. We may
not
be able to answer all your email queries individually.
Note on Academic Offenses
Students are expected to know what
constitutes academic integrity, to avoid committing academic offenses,
and to take responsibility for their actions. Students who are unsure
whether an action constitutes an offense, or who need help in learning
how to avoid offenses (e.g., plagiarism, cheating) or about "rules" for
group work / collaboration should seek guidance from the course
professor, TA, academic advisor, or the Undergraduate Associate Dean.
For information on categories of offenses and types of penalties,
students should refer to Policy #71, Student
Academic Discipline.
Students who
believe that they have been wrongfully or unjustly penalized have the
right to grieve; refer to Policy #70,
Student
Grievance.
Note for students with disabilities
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.