## Introduction to Discrete Mathematics

Department:
MATH
Course Number:
2603
Hours - Lecture:
3
Hours - Lab:
0
Hours - Recitation:
2
Hours - Total Credit:
4
Typical Scheduling:
Every Semester

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

Prerequisites:

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