Discrete Mathematics

AY2018/2019 Semester 2

This core course aims to develop your understanding of fundamental mathematical concepts such as basic counting principles, recurrence relations and basic graph theory concepts. We will cover various combinatorial aspects of graph theory and introduces some of the tools used to tackle graph theoretical questions. These concepts are essential for future mathematics courses. You will learn to understand and apply basic counting principles, and to model practical problems using graph models and apply graph algorithms to solve them. Course Content Counting 1. inclusion-exclusion principle 2 permutations and combinations 3. binomial theorem 4. combinatorial proof 5. generalized permutations and combinations a. permutations around a cycle b. permutations/combinations with repetitions Recurrence Relations 1. linear homogeneous recurrence 2. linear non-homogeneous recurrence Graph Theory 1. paths and circuits 2. trees 3. spanning trees 4. isomorphisms 5. Euler paths/circuits 6. Hamilton paths/circuits 7. planar graphs 8. graph colorings 9. graph algorithms a. Breadth-First Search b. Traversal of a tree: pre-order, in-order, post-order c. Prim's algorithm d. Kruskal's algorithm e. Bellman-Ford algorithm