Lecture Summaries for COMP
assignments return to: course home page
Text: Algorithm Design, J.
Kleinberg and E. Tardos, Pearson 2006.
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
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.
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
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
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
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
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
Nov 15: Approximation algorithms
for vertex cover: lp rounding (review), matching, greedy, list
heuristic. Read: slides,
details the paper.
Nov 20: Approximation algorithms.
Load balancing, knapsack problem. Read: 599-606, 644-647. Omit proof of
Nov 22: Local search. Vertex
cover, metropolis algorithm, Hopfield neural network, max cut. Read:
Nov 27: Local search vs.
greedy. More on max-cut. Best response dynamics and Nash
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