308-362B Winter 2003


NOTE THAT THIS LIST FROM 2003 IS INTENDED TO GIVE A FLAVOUR OF THE COURSE. WE WILL FILL IN THE LECTURE SUMMARIES FOR THIS TERM AS WE GO ALONG

January 7 Lecture: Course Overview and Some Sample Problems

January 9 Lecture: Solving the TSP via Complete Enumeration and Dynamic Programming

January 14 Lecture: Dynamic Programming and Shortest paths (Chapter 24 except for sections 24.3 and 24.4)

January 16 Dynamic Programming and Matrix Multiplication (Section 15.2 you can also read section 15.1 and the introductory section of this chapter although the latter may be injurious to your mental health)

January 21 Lecture: Certifying Shortest Paths . and Topological Sort .

January 23 Lecture: Shortest Paths: Special Cases. .

January 28 Lecture: All Pairs shortest paths via Johnson's Algorithm (see section 25.3 of Cormen), and two algorithms for Minimum weight spanning tree (see Chapter 23 of Cormen)

January 30th Lecture: Disjoint Paths. .

February 4 Lecture: Implementing our Disjoint Path ALgorithm . and Introducing Flows .

February 6 Lecture: More on Flows: Augmenting Paths in The Auxiliary Network.

February 11 Lecture: More on Flows: Faster Flow Algorithms via Clever Augmentation.

Feb 13 Lecture: Applications of our Flow Theory: Matchings and Partial Orders. Notes for this topic were handed out in class. They were a reworking of Chapter 20 of Chvatal's Linear Programming Book. They covered maximum Matchings and Minimum Covers, the Konig-Egervary Theorem, Coverings by Chains in Partial 0rders, Hall's Theorem on systems of distinct representatives. They also discuss the Birkhoff Von-Neuamnn theorem, which we did not discuss and you do not need to know.

Feb 18 Lecture: The Stable marriage problem.

Feb 20 Lecture: Midterm Exam(in Class, normal room, starts at 11:30)

March 4 Lecture: We began our discussion of Linear and Integer Programs. You can read the Lecture Summary as well as the first 10 pages of Professor Fukuda's notes on the subject (no need to read the introduction).

March 6 Lecture: Integer and Linear Programming II: We discussed packing knapsacks briefly and spent most of our time on duality

March 11 Lecture: NP-completeness I. An informal introudction to this subject can be found on pages 365-371 of Cormen. We also discussed the definition of Decision Problem, DTM,NDTM, P and NP as given formally in Chapter 2 of Garey and Johnson's book Comupters and Intractibility (handed out in class).

March 13 Lecture: NP-completeness II. We discussed Turing Reductions and the notion of an NP-complete problem. We defined the Satisfiability Problem. We showed that the Hamilton Circuit Problem reduces to TSP and to Satisfiability. We began the proof of Cook's theorem: the Satisfiability Problem is NP-complete.

March 18 Lecture: NP-completeness III. We completed the proof of Cook's Theorem, which can also be found in Chapter 2 of Garey and Johnson.

March 20 Lecture: NP-completeness IV. We presented some NP-complete Problems.

March 25 Lecture: NP-completeness V. We presented some more NP-complete Problems.

March 27 Lecture: NP-completeness VI. We discussed some Partition Problems.

April 1st Lecture: We discussed 2SAT. Here are some slides on the topic.

April 3rd Lecture: We discussed finding the strong components of a digraph in $O(|V|+|E|)$ time, see Section 22.5 of Cormen.

April 8th Lecture: Taking up Assignment 4.

April 10th Lecture: Review