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 noncredit 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 45pm in McConnell 303.
Questions via email are welcome.
Text:
Jon Kleinberg and Eva Tardos ``Algorithm Design'' Pearson Education (2006), ISBN: 0321295358.
Reference:
Cormen, Leiserson, Rivest, Stein
``Introduction to Algorithm'' (3rd edition) McGrawHill (2009), ISBN10:
0262533057, ISBN13: 9780262033848.
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, closedbook) worth 50%. You must obtain at least 40\% to pass the course;

2 closedbook midterm tests (60 minutes each) worth 10% each, in MDHAR G10 on February 28 and in ENGTR 1080 on April 4;

810 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
Noncredit 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 NPcompleteness.
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, 3COL.
The class NP,
SAT and CookLevin Theorem (KT 8.4).
Polytime Turing reduction (KT 8.1).
Lecture 3 (January 12):
Polytime Manyone reduction (CLRS 34.3).
Reduction from Independent set (IND) to CLIQUE.
NPcompleteness and its proof,
3CNFSAT (CLRS 34.4).
Lecture 4 (January 17):
Reduction from SAT to 3CNFSAT (CLRS 34.4).
Reduction from 3CNFSAT to CLIQUE (CLRS 34.5.1).
Lecture 5 (January 19):
Reduction from 3CNFSAT to SubsetSum (CLRS 34.5.5).
Lecture 6 (January 24):
Correctness proof of the reduction from 3CNFSAT to SubsetSum.
Reduction from 3CNFSAT to 3COL (KT 8.7).
Lecture 7 (January 26):
Review of NPcompleteness.
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).
Shortestpath 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  BellmanFord algorithm (KT 6.8, see also 6.9 and 6.10).
Lecture 15 (March 9):
Negative cycle detection (KT 6.10).
Allpairs Shortest Paths problems  FloydWarshall 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.
FordFulkerson algorithm (KT 7.17.3, CLRS 26.1, 26.2.)
Lecture 19 (March 23):
Finish FordFulkerson algorithm.
Max Flow Min Cut Theorem.
Scaling MaxFlow algorithm.
(KT 7.17.3, CLRS 26.1, 26.2.)
(Extra reading: Preflowpush 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):
Edgedisjoint 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 Mincost Flow problem (CLRS 29).
An approximation algorithm for Weighted Vertex Cover using LP (KT 11.6).
Review of the course.
