Instructor |
Hamed Hatami | |

TA's |
Yi Tian Xu, Edward Smith, Scott Fujimoto, Mathieu Nassif, Dipanjan Dutta, Deven Parekh. Teaching assistants are mainly responsible for grading the assignments. | |

Lecture |
Monday-Wednesday 8:35-9:55 at STBIO S1/4 | |

Outline |
course outline | |

Office hours: |
See the calendar. Wednesdays 2:30-3:30pm in McConnell 308. If you want to meet outside office hours, the best thing is to send me an email, but you can also just drop by my office, and if I'm not busy I will answer your questions. | |

Textbook |
Jon Kleinberg and Eva Tardos, Algorithm Design, 2006 |

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

*Homework (20% = 5 x 4%).*
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 one-day delays, and -20 points for two-day 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.

*Final grade* is whichever of (Homework 20% + Midterm 20% + final 60%) or (Homework 20% + Midterm 10% + final 70%) that results in a better grade. However you must still receive a grade higher than 35% in the final exam in order to pass this course. Both midterm and final are closed-book, and closed-notes.

* Attendance and class participation:* Although not a formal component of the course grade, attendance is essential for success in this course. Active participation can effect your grade in a positive way.

Review |
||

Lecture |
Topic |
Reading |

1 | Background | |

Part I |
||

Lecture |
Topic |
Reading |

2 | The Ford-Fulkerson Algorithm | 7.1 |

3 | Max flow-Min cut Theorem, correctness of the Ford-Fulkerson | 7.2 |

4 | Choosing good augmenting paths, Optional reading: the fattest path algorithm |
7.3 |

5 | Bipartite matching, Konig's theorem Theorem 3.14 here. | 7.5 |

6 | Disjoint path problem (directed and undirected). | 7.6 |

7 | Further Applications of the Max-Flow problem: Baseball Elimination. | 7.12 |

8 | Further Applications of the Max-Flow problem: Project Selection | 7.11 |

Part II |
||

Lecture |
Topic |
Reading |

9 | Linear programming. Formulating problems as LPs. | Some examples. |

10 | geometric interpretation of LP's. | Sections 1 and 2 of Luca Trevisan's Lecture 5. |

11 | LP's in standard form, introduction to duality. |
Finishing Lecture 5 and starting Lecture 6 from Luca's notes. |

12 | midterm (Feb 14th) | |

13 | Strong duality. | Finishing Lecture 6 from Luca's notes. Dual in general. |

14 | Duality and MaxFlow-MinCut. Complementary slackness. | |

15 | No lecture. | |

16 | No lecture. | |

Part III |
||

Lecture |
Topic |
Reading |

17 | The complexity classes P, NP, CoNP, EXP. | 8.3, 8.9 |

18 | The complexity classes P, NP, CoNP, EXP, Polynomial reductions | 8.3, 8.9 |

19 | NP-completeness of SAT and Max Independent Set. | 8.1, 8.2, 8.4 |

16 | NP-completeness of Max Clique, Vertex Cover, 3SAT. | 8.2 |

17 | NP-completeness of Set Cover, 3-Colourability, k-Colourability. | 8.2, 8.7 |

18 | NP-completeness of Hamiltonian cycle and path, Traveling Salesman Problem, SubsetSum. | 8.5, 8.8, 8.10, 9 |

Part IV |
||

Lecture |
Topic |
Reading |

19 | PSPACE contains NP,CoNP, and is contained in EXP. A simple approximation algorithm for vertex cover. | 9, 11.1 |

20 | A 2-factor Approximation algorithm for Vertex Cover based on rounding LP. | this |

21 | Approximation algorithms for Load balancing and the center selection problem. | 11.1. 11.2 |

22 | A PTAS Approximation algorithm for the Knapsack problem. | 11.8 |

23 | An approximation algorithm for Set Cover. Online algorithms | Chapter 6 of these notes and Note's of Luca Trevisan |

- Assignment 1. The solution. Due: Jan 27th, 11:59pm.
- Assignment 2 and solutionDue: Feb 10th, 11:59pm.
- Midterm, Feb 14th in class. The exam covers everything up to (and including) the lecture of Feb 7th. Sample midterm 1 and Sample midterm 2. Here is the midterm and its solution.
- Assignment 3 and solution Due: March 10th, 11:59pm.
- Assignment 4 and solution Due: March 31st, 11:59pm.
- Assignment 5 and Solution Due: April 14th, 11:59pm.
- Sample final and its solution.
- For the final exam you are allowed to bring "One handwritten double-sided letter size sheet". The exam covers the material from Part II, III, and IV of the lectures, except for the online algorithms. I will hold two office hours next week (on Tuesday and Thursday). The exact times will be announced in the calendar. The solution to assignment 5 will be posted next week.

*Academic honesty.* 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 (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.