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 16:05am to 17:25pm in McIntyre Medical Building 522.
Contact: 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:
Please consult the COMP251 calendar below for the most up-to-date schedule including office hours and other important dates.
The location of the office hours is indicated in the calendar.
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 on reddit.
Your final grade will be calculated as follows:
|Release Date||Due Date||Announce|
|Dec 15||Dec 16||We posted a list of tips and information for the final on the reddit forum.|
|Dec 9||Dec 16||We released a selected set of problems with solutions for practicing for the final. More problems can be found on the COMP251 website of Mike Langer or in the text books used in this class [CLRS2009] & [KT2006].|
|Dec 1||Dec 1||It came to our attention that there was a discrepancy in the grading scheme of the long answer of assignment 2. Because of the volume of copies we have to grade, we used multiple graders and this resulted in different interpretation of the grading scheme. After reviewing all answers, we decided to proceed to an harmonization of the grades. This resulted in significant increase for many of you and the overall average for the homework is now the same between all TAs.|
At this point we are considering the grades as final and we will not proceed any further request of regrading. You are welcome to see a TA during the remaining office to clarify what you did right or wrong.
|Nov 30||Dec 7||Following multiple requests, we clarified the programming part of Assignment 4. More details can be found on the reddit forum post. We will also allow submission with NO PENALTY until December 7th, 11:55PM. There will be a second test run on December 7th at 11:55PM. The assignment has been updated accordingly.|
|Nov 23||Dec 7||A complete version of Assignment 4 including the long answers questions has been released.|
Note 1 (Nov 30): The deadline to re-submit without penalty has been extended to Dec 7.
|Nov 21||Dec 7||A preliminary version of Assignment 4 is now available. We provide Java templates for the programming part of this assignment. Read carefully the instructions and guidelines. You must return your answers on MyCourses. A complete version will be released by Nov 23.|
Note 1 (Nov 23): The document has been updated on Nov 23.
Note 2 (Nov 24): We fixed a typo which prevented a warning from being displayed if the min cut algorithm run exceeded maxIterations.
Note 3 (Nov 30): The deadline to re-submit without penalty has been extended to Dec 7.
|Nov 20||Nov 22||We extended the deadline to submit revised or late assignments 3. You will have 48h (instead of 24h) to re-submit with a 20% penalty.|
|Nov 8||Nov 20||Assignment 3 is now available. We provide Java templates for the programming part of this assignment. Read carefully the instructions and guidelines. You must return your answers on MyCourses.|
|Nov 8||Nov 11||The make-up midterm is scheduled at 6pm in MAASS 10. You will be allowed to take the exam if and only if you have been pre-authoriszed by the instructor.|
|Nov 5||Nov 7||
Find below the room assignment for the midterm exam (Nov 7). You are required to take the exam at the location associated with your name. If you show up at another location you may be subject to a penalty.
|Oct 29||Nov 7||The mid-term exam is scheduled on Nov 7 at 6:30pm and the make-up exam on Nov 11 at 6h00. More instruction will follow. Only pre-authorized students who declare a conflict with another mid-term will be able to take the make-up exam.|
Update (Nov 6): The time for the make-up exam has been corrected. It is 6pm instead of 6:30pm. We recommend you to be in the rooms at the latest at 6:15 (Nov 7) and 5:45 (Nov 11).
|Oct 24||Oct 25||Deadline to submit the assignment is postponed to Oct 25 at 11:55pm. To benefit of a complimentary run of the grader, submit your programming files before Oct 24 at 9pm.|
|Oct 10||Oct 17||The mid-term exam is scheduled on Nov 7 at 6:30pm. Contact us at email@example.com before Oct 17, if you have a conflict in your academic agenda.|
|Oct 10||Oct 15||Do not forget to fill the quizz about the course policy and guideline before Oct 15.|
|Oct 10||Oct 24||Assignment 2 is now available. We provide Java templates for the programming part of this assignment. Read carefully the instructions and guidelines. You must return your answers on MyCourses.|
|Sep 24||Oct 8||Assignment 1 is now available. We provide Java templates for the programming part of this assignment. Read carefully the instructions and guidelines. You will be able to access additional material (i.e. lists of keys for the programming question) and return your answers on MyCourses.|
Note: The file has been updated on Sep 28 to address requests for clarifications we received. We updated a variable name in question 3 (there were two k), and in questions 1-2, we clarified the purpose of the main class, the case where no insertion is performed, and the definition of collisions using chaining.
|Sep 7||Nov 7||The mid-term exam is tentatively scheduled on Nov. 7 at 6:30pm. Details will follow.|
|Sep 3||Sep 5||Complete the online quizz. It will not be graded. It is designed to help your reviewing the COMP250 material and help us to customize the COMP 251 lectures.|
|Sep3||Welcome in COMP 251!|
|Lecture 0||Sep 3||Introduction||[SLIDES]|
|Lecture 1||Sep 5||COMP250 review||[SLIDES]|
|Lecture 2||Sep 10||Hashing||[SLIDES]||Chapter 11 of [CLRS2009]|
|Lecture 3||Sep 12||Heaps & Heapsort||[SLIDES]||Chapter 6 of [CLRS2009]|
|Lecture 4||Sep 17||BST and AVL trees||[SLIDES]|
|Lecture 5||Sep 19||Red-black trees||[SLIDES]||Chapter 13 of [CLRS2009]|
|Tutorial I||Sep 24||Linux Tutorial||[SLIDES]|
|Tutorial II||Sep 26||Java Tutorial||[SLIDES]|
|Lecture 6||Oct 1||Disjoint sets||[SLIDES]||Chapter 21 of [CLRS2009]|
|Lecture 7||Oct 3||Greedy algorithms (Scheduling, Huffman coding)||[SLIDES]||Chapter 16 of [CLRS2009]|
|Lecture 8||Oct 8||Elementary graph algorithms||[SLIDES]||Chapter 22 of [CLRS2009]|
|Lecture 9||Oct 10||Topological sort and strongly connected components||[SLIDES]||Chapter 22 of [CLRS2009]|
|Lecture 10||Oct 15||Minimum Spanning Tree||[SLIDES]||Chapter 23 of [CLRS2009]|
|Lecture 11||Oct 17||Single source shortest path||[SLIDES]||Chapter 24 of [CLRS2009]|
|Lecture 12||Oct 22||Bipartite graphs||[SLIDES]||Chapter 1.1 of [KT2006]|
|Lecture 13||Oct 24||Network flow 1||[SLIDES]||Chapter 26 of [CLRS2009]|
|Lecture 14||Oct 29||Network flow 2||[SLIDES]||Chapter 26 of [CLRS2009]|
|Lecture 15||Oct 31||Dynamic Programming 1 (weighted interval scheduling)||[SLIDES]||Chapter 6 of [KT2006]|
|Lecture 16||Nov 5||Dynamic Programming 2 (Bellman Ford, knapsack problem)||[SLIDES]||Chapter 6 of [KT2006]|
|Lecture 17||Nov 7||Dynamic Programming 3 (Pairwise sequence alignment)||[SLIDES]||Chapter 6 of [KT2006]|
|Lecture 18||Nov 12||Divide-and-conquer 1 (Merge sort & integer multiplication)||[SLIDES]||Chapter 5 of [KT2006]|
|Lecture 19||Nov 14||Divide-and-conquer 2 (Master Theorem)||[SLIDES]||Chapter 4 of [CLRS2009]|
|Lecture 20||Nov 20||Amortized analysis||[SLIDES]||Chapter 17 of [CLRS2009]|
|Lecture 21||Nov 22||Randomized algorithms (Global min-cut, randomized quick sort)||[SLIDES]||Chapter 13 of [KT2006]|
|Lecture 22||Nov 26||Probabilistic analysis||[SLIDES]||Chapter 5 of [CLRS2009]|
|Lecture 23||Nov 28||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 reddit. 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 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.
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: