Lecture Summaries  for COMP 360                   Fall 2007

      also check:  announcements      assignments    return to:  course home page

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

Sep 4: Stable Matching. 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.
Sep 6: More on stable marriage. Easy and Hard problems. Variations on the stable marriage problem making it hard. Introduction to the Greedy method. Interval scheduling. Read 4.1.

ps. A famous one line APL program (Conway's game of life), see http://catpad.net/michael/apl

Sep 11: More problems solvable by the greedy method. We also saw that the sushi problem can be formulated as a knapsack problem. Read 4.2, 4.3. Review 4.5.
Sep 13: Assignment 1 posted. A detailed analysis of the cacheing problem and the exchange argument (4.3). Greedy selection problem as a generalization of Kruskal's algorithm for finding a minimum spanning tree.
Read: Handout on selection (pdf) and do the exercises!
Sep 18 Dynamic programming. Weighted interval selection, line fitting and knapsack problems. Read: Beginning of Ch. 6
Upcoming lectures will be based on Sections 6.8,6.9,6.10,7.1,7.2,7.3,7.5 in case you want to print out the pdf files

Sep 20: Shortest paths with negative weights. Bellman-Ford algorithm. Distance vector protocols. Read: Sec. 6.8,6.9

Sep 25: More on Bellman-Ford. Comparison of two algorithms in the text. Negative weight cycles. Also look at the wiki, and its applet.
(Note to detect a negative weight cycle in a network you should understand why the construction in Fig 6.25 on P. 302 is necessary.
Read: 6.10 up to P. 305 inclusive. Also read the economist articles (here and here) on algorithms. You will be asked to review these in Ass. 2

Sep 27: Introduction to network flows. Flows and cuts. Ford and Fulkerson algorithm. The flow lemma (7.6, p. 346). Read pp. 337-346
Oct 2:  Max flow/Min cut theorem. Complexity of F-F algorithm. Finding good augmenting paths. Bipartite matching. Read pp 346-357, Section 7.5
Oct 4:  Selected applications of max flow/min cut problem. Read: 7.6, 7.7, 7.8.   Assignment 3 is posted.
Oct 9: No class, Monday schedule is applied today.
Oct 11: Two more network flow applications: Baseball elimination and Project selection. Read: 7.11 and 7.12
Oct 16: Review if requested. Otherwise an introduction to linear programming.
Oct 18: Midterm, to be held in class. Covers material up to and including Oct. 11, plus all three assignments.
Oct 23,25: Introduction to linear programming. Formulations, standard form, dual lp, weak duality. Read: Class handout (also available from Perouz) sections 7.1,7.4.
Oct 30: Certificates for unbounded solutions and infeasibility. The diet problem and vertex enumeration: giving managers a choice. Read: Komei Fukuda's LP  notes  Sections 2.3 and 2.4.
Nov 1,6,8: Introduction to the theory of NP-completeness: class NP, reductions, NP-complete problems, Cook's theorem (stated without proof).
NP-complete graph problems: VERTEX COVER, INDEPENDENT SET, CLIQUE   Read: pp 452-473
Nov 13: Showing "number" problems are hard. SUBSET SUM, PARTITION, KNAPSACK. Read: Section 8.8, slides from book Ch.8 contain the reduction we did in class from 3-SAT to SUBSET SUM. 
Nov 15: Approximation algorithms for vertex cover: lp rounding (review), matching, greedy, list heuristic. Read: slides, for details the paper.
Nov 20: Approximation algorithms. Load balancing, knapsack problem. Read: 599-606, 644-647. Omit proof of (11.38)
Nov 22: Local search. Vertex cover, metropolis algorithm, Hopfield neural network, max cut. Read: 661-679.
Nov 27: Local search vs. greedy.  More on max-cut. Best response dynamics and Nash Equilibria.
Nov 29: Homework review session lead by Perouz.
Dec 4: The wrap up. Please send topic in advance by email.
Dec 10: Final exam, 2-5 pm. Covers all material on this page up to and including the Nov 22 lecture, plus all homeworks.