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