Text: Introduction to Algorithms,
Cormen, Leiserson, Rivest, Stein (2nd edition)
Full text available on-line at: http://www.library.mcgill.ca/lists/books247.html
Jan 13: Introduction to course via statement of two problems: the assignment
problem and the travelling salesman problem. Outline
of material to be covered in the course. General notions of easy
and hard problems.
Greedy algorithms. Sushi (knapsack)
problem.
Read: introduction(pdf)
Text: Sections 16.1, 16.2
Jan 15: Introduction to selection problems, weighted selection problems
and the greedy algorithm.
Read:
Course notes on selection
(pdf)
and do the exercises!
Jan 20: Proof of the optimality of the greedy algorithm Introduction
to minimum spanning trees. Kruskal's algorithm viewed as
an example of greedy selection. Read:
Review text Ch. 23
Jan 22: Introduction to dynamic programming. Matrix chain multiplication.
Read: David
Bryant's Handout(pdf).
Text: Section 15.2.
Jan 27: More examples of dynamic programming. Knapsack Problem
(see Ex. 16.2-2, p. 384).
C code for knapsack problem and sample run is here.
There is a revision to assignment 1, question 1.
Jan 29: More examples of dynamic programming. Paths through a grid.
Read: David Bryant's Handout(pdf)
.
Feb 3: 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.
Feb 5: Disjkstra's algorithm for directed graphs with non-negative
edge weights. Shortest paths on acyclic graphs. Comparison with
Prim's algorithm. Read: Chapter 24 up to the end of Section 24.3
Feb 10: Johnson's algorithm. Read: Section 25.3. Introduction
to Network Flows.
Note: Network flows are covered in the text,
Sections 26.1, 26.2 using a different definition of flow.
Feb 12: The augmenting path algorithm for finding a maximum flow. Cuts,
and their use in certifying a maximum flow.
Read: The
approach used in class: lecture notes
Feb 17: More on augmenting paths, residual graphs, proof of max flow/
min cut theorem. Read: The approach used in class: lecture notes (first 4 pages)
Feb 19: Matchings in bipartite graphs. Solution via Network Flows.
Certificate of optimality of matching given by a vertex cover of the same
size - known as Konig's Theorem (1931). Section 26.3 of the text has
most of the material but not Konig's Theorem. We did problem 26.3-5 at
the end of the lecture.
Read: Lecture notes
up to the middle of page 8-4, and text Section 26.3
March 2: Review. March 4: Midterm
March 9: 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,
"What's love got to do with it?", which contains the above quote.
Mar. 11: You will need the lp package lp_solve for the next part
of the course, please check announcements for
details.
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: Komei Fukuda's LP notes up
to P. I-5.
Mar. 16: Three outcomes for LP: optimum solution, unbounded solution,
infeasible. The dual LP and certificates for optimality. Statement of strong
and weak duality theorems. Read: Fukuda's notes up to the end of Section
2.2 (you can skip Theorem 2.3).
March 18: Infeasible inequalities and Farkas Lemma. Read: Fukuda's notes
Section 2.3, 2.4
March 23: How to find a solution to a system of inequalities. Read: article
March 25: Introduction to the theory of NP-completeness. Definition of
P and NP. Examples from the problems we have looked at in the course.
Read:
Notes distributed in class and Cormen et al. pages 966-982.
March 30: Problem reductions. Examples from problems studied in the class.
Definition of NP-complete and NP-hard. Cook's theorem and its consequences.
April 1: Reductions from SAT to 3-SAT to INDEPENDENT SET to
VERTEX COVER. Read: Class handout and Cormen 984-6, 1003-8.
Note:
We use the definition of SAT in the handout given in class (ie conjunctive
normal form). The problem SAT in Cormen also allows
implication and if and only if. What we call 3-SAT,
Cormen calls 3-CNF-SAT.
April 6: Reductions from 3SAT to Subset sum to {Partition,Knapsack}.
Read Cormen section 34.5.5.
April 8: Wrap up. Send suggestions in advance!
return to: course home page