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: 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
|
Notes:
|