M426 – Advanced Discrete Mathematics Course Outline
Texts: Discrete Mathematics and its Applications – Rosen
Applications of Discrete Mathematics – Michaels and Rosen
Additional Notes
Week Topic Sections
1 Graphs and Maps, Logic and networks xxx
2 Euler and Hamilton paths, Djiksta’s Algorithm 7.5, 7.6, Ch. 20
Chinese Postman Problem
3 Trees – Introduction to trees, spanning trees, 8.1, 8.2, 8.5, 8.6
minimal spanning trees, Huffman trees
Kruskal’s algorithm.
4 Tree traversal, tree sorting 8.3, 8.4
5 Network flows Ch. 23, Notes
6 Stirling numbers Ch. 6, Notes
7 Catalan numbers Ch. 7, Notes
8 Languages and grammars, finite state machines 10.1, 10.2
Midterm exam
9 Finite state machines 10.3
10 Language recognition, Kleene’s theorem, 10.4, 10.5
Turing machines
11 Kehonen maps Notes
12 Petrie Nets
Ch. 24
13 Markov chains Ch
2, Notes
14 Markov chains
Notes
Final Exam