The University of Sheffield
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.

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:

  1. Introduce machine models (i.e. models of computation) and the corresponding notions of formal languages;
  2. Introduce complexity theory and algorithmic solutions to computationally hard problems;
  3. Enhance analytical and logical skills in reasoning abstractly (about computation and complexity);
  4. 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:

  1. 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);
  2. Show that a problem is computationally easy or hard (aims 2 and 3);
  3. Provide algorithmic solutions for computationally hard problems (aims 2 and 3);
  4. Explain the foundations of automata and language theory, computability, and complexity (aims 1-4).
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, 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
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 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 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.