Summary 
This module introduces the theoretical foundations for
computing systems: finite state machines, pushdown
automata, and Turing machines, along with the formal
languages that can be recognised by these machine models.
It also deals with the question "What is computable?"
and "What is efficiently computable?" by showing when
problems are computationally hard, and how to find
algorithmic solutions to computationally hard problems.

Session 
Academic Year 2021/22 
Credits 
20 
Assessment 
Autumn
 Quizzes  threshold
 Grading exam
Spring
 Quizzes  threshold
 Grading exam

Lecturer(s) 
Dr Kirill Bogdanov, Prof. Rob Hierons & Dr Christian Coester 
Resources 

Aims 
This unit aims to:
 Introduce machine models (i.e. models of computation)
and the corresponding notions of formal languages;
 Introduce complexity theory and algorithmic solutions
to computationally hard problems;
 Enhance analytical and logical skills in reasoning
abstractly (about computation and complexity);
 Teach the foundations of theoretical computer
science, providing a thorough grounding for theoretical
courses at more advanced levels.

Objectives 
By the end of the unit, a candidate will be able to:
 Use different machine models and the formal languages
they are able to recognise as well as be able to reason about the computational limitations of different machines (aims 1 and 3);
 Show that a problem is computationally easy or hard
(aims 2 and 3);
 Provide algorithmic solutions for computationally hard
problems (aims 2 and 3);
 Explain the foundations of automata and language
theory, computability, and complexity (aims 14).

Content 
Automata Theory (Semester 1)
 finite automata and regular languages
 pushdown automata and context free languages
 Turing machines and decidability
Computation and Complexity (Semester 2)
Computational Complexity: P and NP
 Reductions and Rice's Theorem
 P vs. NP, NPcompleteness, Cook's theorem
 Techniques for proving NPhardness
Algorithm Design Techniques:
 Branchandbound
 Dynamic Programming
 Network flows
Approximation Algorithms:
 Examples for approximation algorithms
 Polynomialtime approximation schemes
 Hardness results for approximation
Randomization:
 Examples for randomized algorithms
 Probabilistic complexity classes

Teaching Method 
The theoretical background and techniques will be
presented in a series of formal lectures, 2 lectures per
week. Students will reinforce the material through
selfstudy, and through weekly problems classes where
students will apply analytical skills obtained in class.
Both lectures and problem classes are designed to achieve
objectives 14.

Feedback 
Feedback on tutorial exercises. 
Recommended Reading 
 Dexter C. Kozen. "Automata and Computability" Springer,
1997
 B. Barak and S. Arora “Computational Complexity: A Modern Approach”. Cambridge University Press, 2009
 J. Kleinberg and E. Tardos. "Algorithm Design". Addison Wesley, 2005.
