COMP 360 - Algorithm Design
Term: Fall 2021,
Section: 001, online
Other section: The on campus session is offered by Hamed Hatami, check out his course webpage
Schedule: Monday, Wednesday from 02:35 pm - 03:55 pm
Prerequisites: Either COMP 251/COMP 252, and either MATH 240/MATH 235/MATH 363
Textbook: Jon Kleinberg and Eva Tardos, Algorithm Design, 2006
Instructor information
Name: Lianna Hambardzumyan
Email: lianna [dot] hambardzumyan [at] mail.mcgill.ca
Office hours: online, Thursdays 1pm-2pm
Office: MC 303
  • If you want to meet outside office hours, write me an email, or drop by my office - if I am there I'll answer your questions.
  • Any feedback, concerns, or suggestions are more than welcome!
  • I understand that the pandemic has brought and continues bringing challenges into our lives, therefore if you feel overloaded with the amount of work for this course, you feel burned out or you feel anxious about some of the assessments, I encourage you to contact me so that we can address the concerns together. You are probably not alone feeling that way!
TAs information
Name: Stefan Grosser (stefan.grosser@mail.mcgill.ca),
Tal Elbaz (tal.elbaz@mail.mcgill.ca),
Tsun Ming Cheung (tsun.ming.cheung@mail.mcgill.ca),
Zhong Sheng Hu (zhong.s.hu@mail.mcgill.ca),
Zhangyuan Nie (zhangyuan.nie@mail.mcgill.ca),
Zhang Yong (yong.zhang3@mail.mcgill.ca),
Zedian Xiao (zedian.xiao@mail.mcgill.ca)
Shiyue Liu (shiyue.liu@mail.mcgill.ca)
Office hours: Stefan Grosser - Mondays 10am - 12pm
Tal Elbaz - Fridays 11am - 1pm
  • All the TAs, except Stefan and Tal, are mainly responsible for grading the assignments and for regrading requests. If you have questions email me or post on the discussion board on MyCourses.
Course Description
This course is an undergraduate course on advanced algorithmic techniques and applications. Topics include
  • Network Flows,
  • Linear programming,
  • Complexity and NP-completeness,
  • Approximation Algorithms,
  • Randomized Algorithms,
  • Online Algorithms.
This is a rigorous course with an emphasis on mathematical proofs rather than implementations. You must be comfortable with basic concepts from discrete math, linear algebra, and you must be able to read and write precise mathematical statements. Here are some questions that can help you decide if you have the background to take this course. If you have trouble understanding or answering these questions, in order to succeed in this course, you need to improve your background before enrolling in this course.
Advice: For how to do well in the course, check out and try to follow Hamed's advice.
Final Exam
  • There will a review session on Dec. 13th.
  • The final will have 2 questions for each part of the course: Network flows, Linear Programming, Complexity theory, Approximation Algorithms (Lecture 1-25, the last lecture won't be covered)
  • This is what is allowed to have on the exam: Front page
  • Here are some midterm and final samples, and review materials. Note that the midterm samples cover Network flows and Linear Programming. Final samples cover Complexity theory and Approximation Algorithms. However, our final will cover all the topics. (More problems from the book and other sources will be added soon.)
Grading
The assessment will be based on 5 assignments, x quizzes and a final exam. The final grade will be the best (max) grade resulted from the following two schemes:
Assignments 35%
Quizzes 5%
Final exam 60%
OR
Assignments 25%
Quizzes 5%
Final exam 70%
Note: you must receive higher than 30% on the final exam to pass the course.
Assignments
Each assignment will be posted on the course web page. The grades will be posted on myCourses. You are highly encouraged to work on the problems with each other, however each person should turn in their own formulation of the answer, and, in that case, you need to write down the group of people you worked with on the assignment.
The grade for the assignments depends on
  1. correctness and not effort alone - only the correct answers will get 100% of the marks. If you know your answer is not correct and probably doesn't contain a correct idea, then please don't waste TAs' time.
  2. readability of your solution - you are very much encouraged to use LaTeX. Otherwise, please make sure the assignment is readable according to some common sense (you and your 10 year old brother can read it) - the TAs are allowed to deduct marks or not to grade the assignment.
Late assignment policy. Late homeworks can be submitted until 48 hours after the deadline. There will be a penalty of -10 (out of 100) points for one-day delays, and -20 points for two-day delays on late homeworks.
Extension policy. To guarantee fairness, extensions for homework deadlines will be granted only for the reasons which were out of your control. Such reasons include, but are not limited to: Student illness (mental/physical), Family/partner illness, Death of a person with whom the student has a similarly close relationship, Religious Observances, Pregnancy, Delivery of a child, Parenting issues. In this case, contact me (not the TAs), and do not feel obliged to share any trauma or show any proof - we'll operate under the honor system.
For the reasons which were under your control, extensions will not be granted, for example, Travel/vacation/social plans, Airline flights and schedules, Other assignments and exams due on or about the due date.
Honesty. Work submitted for this course must represent your own efforts. Copying assignments, quizzes or exams from any source (including the book or the "hidden" corners of almighty google), completely or partially, allowing others (including your best friend) to copy your work, will not be tolerated, and they will be reported to disciplinary office.
Quizzes
These are going to be easy, mainly to make sure you are not completely lost in the course. There will be a quiz for each part of the course (4-5 quizzes). You will be given a week to complete the quiz. All the deadlines for the quizzes of the first lectures will be after the add/drop deadline. Late quizzes will be graded with the same policy as the late assignments.
Final
The final exam is going to be in-person, closed-book and closed-notes, however crib sheets will be allowed.
Midterm
No midterm.
Course Schedule (To be updated as we go, the last lecture is highlighted by grey)
Class Date Topic Material Assignments due
1 Sep. 1
Part I
The Max-Flow problem
Chapter 7.1
2 Sep. 8 The Max-Flow Min-Cut theorem
Chapter 7.2
3 Sep. 13 Choosing good augmenting paths
Chapter 7.3
4 Sep. 15 Analysis of Scaling Max-Flow algorithm,
Networks with multiple sources,
Bipartite matchings
Chapter 7.3, 7.5
 Ass. 1 posted on Sep. 17
5 Sep. 20 Bipartite matchings,
Disjoint path problem (directed).
Chapter 7.6
6 Sep. 22 Disjoint path problem (directed).
Menger's theorem.
Chapter 7.6
7 Sep. 27 Image Segmentation, Konig's theorem
8 Sep. 29
Part II
Linear programming. Formulating problems as LPs.
Tim Roughgarden's lecture 7
(Section 1 & 2 & 3.1)
Ass. 1 due on Oct. 1
9 Oct. 4 Geometric interpretation of LP's, Simplex Method Ass. 2 posted
10 Oct. 6 Simplex method, LP's in standard form,
introduction to duality.
Luca Trevisan's lecture 5
(Section 2.3 & 3)
11 Oct. 14 Weak duality, Strong duality.
12 Oct. 18 The Dual of MaxFlow problem,
Complementary slackness.
Tim Roughgarden's
lecture 8 and lecture 9
13 Oct. 20 Complementary slackness.
Part III
The complexity class P.
Chapter 8.3
 Ass. 2 due on Oct. 24
Ass. 3 posted
14 Oct. 25 The complexity classes NP, EXP,
Efficient certifiers, P vs. NP
Chapter 8.3
15 Oct. 27 Examples of problems in NP,
Polynomial reductions
Chapter 8.3, 8.1
16 Nov. 1 Polynomial reductions,
Independent Set, Vertex Cover
Chapter 8.1
17 Nov. 3 3-SAT reduces to Independent Set
Chapter 8.2
 Ass. 3 due on Nov. 7
Ass. 4 posted
18 Nov. 8 Cook-Levin: NP-completeness of SAT.
NP-completeness of Hamiltonian Cycle problem.
Chapter 8.4, 8.5
19 Nov. 10 Hamiltonian cycle and path,
Traveling Salesman Problem(TSP).
Chapter 8.5
20 Nov. 15 NP-completeness of TSP,
3-Colourability, k-Colourability,
Subset-Sum, Knapsack Problem
Integer Programming.
Chapter 8.5, 8.7, 8.8, 8.10
21 Nov. 17
Part IV
Approximation Algorithms,
A greedy approximation algorithm for Vertex Cover,
Load balancing: A greedy approximation algorithm
Chapter 11.1
 Ass. 4 due on Nov. 21
Ass. 5 posted
22 Nov. 22 Load balancing,
Weighted Vertex Cover: LP relaxation algorithm
Chapter 11.1, 11.6
23 Nov. 24 The center selection problem.
Chapter 11.2
24 Nov. 29 Weighted Set Cover.
Chapter 11.3
25 Dec. 1 Weighted Set Cover.
A PTAS Approximation algorithm for the Knapsack problem.
Chapter 11.3, 11.8
26 Dec. 6 A PTAS Approximation algorithm for the Knapsack problem.
How to prepare for the final
Chapter 11.8
Course Policies
Academic integrity. McGill University values academic integrity. Therefore, all students must understand the meaning and consequences of cheating, plagiarism and other academic offences under the Code of Student Conduct and Disciplinary Procedures. (Approved by Senate on 29 January 2003) (See McGill's guide to academic honesty for more information.)
Language of submission. In accord with McGill University's Charter of Student Rights, students in this course have the right to submit in English or in French any written work that is to be graded. This does not apply to courses in which acquiring proficiency in a language is one of the objectives. (Approved by Senate on 21 January 2009)