Introduction to algorithm design and analysis. Graph algorithms, greedy algorithms, data structures, dynamic programming, maximum flows.
Instructor: Prof. Jérôme Waldispühl.
Lectures: Tuesday & Thursday 14:35am to 15:55pm in McIntyre Medical Building 504.
All course-related email (assignments, quizzes, general issues) should be sent to firstname.lastname@example.org. Emails sent to personal addresses will not likely be seen.Office hours:
TA Office Hours will be held in Trottier 3110
Please consult this calendar for the most up to date Office Hour schedule and important dates.
Course Webpage: http://www.cs.mcgill.ca/~jeromew/comp251.html
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:
The official discussion board for this class is available on MyCourses.
Your final grade will be calculated as follows:
|Release Date||Due Date||Announce|
|Dec 5th||The solutions of the practice questions are now available. For your own benefit, we recommend you to try answering the question by yourself first before checking the solutions.|
Note: If you think you found a typo, please email us at email@example.com and we will fix it for everyone.
|Nov 24th||Nov 27th||The Lecture of Nov 27th is cancelled. Carlos G. Oliver will give the last review lecture on Nov 29th.|
|Nov 24th||We released a set of practice questions. We recommend you to try answering the question before Nov 29th. We will publish the solutions after the lecture on Thursday.|
|Nov 21th||Dec 5th (11:55pm)||Assignment 5 is now available. All the test cases can be found in this zip file.|
|Nov 7th||Nov 21th (11:55pm)||Assignment 4 is now available. You will need to complete the Java class Multiply.java and karatsuba.csv.|
|Oct 24th||Nov 7th (11:55pm)||Assignment 3 is now available. The templates, auxiliary and test files are available in the zip file COMP251HW3.zip.|
Note: We clarified the guidelines on Oct. 30th.
|Oct 13th||Oct 26th (11:55pm)||Assignment 2 is now available. The templates, auxiliary and test files are available in the zip file COMP251HW2.zip.|
Note: the files have been updated on Oct. 20th. We fixed a typo in the question 3 and updated the Java template accordingly.
|Oct 3rd||Oct 3rd (11h59)||The first quiz is now available on MyCourses.|
|Sep 26th||An extra set of slides describing how to use ssh and scp is now available.|
|Sep 25th||Oct 9th (11:55pm)||Assignment 1 is now available. Template and auxiliary files are available in the zip file COMP251HW1.zip. You can test your code with Tester.java|
|Sep 5th||Sep 6th||Complete the online quizz. It will not be graded. It is designed to help your reviewing the COMP250 material and customized the lectures.|
|Sep 4th||Welcome in COMP 251!|
|Lecture 0||Sep 4th||Introduction||[SLIDES]|
|Lecture 1||Sep 6th||COMP250 review||[SLIDES]|
|Lecture 2||Sep 11th||Hashing||[SLIDES]||Chapter 11 of [CLRS2009]|
|Lecture 3||Sep 13th||Heaps & Heapsort||[SLIDES]||Chapter 6 of [CLRS2009]|
|Lecture 4||Sep 18th||BST and AVL trees||[SLIDES]|
|Lecture 5||Sep 20th||Red-black trees||[SLIDES]||Chapter 13 of [CLRS2009]|
|Tutorial||Sep 25th||Tutorial for programming questions||[SLIDES]|
|Lecture 6||Sep 27th||Disjoint sets||[SLIDES]||Chapter 21 of [CLRS2009]|
|Lecture 7||Oct 2nd||Greedy algorithms (Scheduling, Huffman coding)||[SLIDES]||Chapter 16 of [CLRS2009]|
|Lecture 8||Oct 4th||Elementary graph algorithms||[SLIDES]||Chapter 22 of [CLRS2009]|
|Lecture 9||Oct 9th||Topological sort and strongly connected components||[SLIDES]||Chapter 22 of [CLRS2009]|
|Lecture 10||Oct 11th||Minimum Spanning Tree||[SLIDES]||Chapter 23 of [CLRS2009]|
|Lecture 11||Oct 16th||Single source shortest path||[SLIDES]||Chapter 24 of [CLRS2009]|
|Lecture 12||Oct 18th||Bipartite graphs||[SLIDES]||Chapter 1.1 of [KT2006]|
|Lecture 13||Oct 23rd||Network flow 1||[SLIDES]||Chapter 26 of [CLRS2009]|
|Lecture 14||Oct 25th||Network flow 2||[SLIDES]||Chapter 26 of [CLRS2009]|
|Lecture 15||Oct 30th||Dynamic Programming 1 (weighted interval scheduling)||[SLIDES]||Chapter 6 of [KT2006]|
|Lecture 16||Nov 1st||Dynamic Programming 2 (Bellman Ford, knapsack problem)||[SLIDES]||Chapter 6 of [KT2006]|
|Lecture 17||Nov 6th||Dynamic Programming 3 (Pairwise sequence alignment)||[SLIDES]||Chapter 6 of [KT2006]|
|Lecture 18||Nov 8th||Divide-and-conquer 1 (Merge sort & integer multiplication)||[SLIDES]||Chapter 5 of [KT2006]|
|Lecture 19||Nov 13th||Divide-and-conquer 2 (Master Theorem)||[SLIDES]||Chapter 4 of [CLRS2009]|
|Lecture 20||Nov 15th||Amortized analysis||[SLIDES]||Chapter 17 of [CLRS2009]|
|Lecture 21||Nov 20th||Randomized algorithms (Global min-cut, randomized quick sort)||[SLIDES]||Chapter 13 of [KT2006]|
|Lecture 22||Nov 22nd||Probabilistic analysis||[SLIDES]||Chapter 5 of [CLRS2009]|
|Nov 27th||No Class|
|Lecture 23||Nov 29nd||Review||[SLIDES]|
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, MATH 240, 363, or 235 are co-requisites of this course.
Policy on discussion Board
The official discussion board is accessible on MyCourses. 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 (as a comment in the header of your source code if it is a programming question) 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 grading
We will use the same formula for calculating your final grade for everyone. We 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 and possibly absence of grading. Late submission of 24h or less will receive a penalty of 20%. In all other cases, your assignment will be refused and not graded.
Assignments may include guidelines and require particular formatting procedures. Solutions that do not follow the required format will not be graded.
The quality of the presentation of your solution is important. Unreadable material, cryptic notations, or bad organization of the material may result 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 (Note: these files are used to help you implement and test your code, but a correct execution of your program on these files will not guarantee that your code is 100% correct). Importantly, 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 and execute on these machines.
Unless specified, only source files should be submitted. Java class files will be discarded without grading. It is your responsability to ensure that you submit the correct file.
The quality of the presentation of your code is important. Bad organization of the code, absence of comments, or poorly named variables may affect your grading.
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.
Additional information and rules may be found in the slides of the first lecture.
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.
All request should be sent at: