Lecture Summaries  for COMP 360                   Fall 2006

      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 5: Intro. Course outline. Easy and Hard Problems.
Sep 7: 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 12:  Greedy Algorithms. Interval scheduling and minimum lateness scheduling. Proof techniques for greedy algorithms. Read: Text, Sections 4.1 and 4.2
Sep 14:  More on greedy algorithms. Kruskal's minimum spanning tree problem as a model for greedy selection. Characterization of which selection problems can be solved by the greedy selection algorithm. Review: Text Section 4.5   Read: Handout on selection (pdf) and do the exercises!

Sep 19: Examples of selection problems where P3 fails, and how to make greedy selection fail. Introduction to dynamic programming, and a solution to the weighted movie selection problem. Read: Text section 6.1, 6.2.

Sep 21: More dynamic programming examples from the text. Read: Knapsack problem and Line fitting problem from Ch. 6. First assignment due on Monday, see announcements for details.
Sep 26: Shortest path problem with negative edge weights. Review of Dijkstra's algorithm. Bellman-Ford algorithm. Note, to find the negative cycle it is better to use the pointer graph (pp296-297) than the artificial node and zero edge weights (slide 16 of 06bellman-ford). The pointer graph also gives the shortest path tree if there is no negative cycle. I'll talk a bit more about this next time. Read: Sections 6.8, 6.9, 6.10
Sep 28: More on Bellman-Ford and the detection of negative cycles. Introduction to the max-flow min-cut problems. Read: 7.1
Oct 3: Ford-Fulkerson algorithm and its proof of correctness. Finding a minimum cut on termination. Read: 7.2
Oct 5: Choosing good augmenting paths. Whose cooking dinner? (Problem 15, P. 421). Read: 7.3
Oct 12: Matchings and Vertex Cover. Read: 7.5
Oct 17: Problems and Review session.

Oct 19: Midterm, in class. Covers all material up to, and including Oct 12 lecture.

Oct 24: Introduction to linear programming, with examples from networks, matchings, vertex cover etc. Formulation in standard form.
               Read: Text pp 630 to top of 635.
Oct 26: Basic production scheduling problem. Three outcomes for a linear program, with discussion of certificates for correctness. The weak duality theorem (with proof) and statement of the strong duality theorem.  Read: Read: Komei Fukuda's LP  notes up to the end of Chapter 1.
Try out the program lp_solve, details given on course announcements page.
Oct 31: Introduction to lpsolve for linear and integer programming. LP approximation to vertex cover. Introduction to intractability and problem reductions.
Read: Text: 635-7 and 451-4.
Nov 2: The class NP and polynomial time reductions. Read: Sections 8.1 and 8.2
Nov 7: NP-complete problems and Cook's theorem. Read: 8.3,8.4, 8.6
Nov 9: The class Co-NP and possible connections between the complexity classes. Factoring and Primality. Read: 8.8, 8.9. Also review slides 24-34 in 08np-complete (see webCT).

Nov 14: Dealing with NP-hard problems. Small vertex covers, stable sets on trees, colouring circular arc graphs. Read: 10.1,2,3.
Nov 16: Approximation algorithms for vertex cover: lp rounding (review), matching, greedy, list heuristic. Read: slides, for details the paper.

Nov 21: Approximation algorithms for load balancing and the knapsack problem. Read: 11.1 and 11.8.
Nov 23: Local search algorithms. Metropolis algorithm, Hopfield neural networks, max cut. Read: 12.1-12.4
Nov 28: A counterexample for local search for stable matching. Best response dynamics and Nash equilibria.
               Nash Equilibria for two person games. Read 12.7
Nov 30: Case study: Travelling salesman problem.
Dec 5:  Rewind and wrap up. Final exam will cover material in the above readings up to and including Nov. 28. The first half and second half of the course will be covered roughly equally on the exam. Good luck!

return to: course home page