Introduction to algorithm design and analysis. Graph algorithms, greedy algorithms, data structures, dynamic programming, maximum flows.
Instructors: Prof. Jérôme Waldispühl and Roman Sarrazin-Gendron.
Teaching Assistants:
Lectures: Online (live & recorded) on Tuesday & Thursday at 10am (EDT).
Contact: All course-related email should be sent to cs251@cs.mcgill.ca. Emails sent to personal addresses will not likely be seen.
Office hours:Please consult the COMP251 calendar below for the most up-to-date schedule including office hours and other important dates.
Course Webpage: http://www.cs.mcgill.ca/~jeromew/comp251.html
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:
Discussion Board:
We are using Ed for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TAs, and instructors. Rather than emailing questions to the teaching staff, we encourage you to post your questions there.
The official discussion board for this class is Ed. You can Login to the platform via MyCourses.
Evaluation
Your final grade will be calculated as follows:
| Release Date | Due Date | Announce |
|---|---|---|
| Nov 24 | Dec 13 at 8h59am | In order to help you preparing the final, we release a set of practice problems. You can also download a previous final 3-hours exam that you can use to calibrate your speed (Please, keep in mind that with the stress a formal examination will feel even shorter). EDIT(Dec. 2): The solutions are now available for the practice problems and previous exam. It is important that you try first to solve these problems by yourselves before reading the solutions. |
| Nov 23 | Dec 6 at 11h59pm | The fourth assignment is now available. You should download the PDF with the instructions and questions and the java templates. You must submit your solution on code post using the template provided here. Register at https://codepost.io/signup/join?code=C2D5JWLLW7. |
| Nov 4 | Nov 17 at 11h59pm | The third assignment is now available. You should download the PDF with the instructions and questions and the java templates. You must submit your solution on code post using the template provided here. Register at https://codepost.io/signup/join?code=C2D5JWLLW7. |
| Oct 15 | Oct 29 at 11h55pm | The second assignment is now available. You should download the PDF with the instructions and questions and the java templates. You must submit your solution on code post using the template provided here. Register at https://codepost.io/signup/join?code=C2D5JWLLW7. Note: The template has been updated on Oct 17. If you donwloaded it earlier, please, download and use the latest version. |
| Sep 30 | Oct 18 at 11h59pm | The first assignment is now available. You should download the PDF with the instructions and questions and the java templates. You must submit your solution using the template on code post. Register at https://codepost.io/signup/join?code=C2D5JWLLW7. Note: We posted an updated version of the assignment on Oct 7 that answers the most frequently asked questions we got. Please, download the new version of the PDF and template if you downloaded yours before Oct 7. The deadline for submitting the assignment has also been extended on Oct 18 (See the announce on Ed). |
| Sep 30 | The tutorial videos are online! You can find the URL in MyCourses. | |
| Sep 2 | Welcome in COMP 251! A link is available on MyCourses. The class will be recorded and available of streaming later. Online office hours will be arranged and announced in due time. |
| Date | Topic | Material | References | Instructor | |
|---|---|---|---|---|---|
| Lecture 0 | Sep 2 | Introduction | [SLIDES] | J. Waldispühl & R. Sarrazin-Gendron | |
| Lecture 1 | Sep 7 | Recurrences | [SLIDES] | Chapter 4 of [CLRS2009] | R. Sarrazin-Gendron |
| Lecture 2 | Sep 9 | Proofs by induction and loop invariants | [SLIDES] | R. Sarrazin-Gendron | |
| Lecture 3 | Sep 14 | Big Oh notation | [SLIDES] | Chapter 3 of [CLRS2009] | R. Sarrazin-Gendron |
| Lecture 4 | Sep 16 | Graphs, Probability and Binary numbers | [SLIDES] | R. Sarrazin-Gendron | |
| Lecture 5 | Sep 21 | Heaps & Heapsort | [SLIDES] | Chapter 6 of [CLRS2009] | R. Sarrazin-Gendron |
| Lecture 6 | Sep 23 | BST and AVL trees | [SLIDES] | R. Sarrazin-Gendron | |
| Lecture 7 | Sep 28 | Red-black trees | [SLIDES] | Chapter 13 of [CLRS2009] | J. Waldispühl |
| Lecture 8 | Sep 30 | Hashing | [SLIDES] | Chapter 11 of [CLRS2009] | J. Waldispühl |
| Lecture 9 | Oct 5 | Disjoint sets | [SLIDES] | Chapter 21 of [CLRS2009] | J. Waldispühl |
| Lecture 10 | Oct 7 | Greedy algorithms (Scheduling, Huffman coding) | [SLIDES] | Chapter 16 of [CLRS2009] | J. Waldispühl |
| Lecture 11 | Oct 15 | Elementary graph algorithms | [SLIDES] | Chapter 22 of [CLRS2009] | J. Waldispühl |
| Lecture 12 | Oct 19 | Topological sort and strongly connected components | [SLIDES] | Chapter 22 of [CLRS2009] | J. Waldispühl |
| Lecture 13 | Oct 21 | Single source shortest path | [SLIDES] | Chapter 24 of [CLRS2009] | J. Waldispühl |
| Lecture 14 | Oct 26 | Minimum Spanning Tree | [SLIDES] | Chapter 23 of [CLRS2009] | R. Sarrazin-Gendron |
| Lecture 15 | Oct 28 | Bipartite graphs | [SLIDES] | Chapter 1.1 of [KT2006] | R. Sarrazin-Gendron |
| Midterm | Nov 2 | Mid-term Examination | Online exam on Crowdmark during regular class hours (10am-11:30am EDT) | ||
| Lecture 16 | Nov 4 | Network flow 1 | [SLIDES] | Chapter 26 of [CLRS2009] | R. Sarrazin-Gendron |
| Lecture 17 | Nov 9 | Network flow 2 | [SLIDES] | Chapter 26 of [CLRS2009] | R. Sarrazin-Gendron |
| Lecture 18 | Nov 11 | Dynamic Programming 1 (weighted interval scheduling) | [SLIDES] | Chapter 6 of [KT2006] | J. Waldispühl |
| Lecture 19 | Nov 16 | Dynamic Programming 2 (Bellman Ford, knapsack problem) | [SLIDES] | Chapter 6 of [KT2006] | J. Waldispühl |
| Lecture 20 | Nov 18 | Amortized analysis | [SLIDES] | Chapter 17 of [CLRS2009] | J. Waldispühl |
| Lecture 21 | Nov 23 | Divide-and-conquer 1 (Merge sort & integer multiplication) | [SLIDES] | Chapter 5 of [KT2006] | J. Waldispühl |
| Lecture 22 | Nov 25 | Divide-and-conquer 2 (Master Theorem) | [SLIDES] | Chapter 4 of [CLRS2009] | J. Waldispühl |
| Lecture 23 | Nov 30 | Randomized algorithms (Global min-cut, randomized quick sort) | [SLIDES] | Chapter 13 of [KT2006] | J. Waldispühl |
| Lecture 24 | Dec 2 | Probabilistic analysis | [SLIDES] | Chapter 5 of [CLRS2009] | J. Waldispühl |
| Final | Dec 13 | Final Examination | In-person formal exam (Full details available at the Exam office) |
Prerequisites
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 Ed. 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 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.
Importantly, 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). Failure to comply to this rule may affect your grading.
Policy on re-grading
When justified, we can re-grade a question on an exam (or assignment). 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, we 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 not be 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 answers 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.
Other rules
Additional information and rules may be found in the slides of the first lecture. In case of doubt, please contact the instructor at cs251@cs.mcgill.ca.
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.
All request should be sent at:
(E-mail) cs251@cs.mcgill.ca