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

Teaching Assistants:

• David Becerra Romero (david.becerraromero@mail.mcgill.ca)
• Alexander Butyaev (alexander.butyaev@mail.mcgill.ca)
• Vladimir Reinharz (vladimir.reinharz@mail.mcgill.ca)
• Antoine Soulé (antoine.soule@mail.mcgill.ca)
• Jing Zhu (jing.zhu3@mail.mcgill.ca)

Lectures: Monday & Wednesday 11:35am to 12:55pm in MDHAR G-10.

Office hours:

Prof. Jérôme Waldispühl	Mon 13:45-15:15pm	ENGTR 3106
David Becerra Romero	Thu 11:00-1:00pm	ENGTR 3150
Alexander Butyaev	Fri 2:00-4:00pm	ENGTR 3140
Antoine Soulé	In charge of forum	Online!
Vladimir Reinharz	Mon 9:00-11:00am	ENGTR 3140
Jing Zhu	Thu 2:00-4:00pm	MC 229

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://cs251qanda.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.

Evaluation
Your final grade will be calculated as follows:

• 40% for 5 assignments
• 10% for the midterm
• 50% 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		You can now access a collection of problems to practice for the final exam.
Apr 18th		J. Waldispühl will hold extra office hours on Monday from 1:30 to 3:00
Apr 6th	Apr 14th at 11:59pm	Assignment 5 is out!
Mar 28th	Mar 30th at 11:59pm	The choice is yours! Answer the survey and give your preferences for the topics to be covered in the last lectures.
Mar 28th	Mar 30th at 11:30am	Answer the questions of the lecture 20 anonymous quiz.
Mar 23rd	Mar 25th at 11:30am	Answer the questions of the lecture 19 anonymous quiz.
Mar 22nd	Mar 23rd at 11:30am	Answer the questions of the lecture 18 anonymous quiz.
Mar 20th	Apr 2nd at 11:59pm	Assignment 4 is out! Additional Java files: Multiply.java, JavaPlotBuilder.jar
Mar 16th	Mar 18th at 11:30am	Answer the questions of the lecture 17 anonymous quiz.
Mar 14th	Mar 16th at 11:30am	Answer the questions of the lecture 16 anonymous quiz.
Mar 10th	Mar 11th at 11:30am	Answer the questions of the lecture 14-15 anonymous quiz.
Mar 4th	Mar 18th at 11:59pm	Assignment 3 is out! Additional Java files: FordFulkerson.java, WGraph.java, BellmanFord.java, ff2.txt, ff226000000.txt, and bf1.txt, bf2.txt, bf3.txt, bf4.txt
Feb 21st		You can now access a collection of problems to practice for the midterm exam.
Feb 19th	Feb 23rd at 11:30am	Answer the questions of the lecture 13 anonymous quiz.
Feb 16th	Feb 18th at 11:30am	Answer the questions of the lecture 12 anonymous quiz.
Feb 11th	Feb 16th at 11:30am	Answer the questions of the lecture 11 anonymous quiz.
Feb 9th	Feb 11th at 11:30am	Answer the questions of the lecture 10 anonymous quiz.
Feb 6th	Feb 20th at 11:59pm	Assignment 2 is out! Additional Java files: DisjointSets.java, WGraph.java, Kruskal.java, unionfind.txt, g1.txt, and mst1.txt
Feb 6th	Feb 9th at 11:30am	Answer the questions of the lecture 9 anonymous quiz.
Feb 2nd	Feb 4th at 11:30am	Answer the questions of the lecture 8 anonymous quiz.
Jan 30th	Feb 2nd at 11:30am	Answer the questions of the lecture 7 anonymous quiz.
Jan 29th	Feb 4th at 11:59am	Assignment 1 has been updated. We provide more information to complete question 1. In consequence, the deadline to submit your answers has been postponed to Wednesday February 4th.
Jan 26th	Jan 28th at 11:30am	Answer the questions of the lecture 6 anonymous quiz.
Jan 22nd	Jan 26th at 11:30am	Answer the questions of the lecture 5 anonymous quiz.
Jan 20th	Feb 4th at 11:59pm	Assignment 1 is out! Additional Java files: COMP251HW1.java and JavaPlotBuilder.jar
Jan 19th	Jan 21st at 11:30am	Answer the questions of the lecture 4 anonymous quiz.
Jan 15th	Jan 19th at 11:30am	Answer the questions of the lecture 3 anonymous quiz.
Jan 13th	Jan 14th at 11:30am	Answer the questions of the lecture 2 anonymous quiz.
Jan 12th		The forum is now online at https://cs251qanda.cs.mcgill.ca/. You can automatically login into this forum using your SOCS login and password.
Jan 5th	Jan 6th at 6pm	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	Survey completed. Please visit the slide of Lecture 1 to review the questions and answers.
Lecture 1	Jan 7th	COMP250 review	Slides: [1/page] or [6/page]
Lecture 2	Jan 12th	Hashing	Slides: [1/page] or [6/page] & Online quiz	Chapter 11 of [CLRS2009]
Lecture 3	Jan 14th	Heaps & Heapsort	Slides: [1/page] or [6/page] & Online quiz	Chapter 6 of [CLRS2009]
Lecture 4	Jan 19th	BST and AVL trees	Slides: [1/page] or [6/page] & Online quiz
Lecture 5	Jan 21th	Red-black trees	Slides: [1/page] or [6/page] & Online quiz	Chapter 13 of [CLRS2009]
Lecture 6	Jan 26th	Disjoint sets	Slides: [1/page] or [6/page] & Online quiz	Chapter 21 of [CLRS2009]
Lecture 7	Jan 28th	Greedy algorithms (Scheduling, Huffman coding)	Slides: [1/page] or [6/page] & Online quiz	Chapter 16 of [CLRS2009]
Lecture 8	Feb 2nd	Strongly connected component (SCC), topological ordering	Slides: [1/page] or [6/page] & Online quiz	Chapter 22 of [CLRS2009]
Lecture 9	Feb 4th	Minimum Spanning Tree	Slides: [1/page] or [6/page] & Online quiz	Chapter 23 of [CLRS2009]
Lecture 10	Feb 9th	Single source shortest path	Slides: [1/page] or [6/page] & Online quiz	Chapter 24 of [CLRS2009]
Lecture 11	Feb 11th	Bipartite graphs	Slides: [1/page] or [6/page] & Online quiz	Chapter 1.1 of [KT2006]
Lecture 12	Feb 16th	Network flow 1	Slides: [1/page] or [6/page] & Online Quiz	Chapter 26 of [CLRS2009]
Lecture 13	Feb 18th	Network flow 2	Slides: [1/page] or [6/page] & Online Quiz	Chapter 26 of [CLRS2009]
Lecture 14	Feb 23rd	Dynamic Programming 1 (weighted interval scheduling, Bellman-Ford)	Slides: [1/page] or [6/page]	Chapter 6 of [KT2006]
	Feb 25th	Mid-term
STUDY BREAK
Lecture 15	Mar 9th	Dynamic Programming 2 (sequence alignment, knapsack problem)	Slides: [1/page] or [6/page] & Online Quiz	Chapter 6 of [KT2006]
Lecture 16	Mar 11th	Divide-and-conquer 1 (Merge sort & integer multiplication)	Slides: [1/page] or [6/page] & Online Quiz	Chapter 5 of [KT2006]
Lecture 17	Mar 16th	Divide-and-conquer 2 (Master Theorem)	Slides: [1/page] or [6/page] & Online Quiz	Chapter 4 of [CLRS2009]
Lecture 18	Mar 18th	Divide-and-conquer 3 (Fast Fourier Transform)	Slides: [1/page] or [6/page] & Online Quizz	Chapter 5 of [KT2006]
Lecture 19	Mar 23rd	Amortized analysis	Slides: [1/page] or [6/page] & Online Quiz	Chapter 17 of [CLRS2009]
Lecture 20	Mar 25th	Randomized algorithms (Global min-cut, randomized quick sort)	Slides: [1/page] or [6/page] & Anonymous quiz	Chapter 13 of [KT2006]
Lecture 21	Mar 30th	Probabilistic analysis	Slides: [1/page] or [6/page]	Chapter 5 of [CLRS2009]
Lecture 22	Apr 1st	Data compression	Slides: [1/page] or [6/page]
Lecture 23	Apr 8th	Pattern Matching	Slides: [1/page] or [6/page]
Lecture 24	Apr 13th	Review	Slides: [1/page] or [6/page]

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://cs251qanda.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. If it is the first time that you return late your assignment, you will receive a penalty of 20% on your normal grade if your assignment is returned late the same day. In all other cases, your assignment will be refused and not graded. Solutions that do not follow the required format will be refused.
The quality of the presentation of your solution is important. Unreadable material, cryptic notations, or bad organization of the material will results 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.