**COURSE DESCRIPTION**

Presents topics in discrete mathematical structures that are basic tools used in computer science. Covers sets, Boolean algebra, counting methods, generating functions and recurrence relations, graph theory, trees, and an introduction to finite state automata. Lecture 4 hours per week.

**GENERAL COURSE PURPOSE**

The objective of this course is to examine mathematical structures and procedures that facilitate the manipulation of discrete or non-continuous data. The course will examine topics that are essential for advanced study in Computer Science and topics that provide powerful tools for mathematical settings in which calculus techniques are not appropriate.

**ENTRY LEVEL COMPETENCIES**

Prerequisite is MTH 174 - "Calculus with Analytic Geometry II" or equivalent

**COURSE OBJECTIVES**

Upon completion of this course, the student should be able to:

A. solve problems involving the concepts of sets, including universe set, null set, subset, union, intersection, complement, differences, Cartesian product and the power setB. understand the logical process, methods of proof and Boolean algebra

C. solve problems using the basic principles of counting theory, including permutation, combinations, and the pigeonhole principle

D. solve problems involving functions and relations, including operations and properties of functions and using recursive relations to solve problems and develop algorithms

E. recognize graphs, represent them as a matrix, solve graph problems and understand related graph algorithms

F. understand trees, including spanning trees and tree traversal algorithms

**MAJOR TOPICS
TO BE INCLUDED**

A. Sets1. Definition, notation, magnitude2. Relations between

a. Subset3. Operations

b. Superset

c. Proper subset

d. Equality

e. Universe and null set

f. Power set

B. Logic, Methods of Proof, and Boolean Algebraa. Union4. Properties

b. Intersection

c. Complement

d. Difference

e. Symmetric difference

f. Cartesian products1. Formal logicC. Counting Methodsa. Propositions2. Methods of Proof

b. Truth tables

c. Tautologiesi. Associative lawd. Logic of quantified statements

ii. Commutative law

iii. Distributive law

iv. DeMorgan's law

e. Valid and invalid argumentsa. Direct proof3. Boolean Algebra

b. Proof by contradiction

c. Proof by contrapositive

d. Proof by Mathematical Inductiona. Algebraic structure

b. Expressions

c. Logic and networks

d. Combinatorial circuits1. PrinciplesD. Functions and Relations2. Permutations

3. Combinations

4. Other methods

5. Pigeonhole Principle

1. Definitions and propertiesE. Graphsa. Reflexive2. Operations

b. Transitive

c. Symmetric

d. Antisymmetric

e. Equivalence relations

f. Orderings (partial, total, well)a. Composition3. Recursive relations

b. Inversea. Definition

b. Solving

c. Use in algorithm analysis1. DirectedF. Trees2. Undirected

3. Isomorphisms

4. Matrices, Relations, and Graphs

5. Traversal problems

a. Edge6. Graph algorithms

b. Vertex1. Definition and propertiesG. Introduction to Finite State Automata2. Spanning trees

3. Traversal

A. AlgorithmsB. Number systems

C. Error detecting/correcting codes

D. Generating functions