Instructor: Prof. Jérôme Waldispühl (jerome.waldispuhl@mcgill.ca).

Teaching Assistants:

• Hossein Aboutalebi (hossein.aboutalebi@mail.mcgill.ca)
• Alexander Butyaev (alexander.butyaev@mail.mcgill.ca)
• Carlos Gonzalez Oliver (carlos.gonzalezoliver@mail.mcgill.ca)
• Antoine Soulé (antoine.soule@mail.mcgill.ca)
• Roman Sarrazin-Gendron (roman.sarrazingendron@mail.mcgill.ca)

Lectures: Tuesday & Thursday 11:35am to 12:55pm in Maass Chemistry Building 112.

Office hours:

Prof. Jérôme Waldispühl	Tue/Thu 13:00-14:00pm	ENGTR 3106
Hossein Aboutalebi	Wed 11:30-1:30	MC303
Alexander Butyaev	Mon 10-12	ENGTR 3110
Carlos Gonzalez Oliver	Wed 14-16	ENGTR 3110
Roman Sarrazin-Gendron	Fri 11-1	ENGTR 3110
Antoine Soulé	In charge of forum	Online!

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. 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 at https://osqa.cs.mcgill.ca/. You can automatically login into this forum using your SOCS login and password. If you do not have a SOCS account, you can create one at https://newuser.cs.mcgill.ca/ from any computer in the mcgill network. Please, note that you can access it only from the McGill network. If you are out of the campus, you will need to use the McGill VPN (kb.mcgill.ca/it/vpn).

Evaluation
Your final grade will be calculated as follows:

• 40% for 5 assignments
• 15% for the midterm
• 45% for the final exam

The exams are closed book. However, you will be allowed 4 pages of notes at the final exam. No electronic devices are allowed (this includes noise-cancelling headphones).

Release Date	Due Date	Announce
Apr 18th		Jérôme Waldispühl will hold hold office hours from 11am to 1pm.
Apr 15th		A final practice exam is now available. For your convenience, we provide two versions. One without answers (practice_final_COMP251_no_answers_W2017.pdf) and another one with solutions (practice_final_COMP251_with_answers_W2017.pdf).
Apr 6th	April 9th at 11:59pm	Fill the online form to suggest concepts and problems you would like to review during the review lecture.
Mar 28th	April 11th at 11:59pm	The fifth assignment is now available. We will accept late submissions of assignment 5 (only) until April 18th, without penalty. Later submissions will be refused.
Mar 28th	April 8th at 11:59pm	The fourth assignment is now available. We provide a template file Multiply.java for the programming question and a sample output output_HW4Q1.txt.
Mar 16th	March 26th	Assignment 3 due date has been postponed to March 26th, 11h59pm.
Mar 16th		The office hours of R. Sarrazin-Gendron are moved from 1pm to 3pm.
Mar 14th		The office hours of J. Waldispühl are moved from 3pm to 4pm.
Mar 8th		C. Gonzalez and R. Sarrazin-Gendron will hold their office hours this Wednesday from 2pm to 4pm in TR3110.
Mar 7th		The office hours of J. Waldispühl are extended to 3pm.
Mar 3rd		A mid-term practice exam is now available. For your convenience, we provide two versions. One without answers (practice_midterm_COMP251_W2017_no_answers.pdf) and another one with solutions (practice_midterm_COMP251_W2017_with_answers.pdf). Note: You will be allowed to bring one crib sheet (i.e. 2 pages) in letter or A4 format at the mid-term exam.
Mar 3rd		The final examination is scheduled on April 21st at 14h00.
Mar 1st	Mar 22th at 11:59pm	The third assignment is now available. You will use the template files BellmanFord.java, FordFulkerson.java, and WGraph.java (Note: this file has been updated after Assignment 2). We also provide you the test files: bf1.txt, bf2.txt, bf3.txt, bf4.txt, ff2.txt, and ff226000000.txt to help you to check your programs.
Mar 1st	Mar 5	Fill the survey to allow us to customize the review session on March 7.
Feb 12th	Feb 26th at 11:59pm	The second assignment is now available. You will use the template files DisjointSets.java, Kruskal.java, and WGraph.java. We also provide you the test files unionfind.txt, mst1.txt, and g1.txt to help you to check your programs.
Jan 26th		The first assignment and Java template file have been updated. Changes will not affect your previous answers, and you are welcome to use the previous template if you prefer. A description of the changes are indicated in this README file.
Jan 23rd		Office hours have been updated. Please, have a look at the updated schedule.
Jan 15th	Feb 1st at 11:59pm	The first assignment is now available. You will use the template file COMP251HW1.java and the jar file JavaPlotBuilder.jar. The files have been updated on Jan 21. Please, check that you use the last versions of the assignment and Java files. A description of the list of changes is available [HERE].
Jan 5th	Jan 8th at 11:59pm	Answer an anonymous quiz that will be used to calibrate the review session and the whole class during the semester.

	Date	Topic	Material	References
Lecture 0	Jan 5th	Introduction	[SLIDES] Answer an anonymous quiz
Lecture 1	Jan 10th	COMP250 review	[SLIDES]
Lecture 2	Jan 12th	Hashing	[SLIDES] & Online quiz	Chapter 11 of [CLRS2009]
Lecture 3	Jan 17th	Heaps & Heapsort	[SLIDES] & Online quiz	Chapter 6 of [CLRS2009]
Lecture 4	Jan 19th	BST and AVL trees	[SLIDES] & Online quiz
Lecture 5	Jan 24th	Red-black trees	[SLIDES] & Online quiz	Chapter 13 of [CLRS2009]
Lecture 6	Jan 26th	Disjoint sets	[SLIDES] & Online quiz	Chapter 21 of [CLRS2009]
Lecture 7	Jan 31th	Greedy algorithms (Scheduling, Huffman coding)	[SLIDES] & Online quiz	Chapter 16 of [CLRS2009]
Lecture 8	Feb 2nd	Elementary graph algorithms	[SLIDES] & Online quiz	Chapter 22 of [CLRS2009]
Lecture 9	Feb 7nd	Topological sort and strongly connected components	[SLIDES] & Online quiz	Chapter 22 of [CLRS2009]
Lecture 10	Feb 9th	Minimum Spanning Tree	[SLIDES] & Online quiz	Chapter 23 of [CLRS2009]
Lecture 11	Feb14th	Single source shortest path	[SLIDES] & Online quiz	Chapter 24 of [CLRS2009]
Lecture 12	Feb 16th	Bipartite graphs	[SLIDES] & Online quiz	Chapter 1.1 of [KT2006]
Lecture 13	Feb 21st	Network flow 1	[SLIDES] & Online Quiz	Chapter 26 of [CLRS2009]
Lecture 14	Feb 23rd	Network flow 2	[SLIDES] & Online Quiz	Chapter 26 of [CLRS2009]
STUDY BREAK
Midterm review	Mar 7th	Review session	[SLIDES] & Survey
Mid-term	Mar 9th	Cover all the material from Lecture 1 to 14. Note: Examination at regular class hours (11:35-12:55) in ADAMS Auditorium
Lecture 15	March 14th	Dynamic Programming 1 (weighted interval scheduling, Bellman-Ford)	[SLIDES]	Chapter 6 of [KT2006]
Lecture 16	Mar 16th	Dynamic Programming 2 (sequence alignment)	[SLIDES]	Chapter 6 of [KT2006]
Lecture 17	Mar 21st	Dynamic Programming 3 (Bellman Ford, knapsack problem)	[SLIDES] & Online Quiz	Chapter 6 of [KT2006]
Lecture 18	Mar 23rd	Divide-and-conquer 1 (Merge sort & integer multiplication)	[SLIDES] & Online Quiz	Chapter 5 of [KT2006]
Lecture 19	Mar 28	Divide-and-conquer 2 (Master Theorem)	[SLIDES] & Online Quiz	Chapter 4 of [CLRS2009]
Lecture 20	Mar 30th	Amortized analysis	[SLIDES] & Online Quiz	Chapter 17 of [CLRS2009]
Lecture 21	Apr 4th	Randomized algorithms (Global min-cut, randomized quick sort)	[SLIDES] & Online quiz	Chapter 13 of [KT2006]
Lecture 22	Apr 6th	Probabilistic analysis	[SLIDES]	Chapter 5 of [CLRS2009]
Lecture 24	Apr 11th	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, courses such as MATH 240, 363, or 235 are recommended (but not required).

Policy on discussion Board
We will use a new forum system available at: https://osqa.cs.mcgill.ca/ (i.e. we will not use the forum in MyCourse).
You will be automatically registered in this forum and will have the possibility to vote for the most useful questions and answers. Students with the most voted questions and answers (after validation by a moderator) will receive bonus points.
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 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 final grades
I will use the same formula for calculating your final grade for everyone. I 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. The first time that you return late your assignment, you will receive a penalty of 20% on your normal grade if and only if your assignment is returned less than 24h after the end of the deadline. In all other cases, your assignment will not be graded.
Assignments may include guiedlines 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. However, 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 on these machines.

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 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. See this link for more information.