# MATH-275: Discrete Mathematics

School
Science, Technology, Engineering & Math
Department
Mathematics
Course Subject
Mathematics
Course Number
275
Course Title
Discrete Mathematics
Credit Hours
4.00
Instructor Contact Hours Per Semester
62.00 (for 15-week classes)
Student Contact Hours Per Semester
62.00 (for 15-week classes)
A-E
Pre-requisites
MATH-180 with a C or better OR concurrent enrollment in MATH-180
Catalog Course Description

For students in a computer engineering or computer science program. Covers logic, methods of proof, set theory, algorithms, recursion, correctness, relations, partial orderings, graphs, trees, Boolean algebra, grammars, and finite-state machines. Includes various applications throughout the course. Requires a graphing calculator, with the TI-84 Plus series recommended.

### Goals, Topics, and Objectives

Goal Statement
1. To provide an introduction to the mathematical reasoning required to read, comprehend, and construct mathematical arguments.
2. To provide methods for working with discrete structures–the abstract mathematical structures used to represent discrete objects and the relationships between these objects.
3. To demonstrate classes of problems solved by the specification of algorithms.
4. To present applications of discrete mathematics–in particular, applications to computer science.
Core Course Topics
1. Logic and Proof
1. Define the negation of a proposition.
2. Define (using truth tables) the disjunction, conjunction, exclusive or, conditional, and biconditional of the propositions p and q.
3. Define the converse, inverse, and contrapositive of a conditional statement.
4. Determine whether two propositions are logically equivalent.
5. Determine whether an argument is valid.
6. Describe what is meant by, and give examples of, direct proofs and proofs by contradiction.
7. Prove a biconditional statement.
8. Apply the rules of logic to evaluate and construct mathematical arguments and proofs.
2. Sets and Functions
1. Determine whether one set is a subset of another.
2. Determine the cardinality of a set.
3. Determine the union, intersection, difference, and symmetric difference of two sets.
4. Explain the relationship between logical equivalences and set identities.
5. Define the domain, codomain, and range of a function.
6. Define what it means for a function to be one-to-one or onto and give examples of functions that are or are not one-to-one or onto.
7. Define and apply various types of functions encountered in discrete structures, including the ceiling and floor functions and recursive functions.
3. Algorithms
1. Describe algorithms, including search and sort algorithms, that will accomplish various tasks.
2. Express an algorithm in pseudocode.
3. Determine properties of an algorithm, including its computational complexity.
4. Induction and Recursion
1. Prove a statement by mathematical induction.
2. Prove a statement using strong induction.
3. Give recursive definitions and describe recursive algorithms.
4. Solve problems involving basic results from number theory, matrices, sequences and summations, and recursive definitions.
5. Use assertions to determine the correctness of a program.
5. Counting
1. Solve problems, including probability problems, that require counting principles (including the product rule, the sum rule, and principle of inclusion-exclusion).
2. State, and solve problems involving, the Pigeonhole Principle.
3. Determine, and solve problems involving, the number of permutations or combinations of n objects taken r at a time.
6. Relations
1. Describe properties of, and methods of representing, a relation, including an n-ary relation.
2. Determine whether a relation is an equivalence relation.
3. Determine whether a relation is a partial ordering.
7. Graphs and Trees
1. Describe properties of graphs, including paths and connectedness.
2. Determine whether a graph is bipartite.
3. Determine whether two graphs are isomorphic.
4. Determine whether a graph is a tree.
5. Apply results relating the numbers of edges and vertices of various types in trees.
8. Boolean Algebra
1. Compute the complement of a Boolean function.
2. Compute the sum and product of Boolean functions.
9. Modeling Computation
1. Describe and apply properties of grammars.
2. Describe properties of finite-state machines, including machines with and without output.

### Assessment and Requirements

1. All students will be required to complete a comprehensive final examination that assesses the learning of all course objectives. This exam must be weighted in a manner so that this exam score is worth a minimum of fifteen percent (15%) of the final course grade. In selected semesters this exam may be a common exam administered to all sections of Math 275.
2. Additional assessment of student achievement may include assignments, quizzes, and exams.
3. Application problems must not only be included on chapter exams but also on the final exam.
General Course Requirements and Recommendations
• A graphing calculator is required of each student. The Mathematics Department recommends and uses the TI-84 series.
• Application problems must be covered in all mathematics courses. Every section in any course outline that includes application problems must be covered.

### Outcomes

General Education Categories
• Mathematics
Institutional Outcomes
• Quantitative Literacy
MTA Categories
• Category 3: Mathematics (College Algebra Track)

### Approval Dates

Effective Term
Fall 2019
ILT Approval Date
11/26/2018
AALC Approval Date
12/19/2018
Curriculum Committee Approval Date
01/16/2019