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.
|Spring||Assessed by end of Spring Semester|
|G52ACE||Algorithms Correctness and Efficiency|
Summary of Content: You will begin by considering the attempts to characterise the problems that can theoretically be solved by physically possible computational processes, along with the practical implications. You will 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. You will examine the classes P and NP, and how to show problems are NP-complete. You will also consider other practically important classes such as: PSPACE, and its relevance to adversarial games, ontologies, and the semantic web; and also complexity classes relevant to limitations of the effectiveness of parallel computation.
Module Web Links:
Method and Frequency of Class:
|Activity||Number Of Weeks||Number of sessions||Duration of a session|
|Lecture||11 weeks||2 per week||1 hour|
Method of Assessment:
|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.
Search for another module
Return to The University of Nottingham Welcome Page