MATH 2200 - Discrete Mathematics
Credit Hours: 4.00
Prerequisites: MATH 1760 with grade C or better; or an equivalent college course; or an acceptable score on a placement or prerequisite exam
MATH 2200 is an introduction to logic, circuits, graphs, trees, matrices, algorithms, combinatorics and relations within the context of applications to computer science.
Billable Contact Hours: 4
Search for Sections
OUTCOMES AND OBJECTIVES
Outcome 1: Upon completion of this course, the student will build the truth table for a complex Boolean expression and draw the corresponding circuit diagram.
- Translate English statements into logical expressions using propositions and connectives.
- Translate English statements into symbolic expressions involving predicates and quantifiers.
- Translate a symbolic logical expression into English.
- Construct truth tables for compound proposition.
- Demonstrate two expressions are logically equivalent using truth tables.
- Show that two expressions are logically equivalent using laws of logic.
- Determine the truth-value of an expression involving quantifiers.
- Construct truth tables for Boolean functions.
- Construct a logic circuit corresponding to a Boolean function.
- Determine the output from a logic circuit.
Outcome 2: Upon completion of this course, the student will perform basic set operations.
- Use set builder notation.
- Work with subsets.
- Find combinations of sets involving unions, intersections, compliments and Cartesian products.
- 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.
- Determine the cardinality of a set using the principle in inclusion-exclusion.
- Determine if a relation is a function.
- 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.
- Recognize the difference between a simple graph, a multigraph, and a psuedograph.
- Construct an adjacency matrix for graph.
- Construct a graph from its adjacency matrix.
- Use the adjacency matrix to determine the number of paths of a fixed length from one vertex to another.
- Determine the degrees of the vertices of a graph.
- Determine if a graph is bipartite.
- Determine if a graph has an Euler cycle.
- Construct an incidence matrix for a graph.
- Determine if two graphs are isomorphic and verify the result.
- Use a digraph to represent a relation.
- Determine if the relation is an equivalence relation.
- Determine if a graph is a tree.
- Determine if a tree is balanced.
- 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.
- Determine the cardinality of a set using the multiplication principle.
- Count the number of possible outcomes using the sum rule.
- Work with the pigeonhole principle.
- Count the number of possible outcomes using permutations.
- Count the number of possible outcomes using combinations.
- Use the binomial theorem to expand a binomial.
- 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.
- Provide a simple formula for geometric and arithmetic sequences.
- Compute the first 5 terms of sequence defined recursively.
- Prove a result using mathematical induction.
- Find the solution of a simple recurrence formula using an iterative approach.
- Solve a linear homogeneous recurrence relation with constant coefficients using the characteristic polynomial.
- Construct a simple algorithm using psuedocode.
- Measure the complexity of a program in psuedocode using big-o and big-theta measurements.
- Work with the division algorithm and modular arithmetic.
- Convert numbers from one base to another with emphasis on binary, octal, and hexadecimal number systems.
- Use the Euclidean algorithm.
COMMON DEGREE OUTCOMES (CDO)
• Communication: The graduate can communicate effectively for the intended purpose and audience.
• Critical Thinking: The graduate can make informed decisions after analyzing information or evidence related to the issue.
• Global Literacy: The graduate can analyze human behavior or experiences through cultural, social, political, or economic perspectives.
• Information Literacy: The graduate can responsibly use information gathered from a variety of formats in order to complete a task.
• Quantitative Reasoning: The graduate can apply quantitative methods or evidence to solve problems or make judgments.
• Scientific Literacy: The graduate can produce or interpret scientific information presented in a variety of formats.
CDO marked YES apply to this course:
Critical Thinking: YES
Quantitative Reasoning: YES
COURSE CONTENT OUTLINE
- Propositional calculus
- Language of propositions
- Symbolic representation
- Truth tables
- Laws of logic
- Logical equivalence
- Predicate calculus
- Symbolic representation
- Language of quantifiers
- Symbolic representation
- The truth-value of a logical expression using predicates and quantifiers
- Nested quantifiers
- Boolean Algebra
- Boolean arithmetic
- Boolean functions
- Logic Circuits
- Set operations: unions, intersections, complements, and Cartesian products
- Relations and functions
- Properties of functions: injection, surjection, and bijection
- Inverse functions
- Search algorithms
- Sorting algorithms
- Bubble sort
- Insert sort
- Big-O, Big-Omega, Big-Theta
- Complexity of algorithms
- Prime numbers and composite numbers
- Division algorithm
- Modular arithmetic
- Other bases
- Euclidian algorithm
- Finite geometric series
- Mathematical induction
- Product rule
- Sum rule
- The Pigeonhole Principle
- Binomial coefficients
- Binomial theorem
- Finite probability
- Modeling with recurrence relations
- Solving homogeneous recurrence relations with constant coefficients
- Graph theory
- Types of graphs
- Graph terminology
- Paths and cycles
- Degree of a vertex
- Euler Cycles
- Matrix representations of graphs
- Isomorphic of graphs
- Tree terminology
- Properties of trees
Official Course Syllabus - Macomb Community College, 14500 E 12 Mile Road, Warren, MI 48088
Add to Favorites (opens a new window)