Date Notes Topics Additional References
Mar 29 See textbook Ch 1,2 Basic definitions; Cayley’s theorem  
Mar 31 See textbook Ch 2 plus text supplement Another proof for Cayley’s theorem, finding a Minimum Spanning Tree in weighted graphs, applications in phylogeny
Apr 5 Notes Basic Asymptotics, Introduction to NP-Hardness
  • a compendium of NP optimization problems
  • a great book on approximation algorithms
Apr 7 See textbook plus handout given in class. Eulerian and Hamiltonian Circuits, Euler's Theorem, applications in bio-informatics: Sequencing by Hybridization
Apr 12 See textbook Ch 5 Hall's marriage theorem, system of distinct representatitves  
Apr 14 Notes coming soon. finding perfect and maximum matchings and minimum vertex cover in bipartite and general graphs  
Apr 19 MVV paper matching via matrix inversion  
Apr 21 MVV paper matching via matrix inversion (cont'd) matrix inversion using parallel processing
Apr 26 See handout given in class. stable matching
Apr 28 See handout given in class. stable matching Three books on stable marriage problem: Donald Knuth, et al, Al Roth, et al, Dan Gusfield, et al
May 3   Max Flow - Min Cut Theorem, Algorithms, Menger's Theorem Textbook Ch 7
May 5 Textbook Ch 6 Dilworth's Theorem, Extremal Set Theory  
May 10 Lecture Notes Coming Soon. Linear Programs, Duality, Applications to Network Flow  
May 12 For definitions, see textbook Ch 3 Graph Coloring, Chromatic Number of a Graph, Brook's Theorem  
May 17   Midterm - No lecture  
May 19 Handout The Probabilistic Method A great book by Alon and Spencer
May 24 Coming Soon Planar Graphs and Four Coloring Theorem  
May 26 Notes Random Walks and Spectral Graph Theory
  • A course on Spectral Graph Theory by Spielman
  • A book on the relationship between random walks and electrical networks.