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
Preparation for scheduled sessions18
Revision10
Total study time150

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