  
Student Learning Outcomes 
 Students will apply number theory, combinatorics, discrete probability, graph theory, and recursion to solve various application problems.
 Students will develop conceptual understanding of formal logic and various methods of arguments that can be used as the basis of a computer program. They will demonstrate and communicate this understanding by writing proofs involving number theory, set theory, combinatorics, and discrete probability.
 Students will develop fluency in deciphering and using the language of logic, proof, and set theory, constructing logical arguments and proofs that can then be used as the basis of a computer program.

Description  
 Discrete mathematics: set theory, logic, Boolean algebra, methods of proof, mathematical induction, number theory, discrete probability, combinatorics, functions, relations, recursion, algorithm efficiencies, graphs, trees.


Course Objectives  
 The student will be able to:
 Use formal logic in constructing valid arguments.
 Write proofs formally, including writing proofs using symbolic logic and Boolean Algebra.
 Use number theory to solve to solve problems.
 Understand the basics of set theory, including solving problems in combinatorics and probability theory.
 Prove combination and permutation principles and use them to solve problems.
 Understand the definition of functions.
 Use recursive thinking and method to solve recurrence relations, including using recursion to analyze algorithms and programs.
 Analyze and write algorithms.
 Identify relations and their properties.
 Draw and analyze graphs and trees, including applying matrices to analyze graphs and trees
 Solve Application problems from Computer Science, including using finite state machines to model computer operations.
 Discuss mathematical problems and write solutions in accurate mathematical language and notation.
 Interpret mathematical solutions.

Special Facilities and/or Equipment  
  Scientific calculator
 When taught hybrid: Four lecture hours per week in facetoface contact and one hour per week using CCC Confer. Students need internet access.

Course Content (Body of knowledge)  
  Logic
 Logical Forms and Equivalences
 Conditional Statements
 Valid and Invalid Arguments
 Predicates and Quantified Statements
 Boolean Algebra
 Application: Digital Logic Circuits
 Methods of Proof/Proof Techniques
 Direct Proof
 Proof by Counterexample
 Proof by Division into Cases
 Proof by Contradiction and Contraposition
 Proof by Induction
 Strong Mathematical Induction and WellOrdering
 Number Theory
 Properties of Prime and Rational Numbers
 Unique Factorization Theorem
 QuotientRemainder Theorem
 Modular Arithmetic
 Floor and Ceiling Notation
 Applications of Number Theory to Problem Solving
 Principal of inclusion and exclusion
 Set Theory
 Notation
 Operations on Sets
 Cartesian Products
 Proving Set Identities
 Counting and Probability
 Events and Sample Space
 Possibility Trees and Multiplication Rule
 Addition Rule
 Pigeonhole Principle
 Combinations and Permutations
 Pascal's Formula
 Binomial Theorem
 Discrete Probability Axioms
 Expected Value
 Conditional Probability, Baye's Formula
 Integer Random variables
 Expectations
 Law of large numbers
 Functions
 OnetoOne, Onto, Inverses
 Compositions
 Well Defined Functions
 Recursion
 Recursively Defined Sequences
 Fibonacci numbers
 Solving Recurrence Relations by Iteration
 Solving Recurrence Relations using Logarithm
 Verifying Solutions by Mathematical Induction
 Efficiency of Algorithms
 BigO, BigTheta, and BigOmega Notation
 Exponential and Logarithmic Orders
 Computing Orders of Algorithms
 Analysis of Various Sort and Search Algorithms
 Relations
 Binary Relations, Nary relations
 Directed Graphs
 Inverse Relations
 Reflexivity, Symmetry, and Transitivity
 Equivalence Relations and Classes
 Graphs and Trees
 Definitions and Properties
 Paths and Circuits
 Euler Path
 Hamiltonian Circuit
 shortest path and minimal spanning tree
 Matrix Representation of Graphs
 Isomorphisms of Graphs
 Spanning Trees
 Traversal Problems
 Decision trees
 Huffman Codes
 Warshall's algorithm
 Solve Application problems from Computer Science
 The application of mathematical induction to recursive computer algorithms
 The use of sequences in loop structures
 The application of computer logic
 AND, OR and NOTGATES
 Boolean algebra structure
 logic networks
 minimization
 Breaking down problems or functions into components, subproblems or subfunctions
 The use of timecomplexity to determine BigO growth rate of various algorithms
 Articulation points (cut vertices) and computer networks
 Modeling arithmetic, computation, and languages including algebraic structures, finitestate machines and formal logic
 Discuss mathematical problems and write solutions in accurate mathematical language and notation.
 Application problems from other disciplines
 Proper notation
 Interpret mathematical solutions.
 Explain the significance of solutions to application problems.

Methods of Evaluation  
  Written homework
 Quizzes, tests
 Proctored comprehensive final examination

Representative Text(s)  
 Epp, Susanna S. Discrete Mathematics with Applications. 4th ed. Brooks/Cole, 2010.

Disciplines  
 Mathematics


Method of Instruction  
  Lecture
 Discussion
 Cooperative learning exercises


Lab Content  
 Not applicable.


Types and/or Examples of Required Reading, Writing and Outside of Class Assignments  
  Homework Problems: Homework problems covering subject matter from text and related material ranging from 30  60 problems per week. Students will need to employ critical thinking in order to complete assignments.
 Lecture: Five hours per week of lecture covering subject matter from text and related material. Reading and study of the textbook, related materials and notes.
 Projects: Student projects covering subject matter from textbook and related materials. Projects will require students to discuss mathematical problems,write solutions in accurate mathematical language and notation and interpret mathematical solutions. Projects may require the use of a computer algebra system such as Mathematica or MATLAB.
 Worksheets: Problems and activities covering the subject matter.
Such problems and activities will require students to think critically. Such worksheets may be completed both inside and/or outside of class.
