The University of Southampton
Courses

COMP2210 Theory of Computing

Module Overview

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

Aims and Objectives

Module Aims

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

Learning Outcomes

Knowledge and Understanding

Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:

  • The relationship between the regular, context-free and recursively enumerable classes of languages, and the state-machines that accept them
  • The nature and examples of undecidable problems
  • The diagonalisation proof technique
  • The time and space complexity of algorithms and problems
  • The complexity classes P and NP together with examples of NP-complete problems
  • The complexity class PSPACE together with examples of PSPACE-complete problems
Subject Specific Intellectual and Research Skills

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 and Teaching

TypeHours
Tutorial12
Follow-up work18
Lecture36
Completion of assessment task15
Preparation for scheduled sessions18
Revision10
Wider reading or practice41
Total study time150

Resources & Reading list

Dexter C. Kozen (1999). Automata and Computabilty. 

Dewdney AK (2001). The (new) Turing Omnibus. 

Barwise J and Etchemendy J (1993). Turing's World. 

Cohen D (1996). Introduction to Computer Theory. 

Hein J (2002). Discrete Structures, Logic, and Computability. 

Jones ND (1997). Computability and Complexity. 

Gruska J (1996). Foundations of Computing. 

Sipser M, (1997). Introduction to the Theory of Computation. 

Harel D (1992). Algorithmics: The Spirit of Computing. 

Hey AJG (1996). Feynman Lectures on Computation. 

Assessment

Summative

MethodPercentage contribution
Exam  (2 hours) 70%
Test 30%

Referral

MethodPercentage contribution
Exam 100%

Repeat Information

Repeat type: Internal & External

Linked modules

Pre-requisites

To study this module, you will need to have studied the following module(s):

CodeModule
COMP1215Foundations of Computer Science
COMP1201Algorithmics
Share this module Facebook Google+ Twitter Weibo

We use cookies to ensure that we give you the best experience on our website. If you continue without changing your settings, we will assume that you are happy to receive cookies on the University of Southampton website.

×