This module aims to provide a broad and stimulating introduction to the theory of computing.
Aims and Objectives
Learning Outcomes
Syllabus
Automata theory
- Finite state automata, regular expressions and regular languages
- The pumping lemma for regular languages
- Closure properties of regular languages
- Context-free grammars and pushdown automata
- Closure properties of context-free languages
- The pumping lemma for context-free languages
Computability theory
- Turing machines, recursively enumerable and recursive languages
- Church-Turing thesis
- Limitations of algorithms: universality, the halting problem and undecidability
Computational complexity theory
- Complexity of algorithms and of problems
- Complexity classes
- Polynomial-time reduction
- NP-Completeness and Cook's theorem
Learning and Teaching
Teaching and learning methods
The content of this module is delivered through lectures, the module website, directed reading, pre-recorded materials and tutorials.
Students work on their understanding through a combination of independent study, preparation for timetabled activities, tutorials, and problem classes, along with formative assessments in the form of problem sheets.
Assessment
Assessment strategy
This module is assessed by a combination of problem sheets and a final assessment in the form of a written examination.