# Module MA2C03: Discrete Mathematics

**Credit weighting (ECTS)**- 10 credits
**Semester/term taught**- Michaelmas and Hilary terms 2017-18
**Contact Hours**- 22 weeks, 3 lectures including tutorials per week
**Lecturer**- Prof. Andreea Nicoara
**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%). The final grade at the supplemental examination session will be wholly determined by the supplemental examination paper.