Text only

 University | Catalogues for 2006/07

University of Bath logo - link to University home page

Department of Computer Science, Unit Catalogue 2006/07

CM30073 Advanced algorithms & complexity

Credits: 6
Level: Honours
Semester: 2
Assessment: EX100
Before taking this unit you must take CM20028
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.
NP-completeness: Deterministic and Non-deterministic Turing Machines; class NP; versions of reducibility; NP-hard and NP-complete 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 other NP-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.


University | Catalogues for 2006/07