# Columbia College

## Master Syllabus

 Administrative Unit: Computer and Mathematical Sciences Department Course Prefix and Number: MATH 225 Course Title: Discrete Mathematics I
Number of:
 Credit Hours 3
 Lecture Hours 3
 Lab Hours 0
 Catalog Description: This course provides a foundation in formal mathematics and theorem-proving. Topics include functions, relations, sets, simple proof techniques, propositional logic, elementary number theory, the fundamentals of counting, recursion, and an introduction to algorithms. Prerequisite: Grade of C or higher in MATH 201. Prerequisite(s) / Corequisite(s): Grade of C or higher in MATH 201. Course Rotation for Day Program: Offered Fall & Spring. Text(s): Most current editions of the following:A TI-84 calculator is required for this course. This calculator will be allowed on most assessment opportunities in this course. Discrete Mathematics and its ApplicationsBy Rosen ( Science Engineering & Math) Recommended Course Objectives To model and analyze computational processes using analytic and combinatorial methods. To use logical notation to define and reason about fundamental mathematical concepts such as sets, relations, functions and integers. To learn the algorithmic approach to problem solving. To display an understanding of the nature of rigorous proof. To write elementary proofs, especially proofs by induction and basic number theory proofs. To reason mathematically about basic data types and structures used in computer algorithms and systems. Measurable Learning Outcomes: Calculate numbers of possible outcomes of elementary combinatorial processes using the sum and product rules, permutations and combinations. Illustrate the use of quantifiers to form mathematical statements and arguments. Apply the fundamental laws of logic and rules of inference to analyze arguments and to form logical arguments. Describe and explain basic set theory definitions and use the set theoretic operations. Describe and explain the well-ordering principles and use in the method of proof by induction. Employ the basic properties of integers such as divisibility, primes and congruences to solve basic number theory problems. Demonstrate a thorough knowledge of the concept of a function including the concepts: range, domain, one-to-one, into, onto, and inverse. Describe and explain the recursive definition of sequences and functions. Use equivalence relations to partition sets. Determine the complexity of an algorithm. Topical Outline: Fundamental principles of counting The rules of sum and product Permutations Combinations: The binomial theorem Combinations with repetition Fundamentals of logic Basic connectives and truth tables Logical equivalence: The laws of logic Logical implication: Rules of inference The use of quantifiers Quantifiers, definitions, and proofs of theorems Set theory Sets and subsets Set operations and the laws of set theory Counting and venn diagrams Properties of the integers: Mathematical induction The well-ordering principle: Mathematical induction Recursive definitions The division algorithm: Prime numbers The greatest common divisor: The Euclidean algorithm The fundamental theorem of arithmetic Relations and functions Cartesian products and relations Functions, one-to-one, and onto Special functions such as the floor and ceiling functions The pigeonhole principle Function composition and inverse functions Computational complexity Analysis of algorithms More on relations Properties of relations Equivalence relations Equivalence relations and partitions 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: Kenneth Felts Date: November 6, 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.