| Week |
Class |
Covered |
Sections |
Remarks |
| 1 |
R Jan 21 |
What is combinatorics? |
|
The two cultures in mathematics, and Sudoku algorithm |
| 2 |
T Jan 26 |
Counting Principles and Binomial Coefficient |
hw 1 assigned |
Patterns in Pascal Triangle |
| |
R Jan 28 |
Binomial Formula and Identities, counting models |
|
The towers of Hanoi Problem |
| 3 |
T Feb 2 |
Recurrence relations |
hw 2 assigned |
Catalan Addendum |
| |
R Feb 4 |
Solve Recurrence Relations I |
|
Catalan number page by Igor Park |
| 4 |
T Feb 9 |
Solve Recurrence Relations II |
hw3 assigned |
|
| |
R Feb 11 |
Generating functions I |
|
|
| 5 |
T Feb 16 |
Generating functions II |
hw4 assigned |
generatingfunctionology |
| |
R Feb 18 |
Inclusion and Exclusion |
|
|
| 6 |
T Feb 23 |
Exponential Generating Functions |
hw5 assigned |
|
| |
R Feb 25 |
Euler circuit and Chinese Postman Problem |
|
|
| 7 |
T Mar 1 |
trees and spanning trees |
hw6 assigned |
|
| |
R Mar 3 |
Cayley's formula, Bipartite graphs, and matching |
|
|
| 8 |
T Mar 8 |
no class, Spring break |
|
|
| |
R Mar 10 |
no class, Spring break |
|
|
| 9 |
T Mar 15 |
Maximum matching, Hall's Theorem |
hw7 assigned |
|
| |
R Mar 17 |
Matching Theory, proof of Tutte 1-factor Theorem |
|
Augmenting path algorithm, Hungarian Algorithm, Stable matching algorithm |
| 10 |
T Mar 22 |
Connectivity |
hw8 assigned |
|
| |
R Mar 24 |
Menger's Theorem |
|
|
| 11 |
T Mar 29 |
Planar graphs |
hw9 assigned |
|
| |
R Mar 31 |
Vertex coloring--I |
|
|
| 12 |
T Apr 5 |
Vertex coloring--II |
hw10 assigned |
|
| |
R Apr 7 |
Edge coloring and Hamiltonian cycle |
|
|
| 13 |
T Apr 12 |
Ramsey Theory |
hw11 assigned |
|
| |
R Apr 14 |
Latin squares |
|
|
| 14 |
T Apr 19 |
Extremal set system-1 |
hw12 assigned |
|
| |
R Apr 21 |
Extremal set system-2 |
|
|
| 15 |
T Apr 26 |
Extremal set system-3 |
|
|
| |
R Apr 28 |
Final review |
|
|
| Exam |
May 11 |
Final Exam: 9-12 Location: TBD |
|
|
