COMP 360: Algorithm Design Techniques
McGill University, Winter 2011

Announcements
April 20: Assignment 10 has been graded and is now available for pickup in my office.
April 18: Solution to A10
Some non-credit exercises on the last two topics (Network Flow and Linear Programming).

Lectures: Monday and Wednesday 11:30 -- 13:00 in ENGTR 0060.

Instructor: Phuong Nguyen  
Office: McConnell 303, phone: 514 398 7080, email for this course: pnguyen AT cs DOT mcgill DOT ca

TA: Neil Girdhar and Andie Sigler.

Office Hours: Monday and Wednesday 4--5pm in McConnell 303. Questions via email are welcome.

Text: Jon Kleinberg and Eva Tardos ``Algorithm Design'' Pearson Education (2006), ISBN: 0-321-29535-8.
Reference: Cormen, Leiserson, Rivest, Stein ``Introduction to Algorithm'' (3rd edition) McGraw-Hill (2009), ISBN-10: 0-262-53305-7, ISBN-13: 978-0262033848. Available online at http://library.books24x7.com/ (with McGill ID). The book ID is 3444.

Click here for the course information sheet (.pdf file).

Grading scheme:

  • final exam (3 hours, closed-book) worth 50%. You must obtain at least 40\% to pass the course;
  • 2 closed-book midterm tests (60 minutes each) worth 10% each, in MDHAR G-10 on February 28 and in ENGTR 1080 on April 4;
  • 8--10 weekly assignments of total worth 30%, due at the beginning of lectures on Monday starting from January 17.

Assignments
Assignment 1  Solution
Assignment 2  Solution
Assignment 3  Solution
Assignment 4  Solution
Assignment 5  Solution
Assignment 6  Solution
Assignment 7  Solution
Assignment 8  Solution
Assignment 9  Solution
Assignment 10  Solution
Non-credit exercises

Tests
Test 1   Solution to Test 1   Sample questions for Test 1.
Test 2   Solution to Test 2   Sample questions for Test 2.

Lecture Summary
Lecture 1 (January 5): Introduction. Topic I: P, NP and NP-completeness. Several decision problems: Connectivity (CONN), CLIQUE, J1, J2. Polynomial time algorithms and class P. Example: polytime algorithm for CONN. Nondeterministic algorithms. Example: nondeterministic algorithm for CLIQUE.
Lecture 2 (Januray 10): More decision problems: Subset Sum, 3-COL. The class NP, SAT and Cook-Levin Theorem (KT 8.4). Polytime Turing reduction (KT 8.1).
Lecture 3 (January 12): Polytime Many-one reduction (CLRS 34.3). Reduction from Independent set (IND) to CLIQUE. NP-completeness and its proof, 3CNF-SAT (CLRS 34.4).
Lecture 4 (January 17): Reduction from SAT to 3CNF-SAT (CLRS 34.4). Reduction from 3CNF-SAT to CLIQUE (CLRS 34.5.1).
Lecture 5 (January 19): Reduction from 3CNF-SAT to SubsetSum (CLRS 34.5.5).
Lecture 6 (January 24): Correctness proof of the reduction from 3CNF-SAT to SubsetSum. Reduction from 3CNF-SAT to 3-COL (KT 8.7).
Lecture 7 (January 26): Review of NP-completeness. Topic II: Greedy algorithms (KT 4.1 and 4.2).
Lecture 8 (January 31): Correctness of the greedy algorithm for Job Scheduling (KT 4.2). Greedy algorithm for Optimal Caching (KT 4.3).
Lecture 9 (February 2): Correctness of the greedy algorithm for Optimal Caching (KT 4.3). Shortest-path problem and Dijstra's algorithm (KT 4.4)
Lecture 10 (February 7): Minimum Spanning Tree problem. Kruskal's algorithm and Prim's algorithm (KT 4.5).
Lecture 11 (February 9): Implementation of Kruskal's algorithm (KT 4.6). Greedy approximation algorithm for Knapsack.
Lecture 12 (February 14): Proof of ratio 2 for the greedy algorithm for Knapsack. Greedy algorithms for the Load Balancing problem (KT 11.1). The Set Cover problem and a greedy approximation algoritm (KT 11.3, CLRS 35.3).
Lecture 13 (February 16): Approximation ratio of the greedy algorithm for Set Cover. Introduction to Dynamic Programming (Topic III).
Lecture 14 (March 7): Dynamic programming (KT 6.2). Shortest Path problem with negative weights -- Bellman-Ford algorithm (KT 6.8, see also 6.9 and 6.10).
Lecture 15 (March 9): Negative cycle detection (KT 6.10). All-pairs Shortest Paths problems -- Floyd-Warshall algorithm (CLRS 25.1, 25.2). A dynamic programming algorithm for Knapsack problem (KT 6.4).
Lecture 16 (March 14): Dynamic programming algorithms for Knapsack and its approximation (KT 6.4, 11.8).
Lecture 17 (March 16): Finish analysis of the approximation algorithm for Knapsack. Dynamic programming algorithms for Sequent Alignment problem (KT 6.6, 6.7).
Lecture 18 (March 21): Finish the algorithm for Sequent Alignment problem. Topic IV: Network flow. Ford-Fulkerson algorithm (KT 7.1-7.3, CLRS 26.1, 26.2.)
Lecture 19 (March 23): Finish Ford-Fulkerson algorithm. Max Flow Min Cut Theorem. Scaling Max-Flow algorithm. (KT 7.1-7.3, CLRS 26.1, 26.2.) (Extra reading: Preflow-push Max Flow algorithm KT 7.4.)
Lecture 20 (March 28): Image Segmention problem (KT 7.10). Maximum Bipartite Matching problem, Hall's Theorem (KT 7.5, CLRS 26.3).
Lecture 21 (March 30): Edge-disjoint st Path problem and Menger's Theorem (KT 7.6). Circulation with demands, and circulation with demands and lower bounds (KT 7.7). Topic 5: Linear Programming (CLRS 29).
Lecture 22 (April 6): Linear Programming formulation for Shortest Path, Max Flow, Multicommodities problems (CLRS 29).
Lecture 23 (April 8): Linear Programming formulation for Min-cost Flow problem (CLRS 29). An approximation algorithm for Weighted Vertex Cover using LP (KT 11.6). Review of the course.