Department of Mathematics

Math 03.150  Discrete Mathematics


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.


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.


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


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