Lecture Summaries  for COMP 360                   Winter  2008

Text: Algorithm Design, J. Kleinberg and E. Tardos, Pearson 2006.
Additional material, including power point slides for this text, available from WebCT

Jan 3. Course overview. As a first representative problem we saw that the sushi problem can be formulated as a knapsack problem.

Jan 8. More representative problems. Fun with stable marriages. Segment intersection problems, matching problems and independent sets.
Read Text Chapter 1. Chapters 2 and 3 are review of material you should have seen in COMP251 and/or MATH240. Please have a look at this material and let me know of anything you did not see before. Slides: 01stable-matching.ppt

Jan 10: Greedy algorithms for interval scheduling, room assignment and scheduling to minimize lateness. Read: Sections 4.1, 4.2. Slides: 04greed.ppt

Jan 15: More on Greedy algorithms and exchange argument. Cacheing problem. Weighted selection problems solvable by greedy.  Read: Section 4.3 and handout on selection (pdf) (do the exercises!)

Jan 17: Dynamic Programming. Weighted interval selection, line fitting and knapsack problems. Read: Beginning of Ch. 6

Jan 22: More on Knapsack. Pseudopolynomial time. Bellman-Ford algorithm. Read sections 6.8 and 6.9

Jan 24: Negative cycles. Introduction to network flows. Read section 6.10.

Jan 29: Network flows and Ford-Fulkerson algorithm. Read pp337-351.

Jan 31: Finding good augmenting paths. Bipartite matching/vertex cover. Read 351-357, section 7.5

Feb 5, 7 : Applications of network flows. Disjoint paths, circulations, lower bounds on capacities, survey design, project selection. Read: 7.6-8, 7.11

Feb 12: Review Session

Feb 14: Midterm test in class. All material above up to and including February 7 lecture, plus assignments.

Feb 19,21: Linear Programming. Formulations and discussion of certificates for the three possible outcomes. Read: lp_handout.pdf  in "hidden" folder, Sections 7.1 and 7.4 and Komei Fukuda's notes Chapter 1.

Mar 4: Introduction to lp_solve (see announcements). More on certificates for infeasible systems (Farkas' Lemma) and how to find using lp_solve.

Coming up: NP-completeness. An introductory comic (thanks to Sevan). Upcoming slides: All slides starting 08 in the hidden folder.

Mar 6, 11. Introduction to the classes P, NP, EXP. Problem reductions. NP-complete problems. Cook's theorem(stated without proof.) Read: Text 451-4, 463-466. Note we will not be using Circuit Satisfiability as our "first" NP-complete problem, but we will use Satisfiability (SAT, P. 450) instead.

Mar 13: We reduced SAT to 3-SAT to IND SET to VERTEX COVER and also IND SET to CLIQUE. Read 459-466.
Mar 18: We reduced 3-SAT to SUBSET SUM to PARTITION and also SUBSET SUM to KNAPSACK. Read: Section 8.8.  Slides 36-37 of 08reductions-poly contain the reduction we did in class from 3-SAT to SUBSET SUM. It is also in Cormen et al. (2nd edition) pp. 1014-6.
Mar 25: NP-hard problems. Co-NP. Integer programming formulation of MAX 3-SAT. Discussion of why there are no general certificates for NP-hard problems. Read: 495-500.
Mar 26: Tutorial on NP-completeness, 12-1pm McConnell 322 (SOCS lounge).

Coming Up: Chapter 11, Approximation algorithms
Mar 27: Approximation algorithms for Vertex Cover. Read: Text sections 11.4 and 11.6

April 1: Approximation algorithms for machine scheduling. We got tighter bounds than those given in the text. Read: Text section 11.1.

April 3: Local search. Max cut and Best Response dynamics. Read: 11.1, 12.4, 12.7.

April 8,10: We will go over Assignment 4 solutions, and the final exam from Dec 2007.  Other topics by email request.

April 18: Final exam, 9am-12 noon place TBA.