- Student Records
Programme & Unit Catalogues

Department of Computer Science, Unit Catalogue 2011/12


CM20217: Foundations of computation 1

Click here for further information Credits: 6
Click here for further information Level: Intermediate (FHEQ level 5)
Click here for further information Period: Semester 1
Click here for further information Assessment: CW 25%, EX 75%
Click here for further information Supplementary Assessment: CM20217 Mandatory Extra Work (where allowed by programme regulations)
Click here for further information Requisites: Before taking this unit you must take CM10227 and take CM10228 and (take CM10196 or take MA10001)
Click here for further information 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.
Click here for further informationProgramme availability:

CM20217 is Compulsory on the following programmes:

Department of Computer Science
  • USCM-AFB06 : BSc (hons) Computer Science (Full-time) - Year 2
  • USCM-AKB07 : BSc (hons) Computer Science (Full-time with Thick Sandwich Placement) - Year 2
  • USCM-AKB15 : BSc (hons) Computer Science with French Language (with Industrial Placement) (Full-time with Thick Sandwich Placement) - Year 4
  • USCM-AAB15 : BSc (hons) Computer Science with French Language (with Study Year Abroad) (Full-time with Study Year Abroad) - Year 4
  • USCM-AKB16 : BSc (hons) Computer Science with German Language (with Industrial Placement) (Full-time with Thick Sandwich Placement) - Year 4
  • USCM-AAB16 : BSc (hons) Computer Science with German Language (with Study Year Abroad) (Full-time with Study Year Abroad) - Year 4
  • USCM-AFB13 : BSc (hons) Computer Science with Mathematics (Full-time) - Year 2
  • USCM-AKB14 : BSc (hons) Computer Science with Mathematics (Full-time with Thick Sandwich Placement) - Year 2
  • USCM-AAB14 : BSc (hons) Computer Science with Mathematics with Study Year Abroad (Full-time with Study Year Abroad) - Year 2
  • USCM-AKB17 : BSc (hons) Computer Science with Spanish Language (with Industrial Placement) (Full-time with Thick Sandwich Placement) - Year 4
  • USCM-AAB17 : BSc (hons) Computer Science with Spanish Language (with Study Year Abroad) (Full-time with Study Year Abroad) - Year 4
  • USCM-AAB07 : BSc (hons) Computer Science with Study Year Abroad (Full-time with Study Year Abroad) - Year 2
  • USCM-AFM01 : MComp (hons) Computer Science (Full-time) - Year 2
  • USCM-AKM02 : MComp (hons) Computer Science (Full-time with Thick Sandwich Placement) - Year 2
  • USCM-AAM02 : MComp (hons) Computer Science with Study Year Abroad (Full-time with Study Year Abroad) - Year 2

CM20217 is Optional on the following programmes:

Department of Computer Science
  • USCM-AFB09 : BSc (hons) Computer Science with Business (Full-time) - Year 3
  • USCM-AKB10 : BSc (hons) Computer Science with Business (Full-time with Thick Sandwich Placement) - Year 4
  • USCM-AAB10 : BSc (hons) Computer Science with Business with Study Year Abroad (Full-time with Study Year Abroad) - Year 4
Department of Mathematical Sciences
  • USMA-AFB15 : BSc (hons) Mathematical Sciences (Full-time) - Year 2
  • USMA-AFB15 : BSc (hons) Mathematical Sciences (Full-time) - Year 3
  • USMA-AKB16 : BSc (hons) Mathematical Sciences (Full-time with Thick Sandwich Placement) - Year 2
  • USMA-AKB16 : BSc (hons) Mathematical Sciences (Full-time with Thick Sandwich Placement) - Year 4
  • USMA-AAB16 : BSc (hons) Mathematical Sciences with Study Year Abroad (Full-time with Study Year Abroad) - Year 2
  • USMA-AAB16 : BSc (hons) Mathematical Sciences with Study Year Abroad (Full-time with Study Year Abroad) - Year 4
  • USMA-AFB13 : BSc (hons) Mathematics (Full-time) - Year 2
  • USMA-AFB13 : BSc (hons) Mathematics (Full-time) - Year 3
  • USMA-AKB14 : BSc (hons) Mathematics (Full-time with Thick Sandwich Placement) - Year 2
  • USMA-AKB14 : BSc (hons) Mathematics (Full-time with Thick Sandwich Placement) - Year 4
  • USMA-AFB01 : BSc (hons) Mathematics and Statistics (Full-time) - Year 3
  • USMA-AKB02 : BSc (hons) Mathematics and Statistics (Full-time with Thick Sandwich Placement) - Year 4
  • USMA-AAB02 : BSc (hons) Mathematics and Statistics with Study Year Abroad (Full-time with Study Year Abroad) - Year 4
  • USMA-AAB14 : BSc (hons) Mathematics with Study Year Abroad (Full-time with Study Year Abroad) - Year 2
  • USMA-AAB14 : BSc (hons) Mathematics with Study Year Abroad (Full-time with Study Year Abroad) - Year 4
  • USMA-AFB05 : BSc (hons) Statistics (Full-time) - Year 2
  • USMA-AFB05 : BSc (hons) Statistics (Full-time) - Year 3
  • USMA-AKB06 : BSc (hons) Statistics (Full-time with Thick Sandwich Placement) - Year 2
  • USMA-AKB06 : BSc (hons) Statistics (Full-time with Thick Sandwich Placement) - Year 4
  • USMA-AAB06 : BSc (hons) Statistics with Study Year Abroad (Full-time with Study Year Abroad) - Year 2
  • USMA-AAB06 : BSc (hons) Statistics with Study Year Abroad (Full-time with Study Year Abroad) - Year 4
  • USMA-AFM14 : MMath Mathematics (Full-time) - Year 2
  • USMA-AFM14 : MMath Mathematics (Full-time) - Year 3
  • USMA-AAM15 : MMath Mathematics with Study Year Abroad (Full-time with Study Year Abroad) - Year 2

NB. Programmes and units are subject to change at any time, in accordance with normal University procedures.