## Lecture Summaries  for COMP 360B                     Winter 2004

Text: Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein (2nd edition)

Full text available on-line at: http://www.library.mcgill.ca/lists/books247.html

Jan 13: 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.
Greedy algorithms. Sushi (knapsack) problem.

Read: introduction(pdf) Text:  Sections 16.1, 16.2

Jan 15: Introduction to selection problems, weighted selection problems and the greedy algorithm.
Read: Course notes on selection (pdf) and do the exercises!

Jan 20: Proof of the optimality of the greedy algorithm  Introduction to minimum spanning trees. Kruskal's algorithm viewed as  an example of greedy selection. Read: Review text Ch. 23

Jan 22: Introduction to dynamic programming. Matrix chain multiplication.
Read: David Bryant's  Handout(pdf). Text: Section 15.2.

Jan 27: More examples of dynamic programming.  Knapsack Problem (see Ex. 16.2-2, p. 384).
C code for knapsack problem and sample run is here.  There is a revision to assignment 1, question 1.

Jan 29: More examples of dynamic programming. Paths through a grid.  Read: David Bryant's  Handout(pdf) .

Feb 3:  Introduction to directed graphs and shortest path problems. Bellman-Ford algorithm for directed graphs with negative edge weights. Read: Bruce Reed's handout(pdf) and Section 24.1.

Feb 5: Disjkstra's algorithm for directed graphs with non-negative edge weights. Shortest paths on acyclic graphs. Comparison with Prim's algorithm. Read: Chapter 24 up to the end of Section 24.3

Feb 10: Johnson's algorithm. Read: Section 25.3.  Introduction to Network Flows.

Note: Network flows are covered in the text, Sections 26.1, 26.2 using a different definition of flow.

Feb 12: The augmenting path algorithm for finding a maximum flow. Cuts, and their use in certifying a maximum flow.
Read: The approach used in class: lecture notes

Feb 17: More on augmenting paths, residual graphs, proof of max flow/ min cut theorem.  Read: The approach used in class: lecture notes (first 4 pages)

Feb 19:  Matchings in bipartite graphs. Solution via Network Flows. Certificate of optimality of matching given by a vertex cover of the same size - known as Konig's Theorem (1931). Section 26.3 of the text has most of the material but not Konig's Theorem. We did problem 26.3-5 at the end of the lecture.
Read: Lecture notes up to the middle of page 8-4, and text Section 26.3

March 2: Review. March 4: Midterm

March 9: 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.

Mar. 11:  You will need the lp package lp_solve for the next part of the course, please check announcements for details.
Introduction to  linear programming, the wine production problem. Formulation of a LP in standard form, and integer linear program (ILP). Introduction to proof of optimality via positive combinations of constraints. Read: Komei Fukuda's LP  notes up to P. I-5.

Mar. 16: Three outcomes for LP: optimum solution, unbounded solution, infeasible. The dual LP and certificates for optimality. Statement of strong and weak duality theorems. Read: Fukuda's notes up to the end of Section 2.2 (you can skip Theorem 2.3).

March 18: Infeasible inequalities and Farkas Lemma. Read: Fukuda's notes Section 2.3, 2.4

March 23: How to find a solution to a system of inequalities. Read: article

March 25: Introduction to the theory of NP-completeness. Definition of P and NP. Examples from the problems we have looked at in the course.
Read: Notes distributed in class and Cormen et al.  pages 966-982.

March 30: Problem reductions. Examples from problems studied in the class. Definition of NP-complete and NP-hard. Cook's theorem and its consequences.

April 1:    Reductions from SAT to 3-SAT to INDEPENDENT SET to VERTEX COVER. Read: Class handout and Cormen 984-6, 1003-8.
Note: We use the definition of SAT in the handout given in class (ie conjunctive normal form). The problem SAT in Cormen also allows                                      implication and if and only if. What we call 3-SAT, Cormen calls 3-CNF-SAT.

April 6:    Reductions from 3SAT to Subset sum to {Partition,Knapsack}. Read Cormen section 34.5.5.

April 8:     Wrap up. Send suggestions in advance!