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

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:

Notes:

ANNOUNCES


Release DateDue DateAnnounce
Dec 5thThe 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 24thNov 27thThe Lecture of Nov 27th is cancelled. Carlos G. Oliver will give the last review lecture on Nov 29th.
Nov 24thWe 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 21thDec 5th (11:55pm)Assignment 5 is now available. All the test cases can be found in this zip file.
Nov 7thNov 21th (11:55pm)Assignment 4 is now available. You will need to complete the Java class Multiply.java and karatsuba.csv.
Oct 24thNov 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 13thOct 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 3rdOct 3rd (11h59)The first quiz is now available on MyCourses.
Sep 26thAn extra set of slides describing how to use ssh and scp is now available.
Sep 25thOct 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 5thSep 6thComplete the online quizz. It will not be graded. It is designed to help your reviewing the COMP250 material and customized the lectures.
Sep 4thWelcome in COMP 251!

SCHEDULE


DateTopicMaterialReferences
Lecture 0Sep 4thIntroduction[SLIDES]
Lecture 1Sep 6thCOMP250 review[SLIDES]
Lecture 2Sep 11thHashing[SLIDES]Chapter 11 of [CLRS2009]
Lecture 3Sep 13thHeaps & Heapsort[SLIDES]Chapter 6 of [CLRS2009]
Lecture 4Sep 18thBST and AVL trees[SLIDES]
Lecture 5Sep 20thRed-black trees[SLIDES]Chapter 13 of [CLRS2009]
TutorialSep 25thTutorial for programming questions[SLIDES]
Lecture 6Sep 27thDisjoint sets[SLIDES]Chapter 21 of [CLRS2009]
Lecture 7Oct 2ndGreedy algorithms (Scheduling, Huffman coding)[SLIDES]Chapter 16 of [CLRS2009]
Lecture 8Oct 4thElementary graph algorithms[SLIDES]Chapter 22 of [CLRS2009]
Lecture 9Oct 9thTopological sort and strongly connected components[SLIDES]Chapter 22 of [CLRS2009]
Lecture 10Oct 11thMinimum Spanning Tree[SLIDES]Chapter 23 of [CLRS2009]
Lecture 11Oct 16thSingle source shortest path[SLIDES]Chapter 24 of [CLRS2009]
Lecture 12Oct 18thBipartite graphs[SLIDES]Chapter 1.1 of [KT2006]
Lecture 13Oct 23rdNetwork flow 1[SLIDES]Chapter 26 of [CLRS2009]
Lecture 14Oct 25thNetwork flow 2[SLIDES]Chapter 26 of [CLRS2009]
Lecture 15Oct 30thDynamic Programming 1 (weighted interval scheduling)[SLIDES]Chapter 6 of [KT2006]
Lecture 16Nov 1stDynamic Programming 2 (Bellman Ford, knapsack problem)[SLIDES]Chapter 6 of [KT2006]
Lecture 17Nov 6thDynamic Programming 3 (Pairwise sequence alignment)[SLIDES]Chapter 6 of [KT2006]
Lecture 18Nov 8thDivide-and-conquer 1 (Merge sort & integer multiplication)[SLIDES]Chapter 5 of [KT2006]
Lecture 19Nov 13thDivide-and-conquer 2 (Master Theorem)[SLIDES]Chapter 4 of [CLRS2009]
Lecture 20Nov 15thAmortized analysis[SLIDES]Chapter 17 of [CLRS2009]
Lecture 21Nov 20thRandomized algorithms (Global min-cut, randomized quick sort)[SLIDES]Chapter 13 of [KT2006]
Lecture 22Nov 22ndProbabilistic analysis[SLIDES]Chapter 5 of [CLRS2009]
Nov 27thNo Class
Lecture 23Nov 29ndReview[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 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.

CONTACT


All request should be sent at:

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

Based on a template from BlackTie.co