Combinatorics and Graph Theory

This course explains how to reason and model using enumerative combinatorics and applied graph theory. It also stresses the systematic analysis of different possibilities, exploration of the logical structure of a problem, and ingenuity. Combinatorial reasoning underlies all analysis of computer systems. It plays a similar role in discrete operations research problems and infinite probability. Topics covered include generating functions, set partitions, recurrence relations, inclusion-exclusion, trees, graph connectivity, independence, graph coloring, Hamiltonian and Euler circuits and paths. Additional topics include computational complexity and the theory of NP-complete problems and theoretical computer science, and recursion theory.