Lecture Summaries for COMP
360
Fall 2009
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 and a hidden website
(contact me or TAs)
Sep 1: Course overview, web
pages etc. All meals for a dollar: linear programming and vertex
enumeration. slides.
Sep 3: The stable marriage
problem. Read: Section 1.1 and this fun article. (Extra for those
interested: LP-bliss paper
is on the hidden website.) Kazuo Iwama will give a colloquium
on Friday Sep 18.
Sep 8: Greedy algorithms.
Scheduling and shortest paths. Read: Sections 4.1, 4.2, 4.4
Sep 10: The sushi
problem and other weighted selection problems. Characterization of
weighted selection problems solvable by greedy selection.
Read: handout on selection
(pdf)
(do the exercises!).
Sep 15: Dynamic Programming.
Weighted interval selection, line fitting. Read:
Beginning of Ch. 6.1-6.3
Sep 17: Maze problem. DP solution
to Knapsack. Read sections 6.4 and 6.8.
Sep 22: Bellman-Ford algorithm.
Detecting negative cycles in graphs. Application to routing. Read:
6.8,6.9,6.10
Sep 24: Network flows and Cuts.
Formulations. Review the slides 07maxcut (first 12) and start reading
Ch. 7.
Sep 29, Oct 1: Residual graphs
and the augmenting path algorithm. Proof of the Max-flow min-cut
theorem. Read: 7.1,7.2
Oct 6: Bipartite matchings,
vertex covers, proof that maximum matching = minimum vertex cover.
Scaling to give a fast implementation of Ford-Fulkerson algorithm.
Read: 7.3,7.5
Oct 8: Circulations, lower bounds
on capacities. Applications: disjoint paths, Image segmentation.
Read: 7.6, 7.7, 7.10
Oct 13: More applications:
project selection and baseball scheduling. Read: 7.11, 7.12
Midterm will be based on all material
above.
Oct 15: Review and exercises.
Oct 20: Midterm in Trottier 0060 .
Closed book, no notes.
Oct 22,27: Introduction to linear
programming. Formulation of wine blending problem and dual. Three
outcomes of linear programming. Geometric interpretation. Read:
lp_handout.pdf in "hidden" folder, Sections 7.1
and 7.4 and Komei Fukuda's notes
Chapter 1.
Oct 29: We worked through an
example of the simplex method from scratch. Certificates for unbounded
solution and infeasible solution.
Read: lp_handout.pdf section 7.6 (the description is a bit different
from what we did in class, but it is equivalent). Also read
and Komei Fukuda's notes
sections 2.1-2.4.
Nov 3,5: Introduction to
NP, NP-complete, NP-hard problems. Polynomial time reductions.
Cook's Theorem. Integer programming is NP-hard,
3-SAT is NP-complete. Note that " A ≤P B" is read "B is at
least as hard as A", or, "A is polynomial time reducible to B" (this
was written incorrectly in class). Read: text 8.1 to 8.4 omitting graph
theory reductions.
Nov 10,12: NP-completeness
reductions. 3-SAT -> IND-SET -> VERTEX COVER -> SET COVER and
3-SAT -> SUBSET-SUM -> PARTITION -> 2-MACHINE SCHEDULING ->
KNAPSACK (Decision version)
Read: Section
8.8. Slides
36-37 of 08reductions-poly contain the reduction we did in class from
3-SAT to
SUBSET SUM. It is also in Cormen et al. (2nd edition) pp. 1014-6.
Nov 17: Travelling salesman
problem case study
Nov 19: Approximation algorithms
for Vertex Cover. Read: Text sections 11.4 and 11.6
Nov 24: Approximation algorithms
for machine scheduling. We get tighter bounds than those given in the
text. Approximation scheme for the Knapsack problem. Read: Text
sections 11.1, 11.8.
Nov 26: Local search. Hopfield
Networks. Max cut. Read: 12.1, 12.3, 12.4.
Nov 30: Problem session and
review.
Dec 16, 2pm Final exam.
Covers all above material except Nov. 17 lecture.