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’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|
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