School

Science, Technology, Engineering and Math

Division

Mathematics

Department

Mathematics

Academic Level

Undergraduate

Course Subject

Mathematics

Course Number

275

Course Title

Discrete Mathematics

Credit Hours

4.00

Instructor Contact Hours Per Semester

77.00 (for 15-week classes)

Student Contact Hours Per Semester

77.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 non-graphing scientific calculator for some formal assessments, access to a free graphing utility application to support learning and during informal assessments, and access to an online homework assessment.

## 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 properties of finite-state machines.

## 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 final 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 final exam may be a common final exam administered to all sections of Math-275.
- All students will be required to complete at least two proctored on-campus exams. The cumulative value of those exams must be at least 40% of a student’s final grade.
- Additional assessment of student achievement may include assignments, quizzes, and exams.
- For proctored in-person formal assessments (quizzes, tests, and exams) the only technology students can use is a non-graphing scientific calculator. Quizzes, tests, and exams may have non-calculator parts. Class projects and informal assessments will require students to use a free graphing application to support learning.
- Application problems must not only be included on chapter exams but also on the final exam.

General Course Requirements and Recommendations

- A non-graphing scientific calculator is required for proctored in-person formal assessments.
- Free graphing applications will be used to support learning, informal assessments, and class work.
- Access to an online homework management system is also required.
- 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

MTA Categories

- Category 3: Mathematics (College Algebra Track)

Satisfies Wellness Requirement

No

Effective Term

Fall 2024