Common Course Numbering System

Searching Current Courses For Fall 2016

	Course:	MAT 215
	Title:	Discrete Mathematics: MA1
	Long Title:	Discrete Mathematics: GT-MA1
	Course Description:	Concentrates on formal logic, algorithms, induction proofs, counting and probability, recurrence relations, equivalence relations, graphs, shortest-path applications, and tree traversal. This course is designed for mathematics and computer science students.
	Min Credit:	4
	Max Credit:

Origin Notes:

CCA

 STANDARD COMPETENCIES:

 I.      Use formal logic to create proofs

 II.     Demonstrate understanding of set operations

 III.    Estimate the complexity of algorithms

 IV.     Prove propositions using mathematical induction

 V.      Use combinations and permutations to solve counting problems

 VI.     Solve problems in discrete probability

 VII.    Solve recurrence relations

 VIII.   Find generating functions for recurrence relations

 IX.     Apply the principle of Inclusion-Exclusion

 X       Demonstrate an understanding of equivalence relations

 XI.     Recognize Euler and Hamilton paths

 XII.    Use Dijkstra`s Algorithm to find a shortest path

 XIII.   Demonstrate an understanding of tree traversal: prefix, postfix and infix.

 TOPICAL OUTLINE:

 I.      Logic and Proof, Sets, and Functions

         A.      Logic

         B.      Propositional Equivalences

         C.      Predicates and Quantifiers

         D.      Nested Quantifiers

         E.      Methods of Proof

         F.      Sets and Operations

                 1.      Functions

         G.      Algorithms, Integers and Matrices

         H.      Algorithms

         I.      The growth of Functions

         J.      Complexity of Algorithms

         K.      The Integers and Division

         L.      Integers and Algorithms

         M.      Matrices

 II.     Mathematical Reasoning, Induction, and Recursion

         A.      Proof Strategy

         B.      Sequences and Summations

         C.      Mathematical Induction

         D.      Recursive Definitions and Structural Induction

         E.      Recursive Algorithms

 III.    Counting

         A.      The Basics of Counting

         B.      The Pigeonhole Principle

         C.      Permutations and Combinations

         D.      Discrete Probability

         E.      Introduction to Discrete Probability

         F.      Probability Theory  (Optional)

         G.      Expected Value and Variance (Optional)

 IV.     Advanced Counting Techniques

         A.      Recurrence Relations

         B.      Solving Recurrence Relations

         C.      Generating Functions

         D.      Inclusion-Exclusion

         E.      Applications of Inclusion-Exclusion

 V.      Relations

         A.      Relations and Their Properties

         B.      Representing Relations

         C.      Equivalence Relations

         D.      Partial Orderings

 VI.     Graphs

         A.      Introduction to Graphs

         B.      Graph Terminology

         C.      Representing Graphs and Graph Isomorphism

         D.      Connectivity

         E.      Euler and Hamilton Paths

         F.      Shortest-Path Problems

 VII.    Introduction to Trees

         A.      Introduction to Trees

         B.      Applications of Trees

         C.      Tree Traversal

 VIII.   Optional:  Added computer applications and problems.

Course Offered At:

Common Course Numbering System		Your current Institution is CCCS