Academic Year:
 2013/4 
Owning Department/School:
 Department of Computer Science 
Credits:
 6 
Level:
 Intermediate (FHEQ level 5) 
Period: 
Semester 1

Assessment:
 CW 25%, 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 wellknown 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. BigO 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
 USCMAFB06 : BSc (hons) Computer Science (Fulltime)  Year 2
 USCMAKB07 : BSc (hons) Computer Science (Fulltime with Thick Sandwich Placement)  Year 2
 USCMAFB20 : BSc (hons) Computer Science and Mathematics (Fulltime)  Year 2
 USCMAKB20 : BSc (hons) Computer Science and Mathematics (Fulltime with Thick Sandwich Placement)  Year 2
 USCMAAB20 : BSc (hons) Computer Science and Mathematics with Study Year Abroad (Fulltime with Study Year Abroad)  Year 2
 USCMAKB16 : BSc (hons) Computer Science with German Language (with Industrial Placement) (Fulltime with Thick Sandwich Placement)  Year 4
 USCMAAB16 : BSc (hons) Computer Science with German Language (with Study Year Abroad) (Fulltime with Study Year Abroad)  Year 4
 USCMAKB17 : BSc (hons) Computer Science with Spanish Language (with Industrial Placement) (Fulltime with Thick Sandwich Placement)  Year 4
 USCMAAB17 : BSc (hons) Computer Science with Spanish Language (with Study Year Abroad) (Fulltime with Study Year Abroad)  Year 4
 USCMAAB07 : BSc (hons) Computer Science with Study Year Abroad (Fulltime with Study Year Abroad)  Year 2
 USCMAFM01 : MComp (hons) Computer Science (Fulltime)  Year 2
 USCMAKM02 : MComp (hons) Computer Science (Fulltime with Thick Sandwich Placement)  Year 2
 USCMAFM14 : MComp (hons) Computer Science and Mathematics (Fulltime)  Year 2
 USCMAKM14 : MComp (hons) Computer Science and Mathematics with Industrial Placement (Fulltime with Thick Sandwich Placement)  Year 2
 USCMAAM14 : MComp (hons) Computer Science and Mathematics with Study Year Abroad (Fulltime with Study Year Abroad)  Year 2
 USCMAAM02 : MComp (hons) Computer Science with Study Year Abroad (Fulltime with Study Year Abroad)  Year 2
CM20217 is Optional on the following programmes:
Department of Computer Science
 USCMAFB09 : BSc (hons) Computer Science with Business (Fulltime)  Year 3
 USCMAKB10 : BSc (hons) Computer Science with Business (Fulltime with Thick Sandwich Placement)  Year 4
 USCMAAB10 : BSc (hons) Computer Science with Business with Study Year Abroad (Fulltime with Study Year Abroad)  Year 4
Department of Mathematical Sciences
 USMAAFB15 : BSc (hons) Mathematical Sciences (Fulltime)  Year 2
 USMAAFB15 : BSc (hons) Mathematical Sciences (Fulltime)  Year 3
 USMAAKB16 : BSc (hons) Mathematical Sciences (Fulltime with Thick Sandwich Placement)  Year 2
 USMAAKB16 : BSc (hons) Mathematical Sciences (Fulltime with Thick Sandwich Placement)  Year 4
 USMAAAB16 : BSc (hons) Mathematical Sciences with Study Year Abroad (Fulltime with Study Year Abroad)  Year 2
 USMAAAB16 : BSc (hons) Mathematical Sciences with Study Year Abroad (Fulltime with Study Year Abroad)  Year 4
 USMAAFB13 : BSc (hons) Mathematics (Fulltime)  Year 2
 USMAAFB13 : BSc (hons) Mathematics (Fulltime)  Year 3
 USMAAKB14 : BSc (hons) Mathematics (Fulltime with Thick Sandwich Placement)  Year 2
 USMAAKB14 : BSc (hons) Mathematics (Fulltime with Thick Sandwich Placement)  Year 4
 USMAAFB01 : BSc (hons) Mathematics and Statistics (Fulltime)  Year 3
 USMAAKB02 : BSc (hons) Mathematics and Statistics (Fulltime with Thick Sandwich Placement)  Year 4
 USMAAAB02 : BSc (hons) Mathematics and Statistics with Study Year Abroad (Fulltime with Study Year Abroad)  Year 4
 USMAAAB14 : BSc (hons) Mathematics with Study Year Abroad (Fulltime with Study Year Abroad)  Year 2
 USMAAAB14 : BSc (hons) Mathematics with Study Year Abroad (Fulltime with Study Year Abroad)  Year 4
 USMAAFB05 : BSc (hons) Statistics (Fulltime)  Year 2
 USMAAFB05 : BSc (hons) Statistics (Fulltime)  Year 3
 USMAAKB06 : BSc (hons) Statistics (Fulltime with Thick Sandwich Placement)  Year 2
 USMAAKB06 : BSc (hons) Statistics (Fulltime with Thick Sandwich Placement)  Year 4
 USMAAAB06 : BSc (hons) Statistics with Study Year Abroad (Fulltime with Study Year Abroad)  Year 2
 USMAAAB06 : BSc (hons) Statistics with Study Year Abroad (Fulltime with Study Year Abroad)  Year 4
 USMAAFM14 : MMath Mathematics (Fulltime)  Year 2
 USMAAFM14 : MMath Mathematics (Fulltime)  Year 3
 USMAAAM15 : MMath Mathematics with Study Year Abroad (Fulltime with Study Year Abroad)  Year 2
