Instructor |
Hamed Hatami | |

TA |
Liana Yepremyan, Xing Shi Cai. TAs are only responsible for grading, and you should only contact them regarding the grading of your assignment and exams. | |

Lecture |
Monday-Wednesday 11:35 AM-12:55 PM in MCMED 1034 | |

Outline |
course outline | |

Office hours |
Monday-Wednesday 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.

*Homework (20% = 5 x 4%).*
There will be six biweekly homework assignments, and your five highest grades will count towards your overall grade. The due dates are going to be announced. No late homework will be accepted (as your lowest score on an assignment will be dropped). The homework will be graded based on correctness rather than effort alone. Each assignment will be posted on the course web page. The homework must be submitted to the drop-off box at Trottier building before the deadline. Your grades will be posted on mycourses.

*Midterm (20%) and final (60%).* There will be two exams: a midterm and a final exam. The exams 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(1/11) | Running Time and Big O notation | |

2(1/13) | Dynamic programming | 6.4 |

Part I |
||

Lecture |
Topic |
Reading |

3(1/18) | The Ford-Fulkerson Algorithm | 7.1 |

4(1/20) | Max flow-Min cut Theorem, correctness of the Ford-Fulkerson | 7.2 |

5(1/25) | Choosing good augmenting paths, Optional reading: the fattest path algorithm |
7.3 |

6(1/27) | Bipartite matching, Konig's theorem Theorem 3.14 here. | 7.5 |

7(2/1) | Disjoint path problem (directed and undirected). | 7.6 |

8(2/3) | Further Applications of the Max-Flow problem | 7.12 |

Part II |
||

Lecture |
Topic |
Reading |

9(2/8) | Linear programming. Formulating problems as LPs, geometric interpretation of LPs. |
This and Luca Trevisan's Lecture 5. |

10(2/15) | LP's in standard form, introduction to duality. |
Finishing Lecture 5 and starting Lecture 6 from Luca's notes. |

11(2/17) | Strong duality, duality and MaxFlow-MinCut. | Finishing Lecture 6 from Luca's notes. Dual in general. Section 1.5 here |

12(2/22) | Midterm Group I. | |

13(2/24) | Midterm Group II. | |

Part III |
||

Lecture |
Topic |
Reading |

14(7/3) | The complexity classes P, NP, CoNP, EXP. | 8.3, 8.9 |

15(9/3) | NP-completeness of SAT and Max Independent Set. | 8.1, 8.2, 8.4 |

16(14/3) | NP-completeness of Max Clique, Vertex Cover, 3SAT. | 8.2 |

17(16/3) | NP-completeness of Set Cover, 3-Colourability, k-Colourability. | 8.2, 8.7 |

18(21/3) | NP-completeness of Hamiltonian cycle and path, Traveling Salesman Problem, SubsetSum. PSPACE contains NP,CoNP, and is contained in EXP, and QSAT is in PSPACE. | 8.5, 8.8, 8.10, 9 |

Part IV |
||

Lecture |
Topic |
Reading |

19(23/3) | Approximation algorithms for Load balancing and vertex cover. | 11.1 |

20(30/3) | Approximation algorithm for the center selection problem, and a 2-factor Approximation algorithm for Vertex Cover based on rounding LP. | 11.2 and this |

21(4/4) | Approximation algorithm for the Set Cover problem. | Chapter 6 of these notes |

22(6/4) | Approximation algorithm for the Knapsack problem. | 11.8 |

23(11/4) | Randomized algorithms: Verifying matrix multiplication (Not in the final exam) | Freivalds' algorithm |

24(13/4) | Online algorithms (Not in the final exam) |

*Midterm:* The midterm covers flow networks and linear programming. If your student id ends in an even number (for example 260000000), you will be taking the exam on Monday 22nd, and if it ends in an odd number (for example 260000001) you will be taking it on Wednesday 24th. If you are registered to take the exam with OSD, then your exam is on 22nd regardless of your student id. Here is the exam from the previous semester: link. (We have not covered the complementary slackness yet, so it won't be in this semester's exam).

- Assignment 1 Due: 6:00pm Jan 28th. Solution.
- Assignment 2 Due: 6:00pm Feb 10th. Solution.
- Midterm: Feb 22nd. Group Even. Solution to midterm I
- Midterm: Feb 24th. Group Odd. Solution to midterm II
- Assignment 3 Due: 6:00pm Feb 29th. Solution.
- Assignment 4 Due: 6:00pm Mar 16th. Solution.
- Assignment 5 Due: 6:00pm Mar 30th. Solution.
- Assignment 6 Due: 6:00pm April 13th. Solution.
- Sample final and its solution.

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

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