MATH 310 Syllabus

Discrete Structures

Revised: February 2015

Course Description

Graph Theory: planarity, eulerian, hamiltonian, colorings, and trees. Enumeration: permutations, combinations, generating functions, recurrence relations, and inclusion-exclusion. Prerequisites: MATH 250. Three credit hours.

Student Learning Objectives

  • Use graphs to model and solve a variety of problems;
  • Identify and prove structural properties possessed by a given graph; and
  • Use combinatorial modeling to solve problems in discrete mathematics.

Text

Alan Tucker, Applied Combinatorics (Fourth Edition), John Wiley & Sons, 2002.

Grading Procedure

Grading procedures and factors influencing course grade are left to the discretion of individual instructors, subject to general university policy.

Attendance Policy

Attendance policy is left to the discretion of individual instructors, subject to general university policy.

Course Outline

  • Chapter 1: Elements of Graph Theory (6 days)
    All sections: Graph models, graph isomorphisms, edge counting, and planarity.
  • Chapter 2: Covering Circuits and Graph Coloring (6 days)
    All sections: Euler circuits, Hamiltonian cycles, graph coloring, and coloring theorems.
  • Chapter 3: Trees and searching (5 days)
    Sections 1 - 2: Properties of trees, depth-first and breadth-first searching, and spanning trees. Remaining topics may be covered at the instructor's discretion.
  • Chapter 4: Network Algorithms (Optional, at the instructor's discretion as time allows)
  • Chapter 5: Counting Methods for Selections and Arrangements (10 days)
    Sections 1 - 4, and highlights of section 5: Basic counting principles, arrangements and selections, arrangements and selections with repetition, distributions, and binomial coefficients.
  • Chapter 6: Generating Functions (4 days)
    Sections 1 and 2: Generating function models, and calculating coefficients of generating functions.
  • Chapter 7: Recurrence Relations (4 days)
    Sections 1 - 3: Recurrence Relation models, divide-and-conquer relations, and solutions of linear recurrence relations.
  • Chapter 8: Inclusion-Exclusion (4 days)
    Sections 1 - 3: Counting with Venn diagrams, the inclusion-exclusion formula, and rook polynomials (if time allows).
Office of Web Services