COMP52915: Advanced Algorithms: Coping with Intractability

• None

• None

• None

• To give students a deeper knowledge of algorithmic solutions for typical computer science problems.
• To extend the students knowledge of the latest advances in understanding the limits of computation and the ways of coping with computational hardness.
• To give the students some experience with applying the theoretical knowledge obtained under the first two aims in a more practical setting.

• Computability (existence of computational tasks without algorithms for their computation
• Computational hardness (in particular, NP-completeness)
• Theoretical methods of comping with computation hardness:
• 1) Tractable classes of intractable problems.
• 2) Approximation algorithms
• 3) Parameterized algorithms
• 4) Exact exponential algorithms.
• Applied methods of coping with NP-hardness:
• 1) SAT solving
• 2) Local search

Subject-specific Knowledge:

• By the end of this module, students should be able to demonstrate:
• a comprehensive and also practical understanding of how the theory of computation is applied in the design of algorithms.
• a critical evaluation of different approaches to the algorithmic solution for computationally hard problems.
• a critical awareness of some of the latest advances in research on various aspects of computation.

Subject-specific Skills:

• By the end of this module, students should be able to demonstrate:
• an ability to critically apply notions from the theory of computation.
• an ability to choose and evaluate the best way to tackle computationally hard problems.
• an ability to judge research on the cutting edge of the theory of computation.

Key Skills:

• By the end of this module, students should be able to demonstrate:
• an ability to abstract and solve problems both in a theoretical and practical way.
• an ability to learn independently.
• an ability to communicate technical information.

• Lectures enable the students to learn new material relevant to the theory of computation.
• Formative homework exercises and practical classes identify areas where further independent research could be conducted and learnt knowledge can be applied to specific algorithmic challenges.
• The summative assessment tests the knowledge acquired and the students' ability to use this knowledge to solve complex problems.

If you have a question about Durham's modular degree programmes, please visit our Help page. If you have a question about modular programmes that is not covered by the Help page, or a query about the on-line Postgraduate Module Handbook, please contact us.

Prospective Students: If you have a query about a specific module or degree programme, please Ask Us.

Current Students: Please contact your department.