Skip to main content
CPE
203
Discrete Structures
Basic logic (propositional logic, predicate logic, limitations, applications in computing). Sets, relations, and functions. Proof techniques (formal proofs, direct, contraposition and contradiction, induction). Basics of counting (permutations and combinations, counting arguments, pigeonhole principle and generating functions). Graphs and trees (spanning trees, shortest path, Euler and Hamiltonian cycles, and traversal strategies). Recursion (definitions, developing and solving recursive equations). The focus of materials is on the applications side of computer engineering.
Prerequisites:
0410101,0410111
0612203
(3-0-3)

Credits and Contact Hours

3 credits, 43 hours

Course Instructor Name

Dr. Buthainah S. Al-Kazemi, Prof. Anastasios Dimitriou

Textbook

Discrete Mathematics and Its Applications, Kenneth H. Rosen, 8th Edition

Catalog Description

Basic logic (propositional logic, predicate logic, limitations, applications in computing). Sets, relations, and functions. Proof techniques (formal proofs, direct, contraposition and contradiction, induction). Basics of counting (permutations and combinations, counting arguments, pigeonhole principle and generating functions). Graphs and trees (spanning trees, shortest path, Euler and Hamiltonian cycles, and traversal strategies). Recursion (definitions, developing and solving recursive equations). The focus of materials is on the applications side of computer engineering.

Prerequisite

MATH-102 and MATH-111

Specific Goals for the Course

Analyze a logical proposition and evaluate its truth table to determine whether it is true or false. (Student outcomes: 1)

Use formal proof techniques (proof by contradiction and proof by induction). (Student outcomes: 1)

Solve problems that use logic, sets, and functions. (Student outcomes: 1)

Identify properties of mathematical relations (including reflexive, symmetric, anti-symmetric and transitive properties).

Recognize and use partial orderings and equivalence relations.

Solve problems that use permutations and combinations and make use of the pigeonhole property and the principle of inclusion/exclusion. (Student outcomes: 1)

Construct and solve simple recurrence relations. (Student outcomes: 1)

Apply graph theory concepts to model and solve real-world problems. (Student outcomes: 1)

Topics to Be Covered

The foundations of logic, set and functions

Proof techniques (formal proofs, direct, contraposition and contradiction, induction)

Counting principles and discrete probability

Relations (relations and their properties, representing relations, closures of relations, equivalence relation, partial orderings) and recurrence relations

Graphs theory

Trees and their applications