Department of Mathematics
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.
Demonstrate knowledge of logical reasoning, manipulate formal
prepositional logic, and evaluate Boolean expressions.
b) Topical Outline
1. Number bases
2. Mathematical induction
Examples of mathematical 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)
Recursive definitions of functions
Other functions and sequences
Permutations and combinations
Pigeon hole principle
6. Graphs and trees
Eulerian and Hamiltonian circuits
Trees (binary, spanning)
Graph coloring (as time permits)
7. Logic and Boolean algebras
Boolean algebras and possibly Boolean circuits (as time permits)
8. Other proof techniques
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