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: 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-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-AFM01 : MComp(Hons) Computer Science (Year 3)
- USCM-AAM02 : MComp(Hons) Computer Science with Study year abroad (Year 4)
- USCM-AKM02 : MComp(Hons) Computer Science with Year long work placement (Year 4)
- 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-AFM14 : MComp(Hons) Computer Science and Mathematics (Year 3)
- USCM-AAM14 : MComp(Hons) Computer Science and Mathematics with Study year abroad (Year 4)
- USCM-AKM14 : MComp(Hons) Computer Science and Mathematics with Year long work placement (Year 4)
- USCM-AFB09 : BSc(Hons) Computer Science with Business (Year 3)
- USCM-AAB10 : BSc(Hons) Computer Science with Business with Study year abroad (Year 4)
- USCM-AKB10 : BSc(Hons) Computer Science with Business with Year long work placement (Year 4)
- USCM-AAB14 : BSc(Hons) Computer Science with Mathematics with Study year abroad (Year 4)
- USCM-AKB14 : BSc(Hons) Computer Science with Mathematics with Year long work placement (Year 4)
- USCM-AFB01 : BSc Computing (Year 3)
- USCM-AKB01 : BSc Computing with Year long work placement (Year 4)
Department of Mathematical Sciences
- USMA-AFB15 : BSc(Hons) Mathematical Sciences (Year 3)
- USMA-AAB16 : BSc(Hons) Mathematical Sciences with Study year abroad (Year 4)
- USMA-AKB16 : BSc(Hons) Mathematical Sciences with Year long work placement (Year 4)
- USMA-AFB13 : BSc(Hons) Mathematics (Year 3)
- USMA-AAB14 : BSc(Hons) Mathematics with Study year abroad (Year 4)
- USMA-AKB14 : BSc(Hons) Mathematics with Year long work placement (Year 4)
- USMA-AFM14 : MMath(Hons) Mathematics (Year 3)
- USMA-AFM14 : MMath(Hons) Mathematics (Year 4)
- USMA-AAM15 : MMath(Hons) Mathematics with Study year abroad (Year 4)
- USMA-AKM15 : MMath(Hons) Mathematics with Year long work placement (Year 4)
- USMA-AKM15 : MMath(Hons) Mathematics with Year long work placement (Year 5)
- TSMA-AFM08 : MSc Modern Applications of Mathematics
- TSMA-AWM14 : MSc Modern Applications of Mathematics
- TSMA-AFL02 : PG Dip Modern Applications of Mathematics
- USMA-AFB05 : BSc(Hons) Statistics (Year 3)
- USMA-AAB06 : BSc(Hons) Statistics with Study year abroad (Year 4)
- USMA-AKB06 : BSc(Hons) Statistics with Year long work placement (Year 4)
|