ROWAN UNIVERSITY

Department of Mathematics

Syllabus

1703.160 Discrete Structures

1703.160 Discrete Structures 3 s.h.

(Prerequisites: 1701.122 Precalculus 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 and trees 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