Student Records
Programme & Unit Catalogues

## CM20217: Foundations of computation 1

Owning Department/School: Department of Computer Science
Credits: 6
Level: Intermediate (FHEQ level 5)
Period: Semester 1
Assessment Summary: CW 25%, EX 75%
Assessment Detail:
• Coursework (CW 25%)
• Exam (EX 75%)
Supplementary Assessment: CM20217 Mandatory Extra Work (where allowed by programme regulations)
Requisites: Before taking this unit you must (take CM10227 and take CM10228 and take CM10196) or (take MA10209 and take XX10190)
Description: Aims:
To introduce formal models of computation. To give students an appreciation of the complexity of different algorithms and problems and the limits of computation. To provide students with a basic understanding of formal computational models such as finite state automata and Turing machines.

Learning Outcomes:
On completion of this unit, students will be able to:
1. demonstrate an understanding of the fundamental models of computation.
2. explain the notion of complexity class, and establish what classes a range of well-known problems belong to.
3. demonstrate that some computational problems are undecidable.

Skills:
Use of IT (A), Application of Number (T/F, A), Problem Solving (T/F, A).

Content:

* Models of computation: for example, basic notions of finite state automata, Turing Machines, register machines.
* Decidability. The undecidability of the Halting Problem. Reduction of other problems to the halting problem.
* Complexity. Big-O notation and complexity of algorithms. The notion of complexity class as a measure of the difficulty of a problem. Reduction between problems. Hardness and completeness of a problem with respect to a complexity class. The hierarchy of complexity classes. The question of whether P=NP and its importance for computer science.
Programme availability:

#### CM20217 is Compulsory on the following programmes:

Department of Computer Science
• USCM-AFB06 : BSc(Hons) Computer Science (Year 2)
• USCM-AAB07 : BSc(Hons) Computer Science with Study year abroad (Year 2)
• USCM-AKB07 : BSc(Hons) Computer Science with Year long work placement (Year 2)
• USCM-AFM01 : MComp(Hons) Computer Science (Year 2)
• USCM-AAM02 : MComp(Hons) Computer Science with Study year abroad (Year 2)
• USCM-AKM02 : MComp(Hons) Computer Science with Year long work placement (Year 2)
• USCM-AFB20 : BSc(Hons) Computer Science and Mathematics (Year 2)
• USCM-AAB20 : BSc(Hons) Computer Science and Mathematics with Study year abroad (Year 2)
• USCM-AKB20 : BSc(Hons) Computer Science and Mathematics with Year long work placement (Year 2)
• USCM-AFM14 : MComp(Hons) Computer Science and Mathematics (Year 2)
• USCM-AAM14 : MComp(Hons) Computer Science and Mathematics with Study year abroad (Year 2)
• USCM-AKM14 : MComp(Hons) Computer Science and Mathematics with Year long work placement (Year 2)

#### CM20217 is Optional on the following programmes:

Department of Computer Science
• USCM-AFB09 : BSc(Hons) Computer Science with Business (Year 3)
• USCM-AAB10 : BSc(Hons) Computer Science with Business with Study year abroad (Year 4)
• USCM-AKB10 : BSc(Hons) Computer Science with Business with Year long work placement (Year 4)
Department of Mathematical Sciences
• USMA-AFB15 : BSc(Hons) Mathematical Sciences (Year 2)
• USMA-AFB15 : BSc(Hons) Mathematical Sciences (Year 3)
• USMA-AAB16 : BSc(Hons) Mathematical Sciences with Study year abroad (Year 2)
• USMA-AAB16 : BSc(Hons) Mathematical Sciences with Study year abroad (Year 4)
• USMA-AKB16 : BSc(Hons) Mathematical Sciences with Year long work placement (Year 2)
• USMA-AKB16 : BSc(Hons) Mathematical Sciences with Year long work placement (Year 4)
• USMA-AFB13 : BSc(Hons) Mathematics (Year 2)
• USMA-AFB13 : BSc(Hons) Mathematics (Year 3)
• USMA-AAB14 : BSc(Hons) Mathematics with Study year abroad (Year 2)
• USMA-AAB14 : BSc(Hons) Mathematics with Study year abroad (Year 4)
• USMA-AKB14 : BSc(Hons) Mathematics with Year long work placement (Year 2)
• USMA-AKB14 : BSc(Hons) Mathematics with Year long work placement (Year 4)
• USMA-AFM14 : MMath(Hons) Mathematics (Year 2)
• USMA-AFM14 : MMath(Hons) Mathematics (Year 3)
• USMA-AAM15 : MMath(Hons) Mathematics with Study year abroad (Year 2)
• USMA-AKM15 : MMath(Hons) Mathematics with Year long work placement (Year 2)
• USMA-AKM15 : MMath(Hons) Mathematics with Year long work placement (Year 4)
• USMA-AFB01 : BSc(Hons) Mathematics and Statistics (Year 3)
• USMA-AAB02 : BSc(Hons) Mathematics and Statistics with Study year abroad (Year 4)
• USMA-AKB02 : BSc(Hons) Mathematics and Statistics with Year long work placement (Year 4)
• USMA-AFB05 : BSc(Hons) Statistics (Year 2)
• USMA-AFB05 : BSc(Hons) Statistics (Year 3)
• USMA-AAB06 : BSc(Hons) Statistics with Study year abroad (Year 2)
• USMA-AAB06 : BSc(Hons) Statistics with Study year abroad (Year 4)
• USMA-AKB06 : BSc(Hons) Statistics with Year long work placement (Year 2)
• USMA-AKB06 : BSc(Hons) Statistics with Year long work placement (Year 4)

Notes:
* This unit catalogue is applicable for the 2014/15 academic year only. Students continuing their studies into 2015/16 and beyond should not assume that this unit will be available in future years in the format displayed here for 2014/15.
* Programmes and units are subject to change at any time, in accordance with normal University procedures.
* Availability of units will be subject to constraints such as staff availability, minimum and maximum group sizes, and timetabling factors as well as a student's ability to meet any pre-requisite rules.