COMP 360: Algorithm Design Techniques (Fall 2012)
Announcement
- Office hours to see your final exam: Monday Dec 17th 2:00-4:00.
- Instructor: Hamed Hatami
- Office: Room 328, McConnell Building
- Contact: hatami (at) cs (dot) mcgill (dot) ca
- Lecture: TR 2:35 - 3:55 pm, Trottier Building 1090
- Office Hours: TR 4:00-5:00 pm McConnell 328, or by appointment (email me)
Teaching Assistants
- Xing Shi Cai
- Anil Ada
Practice Material for Final Exam
- Please go and fill the evaluation forms.
- sample final exam. The solution.
- A final exam.
- Two assignments on NP-completeness: One and Two. The solution to one and two.
- Another final exam.
Schedule
- Assignment 1. Due: 6pm Sept 28th. Solution.
- Midterm is on Oct 11th (Covers flow problems, and modelling problems as linear programs). Solution.
- Assignment 2. Due: 6pm Oct 19th. Solution.
- Assignment 3. Due: 6pm Nov 2nd. Solution.
- Assignment 4 (You may use the NP-completeness of SAT, 3SAT, Independent Set, Clique, Vertex cover, k-colorability for k>=3, Hamiltonian cycle, Hamilton path, Subsetsum, Travelling Salesman Problem). Due: 6pm Nov 16th. Solution.
- Assignment 5 Due: 6pm Dec 5th. Solution.
Evaluation
Course grades will be based upon assignments (20%), midterm (20%), and a final exam (60%) - or
assignments (20%) and final exam (80%) if this leads to a better mark.
Textbook
- Algorithm Design, by Jon Kleinberg and Eva Tardos (2006)
Lectures
- Lecture 1: Ford-Fulkerson (7.1, 7.2 of textbook).
- Lecture 2: Choosing good augmenting paths (7.3 of textbook).
- Lecture 3: Bipartite matching, Disjoint paths (7.5,7.6 of textbook) and Konig's theorem
Theorem 3.14 here .
- Lecture 4: Applications of the Max-Flow problem (7.7, 7.8 of textbook).
- Lecture 5: Further Applications of the Max-Flow problem (7.9,7.11 of textbook).
- Lecture 6: Further Applications of the Max-Flow problem (7.12 of textbook).
- Lecture 7: Further Applications of the Max-Flow problem.
- Lecture 8: Linear Programming.
- Lecture 9: Linear Programming continued.
- Lecture 10: Duality in Linear
Programming.
- Midterm (Covers flow problems, and modelling problems as linear programs).
- Lecture 11, 12: Duality for fractional vertex cover, Max flow, Shortest path, and how to write the dual for linear programs in general form (See Table 4.1 here.)
- Lecture 13: Complementary slackness
- Lecture 14: Efficient certifiers, classes P and NP (8.3 of textbook).
- Lecture 15: class CoNP, Polynomial Reduction, NP-completeness, Max Independent set (8.1,8.2,8.4 of textbook).
- Lecture 16: NP-completeness: Max Clique, Vertex Cover, Set Cover (8.1 of textbook).
- Lecture 17: NP-completeness: 3SAT, Hamiltonian cycle. (8.2,8.5 of textbook)
- Lecture 18: NP-completeness: Traveling Salesman, Graph Coloring. (8.7 of textbook)
- Lecture 19: PSPACE, NP-completeness: subsetsum. (8.9, 9.1, 9.2, 9.3 of textbook)
- Lecture 20: Approximation algorithms: LP rounding, A 2-factor approximation algorithm for vertex cover.
- Lecture 21: Approximation algorithms: Load balancing, The center selection problem. (textbook 11.1-11.2)
- Lecture 22: Approximation algorithms: Set cover. (textbook 11.3)
- Lecture 23: Approximation algorithms using complmenetary slackness. (See this and the solution to Question 1.)
- Lecture 24: Randomized algorithms.
- Lecture 25: Randomized algorithms, randomized LP-rounding.
Course description:
We will cover the following topics.
- Network flows.
- Linear Programming.
- NP-completeness.
- PSPACE.
- approximation algorithms.
- randomized algorithms.
Prerequisite
COMP 251 or COMP 252, and either MATH 240 or MATH 235 or MATH 363. Restrictions:
Not open to students who have taken or are taking COMP 362