CM30073: Advanced algorithms & complexity
[Page last updated: 27 October 2020]
Academic Year:  2020/1 
Owning Department/School:  Department of Computer Science 
Credits:  6 [equivalent to 12 CATS credits] 
Notional Study Hours:  120 
Level:  Honours (FHEQ level 6) 
Period: 

Assessment Summary:  EX 100% 
Assessment Detail: 

Supplementary Assessment: 

Requisites:  Before taking this module you must ( take CM10227 OR take XX10190 ) AND ( take 2 MODULES FROM {CM10196, CM20217} OR take MA10209 ) 
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

Notes:
