Academic Year: 
2014/5 
Owning Department/School: 
Department of Computer Science 
Credits: 
6 
Level: 
Honours (FHEQ level 6) 
Period: 
Semester 2

Assessment Summary: 
EX 100% 
Assessment Detail:  
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: NPcompleteness; 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 NPhard problems and prove the appropriate reductions.
2. To cope with NPcomplete problems.
3. To know some fundamental methods of proving lower complexity bounds.
Skills: Applications of Number (IT).
Content: NPcompleteness: Deterministic and Nondeterministic Turing Machines; class NP; versions of reducibility; NPhard and NPcomplete problems. Proof of NPcompleteness of satisfiability problem for Boolean formulae.
Other NPcomplete problems: clique, vertex cover, travelling salesman, subgraph isomorphism, etc. Polynomialtime approximation algorithms for travelling salesman and some otherNPcomplete graph problems.
Real Number Turing machines: Definitions; completeness of real roots existence problem for 4degree 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
 USCMAFB06 : BSc(Hons) Computer Science (Year 3)
 USCMAAB07 : BSc(Hons) Computer Science with Study year abroad (Year 4)
 USCMAKB07 : BSc(Hons) Computer Science with Year long work placement (Year 4)
 USCMAFM01 : MComp(Hons) Computer Science (Year 3)
 USCMAAM02 : MComp(Hons) Computer Science with Study year abroad (Year 4)
 USCMAKM02 : MComp(Hons) Computer Science with Year long work placement (Year 4)
 USCMAFB20 : BSc(Hons) Computer Science and Mathematics (Year 3)
 USCMAAB20 : BSc(Hons) Computer Science and Mathematics with Study year abroad (Year 4)
 USCMAKB20 : BSc(Hons) Computer Science and Mathematics with Year long work placement (Year 4)
 USCMAFM14 : MComp(Hons) Computer Science and Mathematics (Year 3)
 USCMAAM14 : MComp(Hons) Computer Science and Mathematics with Study year abroad (Year 4)
 USCMAKM14 : MComp(Hons) Computer Science and Mathematics with Year long work placement (Year 4)
 USCMAFB09 : BSc(Hons) Computer Science with Business (Year 3)
 USCMAAB10 : BSc(Hons) Computer Science with Business with Study year abroad (Year 4)
 USCMAKB10 : BSc(Hons) Computer Science with Business with Year long work placement (Year 4)
 USCMAAB14 : BSc(Hons) Computer Science with Mathematics with Study year abroad (Year 4)
 USCMAKB14 : BSc(Hons) Computer Science with Mathematics with Year long work placement (Year 4)
 USCMAFB01 : BSc Computing (Year 3)
 USCMAKB01 : BSc Computing with Year long work placement (Year 4)
Department of Mathematical Sciences
 USMAAFB15 : BSc(Hons) Mathematical Sciences (Year 3)
 USMAAAB16 : BSc(Hons) Mathematical Sciences with Study year abroad (Year 4)
 USMAAKB16 : BSc(Hons) Mathematical Sciences with Year long work placement (Year 4)
 USMAAFB13 : BSc(Hons) Mathematics (Year 3)
 USMAAAB14 : BSc(Hons) Mathematics with Study year abroad (Year 4)
 USMAAKB14 : BSc(Hons) Mathematics with Year long work placement (Year 4)
 USMAAFM14 : MMath(Hons) Mathematics (Year 3)
 USMAAFM14 : MMath(Hons) Mathematics (Year 4)
 USMAAAM15 : MMath(Hons) Mathematics with Study year abroad (Year 4)
 USMAAKM15 : MMath(Hons) Mathematics with Year long work placement (Year 4)
 USMAAKM15 : MMath(Hons) Mathematics with Year long work placement (Year 5)
 TSMAAFM08 : MSc Modern Applications of Mathematics
 TSMAAWM14 : MSc Modern Applications of Mathematics
 TSMAAFL02 : PG Dip Modern Applications of Mathematics
 USMAAFB05 : BSc(Hons) Statistics (Year 3)
 USMAAAB06 : BSc(Hons) Statistics with Study year abroad (Year 4)
 USMAAKB06 : BSc(Hons) Statistics with Year long work placement (Year 4)
