MATH 2200 - Discrete Mathematics

Credit Hours: 4.00

Objectives:

1. Translate English statements into logical expressions using propositions and connectives.
2. Translate English statements into symbolic expressions involving predicates and quantifiers.
3. Translate a symbolic logical expression into English.
4. Construct truth tables for compound proposition.
5. Demonstrate two expressions are logically equivalent using truth tables.
6. Show that two expressions are logically equivalent using laws of logic.
7. Determine the truth-value of an expression involving quantifiers.
8. Construct truth tables for Boolean functions.
9. Construct a logic circuit corresponding to a Boolean function.
10. Determine the output from a logic circuit.

Outcome 2: Upon completion of this course, the student will perform basic set operations.

Objectives:

1. Use set builder notation.
2. Work with subsets.
3. Find combinations of sets involving unions, intersections, compliments and Cartesian products.
4. Show that two sets are equal by: showing that they are subsets of each other, using laws of set operations, using membership tables, and using Venn diagrams.
5. Determine the cardinality of a set using the principle in inclusion-exclusion.
6. Determine if a relation is a function.
7. Determine whether a function is a bijection.

Outcome 3: Upon completion of this course, the student will draw and explain the significance of graphs and trees.

Objectives:

1. Recognize the difference between a simple graph, a multigraph, and a psuedograph.
2. Construct an adjacency matrix for graph.
3. Construct a graph from its adjacency matrix.
4. Use the adjacency matrix to determine the number of paths of a fixed length from one vertex to another.
5. Determine the degrees of the vertices of a graph.
6. Determine if a graph is bipartite.
7. Determine if a graph has an Euler cycle.
8. Construct an incidence matrix for a graph.
9. Determine if two graphs are isomorphic and verify the result.
10. Use a digraph to represent a relation.
11. Determine if the relation is an equivalence relation.
12. Determine if a graph is a tree.
13. Determine if a tree is balanced.
14. Work with the relationship between the number of vertices, internal vertices, and leaves for a full m-ary tree.

Outcome 4: Upon completion of this course, the student will calculate permutations and combinations.

Objectives:

1. Determine the cardinality of a set using the multiplication principle.
2. Count the number of possible outcomes using the sum rule.
3. Work with the pigeonhole principle.
4. Count the number of possible outcomes using permutations.
5. Count the number of possible outcomes using combinations.
6. Use the binomial theorem to expand a binomial.
7. Use the above counting techniques to determine the probability of an event.

Outcome 5: Upon completion of this course, the student will identify and analyze recurrence relations.

Objectives:

1. Provide a simple formula for geometric and arithmetic sequences.
2. Compute the first 5 terms of sequence defined recursively.
3. Prove a result using mathematical induction.
4. Find the solution of a simple recurrence formula using an iterative approach.
5. Solve a linear homogeneous recurrence relation with constant coefficients using the characteristic polynomial.
6. Construct a simple algorithm using psuedocode.
7. Measure the complexity of a program in psuedocode using big-o and big-theta measurements.
8. Work with the division algorithm and modular arithmetic.
9. Convert numbers from one base to another with emphasis on binary, octal, and hexadecimal number systems.
10. Use the Euclidean algorithm.

1. Logic
   1. Propositional calculus
      1. Language of propositions
      2. Symbolic representation
      3. Truth tables
      4. Laws of logic
      5. Logical equivalence
   2. Predicate calculus
   3. Symbolic representation
   4. Quantifiers
   5. Language of quantifiers
   6. Symbolic representation
   7. The truth-value of a logical expression using predicates and quantifiers
   8. Nested quantifiers
2. Boolean Algebra
   1. Boolean arithmetic
   2. Boolean functions
   3. Logic Circuits
3. Sets
   1. Set operations: unions, intersections, complements, and Cartesian products
   2. Relations and functions
      1. Images
      2. Properties of functions: injection, surjection, and bijection
      3. Inverse functions
4. Algorithms
   1. Search algorithms
      1. Linear
      2. Binary
   2. Sorting algorithms
      1. Bubble sort
      2. Insert sort
   3. Big-O, Big-Omega, Big-Theta
   4. Complexity of algorithms
5. Integers
   1. Prime numbers and composite numbers
   2. Division algorithm
   3. Modular arithmetic
   4. Other bases
   5. Euclidian algorithm
   6. Sequences
   7. Summation
      1. Finite geometric series
   8. Mathematical induction
6. Counting
   1. Product rule
   2. Sum rule
   3. The Pigeonhole Principle
   4. Permutations
   5. Combinations
      1. Binomial coefficients
      2. Binomial theorem
   6. Finite probability
   7. Modeling with recurrence relations
   8. Solving homogeneous recurrence relations with constant coefficients
7. Graph theory
   1. Types of graphs
   2. Graph terminology
      1. Paths and cycles
      2. Degree of a vertex
   3. Euler Cycles
   4. Matrix representations of graphs
   5. Isomorphic of graphs
   6. Trees
      1. Tree terminology
      2. Properties of trees