Module manager: Dr Haiko Muller
Email: h.muller@leeds.ac.uk
Taught: Semester 1 (Sep to Jan) View Timetable
Year running 2026/27
COMP3940
This module is not approved as a discovery module
There are practically important computational problems that can be solved in principle, but there are no efficient algorithms known. This intractability is formalised in the theory of NP-completeness. To cope with such problems in practice, we must compromise. This module considers three approaches: fixed parameter algorithms, approximation algorithms and randomised algorithms.
The objective of this module is to develop students’ advanced understanding of computational intractability and to equip them with practical strategies for addressing complex problems for which no known efficient algorithms exist. The module aims to bridge theoretical foundations and practical problem-solving by examining NP-completeness as a formal framework for understanding computational hardness, and by exploring three complementary approaches—fixed parameter algorithms, approximation algorithms, and randomised algorithms—as pragmatic responses to intractable problems.
On successful completion of the module students will be able to:
apply knowledge of mathematics, statistics, natural science and engineering principles to the solution of complex problems. Some of the knowledge will be at the forefront of the subject of study. (C1, M1)
select and apply appropriate computational and analytical techniques to model complex problems, discussing the limitations of the techniques employed. (C3, M3)
select and evaluate technical literature and other sources of information to address complex problems. (C4, M4)
select and use practical laboratory and workshop skills to investigate complex problems and be able to comment on their limitations. (C12, M12, C13, M13)
communicate effectively on complex engineering matters with technical and non-technical audiences, evaluating the effectiveness of the methods used. (C17, M17)
reflect on their level of mastery of subject knowledge and skills and plan for personal development. (C18, M18)
On successful completion of the module students will be able to:
Critically analyse and evaluate the correctness, efficiency, and computational complexity of algorithms using formal methods and mathematical reasoning.
Design, implement, and optimise efficient algorithmic solutions using appropriate data structures and design paradigms.
Evaluate algorithmic design choices with respect to scalability, maintainability, and resource usage, including time and space.
Apply advanced algorithmic problem-solving skills to complex, real-world and industry-informed scenarios, exercising professional judgement, autonomy, and decision-making.
Communicate and justify algorithmic solutions, complexity trade-offs, and technical decisions effectively to specialist and non-specialist audiences.
NP-completeness:
Decision, optimisation and construction problems. The classes P and NP.
Polynomial time many-one reductions, NP-completeness.
Cook/Levin theorem, NP-completeness of SAT.
Further NP-complete problems via reductions.
Parameterized algorithms:
Bounded search tree for Vertex Cover, bounded degree Independent Set and Dominating Set.
Kernelization: Vertex Cover, Bounded degree Independent Set and Dominating Set, Satisfiability, Hitting Set, point line cover
Structural parameters: Vertex Cover for Independent Set/Hamiltonian Path/Colouring, Satisfiability deletion to unit clauses, deletion to square free
W[1] hardness, Fixed Parameter Tractability reductions
Approximation algorithms:
Vertex Cover via matchings, Vertex Cover using Linear Program rounding, centre selection.
Approximation schemes: Polynomial-time approximation scheme for Knapsack
Inapproximability: gap-preserving reductions
Randomised algorithms:
Motivation and models of randomisation, including Las Vegas and Monte Carlo algorithms and the role of randomness in improving efficiency or simplicity.
Probabilistic tools and analysis techniques for randomised algorithms, such as expectation and average-case performance analysis.
Applications and theory of randomised algorithms, covering classic examples, randomised data structure
| Delivery type | Number | Length hours | Student hours |
|---|---|---|---|
| Lecture | 22 | 2 | 44 |
| Seminar | 11 | 1 | 11 |
| Private study hours | 145 | ||
| Total Contact hours | 55 | ||
| Total hours (100hr per 10 credits) | 200 | ||
Check the module area in Minerva for your reading list
Last updated: 30/04/2026
Errors, omissions, failed links etc should be notified to the Catalogue Team