Skip to Main Content

MASTER SYLLABUS

Master Syllabus

Print this Syllabus « Return to Previous Page

Administrative Unit: Computer and Mathematical Sciences Department
Course Prefix and Number: MATH 325
Course Title: Discrete Mathematics II
Number of:
Credit Hours 3
Lecture Hours 3
Lab Hours 0
Catalog Description: This course continues the discussion begun in Discrete Mathematics I (MATH 225) and serves to develop students’ understanding of the discrete mathematical concepts that underlie computer science. Topics in this second course include recurrence relations, graphs, paths and circuits, trees and optimization and matching theory. Prerequisite: Grade of C or higher in MATH 225.
 
Prerequisite(s) / Corequisite(s): Grade of C or higher in MATH 225.
 
Course Rotation for Day Program: Offered Spring.
 
Text(s): Most current editions of the following:

Discrete and Combinatorial Mathematics
By Grimaldi (Addison Wesley/Longman)
Category/Comments - The majority of Chapters 8-13 and 15 should be covered.
Recommended
Discrete Mathematics with Combinatorics
By Anderson (Prentice Hall)
Category/Comments - The majority of Chapters 6, 11, 13-16, and 19 should be covered.
Recommended
 
Course Objectives
  • To understand an algorithmic approach to problem solving.
  • To study further the topic of recurrence relations that is fundamental to computer science.
  • To understand and appreciate the topics of discrete mathematics and their applicability to computer science.
  •  
    Measurable Learning Outcomes:
  • Reason mathematically about basic data types and structures used in computer algorithms and systems.
  • Apply graph theory models of data structures and state machines to solve problems of connectivity and constraint satisfaction such as scheduling.
  • Derive closed-form and asymptotic expressions from series and recurrences for growth rates of processes.
  • Describe and successfully implement “recursive thinking.”
  • Solve recurrence relations by various techniques.
  • Evaluate and utilize graph characteristics such as vertex degree, connectedness, and matrix representations.
  • Determine whether Euler and Hamiltonian circuits exist for a given graph.
  • Work and model with discrete structures.
  • Apply recurrence relations to the analysis of algorithms.
  • Recognize paths, cycles and Euler cycles in a graph.
  •  
    Topical Outline:
  • The principle of inclusion and exclusion
    - Generalizations of the principle
  • Generating functions
    - Introductory examples
    - Definition and examples: calculational techniques
    - Partitions of integers
    - The exponential generating functions
    - The summation operator
  • Recurrent relations
    - The first-order linear recurrence relation
    - The second-order linear homogeneous recurrence relation with constant coefficients
    - The non-homogeneous recurrence relation
    - The method of generating functions
    - A special kind of nonlinear recurrence relation (Optional)
    - Divide and conquer algorithms
  • An introduction to graph theory
    - Definitions and examples
    - Subgraphs, complements, and graph isomorphism
    - Vertex degree: Euler trails and circuits
    - Planar graphs
    - Hamilton paths and cycles
    - Graph coloring and chromatic polynomials
  • Trees
    - Definitions, properties, and examples
    - Rooted trees
    - Trees and sorting
    - Weighted trees and prefix codes
    - Biconnected components and articulation points
  • Optimization and matching
    - Dijkstra’s Shortest Path Algorithm
    - Minimal spanning trees: the algorithms of Kruskal and Prim
    - Transport networks: the max-flow min-cut theorem
    - Matching theory
  • Boolean algebra and switching functions
    - Switching functions: disjunctive and conjunctive normal forms
    - Gating networks: minimal sums of products: Kamaugh maps
    - Further applications: don’t-care conditions
    - The structure of a Boolean algebra (optional)
  •  
    Culminating Experience Statement:

    Material from this course may be tested on the Major Field Test (MFT) administered during the Culminating Experience course for the degree. 
    During this course the ETS Proficiency Profile may be administered.  This 40-minute standardized test measures learning in general education courses.  The results of the tests are used by faculty to improve the general education curriculum at the College.

     

    Recommended maximum class size for this course: 20

     
    Library Resources:

    Online databases are available at http://www.ccis.edu/offices/library/index.asp. You may access them from off-campus using your CougarTrack login and password when prompted.

     
    Prepared by: Lawrence West Date: October 25, 2007
    NOTE: The intention of this master course syllabus is to provide an outline of the contents of this course, as specified by the faculty of Columbia College, regardless of who teaches the course, when it is taught, or where it is taught. Faculty members teaching this course for Columbia College are expected to facilitate learning pursuant to the course objectives and cover the subjects listed in the topical outline. However, instructors are also encouraged to cover additional topics of interest so long as those topics are relevant to the course's subject. The master syllabus is, therefore, prescriptive in nature but also allows for a diversity of individual approaches to course material.

    Office of Academic Affairs
    12/04