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

                 Primitive shift registers

 

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