| Module Code | MAU22C00 |
| Module Name | Discrete Mathematics |
| ECTS Weighting [1] | 10 ECTS |
| Semester Taught | Semester 1 & 2 |
| Module Coordinator/s | Dr Andreea Nicoara & Dr John Stalker |
Module Learning Outcomes
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 identify 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;
- 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.
Assessment Details
| Assessment Component | Brief Description | Learning Outcomes Addressed | % of Total | Week Set | Week Due |
| Continuous Assessment | Assignments consisting of problems; no minimal level of engagement set. | LO1, LO2, LO3, LO4, LO5, LO6, and LO7 | 40% | Weeks 3-8, 10-14, 22-27, 29-33 | Weeks 4-9, 10-15, 23-28, 29-34 |
| Examination | Given in Trinity Term. | LO1, LO2, LO3, LO4, LO5, LO6, and LO7 | 60% | N/A | N/A |
Reassessment Details
In-person Examination (Time Limited), 3 hours, 100%.
Contact Hours and Indicative Student Workload
| Contact Hours (scheduled hours per student over full module), broken down by: | 90 hours |
| Lecture, 3 per week during term time | 66 hours |
| Tutorial, 1 per week during term time and reading weeks | 24 hours |
| Independent Study (outside scheduled contact hours), broken down by: | 150 hours |
| Preparation for classes and review of material (including preparation for examination, if applicable) | 75 hours |
| Completion of assessments (including examination, if applicable) | 75 hours |
| Total Hours | 240 hours |
Reading List
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
Module Co-requisites
N/A