### Lecture Summaries  for COMP 360                   Fall 2009

Text: Algorithm Design, J. Kleinberg and E. Tardos, Pearson 2006.
Additional material, including power point slides for this text, available from WebCT  and a hidden website (contact me or TAs)

Sep 1: Course overview, web pages etc. All meals for a dollar: linear programming and vertex enumeration. slides.

Sep 3: The stable marriage problem. Read: Section 1.1 and this fun article. (Extra for those interested: LP-bliss paper is on the hidden website.) Kazuo Iwama will give a colloquium on Friday Sep 18.

Sep 8: Greedy algorithms. Scheduling and shortest paths. Read: Sections 4.1, 4.2, 4.4
Sep 10: The sushi problem and other weighted selection problems. Characterization of weighted selection problems solvable by greedy selection.  Read:  handout on selection (pdf) (do the exercises!).
Sep 15: Dynamic Programming. Weighted interval selection, line fitting. Read: Beginning of Ch. 6.1-6.3

Sep 17: Maze problem. DP solution to Knapsack. Read sections 6.4 and 6.8.
Sep 22: Bellman-Ford algorithm. Detecting negative cycles in graphs. Application to routing. Read: 6.8,6.9,6.10

Sep 24: Network flows and Cuts. Formulations. Review the slides 07maxcut (first 12) and start reading Ch. 7.

Sep 29, Oct 1: Residual graphs and the augmenting path algorithm. Proof of the Max-flow min-cut theorem. Read: 7.1,7.2
Oct 6: Bipartite matchings, vertex covers, proof that maximum matching = minimum vertex cover. Scaling to give a fast implementation of Ford-Fulkerson algorithm. Read: 7.3,7.5
Oct 8: Circulations, lower bounds on capacities. Applications: disjoint paths, Image segmentation. Read:  7.6, 7.7, 7.10
Oct 13: More applications: project selection and baseball scheduling. Read: 7.11, 7.12
Midterm will be based on all material above.

Oct 15: Review and exercises.
Oct 20: Midterm in Trottier 0060 . Closed book, no notes.
Oct 22,27: Introduction to linear programming. Formulation of wine blending problem and dual. Three outcomes of linear programming. Geometric interpretation. Read: lp_handout.pdf  in "hidden" folder, Sections 7.1 and 7.4 and Komei Fukuda's notes Chapter 1.
Oct 29: We worked through an example of the simplex method from scratch. Certificates for unbounded solution and infeasible solution.
Read: lp_handout.pdf section 7.6 (the description is a bit different from what we did in class, but it is equivalent).  Also read and Komei Fukuda's notes sections 2.1-2.4.

Nov 3,5: Introduction to NP,  NP-complete, NP-hard problems. Polynomial time reductions. Cook's Theorem. Integer programming is NP-hard,
3-SAT is NP-complete. Note that " A ≤P B" is read "B is at least as hard as A", or, "A is polynomial time reducible to B" (this was written incorrectly in class). Read: text 8.1 to 8.4 omitting graph theory reductions.
Nov 10,12: NP-completeness reductions. 3-SAT -> IND-SET -> VERTEX COVER -> SET COVER and
3-SAT -> SUBSET-SUM -> PARTITION -> 2-MACHINE SCHEDULING -> KNAPSACK (Decision version)
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.

Nov 17: Travelling salesman problem case study
Nov 19: Approximation algorithms for Vertex Cover. Read: Text sections 11.4 and 11.6

Nov 24: Approximation algorithms for machine scheduling. We get tighter bounds than those given in the text. Approximation scheme for the Knapsack problem. Read: Text sections 11.1, 11.8.

Nov 26: Local search. Hopfield Networks. Max cut. Read: 12.1, 12.3, 12.4.
Nov 30: Problem session and review.
Dec 16, 2pm   Final exam. Covers all above material except Nov. 17 lecture.