MAU22C00 Discrete mathematics

This module is examined in a 3-hour examination at the end of Semester 2.
Continuous assessment contributes 40% towards the overall mark.
Any failed components are reassessed, if necessary, by an exam in the reassessment session.

11+11 weeks of teaching with 3 lectures and 1 tutorial per week.

On successful completion of this module, students will be able to

Justify, with reasoned logical arguments, basic properties of mathematical objects that are specified as sets, relations on sets, functions between sets, and/or monoids.
Analyse simple context-free grammars to determine the formal languages that they generate, and construct specifications of context-free grammars and finite state machines that generate and/or determine formal languages, given specifications of such formal languages.
Recognise, identify and justify properties of undirected graphs that are networks consisting of vertices together with edges joining pairs of vertices.
Apply standard algorithms in order to determine spanning trees in connected graphs.
Determine whether a set is finite, countably infinite or uncountably infinite and apply these ideas to the study of formal languages.
Construct a Turing machine that recognises a given formal language.
Understand variants of Turing machines, the classes of Turing-decidable and Turing-recognisable languages, and why not all formal languages are Turing-recognisable.