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 set

B. 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. Sets

1. Definition, notation, magnitude

2. Relations between

a. Subset
b. Superset
c. Proper subset
d. Equality
e. Universe and null set
f. Power set

3. Operations

a. Union
b. Intersection
c. Complement
d. Difference
e. Symmetric difference
f. Cartesian products

4. Properties

B. Logic, Methods of Proof, and Boolean Algebra

1. Formal logic

a. Propositions
b. Truth tables
c. Tautologies

i. Associative law
ii. Commutative law
iii. Distributive law
iv. DeMorgan's law

d. Logic of quantified statements
e. Valid and invalid arguments

2. Methods of Proof

a. Direct proof
b. Proof by contradiction
c. Proof by contrapositive
d. Proof by Mathematical Induction

3. Boolean Algebra

a. Algebraic structure
b. Expressions
c. Logic and networks
d. Combinatorial circuits

C. Counting Methods

1. Principles

2. Permutations

3. Combinations

4. Other methods

5. Pigeonhole Principle

D. Functions and Relations

1. Definitions and properties

a. Reflexive
b. Transitive
c. Symmetric
d. Antisymmetric
e. Equivalence relations
f. Orderings (partial, total, well)

2. Operations

a. Composition
b. Inverse

3. Recursive relations

a. Definition
b. Solving
c. Use in algorithm analysis

E. Graphs

1. Directed

2. Undirected

3. Isomorphisms

4. Matrices, Relations, and Graphs

5. Traversal problems

a. Edge
b. Vertex

6. Graph algorithms

F. Trees

1. Definition and properties

2. Spanning trees

3. Traversal

G.  Introduction to Finite State Automata

A. Algorithms

B. Number systems

C. Error detecting/correcting codes

D. Generating functions