Course Syllabus 575/513


Chapter references are to Tucker textbook:Applied Combinatorics, Alan Tucker, 6th edition, Wiley, 2012. Additional materials from Pearls in Graph Theory, Hartfield and Ringel, and other scattered sources.

Date Topic Book Reference Comments
9/2 Intro/PidgeonHole A.4  
9/4 Basic Graph Theory ch 1 Basics, graph isomorphism, hand-shaking lemma
9/9 HWK 1 due    
9/9 Basics/planarity ch 1 More basics, planarity, the Kuratowski characterization
9/11 Planarity ch 1 Euler's Thm; Straight-line Thm (Wagner)
9/16 HWK 2 due    
9/16 Euler/Hamilton ch 2 Multigraphs; Euler characterization; Hamiltonian circuits; Ore's Thm
9/18 TSP   Definitions, approximation; branch and bound exact solutions
9/23 HWK 3 due    
9/23 Graph Coloring ch 2 Motivation and applications; The Art Gallery Thm; Five color Thm for planar graphs
9/25 Trees ch 2,3 Basics; rooted trees; puzzles and trees
9/30 HWK 4 due    
9/30 Trees; TSP ch 3 Trees and TSP; the MST-based approximation algorithm
10/2 Matching   Bipartite and non-bipartite matching
10/5 HWK 5 due    
10/7 Flows ch 4 Basics; Ford-Fulkerson algorithm
10/9 HWK 6 due    
10/9 Midterm exam ch 1-4  
10/14 no class columbus day  
10/16 Counting Ch 5 Basic counting I
10/21 Counting   Basic counting II; occupancy problems
10/23 Generating Fns ch 6 The generating function model introduced
10/23 HWK 7 due    
10/28 Generating Fns ch 6 More on generating functions
10/30 Generating Fns ch 6 Exponential generating functions
10/30 HWK 8 due    
11/4 Recurrences ch 7 Modelling via recurrences
11/6 Recurrences ch 7 Solving recurrences
11/6 HWK 9 due    
11/11 Veteran's day   Holiday
11/12 Inclusion/Exclusion ch 8 Basic results and applications
11/13 Inc/Exc/Rook poly ch 8 Rook polynomials
11/13 HWK 10 due ch 8  
11/18 Polya Theory ch 9 Basics on group theory and permutations; Burnside's lemma
11/20 Polya Theory ch 9 Polya theory and the pattern inventory
11/25 Polya Theory ch 9 Polya applications
11/25 HWK 11 due ch 9  
12/2 special topics   Problem solving review for final exam
12/4 wrap up    
12/4 HWK 12 due various  
12/11 Final exam 1-3 in ELab 303  
-- RobbieMoll - 28 Jan 2004
Topic revision: r31 - 2015-03-12 - RobbieMoll
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback

mersin escort adana escort izmir escort gaziantep escort