COMP 360: Algorithm Design Techniques
McGill University, Winter 2011
Assignment 10 has been graded and is now available for pickup in my office.
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.
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.
Jon Kleinberg and Eva Tardos ``Algorithm Design'' Pearson Education (2006), ISBN: 0-321-29535-8.
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).
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.
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
Solution to Test 1
Sample questions for Test 1.
Solution to Test 2
Sample questions for Test 2.
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.
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.