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, 4th edition.

             

Washburn, Sherwood and Marlowe, Thomas, DISCRETE MATHEMATICS