Department of Computer Science, Unit Catalogue 2009/10 |
CM30073: Advanced algorithms & complexity |
 Credits:
| 6 |
| Level:
| Honours |
| Period: | Semester 2 |
| Assessment:
| EX 100% |
| 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. |