Department of Mathematics

SYLLABUS

Math 03.150 Discrete Mathematics

CATALOG DESCRIPTION:

Math 03.150 Discrete Mathematics

This course provides an overview of the branch of mathematics commonly known as discrete mathematics. Topics included are sets, relations, functions, induction and other methods of proof, recursion, combinatorics, graph theory, and algorithms. Emphasis is placed on the solution of problems and proofs. The use of graphing calculator is required.

OBJECTIVES:

In terms of outcomes, students will be able to:

a) discuss and use set theoretic techniques, (operations, Venn diagrams,
etc.).

b) solve problems in combinatorics (permutations, combinations, etc..).

c) perform various operations with relations and functions (congruence,
methods of proof, induction, recursion, etc..).

d) explain and use the concepts of graphs and trees.

e) Apply algorithms to problem situations involving search, optimization,
voting methods, and apportionment.

CONTENT

I. Set theory - 2.5 weeks

· Operations - union, intersection, complement, difference

· DeMorgan's Laws

· Subsets, power sets, Venn diagrams

· Equal vs. equivalent sets

· Countability

· Sets of numbers (integers, reals, etc.)

· Cartesian products

· Proof by Contadiction

· History - Cantor, Mandelbrot, Descartes, Venn

II. Relations and functions - 2.5 weeks

· Symmetry, transitivity, reflexivity

· Equivalence classes

· Congruence, partitions, domain, range, co-domain

· One-to-one, onto, inverse

· Modular numbers

· History - Pythagorean relationship, Descartes

III. Combinatorics - 2 weeks

· Pigeonhole principle

· Fundamental Theorem of Counting

· Permutations

· Combinations

· Binomial Theorem

· History - Pascal's Triangle, Towers of Hanoi, Euclid's geometric
progression

IV. Graph Theory - 4 weeks

· Euler and Hamiltonian networks

· Graph coloring

· Directed and undirected

· Isomorphisms

· Spanning (optional)

· Traveling Salesperson problems

· PERT(Program Evaluation and Resource Technique)

· CPM(Critical Path Method)

· Expression trees (order of operations)

· History - Euler, Hamilton, Bridges of Konigsberg

V. Induction - 1 week

· History - Gauss formulas, classic plane geometry problems

VI. Recursion - 1 week

· History - Nim, Fibonacci, Pascal

VII. Algorithms - 2 weeks

· Voting methods

· Apportionment

· Search algorithms

· Optimization algorithms

TEXTS:

Scheinerman, Edward, Mathematics: A Discrete Introduction, 2006, Cengage.

*Roman, Steven. An Introduction to Discrete Mathematics, 2nd edition, Saunders, NY.

Rosen, Kenneth h. Discrete Mathematics and Its Applications, 2 ed, McGraw/Hill

Barnett, Steven. Discrete Mathematics, Addison Wesley, Reading, MA (Accessory resource for number bases)

Dossey, John A. et al, Discrete Mathematics, 3rd edition, Addison-Wesley, Reading, MA.

Johnsonbaugh, Richard, *Essential Discrete Mathematics*,

MacMillan Publishing Co., NY. 2005

Rev.11/15/02

C:ADVISING~99/DISCMATHSYL