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

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.