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

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.