Lectures:    MWF    1:30—2:20  pm,    Room:    MC  4040

Instructor:    Ashwin Nayak,    anayak [at] math,    MC 4034,    x 33601

Teaching Assistants:

1. •David Roberson, droberson [at] uwaterloo,    DC 3144,    x 37814
   

2. •Cristiane Sato,  cmsato [at] gmail,    MC 6104C,    x 35320
   

Office hours:    A.N.    Fri  2:30—3:20 pm,    D.R.    Thu  12:10—1:10 pm,    C.S.    Thu  2:30—3:30 pm

Announcements

C.S. will hold extra office hours on Tuesday, Dec. 13, and Wednesday, Dec. 14, 2:30 to 3:30 pm.

Unclaimed assignments and midterm booklets are with C.S. Please collect them from her.

A.N.’s office hour on Friday, Dec. 9 is cancelled. He will have an office hour on Monday, Dec. 5, from 4—5 pm. You may send him email with your queries after that. Please allow a day for a response.

Past announcements may be found here.

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. We will follow roughly the following schedule (the section numbers refer to the course notes for the class):

1. •Sep. 12, 14, 16:    Shortest path problem (2.1, 2.1.2)
   

2. •Sep. 19, 21, 23:    LP formulation, Dijkstra algorithm (2.2.2, 2.2.3, 2.3), Quiz during Sep. 19 lecture
   

3. •Sep. 26, 28, 30:    Correctness and complexity of dual algorithm, DAGs (2.3, 2.3.1, 2.2.2, 2.4.1)
   

4. •Oct. 3, 5, 7:    PERT, Totally unimodularity, integer solutions, (2.4.2, 2.4.3)
   

5. •Oct. 12, 14:    Bellman-Ford algorithm (appendix A, additional notes), Thanksgiving holiday on Oct. 10
   

6. •Oct. 17, 19, 21:    Maximum flow problem, augmenting paths (3 (intro), 3.6.3, 3.1, 3.2)
   

7. •Oct. 24, 26, 28:    Max Flow-Min Cut, Ford-Fulkerson algo., Edmonds-Karp rule (3.2, 3.3, 3.3.1), Midterm on Oct. 26
   

8. •Oct. 31, Nov. 2, 4:    Maximum matching, Optimal closure, flow decomposition (3.6.3, 3.5.3, 3.6.1)
   

9. •Nov. 7, 9, 11:    More applications and flows, Min-cost flow: feasibility and applications (3.6.2, 3.5.1, 3.4, 4.1, 4.2)
   

10. •Nov. 14, 16, 18:    Applications continued, Cycle canceling algorithm (4.1, 4.3, 4.4.3)
    

11. •Nov. 21, 23, 25:    Flow decomposition revisited, Fattest negative dicycle rule (additional notes)
    

12. •Nov. 28, 30, Dec. 2:    Barahona-Tardos rule (additional notes)
    

13. •Dec. 5:    Minimum weight perfect matchings, the Hungarian algorithm (will not be tested in the final exam)
    

Text book

Network Flows: Course Notes for CO 351, Spring/Fall 2011

This book is available from the UW Media.doc location in MC 2018, and is also available in PDF format here for students in the course.  Here are some additional notes:

1. •The Bellman-Ford algorithm    [ pdf ]
   

2. •The cycle canceling algorithm    [ pdf ]
   

3. •The Barahona-Tardos Rule    [ pdf ]
   

These notes are not a substitute for the lectures. The lectures may present the material covered in the text in a different manner, or deviate from them 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

1. •Quiz:                4%
   

2. •Homework:    16%
   

3. •Midterm:        30%
   

4. •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 fall 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 five graded homework assignments in all. All of these will be counted towards your final mark in the course.

The homework will be based on the material covered from the previous Monday until the following Friday, and it will be due two weeks from the posting date, before 1:30 pm, in CS drop box no. 1, slot no. 13. The CS drop boxes are the bank of pink drop boxes on the 3rd floor of MC, across from the doors for the DC overpass. 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.

1. •Assignment 1, out Sep. 19, due Oct. 3, solutions
   

2. •Assignment 2, out Oct. 3, due Oct. 17, solutions
   

3. •Assignment 3, out Oct. 17, part I due Oct. 24, part II due Oct. 31, solutions
   

4. •Assignment 4, out Oct. 31, due Nov. 14, solutions, common errors
   

5. •Assignment 5, out Nov. 14, due Nov. 28, solutions
   

6. •Practice questions, not for submission
   

Office hours

We will make ourselves available to help you with the course one hour every week (listed at the top of this page). You are advised to see us during that time 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.

Avoidance of 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. The Office of Academic Integrity at the University of Waterloo maintains a website with a number of items of interest to students. In particular the pages on Academic Integrity for students provide various examples as well as a tutorial on the subject. For information on categories of offenses and types of penalties, students should refer to Policy #71, Student Discipline. Students who believe that they have been wrongfully or unjustly penalized have the right to grieve; refer to Policy #70, Student Petitions and Grievances, as well as Policy #72, Student Appeals.

Students that need special help are accommodated

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.

Exams

Information about the exams is posted here as it becomes available.

There was a quiz on Monday, Sep. 19, 1:50 pm to 2:20 pm (during the lecture). The quiz covered Chapter 1 from the course notes (basic graph theory) and basics of linear programming (formulation, dual, feasibility, existence of optimum, weak and strong duality, complementary slackness).    [ solutions ]    [ notes on grading ]

The midterm exam was on Wednesday, October 26, 5 pm to 7 pm, in MC 2017. The syllabus included everything we covered until October 14, 2011, i.e., until and including the Bellman-Ford algorithm. Also included were graph theory and linear programming basics.    [ solutions ]

The final exam is on Thursday, December 15, 7:30 pm to 10 pm, in MC 2034. Everything covered in class until December 2, 2011 is included in the syllabus. However, only 20% of the weight will be given to the material tested in the midterm.