vcc.ca
MATH 2120: Discrete Mathematics 2
Effective date
September 2026
Department
UT Math
School
Arts and Sciences
Description
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.
Credits
3.0
Year of study
2nd Year Post-secondary
Prerequisites
MATH 1120 or equivalent.
Corequisites
None
Course Learning Outcomes
Upon successful completion of this course, students will be able to:
- Apply and demonstrate more advanced methods of mathematical proof in problem solving.
- Describe and use generating functions to solve counting problems and recurrence relations.
- Solve linear homogeneous and nonhomogeneous recurrence relations and develop recurrence relations to model problems.
- Explain and construct solutions related to Euler trails/circuits, Hamilton path/cycles and chromatic numbers and polynomials.
- Generate functions based on recurrence relations using infinite sums and various algebraic methods.
- Solve optimization problems by implementing the Dijkstra's Shortest-Path algorithm and Kruskal's and Prim's algorithms.
- Solve the “assignment problem” using matching functions that establish one-to-one correspondence between elements of subsets.
Prior Learning Assessment & Recognition (PLAR)
None
Hours
Lecture, Online, Seminar, Tutorial: 60
Total Hours: 60
Total Hours: 60
Instructional Strategies
Lectures and exercises
Grading System
Letter Grade (A-F)
Passing grade
D
Evaluation Plan
|
Type |
Percentage |
Assessment activity |
|
Assignments |
15-30 |
Formative assessments |
|
Midterm Exam |
20-25 |
|
|
Midterm Exam |
20-25 |
|
|
Final Exam |
25-35 |
For the online option, students must receive a grade of at least 50% on the final in order to pass the course. |
Course topics
- • 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
Notes:
- Course contents and descriptions, offerings and schedules are subject to change without notice.
- Students are required to follow all College policies including ones that govern their educational experience at VCC. Policies are available on the VCC website at:
https://www.vcc.ca/about/governance--policies/policies/. - To find out if there are existing transfer agreements for this course, visit the BC Transfer Guide at https://www.bctransferguide.ca.