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:
Most current editions of the following:
By Rosen (McGraw-Hill) Category/Comments - The majority of Chapters 8-13 and 15 should be covered. Recommended
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.
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.
Recurrence Relations and their applications
Solving Linear Recurrence Relations
Divide-and-Conquer Algorithms and Recurrence Relations
Applications of Inclusion-Exclusion
Relations and Their Properties
Graphs and Graph Models
Graph Terminology and Special Types of Graphs
Representing Graphs and Graph Isomorphism
Euler and Hamilton Paths
Introduction to Trees
Applications of Trees
Minimum Spanning Trees
Representing Boolean Functions
Minimization of Circuits
Languages and Grammars
Finite-State Machines with Output
Recommended maximum class size for this course: 20
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.