The University of Southampton
×
Electronics and Computer Science➞Undergraduate

COMP2210 Theory of Computing

Module Overview

This module aims to provide a broad and stimulating introduction to the theory of computing.

Aims & Objectives

Aims

Aim

Having successfully completed this module, you will be able to:

  • Ascertain and prove whether or not a given language is regular
  • Ascertain and prove whether or not a given language is context-free
  • Use the reduction technique to show that a problem is undecidable
  • Analyse the complexity of a given algorithm or problem
  • Use polynomial-time reduction to reason about the complexity class of a problem

Syllabus

  • Automata theory
    • Finite state automata, regular expressions and regular languages
    • The pumping lemma for regular languages
    • Closure properties of regular languages
    • The Myhill-Nerode theorem
    • 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 P, NP, PSPACE
    • Polynomial-time reduction
    • NP-Completeness and Cook's theorem
    • PSPACE-Completeness

Learning & Teaching

Learning & teaching methods

ActivityDescriptionHours
Lecture36
Tutorial12

Assessment

Assessment methods

MethodHoursPercentage contribution
In-class tests -70%
Exam1 hour30%

Referral Method: By examination

Share this module FacebookTwitterWeibo