Department of Computer Science

## COM2109 Automata, Computation and Complexity

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. Academic Year 2021/22 20 Autumn Quizzes - threshold Grading exam Spring Quizzes - threshold Grading exam Dr Kirill Bogdanov, Prof. Rob Hierons & Dr Christian Coester 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. 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 1-4). 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, NP-completeness, Cook's theorem Techniques for proving NP-hardness Algorithm Design Techniques: Branch-and-bound Dynamic Programming Network flows Approximation Algorithms: Examples for approximation algorithms Polynomial-time approximation schemes Hardness results for approximation Randomization: Examples for randomized algorithms Probabilistic complexity classes The theoretical background and techniques will be presented in a series of formal lectures, 2 lectures per week. Students will reinforce the material through self-study, and through weekly problems classes where students will apply analytical skills obtained in class. Both lectures and problem classes are designed to achieve objectives 1-4. Feedback on tutorial exercises. 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.