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 1pm2pm 
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.
 A 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 NPcompleteness,
 Approximation Algorithms,
 Randomized Algorithms,
 Online Algorithms.
Advice: For how to do well in the course, check out and try to follow Hamed's advice.
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:
OR
The grade for the assignments depends on
Assignments  35% 
Quizzes  5% 
Final exam  60% 
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
 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.
 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 oneday delays, and 20 points for twoday 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.
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 (45 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 inperson, closedbook and closednotes, 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 MaxFlow problem 
Chapter 7.1


2  Sep. 8  The MaxFlow MinCut theorem 
Chapter 7.2


3  Sep. 13  Choosing good augmenting paths 
Chapter 7.3


4  Sep. 15  Analysis of Scaling MaxFlow 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 
Chapter 7.10
Konig's Theorem (3.14) 

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 
Luca Trevisan's lecture 5
(Section 2) 
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  Duality, Fractional vertex cover, Fractional matching, Complementary slackness. 

13  Oct. 20  Duality and MaxFlowMinCut.  Ass. 2 due on Oct. 24 Ass. 3 posted 

14  Oct. 25  Part III Shortest Path problem as a linear program. The complexity classes P and NP. 
Chapter 8.3


15  Oct. 27  The complexity classes P, NP, CoNP, EXP, Efficient certifiers. 
Chapter 8.3, 8.9


16  Nov. 1  Polynomial reductions, CookLevin: NPcompleteness of SAT. 
Chapter 8.3, 8.9


17  Nov. 3  NPcompleteness of the Maximum Independent Set problem. 
Chapter 8.1, 8.2, 8.4

Ass. 3 due on Nov. 5 Ass. 4 posted 
18  Nov. 8  NPcompleteness of Max Clique, Vertex Cover, 3SAT. 
Chapter 8.2


19  Nov. 10  NPcompleteness of Set Cover, 3Colourability, kColourability, Hamiltonian cycle and path, Traveling Salesman Problem, SubsetSum. PSPACE, and QSAT 
Chapter 8.2, 8.5,
8.7, 8.8, 8.10, 9 

20  Nov. 15  Part IV
A simple approximation algorithm for Vertex Cover, A 2factor Approximation algorithm for Vertex Cover based on rounding LP. 
Chapter 11.1


21  Nov. 17  Approximation algorithms for Load balancing and the center selection problem. 
Chapter 11.1, 11.2

Ass. 4 due on Nov. 19 Ass. 5 posted 
22  Nov. 22  A PTAS Approximation algorithm for the Knapsack problem. 
Chapter 11.8


23  Nov. 24  
24  Nov. 29  
25  Dec. 1  Ass. 5 due on Dec. 3  
26  Dec. 6 
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)