Mathematics

Discrete Mathematics

Module code: G5136
Level 4
15 credits in autumn semester
Teaching method: Lecture
Assessment modes: Unseen examination, Coursework

Mathematics developed because humans had the need to count objects, or to understand the land around them (e.g. areas, volumes, location of stars). So this is where we begin this module.

A proportion of it is devoted to counting, i.e. we will find proper ways to count the number of elements in complicated sets. For example the number of phone numbers that can still connect you to the correct number, even if one digit is wrong.

These principles of counting, like the inclusion-exclusion principle naturally lead into a chapter on combinatorics, where we explore ways to count fast so we can use this ability in other disciplines, like probability.

Finally, we understand that not everything can be counted in a nice fast way. We will develop the idea of recursive equations to help us count complicated sets with the aid of computing power, which also feeds into the Computational Mathematics module.

We also develop the mathematics of graph theory. A graph is just a collection of points and lines and they are extremely versatile modelling objects. For example, a constellation is a graph, a genealogy tree is a graph and so is a map of a country. Similarly, the connections between Instagram followers is a graph, and so is the road network of a city. We will describe properties of all these different graphs in a rigorous mathematical context.

Some questions we may answer:

  • How can you draw a given graph without lifting your pencil from the paper and without backtracking?
  • How can a university timetable be created so that every student can select the modules they like without conflict?
  • How many squares can you see in an NxN square grid?

Module learning outcomes

  • Model real problems using recursive equations of order 1 or 2 and solve them;
  • Identify and classify graphs based on their geometric properties;
  • Apply the basic principles and theorems of counting to a variety of examples.