ROWAN
UNIVERSITY

Department
of Mathematics

Syllabus

**Math 03.160
Discrete Structures
**

**Math 03.160 Discrete Structures 3s.h.
**

(Prerequisites: Math-01.122 Precalculus or Math-01.130 Calculus I
or permission of the department of mathematics or permission of the department
of computer science)

This course covers mathematical topics
essential for work in computer science. This material includes number bases,
mathematical induction, sets, relations, functions, congruence, recursion,
combinatorics, graphs, trees, logic, Boolean algebras, and proof techniques.
While this is a course in mathematics, many of the examples and applications
will be taken from computer science. The instructor may require use of a
graphing calculator and / or computer. This course covers much of the same
material as Discrete Mathematics (1703.150), but with a computer science focus.
In no case

will a student be allowed to receive
credit for both courses. Both courses will be treated as equivalent for the
purposes

of satisfying prerequisites and course
requirements.

**a)
****Objectives in Relation to Student Outcomes**

Upon completion of this course,
students should be able to:

1. Calculate using
binary and hexadecimal arithmetic

2. Understand
and use mathematical induction and other techniques to prove mathematical
results.

3. Understand and work
with sets, relations, functions, and congruences.

4. Perform computations
using recursively defined functions and structures.

5. Use methods of
combinatorics to solve counting problems.

6. Illustrate the basic terminology and
properties of graphs and trees, as well as relate graphs andtrees to algorithms
and counting.

7.

Demonstrate
knowledge of logical reasoning, manipulate formal

prepositional
logic, and evaluate Boolean expressions.

**b)
****Topical Outline**

** **

1. __Number
bases__

Binary

Hexadecimal

2.
__Mathematical induction__

Examples of mathematical induction

Strong induction

3.
__Sets, relations functions, congruences__

Sets (Venn diagrams, complements,
power sets, operations, laws)

Relations (equivalence relations,
equivalence classes)

Functions (injective, surjective,
inverse, composition, domain, codomain, range)

4.
__Recursion__

Recursive definitions of functions

Factorials

Fibonacci sequences

Other functions and sequences

5.
__Combinatorics__

Binomials

Counting arguments

Permutations and combinations

Pigeon hole principle

6.
__Graphs and trees__

Directed graphs

Undirected graphs

Eulerian and Hamiltonian circuits

Trees (binary, spanning)

Graph coloring (as time permits)

7.
__Logic and Boolean algebras__

Truth tables

Propositional calculus

Boolean algebras and possibly
Boolean circuits (as time permits)

8.
__Other proof techniques__

Direct proof

Proof by counterexample

Proof by contrapositive

Proof by contradiction

Logical equivalence and circles of
implication

** **

**Possible
Texts:** Kolman, Bernard
et al Busby, Robert and Ross, Sharon, *DISCRETE MATHEMATICS STRUCTURES, *4^{th}
edition.

Washburn, Sherwood and Marlowe,
Thomas, *DISCRETE MATHEMATICS *