This course is a continuation of MATH 1120. It introduces students to more advanced topics in graph theory, inclusion and exclusion, recurrence relations, generating functions, optimization and matching, with an emphasis on applications in computer science.
Prerequisites
MATH 1120 or equivalent.
Course type
This course is offered as part of a VCC program and cannot be taken individually.
International students: Eligibility is determined at the program level. Visit the program page for international student requirements and application information.
- • Inclusion-exclusion: The principle of inclusion-exclusion (review); Generalized inclusion-exclusion; Derangements • Generating functions: Introduction to generating functions; Computational techniques; Inverses; Rational generating functions; Partitions of integers; Coefficient extraction • Recurrence relations: General form of linear recurrence relations; First-order linear recurrence relations; Second-order linear homogeneous relations; Nonhomogeneous recurrence relations; Solutions via method of undetermined coefficients; Solutions via generating functions • Graph theory: Review; Euler trails and circuits; Planar graphs; Hamilton paths and cycles; Graph coloring and chromatic number • Optimization and matching: Review of trees; Dijkstra's shortest-path algorithm; Minimum spanning trees: Kruskal's and Prim's algorithms; Matching theory
Course schedules
Select your program to see the available course schedules.
How to take this course
This course is offered as part of a VCC program only.
Contact us
If you have any questions, please email at [email protected].
† This information is intended as a guideline only. Program and course details are subject to change with the approval of VCC's Board of Governors.