Lecture Summaries  for 308-360B                     Winter 2003

      also check:  announcements      assignments    return to:  course home page
You will need the lp package lp_solve for the next part of the course, please check announcements for details.

Notes for Linear Programming:      http://cgm.cs.mcgill.ca/~avis/courses/360/notes/    Either: fukuda.pdf or fukuda.ps

Notes for NP-completenss: Handout given in class,  also available at Copi-EUS.

For office hours during exam period, please see announcements

April 10: Final monologue and question period. Good luck on the exam.

April 8: Reductions from SAT to 3-SAT, 3-SAT to Subset Sum. Read: Sections 35.5.1, 35.5.5

April 3: More reductions. Ind. set to clique and vertex cover,  Sat to 3-Sat.  Finding the "boundary" between P and NP-complete. Read: Text Ch 34, 966-986
April 1: NP-hard vs NP-complete. Cook's theorem and it implications. How to prove problems are NP-complete using polynomial time reductions. First reduction: sat to ind. set. Assigment 4 is posted.

Mar 27: Definitions of polynomial reducibility, non deterministic algorithms and the class NP.
Emphasis on checking the "yes" answer in polynomial time by use of a certificate.
Read: Read NP-completeness handout
Mar 25: Introduction to NP completeness. Easy and hard problems. Examples of obtaining hard problems from easy ones by
small modifications. Properties of "hard" problems.

Mar 20: Bohdan's lecture on finding a feasible solution to a system of inequalities using the b-rule.
Read:  brule.ps (brule.pdf) at least first 4 pages.
Mar 18: Certificates of optimality, infeasibility and unboundedness. The weak duality theorem.
Read: LP notes  up to and including Section 2.4.
Mar 13: Introduction to  linear programming, the wine production problem. Formulation of a LP in standard form, and integer linear program (ILP). Introduction to proof of optimality via positive combinations of constraints.
Read:  LP  notes up to P. I-5.
Mar 11: Max flow min cut theorem, Integrality theorem. We used this theorem to prove that a bipartite graph in which each vertex has degree k has a perfect matching. Variants to guarantee polynomial time: augmenting path using minimum number of edges (Edmonds-Karp) and augmenting path of maximum capacity.
March 8: Discussion of midterm. Implementation of the network flow algorithm.
Mar 4: Midterm

Feb 20: Augmenting Paths. Matchings. Relationship of matching algorithm using alternating paths to network flow algorithm using augmenting paths.
Read: handout from Feb 11 up to, but not including, the Augmenting Path theorem.
Feb 18: Network Flows. Basic concepts, augmenting paths, cuts.
Feb 13:  The Stable Marriage Problem. Today we learned the important:

Lesson in love: Unless you are fantastically good-looking, you need to take the initiative.

Read:  David Feldman's notes, and the New Scientist article, which contains the above quote.


Feb 11: Bipartite matchings. Solution by alternating paths. A Vertex Cover for a graph G is a subset S of vertices such that each edge of G has at least one of its endpoints in S. We saw that for any matching M and any vertex cover S, the number of edges in M is at most the number of vertices in S.
Get handout Matchings and Flows from Copi-EUS, ground floor of McConnell Engineering. Read section 7.10 of the handout.


Feb 6: Johnson's algorithm. Read: Section 25.3


Feb 4: Disjkstra's algorithm for directed graphs with non-negative edge weights. Comparison with Prim's algorithm. Checking the correctness of a shortest paths treee by one iteration of the Bellman-Ford algorithm.
Read: Chapter 24 up to the end of Section 24.3

Jan 30: Introduction to directed graphs and shortest path problems. Bellman-Ford algorithm for directed graphs with negative edge weights.
Read: Bruce Reed's handout(pdf) and Section 24.1.

Jan 28: More examples of dynamic programming. Paths through a grid. Knapsack Problem (see Ex. 16.2-2, p. 384). C code for knapsack problem and sample run is here.

Read: David Bryant's  Handout(pdf) .

Jan 23: Introduction to dynamic programming. Matrix chain multiplication.
Read: David Bryant's  Handout(pdf). Section 15.2.

Jan 21: The algorithms of Prim and Kruskal, and implementations in O(mlogn) time.
Read: Finish reading chapter 23.    Tutorials start today!

Jan 16: Proof of the optimality of the greedy algorithm (I added this proof to the course notes selection.(pdf)) Introduction to minimum spanning trees. Kruskal's algorithm viewed as  an example of greedy selection. Read: Section 16.4,  Start reading chapter 23.

Jan 14: Introduction to selection problems, weighted selection problems and the greedy algorithm.
Read: Course notes on selection (pdf) and do the exercises!

 Jan 9: Outline of material to be covered in the course. General notions of easy and hard problems.
Greedy algorithms. Sushi (knapsack) problem.
Read: Sections 16.1, 16.2 ( 17.1, 17.2 first edition).
Exercise: Prove the greedy heuristic finds an optimal solution for the fractional knapsack problem.

Jan 7: Introduction to course via statement of two problems: the assignment problem and the travelling salesman problem.
Read: introduction(pdf)