Introduction to algorithm design and analysis. Graph algorithms, greedy algorithms, data structures, dynamic programming, maximum flows.

GENERAL INFORMATION


Instructors: Giulia Alberini and Prof. Jérôme Waldispühl.

Teaching Assistants:

Lectures: Adams Auditorium on Tuesday & Thursday at 10am (EDT). The lecture will be recorded and available on MyCourses.

Contact: All course-related email 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.

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:
We are using Ed for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TAs, and instructors. Rather than emailing questions to the teaching staff, we encourage you to post your questions there. The official discussion board for this class is Ed. You must Login to the platform via MyCourses.

Evaluation
Your final grade will be calculated as follows:

ANNOUNCES


Release DateDue DateAnnounce
Nov 18Dec 5, 2022 (11h59am)Assignment 3 is now released! You can download the problem set here. You will have to submit your answers on Crowdmark.
Note: The deadline has been extended to Dec. 5 at 11h59pm.
Oct 24Nov 14, 2022 (11h59am)Assignment 2 is now released! You can download the problem set here. You will have to submit your answers on Crowdmark.
Note: The deadline has been extended from Nov. 10 to Nov. 14 noon.
Sep 23Oct 15, 2022 (11h55pm)Assignment 1 is now released! You can download the problem set here. You will have to submit your answers on Crowdmark.
Sep 1Welcome in COMP 251! A link is available on MyCourses. The class will be recorded and available of streaming later. Online office hours will be arranged and announced in due time.

SCHEDULE


DateTopicMaterialReferencesInstructor
Lecture 0Sep 1Introduction[SLIDES]J. Waldispühl
Lecture 1Sep 6Recurrences[SLIDES]Chapter 4 of [CLRS2009]J. Waldispühl
Lecture 2Sep 8Big Oh notation[SLIDES]Chapter 3 of [CLRS2009]J. Waldispühl
Lecture 3Sep 13Proofs by induction and loop invariants[SLIDES]J. Waldispühl
Lecture 4Sep 15Graphs, Probability and Binary numbers[SLIDES]G. Alberini
Lecture 5Sep 20Heaps & Heapsort[SLIDES]Chapter 6 of [CLRS2009]G. Alberini
Lecture 6Sep 22BST and AVL trees[SLIDES]G. Alberini
Lecture 7Sep 27Red-black trees[SLIDES]Chapter 13 of [CLRS2009]J. Waldispühl
Lecture 8Sep 29Hashing[SLIDES]Chapter 11 of [CLRS2009]J. Waldispühl
Lecture 9Oct 4Disjoint sets[SLIDES]Chapter 21 of [CLRS2009]J. Waldispühl
Lecture 10Oct 6Greedy algorithms (Scheduling, Huffman coding)[SLIDES]Chapter 16 of [CLRS2009]J. Waldispühl
Reading BreakOct 11
Lecture 11Oct 14Elementary graph algorithms[SLIDES]Chapter 22 of [CLRS2009]G. Alberini
Lecture 12Oct 18Topological sort and strongly connected components[SLIDES]Chapter 22 of [CLRS2009]G. Alberini
Lecture 13Oct 20Single source shortest path[SLIDES]Chapter 24 of [CLRS2009]G. Alberini
Lecture 14Oct 25Minimum Spanning Tree[SLIDES]Chapter 23 of [CLRS2009]G. Alberini
Lecture 15Oct 27Bipartite graphs[SLIDES]Chapter 1.1 of [KT2006]G. Alberini
Midterm ExamNov 1Mid-term ExaminationOnline during the regular class hours (10am-11:30am EDT)
Lecture 16Nov 3Network flow 1[SLIDES]Chapter 26 of [CLRS2009]J. Waldispühl
Lecture 17Nov 8Network flow 2[SLIDES]Chapter 26 of [CLRS2009]J. Waldispühl
Lecture 18Nov 10Dynamic Programming 1 (weighted interval scheduling)[SLIDES]Chapter 6 of [KT2006]J. Waldispühl
Lecture 19Nov 15Dynamic Programming 2 (Bellman Ford, knapsack problem)[SLIDES]Chapter 6 of [KT2006]J. Waldispühl
Lecture 20Nov 17Amortized analysis[SLIDES]Chapter 17 of [CLRS2009]J. Waldispühl
Lecture 21Nov 22Divide-and-conquer 1 (Merge sort & integer multiplication)[SLIDES]Chapter 5 of [KT2006]G. Alberini
Lecture 22Nov 24Divide-and-conquer 2 (Master Theorem)[SLIDES]Chapter 4 of [CLRS2009]G. Alberini
Lecture 23Nov 29Randomized algorithms (Global min-cut, randomized quick sort)[SLIDES]Chapter 13 of [KT2006]G. Alberini
Lecture 24Dec 1Probabilistic analysis[SLIDES]Chapter 5 of [CLRS2009]G. Alberini
Final ExamTBDFinal ExaminationIn-person formal exam (Full details available at the Exam office)

RULES & POLICIES


Prerequisites
The official prerequisites for this course are COMP 250 (Introduction to Computer Science) and MATH 240 (Discrete Structures) or MATH 235 (Algebra 1). We recommend the students to review the material covered in this class. The students must also be familiar with basic concepts and techniques in probability.

Policy on discussion Board
The official discussion board is accessible on Ed. 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. Please, note that regrading may also eventually result in a lower grade.

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. Yet, we will release the evaluation material (e.g., assignments) ahead of time to allow you to organize your schedule. It is your responsability to accomodate the deadlines.
The only exceptions will be medical exceptions. When appropriate, we might ask a medical note. It is important to inform the instructors as early as possible. Failure to do so, may result 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 not be graded.
Assignments may include guidelines and require particular formatting procedures. Solutions that do not follow the required format may not be graded.
The quality of the presentation of your answers 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.

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

CONTACT


All request should be sent at:

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

Based on a template from BlackTie.co