COMP 251 Winter 2012
Course Announcements
Please check
this page once a
week. New
items at the top of the page.
course home page lecture summaries
Wrap up
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
course".
Have a good summer!
Final
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
Sunday.
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
questions ?
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
distributed ?
The questions will be roughly evenly distributed over all of the
material covered.
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
exam?
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.
New: 7:If
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
http://cgm.cs.mcgill.ca/~avis/courses/251/2012/soltns/hwk4/
password: birds
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.
2012.4.5 Assignment
5: Exercises from lectures Mar 26, 28, Apr 2,4 collected on April
11 in class.
(April
9 is a holiday)
A
tutorial
on
this assignment will be given by Rami and Raphael, in class, April
16.
2012.4.2
These tutorials
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
Bentley Oakes
Tutorial 3B: 2pm Thurs March 22,
TR 3060 Yam Chettri
2012.3.9 Grades
for midterms posted here:Exams and
Solutions Class average:
35.9/50.
The exams will be returned in
class on Monday March 12. The solutions will be posted shortly.
2012.2.15
Tutorial 2A: 4pm Wed February 15, TR 3060
Wanru Lin
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
appointment.
Rami
Aladdin
rami.aladdin@mail.mcgill.ca
Yam
Chhetri
yam.chhetri@mail.mcgill.ca
Wanru
Lin
wanru.lin@mail.mcgill.ca
Raphael
Mannadiar raphael.mannadiar@mail.mcgill.ca
Bentley
Oakes
bentley.oakes@mail.mcgill.ca
2012.1.25
Final exam tentatively
scheduled for Monday Apr 30 2 pm. Yes, last day of the exam
period.
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
Wanru Lin
Tutorial 1B: 4pm Wed February 1, TR 3060
Bentley Oakes
2012.1.23
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
etc.
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
time slots.
Please visit these two doodle sites and indicate you preferred time
slots. We will choose the most popular slot for each doodle site.
http://doodle.com/n8pkz9ei55fq69e4
http://doodle.com/tgz569byng4ktt5r
Tentative schedule
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
Feb 13.
Assignment 3: From lectures Feb 13, 17, 27, 29 collected on March 5.
Midterm March 7
Based
on above material. Review class on March 5.
Assignment 4: From lectures Mar 12,14,19,21 collected on March
26.
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
summaries page.
2. They will be collected in class according to the schedule below
and graded.
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.