Module Descriptors

Mathematical Studies

MA204: Discrete Mathematics (5 ECTS)

This course deals with elementary enumeration, permutations, combinations, and graphs including eulerian and hamiltonian graphs.

Taught in Semester(s) 1. Examined in Semester(s) 1.

Workload: 100 hours (24 Lecture hours, 12 Tutorial hours, 64 Self study hours).

Module Learning Outcomes. On successful completion of this module the learner should be able to:

  1. Distinguish between orderings (permutations) and subsets (combinations).
  2. Count the size of unions and intersections of sets and solve elementary recurrences.
  3. Define and apply Binomial and multinomial coefficients to enumeration problems.
  4. Use tree graphs for enumeration.
  5. Use trees to write algebraic expressions in Polish and Reverse Polish notation.
  6. Define the notion of graph, eulerian, hamiltonian, bipartite and tree graphs.
  7. Define the notion of graph colourings and applications to scheduling problems.

Indicative Content

The course introduces the fundamentals of Discrete Mathematics. How to count, the addition rule, the multiplication rule. the Inclusion-Exclusion formula. Permutations and Combinations. the Binomial coefficients and some identities. Recurrences, the Fibonacci numbers, Derangements, "Tower of Hanoi". Distributions, Multinomial coefficients. Introduction to Graph Theory, Euler and the Koenigsberg Bridges Problem. Eulerian and Hamiltonian graphs. Tree graphs and bipartite graphs. Ordered Rooted trees, Polish and Reverse Polish Notation. Planarity of Graphs. Eulers formula for a connected planar graph. Colouring of Graphs the Welsh-Powell algorithm. Applications to simple scheduling problems.

Module Resources

Back