Text: Introduction to Algorithms,
Cormen, Leiserson, Rivest, Stein (2nd edition)
Full text available on-line at: http://www.library.mcgill.ca/lists/books247.html
Sep 1: No class
Sep 8: Introduction to selection problems, weighted selection
problems and the greedy algorithm.
Read: Course notes on selection (pdf) and do the exercises! Note the correct definition of admissible sets for the minimum spanning tree problem is given in Ex. 6 of the notes - not what I wrote in class on the board!
Sep 13: Proof of correctness of the greedy algorithm when 3
conditions are satisfied. Counterexamples to greedy when P3 fails.
Buying sushi optimally and the knapsack problem. Read text section 16.2.
Sep 15: Dynamic programming of the Knapsack Problem (see Ex. 16.2-2, p. 384).
C code for knapsack problem and sample run is here. Why is this not a polynomial time algorithm?
Sep 20: Introduction to Networks. The maximum flow problem.
Certificates of optimality via cuts.
Read: Class handout, pp. 337-342.
Sep 22: Finding augmenting paths by using a residual capacity graph.
Finite terminate and integrality of the flow.
Definition of a cut, and proof that the max flow = min cut. Read: Class handout 342-351.
Sep 27: We worked out a network flow problem in class and found the
max flow/ min cut. We formulated the flood survivors problem as a
network flow problem, and interpreted the max flow/min cut in terms of
the original problem.
Sep 29: Complexity issues. Bad example for the Ford-Fulkerson
algorithm. Edmonds-Karp algorithm (we did not prove the complexity
bound). Scaling algorithm. Read class handout pp 352-357. A second
handout was given that will be needed for the second assignment which
is now posted.
Oct 4: The Stable Marriage Problem. Today we learned the important:
Lesson in love: Unless you are fantastically good-looking, you need to take the initiative.
Read: David Feldman's notes, and the New Scientist article, "What's love got to do with it?", which contains the above quote.
Oct 6: We proved that the maximum matching in a bipartite graph has
the same cardinality as the minimum vertex cover.
We used the integrality theorem to prove that every regular (each vertex has the same degree) bipartite graph has a perfect matching. Read the second class handout.
Oct 11, 13: How to find a solution to a system of inequalities.
Certificates of infeasibility. Read: article
Oct 18: Review problems.
Oct 20: Midterm, in class. You are responsible for all material
above plus the first two homework assignments.
Oct 25: Introduction to linear programming. Read: Komei Fukuda's LP notes
up to the end of Chapter 1. Cormen 770-777.
Oct 27: We studied the diet problem, and what information can be obtained from the LP solution, as well as strengths and weaknesses. Slides from the lecture. You can make you own diet here. A history of the diet problem is here.
Nov 1: Proof of the weak duality theorem. Unbounded linear programs.
Introduction to integer linear programming.
Read: Fukuda's notes up to the end of Section 3.1.
Nov 3: Introduction to NP-completeness. Definition of NP via certificate checking. Read: Cormen 34.1, 34.2. We also discussed the travelling salesman problem.
Nov 8: Problem transformation, with several examples. Definition of NP-complete. Statement of Cook's Theorem. Read: Cormen 34.3 up to p. 986. (Optional: Lemma 34.6 contains a proof of Cook's theorem.)
Nov 10: Satisfiability and 3-SAT. How to reduce one problem to
Nov 15: Reduction of 3-SAT to Independent Set to Vertex Cover, and
reduction of Independent Set to Clique.
Read: Cormen Section 34.5.1 and 34.5.2
Nov 17: Reduction of 3-SAT to SUBSET-SUM, further reductions to
PARTITION and KNAPSACK PROBLEM.
Nov 22: Approximation algorithms. Heuristics for vertex cover:
Matching heuristic and greedy heuristic.
Read: pp1022-1027. We also did Prof. Nixon's problem, 35.1-3, getting a log n ratio bound.
Nov 24: The linear programming heuristic for vertex cover. The list
heuristic for scheduling jobs on m processors.
Read: pp 1040-1043. Notes on scheduling heuristics prepared by Melanie.
Nov 29: The
fat lady sings.
return to: course home page