MATH 342 Applied Combinatorics (3)

Catalog Description:

Counting methods for arrangements and selections, generating functions, recurrence relations, inclusion-exclusion principle, elementary graph theory, trees and searching, network algorithms.


Prerequisites:


MATH 211 Calculus III

Required Course Materials:


Alan Tucker, Applied Combinatorics, 4th edition, John Wiley & Sons Inc., 2001

Course Coordinator:


Lamarr C. Widmer, Ph.D., Professor of Mathematics

Course Audience:


Math and computer science majors

Course Objectives:

  1. To develop problem solving skills.
  2. To emphasize the design of solution methods.
  3. To learn elementary counting techniques in forms of combinations and permutations
  4. To develop the ability to see the mathematics in the structure of the problem.
  5. To write clear and concise descriptions of problems and their solutions.
  6. To use when appropriate, the concept of generating functions and the corresponding identities.
  7. To employ elementary graph theory in solving network and scheduling problems.
  8. To analyze simple games and implement strategies for winning.
  9. To use the inclusion-exclusion principle in analyzing counting problems.
  10. To develop the ability to discern which problem solving technique is appropriate for the given problem.

Topics:

Introductory graph theory, Euler circuits, Hamiltonian paths, graph coloring, planarity, graph isomorphism, shortest paths, networks, and applications of graphs. The combinatorics topics include generating polynomials, exponential generating functions, solving Diophantine equations, the inclusion-exclusion principle, derangements, mathematical induction, recursion and elementary counting problems including partitions of integers, the analysis of elementary games and puzzles using graph analysis will also be a topic of discussion. Comparison of several sorting algorithms will be discussed.


 

Revised: August 2010

Return to Course Index