School

Science, Technology, Engineering & Math

Department

Mathematics

Academic Level

Undergraduate

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)

Grading Method

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

- To provide an introduction to the mathematical reasoning required to read, comprehend, and construct mathematical arguments.
- To provide methods for working with discrete structures–the abstract mathematical structures used to represent discrete objects and the relationships between these objects.
- To demonstrate classes of problems solved by the specification of algorithms.
- To present applications of discrete mathematics–in particular, applications to computer science.

Core Course Topics

- Logic and Proof
- Define the negation of a proposition.
- Define (using truth tables) the disjunction, conjunction, exclusive or, conditional, and biconditional of the propositions p and q.
- Define the converse, inverse, and contrapositive of a conditional statement.
- Determine whether two propositions are logically equivalent.
- Determine whether an argument is valid.
- Describe what is meant by, and give examples of, direct proofs and proofs by contradiction.
- Prove a biconditional statement.
- Apply the rules of logic to evaluate and construct mathematical arguments and proofs.

- Sets and Functions
- Determine whether one set is a subset of another.
- Determine the cardinality of a set.
- Determine the union, intersection, difference, and symmetric difference of two sets.
- Explain the relationship between logical equivalences and set identities.
- Define the domain, codomain, and range of a function.
- 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.
- Define and apply various types of functions encountered in discrete structures, including the ceiling and floor functions and recursive functions.

- Algorithms
- Describe algorithms, including search and sort algorithms, that will accomplish various tasks.
- Express an algorithm in pseudocode.
- Determine properties of an algorithm, including its computational complexity.

- Induction and Recursion
- Prove a statement by mathematical induction.
- Prove a statement using strong induction.
- Give recursive definitions and describe recursive algorithms.
- Solve problems involving basic results from number theory, matrices, sequences and summations, and recursive definitions.
- Use assertions to determine the correctness of a program.

- Counting
- Solve problems, including probability problems, that require counting principles (including the product rule, the sum rule, and principle of inclusion-exclusion).
- State, and solve problems involving, the Pigeonhole Principle.
- Determine, and solve problems involving, the number of permutations or combinations of n objects taken r at a time.

- Relations
- Describe properties of, and methods of representing, a relation, including an n-ary relation.
- Determine whether a relation is an equivalence relation.
- Determine whether a relation is a partial ordering.

- Graphs and Trees
- Describe properties of graphs, including paths and connectedness.
- Determine whether a graph is bipartite.
- Determine whether two graphs are isomorphic.
- Determine whether a graph is a tree.
- Apply results relating the numbers of edges and vertices of various types in trees.

- Boolean Algebra
- Compute the complement of a Boolean function.
- Compute the sum and product of Boolean functions.

- Modeling Computation
- Describe and apply properties of grammars.
- Describe properties of finite-state machines, including machines with and without output.

### Assessment and Requirements

Assessment of Academic Achievement

- 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.
- Additional assessment of student achievement may include assignments, quizzes, and exams.
- 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.

### Approval Dates

Effective Term

Fall 2019