COMP 251 Winter 2012
this page once a
items at the top of the page.
course home page lecture summaries
It took McGill admin 36 hours, but finally the grades have
been rolled over to webCT.
The median course grade was B+.
A special thanks to the 41 of you who completed the course
evaluation. The comments are particularly useful to me.
I was especially heartened that only 3 respondents disagreed with
the statement: "Overall I have learned a great deal from this
Have a good summer!
Exam FAQ (based on questions in student emails)
New: 0. When will the grades be posted?
Hopefully I will be uploading the grades to minerva by noon on
1. Is doing the slides and re-doing
the assignments sufficient for the final ?
This is a good start, but it is also very useful to read the
sections in the text given on the lecture summaries page. The text
has much fuller explanations and often uses another approach, all of
which will help you to better understand the material. Also do not
forget to review the midterm solutions.
2. Are we expected
to write complete algorithms in the finals or just have an
understanding of how an algorithm works and tackles the problems
that we have ?
Yes, you are supposed to be able to write out in pseudocode the
algorithms covered in the material on the lecture summaries page and
assignments. If you really do understand how an algorithm works this
should not require memorizing it from the text or slides.
3. Is the final going to
be in the same format as the midterm , as in multiple short
Yes, it will be in the same format but roughly twice as long.
4. Will the focus be more
on the material after the midterm or it will it be roughly evenly
The questions will be roughly evenly distributed over all of the
5. Looking at the lecture
summaries online, does this mean our exam will cover chapter 1 -7
of our textbook?
Not all of this material was covered, and a few topics are covered
in the slides that are not in the text. The precise sections of the
book to study are as given in the lecture summaries.
New: 6. Will we have to do proofs on the
While you will not be asked to do formal proofs, you will be asked
to justify your answers. To do this it is very important to
understand the results proved in class and in the readings given.
Most of these proofs closely follow the algorithm concerned, and
following the proof allows you to understand better how the
algorithm works. You should be able to state these results and use
them as necessary in justifying your answers.
I need to do a Max Flow on a graph (by hand), does it matter what
order of paths I take? Also, do I really need a residual graph
(when doing it on pen and paper)?
The purpose of this kind of question is usually to test
whether you understand the complete algorithm.
The residual graph is the key to the algorithm, so you definitely
need to know how to construct one.
So you should read the question very carefully (as always!) and try
to do exactly what is asked.
It does not matter which order you choose the paths, so choose them
in the most favourable way to minimize your work!
New: 8. Can you post a solution to Ch 7,
Ex. 39 (Census problem)
Sorry for not posting this earlier, it slipped through the cracks.
The official solution is now at
The solution I expected is on the first half of page 1.
The main point is to set up the network described in (a) and to
realize that the Ford-Fulkerson algorithm always gives an integer solution if all
the capacities are integer.
5: Exercises from lectures Mar 26, 28, Apr 2,4 collected on April
11 in class.
9 is a holiday)
this assignment will be given by Rami and Raphael, in class, April
will cover Assignment 4 and network flows.
Tutorial 4A: 4pm Wed April 4, TR 3060 Rami Aladdin
Tutorial 4B: 2pm Thurs April 5,
TR 3060 Raphael Mannadiar
2012.3.17 These tutorials will cover
Assignment 3 and dynamic programming examples.
Tutorial 3A: 4pm Wed March 21, TR 3060
Tutorial 3B: 2pm Thurs March 22,
TR 3060 Yam Chettri
for midterms posted here:Exams and
Solutions Class average:
The exams will be returned in
class on Monday March 12. The solutions will be posted shortly.
Tutorial 2A: 4pm Wed February 15, TR 3060
Tutorial 2B: 2pm Thurs February
16, TR 3060 Yam Chettri
2012.2.8 The midterm is
confirmed for Wednesday March 7 in class:
Family name: A-O Trottier 0100
Family name: P-Z Trottier 1100
2012.1.31 The course teaching assistants are there to help you
with the exercises. Please contact them by email to make an
Final exam tentatively
scheduled for Monday Apr 30 2 pm. Yes, last day of the exam
Problems on the first assignment will be discussed in each of
these tutorials. Please attend either or both.
Tutorial 1A: 2pm Tues January 31, TR 3060
Tutorial 1B: 4pm Wed February 1, TR 3060
WebCT is now open
for chat and discussion. It will also be moderated from time to time
by the TAs. Please make use of it to discuss lectures, exercises
Assignment 1 will be accepted for grading if it is handed in after
class on Jan. 25.
The doodle sites below will close at that time, and the tutorial
times will be announced on this web page by Friday Jan 27.
2012.1.18: An informal tutorial will be held to discuss solutions to
each assignment set. The tutorial will be given at two different
Please visit these two doodle sites and indicate you preferred time
slots. We will choose the most popular slot for each doodle site.
Please hand in the assignments
at the end of the lecture.
Assignment 1: From lectures Jan 9,11,16,18 collected on January 23.
Assignment 2: From lectures Jan 23, 25, 30 and Feb 1 collected on
Assignment 3: From lectures Feb 13, 17, 27, 29 collected on March 5.
Midterm March 7
on above material. Review class on March 5.
Assignment 4: From lectures Mar 12,14,19,21 collected on March
Assignment 5: From lectures Mar 26, 28, Apr 2,4 collected on April
11. (April 9 is a holiday)
Final exam in the exam period
based on all above material. Review April 16.
1. Exercises for each lecture are given on the lecture
2. They will be collected in class according to the schedule below
3. Grades will not count to your final grade, but at least half of
each exam will be based on these exercises.
4. Solutions will be posted after the exercises are collected.