Introduction to algorithm design and analysis. Graph algorithms, greedy algorithms, data structures, dynamic programming, maximum flows.


Instructor: Prof. Jérôme Waldispühl (

Teaching Assistants:

Lectures: Monday & Wednesday 11:35am to 12:55pm in MDHAR G-10.

Office hours:

Prof. Jérôme WaldispühlMon 13:45-15:15pmENGTR 3106
David Becerra RomeroThu 11:00-1:00pmENGTR 3150
Alexander ButyaevFri 2:00-4:00pmENGTR 3140
Antoine SouléIn charge of forumOnline!
Vladimir ReinharzMon 9:00-11:00amENGTR 3140
Jing ZhuThu 2:00-4:00pmMC 229

Course Webpage:

Course Material:
All the material needed for this class will be available on the public course web page. There is no required textbook. However, we recommend the following textbooks from which most lectures will be based upon:

Lecture slides will be made available in PDF form on the course web page. Lectures will be recorded and available on MyCourse. Instructions to borrow a E-book online are available at

Discussion Board:
The official discussion board for this class is available at You can automatically login into this forum using your SOCS login and password. If you do not have a SOCS account, you can create one at from any computer in the mcgill network.

Your final grade will be calculated as follows:

The exams are closed book. However, you will be allowed 4 pages of notes at the final exam. No electronic devices are allowed (this includes noise-cancelling headphones).


Release DateDue DateAnnounce
Apr 18thYou can now access a collection of problems to practice for the final exam.
Apr 18thJ. Waldispühl will hold extra office hours on Monday from 1:30 to 3:00
Apr 6thApr 14th at 11:59pmAssignment 5 is out!
Mar 28thMar 30th at 11:59pmThe choice is yours! Answer the survey and give your preferences for the topics to be covered in the last lectures.
Mar 28thMar 30th at 11:30amAnswer the questions of the lecture 20 anonymous quiz.
Mar 23rdMar 25th at 11:30amAnswer the questions of the lecture 19 anonymous quiz.
Mar 22ndMar 23rd at 11:30amAnswer the questions of the lecture 18 anonymous quiz.
Mar 20thApr 2nd at 11:59pmAssignment 4 is out! Additional Java files:, JavaPlotBuilder.jar
Mar 16thMar 18th at 11:30amAnswer the questions of the lecture 17 anonymous quiz.
Mar 14thMar 16th at 11:30amAnswer the questions of the lecture 16 anonymous quiz.
Mar 10thMar 11th at 11:30amAnswer the questions of the lecture 14-15 anonymous quiz.
Mar 4thMar 18th at 11:59pmAssignment 3 is out! Additional Java files:,,, ff2.txt, ff226000000.txt, and bf1.txt, bf2.txt, bf3.txt, bf4.txt
Feb 21stYou can now access a collection of problems to practice for the midterm exam.
Feb 19thFeb 23rd at 11:30amAnswer the questions of the lecture 13 anonymous quiz.
Feb 16thFeb 18th at 11:30amAnswer the questions of the lecture 12 anonymous quiz.
Feb 11thFeb 16th at 11:30amAnswer the questions of the lecture 11 anonymous quiz.
Feb 9thFeb 11th at 11:30amAnswer the questions of the lecture 10 anonymous quiz.
Feb 6thFeb 20th at 11:59pmAssignment 2 is out! Additional Java files:,,, unionfind.txt, g1.txt, and mst1.txt
Feb 6thFeb 9th at 11:30amAnswer the questions of the lecture 9 anonymous quiz.
Feb 2ndFeb 4th at 11:30amAnswer the questions of the lecture 8 anonymous quiz.
Jan 30thFeb 2nd at 11:30amAnswer the questions of the lecture 7 anonymous quiz.
Jan 29thFeb 4th at 11:59amAssignment 1 has been updated. We provide more information to complete question 1. In consequence, the deadline to submit your answers has been postponed to Wednesday February 4th.
Jan 26thJan 28th at 11:30amAnswer the questions of the lecture 6 anonymous quiz.
Jan 22ndJan 26th at 11:30amAnswer the questions of the lecture 5 anonymous quiz.
Jan 20thFeb 4th at 11:59pmAssignment 1 is out! Additional Java files: and JavaPlotBuilder.jar
Jan 19thJan 21st at 11:30amAnswer the questions of the lecture 4 anonymous quiz.
Jan 15thJan 19th at 11:30amAnswer the questions of the lecture 3 anonymous quiz.
Jan 13thJan 14th at 11:30amAnswer the questions of the lecture 2 anonymous quiz.
Jan 12thThe forum is now online at You can automatically login into this forum using your SOCS login and password.
Jan 5thJan 6th at 6pmAnswer an anonymous quiz that will be used to calibrate the review session and the whole class during the semester.


Lecture 0Jan 5thIntroductionSurvey completed. Please visit the slide of Lecture 1 to review the questions and answers.
Lecture 1Jan 7thCOMP250 reviewSlides: [1/page] or [6/page]
Lecture 2Jan 12thHashingSlides: [1/page] or [6/page] & Online quizChapter 11 of [CLRS2009]
Lecture 3Jan 14thHeaps & HeapsortSlides: [1/page] or [6/page] & Online quizChapter 6 of [CLRS2009]
Lecture 4Jan 19thBST and AVL treesSlides: [1/page] or [6/page] & Online quiz
Lecture 5Jan 21thRed-black treesSlides: [1/page] or [6/page] & Online quizChapter 13 of [CLRS2009]
Lecture 6Jan 26thDisjoint setsSlides: [1/page] or [6/page] & Online quizChapter 21 of [CLRS2009]
Lecture 7Jan 28thGreedy algorithms (Scheduling, Huffman coding)Slides: [1/page] or [6/page] & Online quizChapter 16 of [CLRS2009]
Lecture 8Feb 2ndStrongly connected component (SCC), topological orderingSlides: [1/page] or [6/page] & Online quizChapter 22 of [CLRS2009]
Lecture 9Feb 4thMinimum Spanning TreeSlides: [1/page] or [6/page] & Online quizChapter 23 of [CLRS2009]
Lecture 10Feb 9thSingle source shortest pathSlides: [1/page] or [6/page] & Online quizChapter 24 of [CLRS2009]
Lecture 11Feb 11thBipartite graphsSlides: [1/page] or [6/page] & Online quizChapter 1.1 of [KT2006]
Lecture 12Feb 16thNetwork flow 1Slides: [1/page] or [6/page] & Online QuizChapter 26 of [CLRS2009]
Lecture 13Feb 18thNetwork flow 2Slides: [1/page] or [6/page] & Online QuizChapter 26 of [CLRS2009]
Lecture 14Feb 23rdDynamic Programming 1 (weighted interval scheduling, Bellman-Ford)Slides: [1/page] or [6/page]Chapter 6 of [KT2006]
Feb 25thMid-term
Lecture 15Mar 9thDynamic Programming 2 (sequence alignment, knapsack problem)Slides: [1/page] or [6/page] & Online QuizChapter 6 of [KT2006]
Lecture 16Mar 11thDivide-and-conquer 1 (Merge sort & integer multiplication)Slides: [1/page] or [6/page] & Online QuizChapter 5 of [KT2006]
Lecture 17Mar 16thDivide-and-conquer 2 (Master Theorem)Slides: [1/page] or [6/page] & Online QuizChapter 4 of [CLRS2009]
Lecture 18Mar 18thDivide-and-conquer 3 (Fast Fourier Transform)Slides: [1/page] or [6/page] & Online QuizzChapter 5 of [KT2006]
Lecture 19Mar 23rdAmortized analysisSlides: [1/page] or [6/page] & Online QuizChapter 17 of [CLRS2009]
Lecture 20Mar 25thRandomized algorithms (Global min-cut, randomized quick sort)Slides: [1/page] or [6/page] & Anonymous quizChapter 13 of [KT2006]
Lecture 21Mar 30thProbabilistic analysisSlides: [1/page] or [6/page]Chapter 5 of [CLRS2009]
Lecture 22Apr 1stData compressionSlides: [1/page] or [6/page]
Lecture 23Apr 8thPattern MatchingSlides: [1/page] or [6/page]
Lecture 24Apr 13thReviewSlides: [1/page] or [6/page]


The official prerequisite for this course is COMP 250 Introduction to Computer Science. We recommend the students to review the material covered in this class. The students must also be familiar with basic concepts in discrete mathematics and probability. Therefore, courses such as MATH 240, 363, or 235 are recommended (but not required).

Policy on discussion Board
We will use a new forum system available at: (i.e. we will not use the forum in MyCourse).
You will be automatically registered in this forum and will have the possibility to vote for the most useful questions and answers. Students with the most voted questions and answers (after validation by a moderator) will receive bonus points.
Please follow common sense rules and etiquette for discussion board postings: be polite, avoid texting shorthand ("ur" instead of "you are", ...), choose a suitable subject line for your posting and use multiple postings for multiple subjects, keep your postings brief, etc.

Policy on collaborations
We greatly encourage you to discuss the assignment problems with each other. However, these discussions should not so far that you are sharing code or giving away the answer. A rule of thumb is that your discussions should considered public in the sense that anything you share with a friend should be sharable with any student in the class. We ask you to indicate on your assignments the names of the persons with who you collaborated or discussed your assignments (including the TA’s and the instructor).

Policy on re-grading
If you wish us to re-grade a question on an exam (or assignment), we will do so. However, to avoid grade ratcheting, we reserve us the right to re-grade other questions on your exam as well.

Policy on final grades
I will use the same formula for calculating your final grade for everyone. I understand that your performances may be influenced by many factors, possibly out of your control. However, that is the only way we can be fair. The only exceptions will be medical exceptions. In that case, I will require a medical note, which has to be also reported to McGill, and to be informed as early as possible. Failure to comply to these rules, may results in the impossibility to invoke a medical exception.

Policy on Assignments
Due date/time, location/mode for returning your solutions, and accepted formats will be announced in class and indicated on the course web page.
Failure to return your assignment in time will results in penalties. If it is the first time that you return late your assignment, you will receive a penalty of 20% on your normal grade if your assignment is returned late the same day. In all other cases, your assignment will be refused and not graded. Solutions that do not follow the required format will be refused.
The quality of the presentation of your solution is important. Unreadable material, cryptic notations, or bad organization of the material will results in absence of grading. Clarity of your explanations will be an integral part of your final grade.

Policy on programming code
Questions in assignments may require you to write a Java program. We will provide, as much as possible, input and output data to test your programs. However, it will be your duty to ensure that your Java files compile on LINUX SOCS workstations. We will not grade programs that do not compile on these machines.

Use of French in assignments and exams
In accordance with McGill University’s Charter of Students’ Rights, students in this course have the right to submit in English or in French any written work that is to be graded.

McGill policies
McGill University values academic integrity. Therefore, all students must understand the meaning and consequences of cheating, plagiarism and other academic offenses under the Code of Student Conduct and Disciplinary Procedures. See this link for more information.


For any issue that is not directly related to the material covered in the class, you can contact me directly at:

3630 University Street, Room 3106, Montreal QC H3A 0C6
(Phone) +1 514 398 5018

Based on a template from