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 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
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
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,
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.
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
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
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
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