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 2023/24
Credits 20
Assessment

Autumn

  • Formal exam

Spring

  • Formal exam
Lecturer(s) Dr Maksim Zhukovskii, Prof. Rob Hierons, Mr Tahsinur Khan, Dr Andreas Feldman, Dr Charles Grellois & Dr Georgios Moulantzikos
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.
Learning Outcomes 

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;      
  2. Show that a problem is computationally easy or hard;                     
  3. Identify algorithmic solutions for computationally hard problems.
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.