MAU22C00 – Discrete Mathematics

Module Learning Outcomes

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

1. Justify with reasoned logical arguments basic properties of mathematical objects that are specified as sets, relations on sets, functions between sets, and/or monoids;
2. 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;
3. Recognise, identify, and justify properties of undirected graphs that are networks consisting of vertices together with edges joining pairs of vertices;
4. Apply standard algorithms in order to identify spanning trees in connected graphs;
5. Determine whether a set is finite, countably infinite or uncountably infinite and apply these ideas to the study of formal languages;
6. Construct a Turing machine that recognises a given formal language;
7. Distinguish variants of Turing machines, determine whether a given formal language is Turing-decidable or Turing-recognisable, and justify why not all formal languages are Turing-recognisable.

Module Content

The mathematical objects studied in this module are fundamental not just for theoretical computer science but constitute the building blocks for formalising problems and writing down algorithms to solve those problems. The aim of the module is thus twofold. It seeks to provide a lifelong ability to operate with the mathematical objects studied in the context of solving concrete problems. It also aims to make students comfortable with mathematical proofs in order to enable them to parse without difficulty all theoretical arguments that they will see in their subsequent coursework.

Specific topics addressed in this module include the following:

• The Principle of Mathematical Induction;
• Sets, Relations and Functions;
• Introduction to Abstract Algebra;
• Introduction to Formal Languages and Context-Free Grammars;
• Introduction to Graph Theory;
• Algorithms for computing Minimal Spanning Trees;
• Spanning Trees in Connected Graphs;
• Countability of Sets;
• Turing Machines.

Teaching and Learning Methods

The module will consist of formal lectures and small group tutorials. Students will be expected to complete problem sets. The mathematical objects, results, and techniques taught in MAU22C00 underpin all subsequent coursework in computer science. Students are expected to engage with the material not just to pass an exam at the end of the academic year but to acquire lifelong proficiency.

Reassessment Details

In-person Examination (Time Limited), 3 hours, 100%.

Contact Hours and Indicative Student Workload

The course notes are the primary source material needed for the course. Two optional textbooks will be placed on reserve in the Hamilton Library:

• Robert Wolf “Proof, Logic, and Conjecture: The Mathematician’s Toolbox.”
• Michael Sipser “Introduction to the Theory of Computation.”

Module Pre-requisites

Prerequisite modules: Modules CSU11001 (Mathematics I) and CSU12002 (Mathematics II) or equivalent modules developing the necessary mathematical skills in areas such as calculus, linear algebra, first order logic, and set theory.

Other/alternative non-module prerequisites: N/A

N/A

Blackboard