AMS 301, Finite Mathematics Structures

Catalog Description: Introduction to graph theory and combinatorial analysis. The emphasis is on solving applied problems rather than on theorems and proofs. Techniques used in problem solving will include generating functions, recurrence relations, and network flows. This course develops the type of mathematical thinking that is fundamental to computer science and operations research.  SBC: STEM+

Prerequisite: AMS 210 or MAT 211 orAMS 361 or MAT303.

3 credits

Course Materials for Winter and Spring 2024:

"Applied Combinatorics" by Alan Tucker, 6th edition, John Wiley & Sons; ISBN# 9780470458389

AMS 301 IS ALSO OFFERED DURING SUMMER SESSION.

 

Topics
1.  Basic concepts of graphs, graph models and isomorphism - 4 class hours.
2.  Euler and Hamilton circuits and their applications - 3 class hours.
3.  Graph coloring and its applications - 3 class hours.
4.  Trees, their use in searching - 5 class hours.
5.  Problems with permutations and combinations - 8 class hours.
6.  Generation Functions -  5 class hours.
7.  Recurrence Relations - 4 class hours.
8.  Inclusion-Exclusion principle - 5 class hours
9.  Examinations and Review – 5 class hours. 

Learning Outcomes for AMS 301, Finite Mathematical Structures

1.) Strengthen logical reasoning skills to solve combinatorial problems using:
        * elements of propositional calculus;
        * proof by contradiction;
        * logical consequences of assumptions.

2.) Learn to find multiple (equally valid) ways to solve a combinatorics problem:
        * apply a top-down strategy (breaking a problem into parts and subparts); 
        * apply a bottom-up strategy (solving special subcases and building up).
        * learn to solve problems from first principles, rather than looking for existing templates or formulas.
        * solve a complementary problem;
        * use different strategies to categorize subcases of a problem;
        * use different techniques (e.g., generating functions, inclusion-exclusion).

3.) Learn basic graph theory results and apply them in problem-solving: 
        * isomorphism; 
        * planar graphs; 
        * Hamilton circuits and Euler cycles;
        * graph coloring; 
        * trees and ways to search them.

4.) Use formulas for counting basic combinatorial outcomes to construct solutions to more complex combinatorial enumeration problems:
        * permutations, with and without repetition;
        * combinations, with and without repetition.

5.) Apply counting strategies to solve discrete probability problems.

6.) Use specialized techniques to solve combinatorial enumeration problems:
        * generating functions; 
        * recurrence relations; 
        * inclusion-exclusion principle.