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

Teaching Assistants:

• Roman Sarrazin-Gendron - Head TA
• Kian Ahrabian
• Florestan Brunck
• Raymond Chua
• Amir Kalantaridehaghi
• Aayushi Kulshrestha
• Auguste Lalande
• An Li
• Pierre Orhan
• Alika Utepova
• Hua-Ting Yao

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:

• [CLRS2009] Cormen, Leiserson, Rivest, & Stein, Introduction to Algorithms. (E-book)
• [KT2006] Kleinberg & Tardos, Algorithm Design.

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:

• 24% for 4 assignments (6% each)
• 25% for the midterm exam
• 50% for the final exam (75% if the grade of your final exam if higher than the one ofyour midterm)
• 1% for agreeing and following the rules and policy of this course.

Notes:

• The exam will be closed book, but you will be allowed 2 pages (i.e. 1 sheet) of notes (A4 or letter format) at the final exam. No electronic devices will be allowed (this includes noise-cancelling headphones).

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. Room First Last CMPUS 1 Rm. 101 Abi-Saad Dai CMPUS 1 Rm. 109 Dam Karna RPHYS 112 Kasapoglu Marks STBIO N2/2 Martin Rahman STBIO S1/3 Ramdany Warsi STBIO S3/3 Wei Zou 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 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 cs251@cs.mcgill.ca 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!

	Date	Topic	Material	References
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]

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.