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

GENERAL INFORMATION


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

Teaching Assistants:

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 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.

The location of the office hours is indicated in the calendar.

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:

Lecture slides will be made available in PDF form on the course web page. Lectures will be recorded and available on MyCourse (You must login into MyCourses. Download is not enabled). Instructions to borrow a E-book online are available at http://www.mcgill.ca/library/find/ebooks/borrowing-ebooks/.

Discussion Board:
The official discussion board for this class is on reddit.

Evaluation
Your final grade will be calculated as follows:

Notes:

ANNOUNCES


Release DateDue DateAnnounce
Nov 8Nov 20Assignment 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 8Nov 11The 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 5Nov 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.
RoomFirstLast
CMPUS 1 Rm. 101Abi-SaadDai
CMPUS 1 Rm. 109DamKarna
RPHYS 112KasapogluMarks
STBIO N2/2MartinRahman
STBIO S1/3RamdanyWarsi
STBIO S3/3WeiZou
Update (Nov 6): Your key for the table above is your last name. The "First" and "Last" columns indicate the last names of first and last student assigned to this room.
Oct 29Nov 7The 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 24Oct 25Deadline 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 10Oct 17The mid-term exam is scheduled on Nov 7 at 6:30pm. Contact us at cs251@cs.mcgill.ca before Oct 17, if you have a conflict in your academic agenda.
Oct 10Oct 15Do not forget to fill the quizz about the course policy and guideline before Oct 15.
Oct 10Oct 24Assignment 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 24Oct 8Assignment 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 7Nov 7The mid-term exam is tentatively scheduled on Nov. 7 at 6:30pm. Details will follow.
Sep 3Sep 5Complete 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.
Sep3Welcome in COMP 251!

SCHEDULE


DateTopicMaterialReferences
Lecture 0Sep 3Introduction[SLIDES]
Lecture 1Sep 5COMP250 review[SLIDES]
Lecture 2Sep 10Hashing[SLIDES]Chapter 11 of [CLRS2009]
Lecture 3Sep 12Heaps & Heapsort[SLIDES]Chapter 6 of [CLRS2009]
Lecture 4Sep 17BST and AVL trees[SLIDES]
Lecture 5Sep 19Red-black trees[SLIDES]Chapter 13 of [CLRS2009]
Tutorial ISep 24Linux Tutorial[SLIDES]
Tutorial IISep 26Java Tutorial[SLIDES]
Lecture 6Oct 1Disjoint sets[SLIDES]Chapter 21 of [CLRS2009]
Lecture 7Oct 3Greedy algorithms (Scheduling, Huffman coding)[SLIDES]Chapter 16 of [CLRS2009]
Lecture 8Oct 8Elementary graph algorithms[SLIDES]Chapter 22 of [CLRS2009]
Lecture 9Oct 10Topological sort and strongly connected components[SLIDES]Chapter 22 of [CLRS2009]
Lecture 10Oct 15Minimum Spanning Tree[SLIDES]Chapter 23 of [CLRS2009]
Lecture 11Oct 17Single source shortest path[SLIDES]Chapter 24 of [CLRS2009]
Lecture 12Oct 22Bipartite graphs[SLIDES]Chapter 1.1 of [KT2006]
Lecture 13Oct 24Network flow 1[SLIDES]Chapter 26 of [CLRS2009]
Lecture 14Oct 29Network flow 2[SLIDES]Chapter 26 of [CLRS2009]
Lecture 15Oct 31Dynamic Programming 1 (weighted interval scheduling)[SLIDES]Chapter 6 of [KT2006]
Lecture 16Nov 5Dynamic Programming 2 (Bellman Ford, knapsack problem)[SLIDES]Chapter 6 of [KT2006]
Lecture 17Nov 7Dynamic Programming 3 (Pairwise sequence alignment)[SLIDES]Chapter 6 of [KT2006]
Lecture 18Nov 12Divide-and-conquer 1 (Merge sort & integer multiplication)[SLIDES]Chapter 5 of [KT2006]
Lecture 19Nov 14Divide-and-conquer 2 (Master Theorem)[SLIDES]Chapter 4 of [CLRS2009]
Lecture 20Nov 20Amortized analysis[SLIDES]Chapter 17 of [CLRS2009]
Lecture 21Nov 22Randomized algorithms (Global min-cut, randomized quick sort)[SLIDES]Chapter 13 of [KT2006]
Lecture 22Nov 26Probabilistic analysis[SLIDES]Chapter 5 of [CLRS2009]
Lecture 23Nov 28Review[SLIDES]
Note: This schedule is subject to modification.

RULES & POLICIES


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 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.

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.

CONTACT


All request should be sent at:

(E-mail) cs251@cs.mcgill.ca

Based on a template from BlackTie.co