## Lecture Summaries  for COMP 360A                     Fall 2005

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 6:  Introduction to course via statement of two problems: the assignment problem and the travelling salesman problem. Outline of material to be covered in the course. General notions of easy and hard problems.

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.

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 another.

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.

----------------------------------------------