Student Records
Programme & Unit Catalogues

## CM30073: Advanced algorithms & complexity

Owning Department/School: Department of Computer Science
Credits: 6
Level: Honours (FHEQ level 6)
Period: Semester 2
Assessment: EX 100%
Supplementary Assessment: CM30073 Mandatory Extra Work (where allowed by programme regulations)
Requisites: Before taking this unit you must take CM20028 or (take CM10196 and take CM10197 and take CM20217)
Description: Aims:
To present a detailed introduction to one of the central concepts of combinatorial algorithmics: NP-completeness; to extend this concept to real numbers computations; to study foundations of a more general problem of proving lower complexity bounds.

Learning Outcomes:
1. To be able to recognise NP-hard problems and prove the appropriate reductions.
2. To cope with NP-complete problems.
3. To know some fundamental methods of proving lower complexity bounds.

Skills:
Applications of Number (IT).

Content:
NP-completeness: Deterministic and Non-deterministic Turing Machines; class NP; versions of reducibility; NP-hard and NPcomplete problems. Proof of NP-completeness of satisfiability problem for Boolean formulae.
Other NP-complete problems: clique, vertex cover, travelling salesman, subgraph isomorphism, etc. Polynomial-time approximation algorithms for travelling salesman and some otherNP-complete graph problems.
Real Number Turing machines: Definitions; completeness of real roots existence problem for 4-degree polynomials.
Lower complexity bounds: Algebraic computation trees and their complexities; complexity of distinctness problem and of knapsack.
Programme availability:

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

Department of Computer Science
• USCM-AFB01 : BSc Computing (Full-time) - Year 3
• USCM-AKB01 : BSc Computing (Full-time with Thick Sandwich Placement) - Year 4
• USCM-AFB06 : BSc (hons) Computer Science (Full-time) - Year 3
• USCM-AKB07 : BSc (hons) Computer Science (Full-time with Thick Sandwich Placement) - Year 4
• USCM-AFB20 : BSc (hons) Computer Science and Mathematics (Full-time) - Year 3
• USCM-AKB20 : BSc (hons) Computer Science and Mathematics (Full-time with Thick Sandwich Placement) - Year 4
• USCM-AAB20 : BSc (hons) Computer Science and Mathematics with Study Year Abroad (Full-time with Study Year Abroad) - Year 4
• 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
• 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 3
• USCM-AKB14 : BSc (hons) Computer Science with Mathematics (Full-time with Thick Sandwich Placement) - Year 4
• USCM-AAB14 : BSc (hons) Computer Science with Mathematics with Study Year Abroad (Full-time with Study Year Abroad) - Year 4
• 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 4
• USCM-AFM01 : MComp (hons) Computer Science (Full-time) - Year 3
• USCM-AKM02 : MComp (hons) Computer Science (Full-time with Thick Sandwich Placement) - Year 4
• USCM-AFM14 : MComp (hons) Computer Science and Mathematics (Full-time) - Year 3
• USCM-AKM14 : MComp (hons) Computer Science and Mathematics with Industrial Placement (Full-time with Thick Sandwich Placement) - Year 4
• USCM-AAM14 : MComp (hons) Computer Science and Mathematics with Study Year Abroad (Full-time with Study Year Abroad) - Year 4
• USCM-AAM02 : MComp (hons) Computer Science 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 3
• 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 4
• USMA-AFB13 : BSc (hons) Mathematics (Full-time) - Year 3
• USMA-AKB14 : BSc (hons) Mathematics (Full-time with Thick Sandwich Placement) - Year 4
• 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 3
• 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 4
• USMA-AFM14 : MMath Mathematics (Full-time) - Year 3
• USMA-AFM14 : MMath Mathematics (Full-time) - Year 4
• USMA-AAM15 : MMath Mathematics with Study Year Abroad (Full-time with Study Year Abroad) - Year 4
• TSMA-AFM08 : MSc Modern Applications of Mathematics (Full-time)
• TSMA-AWM14 : MSc Modern Applications of Mathematics (Full-time incorporating placement)
• TSMA-AFL02 : PG Dip Modern Applications of Mathematics (Full-time)

Notes:
* This unit catalogue is applicable for the 2013/4 academic year only. Students continuing their studies into 2014/15 and beyond should not assume that this unit will be available in future years in the format displayed here for 2013/14.
* 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.