Module MAU2C00: Discrete Mathematics
- Credit weighting (ECTS)
- 10 credits
- Semester/term taught
- Michaelmas and Hilary terms 2019-20
- Contact Hours
- 22 weeks, 3 lectures including tutorials per week
- Lecturer
-
Prof. Andreea Nicoara
Prof. John Stalker
- Learning Outcomes
-
On successful completion of this module, students will be able to
- justify, with reasoned logical argument, 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;
- recognize, 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;
- figure out 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.
- Module Content
-
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
- Module Prerequisite
- Module CS1001 (Mathematics I), or an equivalent module developing the necessary mathematical skills in areas such as calculus and linear algebra.
- Assessment Detail
- This module will be examined in a 3 hour examination in Trinity term. Also students should complete a small number of assignments during the academic year. The final grade at the annual examination session will be a weighted average over the examination mark (90%) and the continuous assessment mark (10%). Re-assessments if required will consist of 100% exam.