Introduction to Discrete Mathematics

Course Number: 
Hours - Lecture: 
Hours - Lab: 
Hours - Recitation: 
Hours - Total Credit: 
Typical Scheduling: 
Every Semester

Mathematical logic and proof, mathematical induction, counting methods, recurrence relations, algorithms and complexity, graph theory and graph algorithms.


MATH 1552 or MATH 1502 or MATH 1512 or MATH 15X2.

This course is equivalent to MATH 2602.

Course Text: 

Discrete Mathematics with Graph Theory, Goodaire and Parmenter, 3rd edition

Topic Outline: 
Topic Text Sections Lectures

Logic and proofs: Compound statements, proofs, truth tables, sets, relations, functions.

 0.1-0.2, 2.1-2.4, 3.1-3.2 11

Algorithms and recursion. Division algorithm, Euclidean algorithm, congruence, mathematical induction, recursively defined sequences, recurrence relations and the characteristic polynomial, algorithms, complexity, searching and sorting.

4.1-4.2, 4.4-4.5, 5.1-5.3, 8.1-8.3 11

Combinatorics: Inclusion/exclusion principle, addition and multiplication rules, pigeonhole principle, permutations, combinations, repetitions, probability, binomial theorem.

6.1-6.3, 7.1-7.5, 7.7 11

Graph Theory: Isomorphism, Eulerian paths, Hamiltonian paths, Dijkstra's algorithm, trees, Kruskal's algorithm, planar graphs, chromatic number.

9.1-9.3, 10.1-10.2, 10.4, 12.1-12.3, 13.1-13.2 11