- Academic Registry
Programme & Unit Catalogues


CM30073: Advanced algorithms & complexity

[Page last updated: 02 August 2022]

Academic Year: 2022/23
Owning Department/School: Department of Computer Science
Credits: 6 [equivalent to 12 CATS credits]
Notional Study Hours: 120
Level: Honours (FHEQ level 6)
Period:
Semester 2
Assessment Summary: EX 100%
Assessment Detail:
  • Examination (EX 100%)
Supplementary Assessment:
Like-for-like reassessment (where allowed by programme regulations)
Requisites: Before taking this module you must take CM10227 AND take CM20217
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.

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.

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-AFB06 : BSc(Hons) Computer Science (Year 3)
  • USCM-AAB07 : BSc(Hons) Computer Science with Study year abroad (Year 4)
  • USCM-AKB07 : BSc(Hons) Computer Science with Year long work placement (Year 4)
  • USCM-AFB27 : BSc(Hons) Computer Science and Artificial Intelligence (Year 3)
  • USCM-AFB20 : BSc(Hons) Computer Science and Mathematics (Year 3)
  • USCM-AAB20 : BSc(Hons) Computer Science and Mathematics with Study year abroad (Year 4)
  • USCM-AKB20 : BSc(Hons) Computer Science and Mathematics with Year long work placement (Year 4)
  • USCM-AFM01 : MComp(Hons) Computer Science (Year 3)
  • USCM-AAM02 : MComp(Hons) Computer Science with Study year abroad (Year 3)
  • USCM-AKM02 : MComp(Hons) Computer Science with Year long work placement (Year 3)
  • USCM-AFM27 : MComp(Hons) Computer Science and Artificial Intelligence (Year 3)
  • USCM-AAM27 : MComp(Hons) Computer Science and Artificial Intelligence with Study year abroad (Year 3)
  • USCM-AKM27 : MComp(Hons) Computer Science and Artificial Intelligence with Year long work placement (Year 3)
  • USCM-AFM14 : MComp(Hons) Computer Science and Mathematics (Year 3)
  • USCM-AAM14 : MComp(Hons) Computer Science and Mathematics with Study year abroad (Year 3)
  • USCM-AKM14 : MComp(Hons) Computer Science and Mathematics with Year long work placement (Year 3)

Notes:

  • This unit catalogue is applicable for the 2022/23 academic year only. Students continuing their studies into 2023/24 and beyond should not assume that this unit will be available in future years in the format displayed here for 2022/23.
  • Programmes and units are subject to change 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.
  • Find out more about these and other important University terms and conditions here.