Instructor  Hamed Hatami  
TA's  Teaching assistants (Tsun Ming Cheung, Benjamin Davis, Yingzi Xu, Zhong Sheng Hu) are mainly responsible for grading the assignments.  
Lecture  112 Maass Chemistry Building 14:3515:55 (WednesdayFriday)  
Office hours:  (Hamed MC 308) Wednesdays 16:0517:00. (Tsun Ming Cheung MC 303) Tuesdays 12:0013:00 (Ben Davis MC 303) Fridays 16:0017:00 

Textbook  Jon Kleinberg and Eva Tardos, Algorithm Design, 2006  
Recording  Lectures are going to be recorded so that the students can review them later. 
This course is an undergraduate course on advanced algorithmic techniques and applications. Topics include Network Flows, Linear programming, Semidefinite programming, Complexity and NPcompleteness, Approximation Algorithms, Randomized Algorithms, and Online Algorithms.
This is a rigorous course with an emphasis on mathematical proofs rather than implementations. The prerequisites are Comp 251 and one of Math 240/Math 235/Math 363. You must be comfortable with basic concepts from 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.
Surprise Quizzes (10%): There will be 5 surprise quizzes in the class. The purpose of these short quizzes is to enforce attendance and also to provide a practice for the final exam. These quizzes will not be graded and participation in them will suffice. Each quiz is worth 2.5% (with a maximum total 10%). Therefore, you only need to take 4 quizzes to receive the full 10%.
Homework (15% = 5 x 3%). There will be five homework assignments. The due dates are going to be announced. The homework and the exams will be graded based on correctness rather than effort alone. Each assignment will be posted on the course web page. Your grades will be posted on mycourses.
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 unless a valid reason is provided by the student. Some personal circumstances for which accommodation may be warranted include, but are not limited to: Student illness (mental/physical), Family/partner illness, Death in the immediate family or of a person with whom the student has a similarly close relationship, Religious Observances, Pregnancy, Delivery of a child, Parenting issues.
The following are reasons for which an extension request will normally NOT be granted: Employment reasons, Travel/vacation/social plans, Airline flights and schedules, Other assignments and exams due on or about the due date.
Midterm (15% ). There will be an inclass midterm.
Final grade is (Homework 15% + Midterm 15% + Quizzes 10% + Final exam 60%). However you must still receive a grade higher than 30% in the final exam in order to pass this course. Both midterm and final are closedbook, and closednotes.
Class participation: Although not a formal component of the course grade, active participation can effect your grade in a positive way.
Your (i) background, your (ii) efforts, and more importantly (iii) the efficiency of your efforts will be the main determining factors on how well you will master the subject.
The grades are to give you some feedback, but you are the only person who can interpret them. They have some correlation with how well you have understood and learned the subject (that is why people will look at your grades, and GPA), but by no means this is definite. Some people are good at exams, and some are not, and we all have good days and bad days. Your main goal should be to acquire and improve your relevant problem solving skills rather than obtaining a good grade. The good grade hopefully will be a consequence of that.
Review  
Part I  
Lecture  Topic  Reading 
1  The FordFulkerson Algorithm  7.1 
2  Max flowMin cut Theorem, correctness of the FordFulkerson  7.2 
3  Choosing good augmenting paths (Scaling FF), Bipartite matching  7.3 
4  Konig's theorem Theorem 3.14 here., Disjoint path problem (directed).  7.5, 7.6 
5  Multi Source/Sink, Circulation with demands, Airline scheduling.  7.7, 7.9 
6  Project Selection  7.11 
Part II  
Lecture  Topic  Reading 
7  Linear programming. Formulating problems as LPs.  Some examples. 
8  geometric interpretation of LP's.  Sections 1 and 2 of Luca Trevisan's Lecture 5. 
9  LP's in canonical form, introduction to duality. 
Finishing Lecture 5 and starting Lecture 6 from Luca's notes. 
10  Strong duality.  Finishing Lecture 6 from Luca's notes. Dual in general. 
11  Duality, Maxflow mincut and duality, Minimum Cost Unitflow.  Some examples of duality. 
Part III  
Lecture  Topic  Reading 
12  The complexity classes P and NP.  8.3 
13  The complexity classes P, NP, EXP, Efficient certifiers, reductions.  8.3, 8.9 
14  Polynomial reductions, CookLevin: NPcompleteness of SAT.  8.3, 8.9 
15  NPcompleteness of the Maximum Independent Set problem, Max Clique, Vertex Cover, Set Cover.  8.1, 8.2, 8.4 
16  NPcompleteness of 3SAT, 3Colourability, kColourability.  8.2, 8.5, 8.7, 8.8, 8.10, 9. 
17  NPcompleteness of Hamiltonian cycle and path, Traveling Salesman Problem, SubsetSum, Knapsack, Integer programming.  8.2, 8.5, 8.7, 8.8, 8.10 
Part VI  
Lecture  Topic  Reading 
18  A simple approximation algorithm for vertex cover, A 2factor Approximation algorithm for Vertex Cover based on rounding LP. Approximation algorithms for Load balancing and the center selection problem.  11.1, and this 11.1. 11.2 
19  Approximation algorithms for Set cover.  11 
20  A PTAS Approximation algorithm for the Knapsack problem.  11.8 
21  Randomized algorithm for matrix multiplication. Union bound and satisfying an mCNF with less than 2^m clauses.  
2223  Randomized algorithm for MAXSAT.  MAXSAT 
Academic honesty. 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 (see http://www.mcgill.ca/integrity for more information). Most importantly, work submitted for this course must represent your own efforts. Copying assignments or tests from any source, completely or partially, allowing others to copy your work, will not be tolerated, and they will be reported to disciplinary office.
Submission of written work in French. In accord [sic] 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.