Mathematical logic and proof, mathematical induction, counting methods, recurrence relations, algorithms and complexity, graph theory and graph algorithms.
Discrete Mathematics with Graph Theory, Goodaire and Parmenter, 3rd edition
| 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 |
