Lecture Summaries for COMP
360
Winter 2008
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
Jan 3. Course overview. As a first representative problem we saw that
the sushi
problem can be formulated as a knapsack problem.
Jan 8. More representative
problems. Fun with stable marriages. Segment intersection problems,
matching problems and independent sets.
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. Slides:
01stable-matching.ppt
Jan 10: Greedy algorithms for
interval scheduling, room assignment and scheduling to minimize
lateness. Read: Sections 4.1, 4.2. Slides: 04greed.ppt
Jan 15: More on Greedy algorithms
and exchange argument. Cacheing problem. Weighted selection problems
solvable by greedy. Read: Section 4.3 and handout on selection
(pdf)
(do the exercises!)
Jan 17: Dynamic Programming.
Weighted interval selection, line fitting and knapsack problems. Read:
Beginning of Ch. 6
Jan 22: More on Knapsack.
Pseudopolynomial time. Bellman-Ford algorithm. Read sections 6.8 and 6.9
Jan 24: Negative cycles.
Introduction to network flows. Read section 6.10.
Jan 29: Network flows and
Ford-Fulkerson algorithm. Read pp337-351.
Jan 31: Finding good augmenting
paths.
Bipartite matching/vertex cover. Read 351-357, section 7.5
Feb 5, 7 : Applications of
network flows. Disjoint paths, circulations, lower bounds on
capacities, survey design, project selection. Read: 7.6-8, 7.11
Feb 12: Review Session
Feb 14: Midterm test in class.
All material above up to and including February 7 lecture, plus
assignments.
Feb 19,21: Linear Programming.
Formulations and discussion of certificates for the three possible
outcomes. Read: lp_handout.pdf in "hidden" folder, Sections 7.1
and 7.4 and Komei Fukuda's notes
Chapter 1.
Mar 4: Introduction to lp_solve
(see announcements). More on certificates for infeasible systems
(Farkas' Lemma) and how to find using lp_solve.
Coming up: NP-completeness. An
introductory comic
(thanks to Sevan). Upcoming slides:
All slides starting 08 in the hidden folder.
Mar 6, 11. Introduction to the
classes P, NP, EXP. Problem reductions. NP-complete problems. Cook's
theorem(stated without proof.) Read: Text 451-4, 463-466. Note we will
not be using Circuit Satisfiability
as our "first" NP-complete problem, but we will use Satisfiability (SAT, P. 450)
instead.
Mar 13: We reduced SAT to 3-SAT
to IND SET to VERTEX COVER and also IND SET to CLIQUE. Read 459-466.
Mar 18: We reduced 3-SAT to
SUBSET SUM to PARTITION and also SUBSET SUM to KNAPSACK. 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.
Mar 25: NP-hard problems. Co-NP.
Integer programming formulation of MAX 3-SAT. Discussion of why there
are no general certificates for NP-hard problems. Read: 495-500.
Mar 26: Tutorial on
NP-completeness, 12-1pm McConnell 322 (SOCS lounge).
Coming Up: Chapter 11,
Approximation algorithms
Mar 27: Approximation algorithms
for Vertex Cover. Read: Text sections 11.4 and 11.6
April 1: Approximation algorithms
for machine scheduling. We got tighter bounds than those given in the
text. Read: Text section 11.1.
April 3: Local search. Max cut
and Best Response dynamics. Read: 11.1, 12.4, 12.7.
April 8,10: We will go over
Assignment 4 solutions, and the final exam from Dec 2007. Other
topics by email request.
April 18: Final exam, 9am-12 noon place
TBA.