Lecture Notes for COMP572 -- Fall 2004
All revisions to the lecture notes will be recorded
here.
- Introduction
PS PDF
The fact that there are n^{n-2} spanning trees on K_n is
Cayley's theorem. One standard proof of Cayley's theorem uses
Prufer encodings. See these two links for
more information:
Link1
Link2
- Maximum Flows PS
PDF
Last revision of slides: 9/9/04
The description in the slides follows Sections 26.1-26.3 of the
CLRS book.
- Binomial & Fibonnacci Heaps and an Introduction to
Amortized Analysis
Our description will follow Chapter 19, Sections 17.1-17.3 and Chapter
20 of the
CLRS book.
Another (possibly simpler) reference is Chapter 11 of Data Structures and
Algorithm Analysis in C, Mark Allen Weiss, 1993, Benjamin Cummings.
Also check out this
animation of Fibonacci Heaps
Binomial Heaps
PS PDF
Amortized Analysis
PS PDF
Fibonacci Heaps
PS PDF
Last revision of slides: 21/9/04
- The Hungarian Algorithm for the Assignment Problem
PS PDF
Last revision of slides: 28/9/04
Corrects major bug on page 13 and 18
Please also see this handout (PS
PDF) for proof of lemma on page 13
Our description follows formulation presented in
http://www.cs.ucsb.edu/~suri/cs230/Matching.pdf
For a nice historical introduction on the development of the algorithm see
pages 4-10 of
On the history of
combinatorial optimization (till 1960)
by Alexander
Schrijver
-
Linear Programming
This (long) section is based on Chapter 2+ of
Papadimitriou and Steiglitz
After learning about LP check out the short guide
What Can’t You Do
With LP? by Devdatt P. Dubhashi for an interesting perspective.
Simplex Part 1: Introduction and Basic Feasible
Solutions
PS PDF
Last revision of slides: 6/10/04
Simplex Part 1 (extra) Correspondence between
polytopes and feasible sets
PS PDF
Simplex Part 2: Changing BFSs and Pivots
PS PDF
Last revision of slides: 13/10/04
Simplex Part 3: The Simplex Algorithm
PS
PDF
Last revision of slides: 14/10/04
Odds & Ends: Variations on Simplex & LP
PS
PDF
-
Linear Programming Duality PS
PDF
This section is based on Chapter 3 of
Papadimitriou and Steiglitz
Last revision of slides:
01/11/04
Some more applications of Duality
PS PDF
-
The Primal-Dual Algorithm
This section is based on Chapter 5 of
Papadimitriou and Steiglitz
Primal-Dual Part 1: Introduction and Basic
Concepts
PS PDF
Last revision of slides: 23/11/04
Primal-Dual Part 2: Shortest Path & Max-Flow
PS
PDF
Primal-Dual Part 3: (Extra Material)
Approximation Algorithms
PS
PDF
-
Dynamic Programming Speedups
This section is based on papers referenced in the notes. In
particular, check out, Efficient dynamic programming using quadrangle
inequalities, by F.F. Yao in the Proceedings of the 12th Annual ACM
Symposium on Theory of Computing (1980) available through the ACM
Digital Library via the HKUST library.
DP Speedups 1: Introduction and the
Quadrangle Inequality
PS PDF
A worked example PS
PDF
DP Speedups II: Totally Monotone Matrices
PS PDF
Last revision of slides: 07/12/04
Note: The PS version of DPII doesn't
display properly on some GS viewers. The PDF version is recommended