Catalogue of Modules, University of Nottingham

G53COM Computability
(Last Updated:03 May 2017)

Year  16/17

Total Credits: 10

Level: Level 3

Target Students:  Part II undergraduate students in the School of Computer Science. Also available to students from other Schools with the agreement of the module convenor.

This module is part of the Foundations of Computer Science theme in the School of Computer Science.  Available to JYA/Erasmus students.

Taught Semesters:

Spring Assessed by end of Spring Semester 


G52ACE Algorithms Correctness and Efficiency 

Corequisites:  None.

Summary of Content:  You’ll begin by considering the attempts to characterise the problems that can theoretically be solved by physically-possible computational processes. You’ll then consider the area of complexity theory, looking at whether or not problems can be solved under limitations on resources such as time or space. A key topic is an examination of the classes P and NP and the definition of the term NP-complete. You’ll spend around two hours a week in lectures for this module. Module Web Links:
  • Reading List
  • Method and Frequency of Class:

    ActivityNumber Of WeeksNumber of sessionsDuration of a session
    Lecture 10 weeks2 per week1 hour

    Activities may take place every teaching week of the Semester or only in specified weeks. It is usually specified above if an activity only takes place in some weeks of a Semester

    Method of Assessment: 

    Assessment TypeWeightRequirements
    Exam 1 100 2 hr written examination 

    Dr A Parkes

    Education Aims:  
    The overall aim of the course is to provide an understanding of the concepts of computability and computational complexity. In particular, course objectives are: To provide an appreciation of the many attempts that have been made to define the class of computable functions and also to indicate that all the sensible attempts to do this have been shown to be equivalent. To introduce the fact that there are problems that cannot possibly be solved on a computer. To show how, apparently different, computable problems are related in respect of their algorithmic complexity.

    Learning Outcomes:  Knowledge and Understanding
    To understand the theory of computation via mathematical methods.

    Intellectual Skills
    To apply and deploy mathematical ability, practices and tools;
    To understand and logically evaluate the problems in computability and complexity;
    To think independently about the issues while giving due weight to previous work;
    To understand the ideas of the theory of computability and complexity and relate them to particular problems.

    Professional Skills
    To extend their own abilities by specialising or generalising from their previous knowledge.

    Transferable Skills
    The ability to solve problems using mathematics, by consulting external sources if necessary.

    Offering School:  Computer Science

    Use the Back facility of your browser to return to the previous page.

    Module Catalogue Search for another module

    [UoN Welcome Page] Return to The University of Nottingham Welcome Page