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

Teaching Assistants:

• Roman Sarrazin-Gendron - Head TA
• Robert Belfer
• Chengkai Zhu
• Seara Chen
• Qianyuan Sun
• Konrad Anand
• Michael Haaf
• Rudolf Lam
• Eric Zhang
• Huiwen You

Lectures: Tuesday & Thursday 14:35am to 15:55pm in McIntyre Medical Building 504.

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:

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

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 available on MyCourses.

Evaluation
Your final grade will be calculated as follows:

• 40% for 5 assignments
• 10% for the quizzes (Optional)
• 49% for the final exam (59% if the grade of your final exam if higher than the average score of the quizzes)
• 1% for agreeing and following the rules and policy of this course.

Notes:

• The quizzes will be available on MyCourse.
• The quizzes are optional. Your average score will be used to calculate your final grade only if it exceeds the grade of your final exam. If it is not the case, the weight of your final exam will be 60%.
• 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
Jan 24th		The first exam viewing session is schedule from 11 to 12 on Jan 24. We will schedule another one next Thursday at 12.
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 cs251@cs.mcgill.ca 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!

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

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

Other rules
Additional information and rules may be found in the slides of the first lecture.

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.