Overview
Description
Counting rules; generating functions; recurrence relations; inclusion-exclusion; pigeonhole principle; Ramsey theory; fundamental graph theory concepts (connectedness, coloring, planarity); Eulerian/Hamiltonian chains and circuits; matching.
Requirements
Recommended Preparation
MATH 330
Original catalog text
Recommended Preparation
Recommended Preparation: MATH 330.
Units
Lecture3
Catalog Details
Offering
Offered: Every Fall
Terms
fall
Attributes
Standard
Learning Outcomes
- solve simple and complex counting problems, by using the addition and product rules, recognizing permutation/combinations with and without replacement, rephrasing as occupancy problems, and/or using the inclusion-exclusion principle/derangements.
- demonstrate an understanding of the concept of computational complexity for algorithms, including the use of “Big O” notation.
- demonstrate an understanding of the main concepts of graph theory, including graphs versus digraphs, connectedness, graph coloring, planarity, as well as the properties of bipartite graphs, complete graphs, and trees.
- demonstrate knowledge of some of the great historical problems and results in graph theory/combinatorics, including the four-color problem, the Konigsberg bridge problem, Euler’s formula, the travelling salesman problem, the hatcheck problem, Kuratowski’s theorem, Ramsey’s theorem, and the solution to the Fibonacci recursion.
- make simple “discrete” arguments/proofs, such as using mathematical induction or making “combinatorial arguments”.