(Last Updated:03 May 2017)

**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.

**Taught Semesters:**

Semester | Assessment |
---|---|

Spring | Assessed by end of Spring Semester |

**Prerequisites: **

Mnem | Title |
---|---|

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:**

**Method and Frequency of Class: **

Activity | Number Of Weeks | Number of sessions | Duration of a session |
---|---|---|---|

Lecture | 10 weeks | 2 per week | 1 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 Type | Weight | Requirements |
---|---|---|

Exam 1 | 100 | 2 hr written examination |

**Convenor: **

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.

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.

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

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.

Return to The University of Nottingham Welcome Page