# Master Syllabus

 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 MathematicsBy Rosen (McGraw-Hill) Category/Comments - The majority of Chapters 8-13 and 15 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: Recurrence Relations and their applications Solving Linear Recurrence Relations Divide-and-Conquer Algorithms and Recurrence Relations Generating Functions Inclusion-Exclusion Applications of Inclusion-Exclusion Relations and Their Properties Representing Relations Equivalence Relations Graphs and Graph Models Graph Terminology and Special Types of Graphs Representing Graphs and Graph Isomorphism Connectivity Euler and Hamilton Paths Shortest-Path Problems Planar Graphs Graph Coloring Introduction to Trees Applications of Trees Tree Traversal Spanning Trees Minimum Spanning Trees Boolean Functions Representing Boolean Functions Logic Gates Minimization of Circuits Languages and Grammars Finite-State Machines with Output 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 using your CougarTrack login and password when prompted.
Prepared by: Ann Schlemper Date: November 13, 2013
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.