Postgraduate Programme and Module Handbook 2025-2026
Module COMP53215: Algorithms and Complexity
Department: Computer Science
COMP53215: Algorithms and Complexity
Type | Tied | Level | 5 | Credits | 15 | Availability | Available in 2025/2026 | Module Cap |
---|
Tied to | G5T609 |
---|---|
Tied to | G5T709 |
Prerequisites
- None
Corequisites
- None
Excluded Combination of Modules
- None
Aims
- Provide knowledge and critical understanding of paradigms, and fundamental ideas behind algorithms.
- Provide knowledge and critical understanding of paradigms, fundamental ideas and methods relating to computational complexity.
- Discuss the design and analysis of efficient algorithms.
Content
- Algorithmic methods: e.g. divide and conquer, dynamic programming.
- Mitigating hardness: e.g. approximation, branch and bound, exact methods.
- Computational complexity: e.g. classes between L and EXPTIME, time and space hierarchy theorems, FPT and the W-hierarchy.
- Randomised Algorithms: e.g. QuickSort, randomised data structures.
- Probabilistic Methods: e.g. Monte Carlo methods, tail inequalities
Learning Outcomes
Subject-specific Knowledge:
- By the end of this module, students should be able to demonstrate:
- a systematic understanding of core techniques for constructing algorithms.
- an advanced understanding of core concepts from computational complexity theory.
- an ability to design novel algorithms to solve specific complex problems.
Subject-specific Skills:
- By the end of this module, students should be able to demonstrate:
- familiarity with state-of-the-art algorithms to solve complex challenges and understanding of computational complexity implications.
- competence to translate abstract problem descriptions into algorithmic formulations; competent and educated selection of appropriate solution algorithms.
Key Skills:
- By the end of this module, students should be able to demonstrate:
- familiarity with advanced paradigms and modern algorithms underlying computer science applications, and their analysis
Modes of Teaching, Learning and Assessment and how these contribute to the learning outcomes of the module
- Lectures enable students to learn the core material relevant to the topic and problem classes enable students to develop their theoretical understanding and problem-solving skills.
- Summative assessments and formative exercises encourage students to focus their ability to independently analyse and solve problems as it relates to the topic of algorithms and complexity.
Teaching Methods and Learning Hours
Activity | Number | Frequency | Duration | Total/Hours | |
---|---|---|---|---|---|
Lectures | 8 | 1 per week | 2 hours | 16 | ■ |
Lectures | 8 | 1 per week | 1 hour | 8 | ■ |
Problem Classes | 1 | 1 per week | 2 hours | 8 | ■ |
Preparation and Reading | 118 | ||||
Total | 150 |
Summative Assessment
Component: Coursework | Component Weighting: 100% | ||
---|---|---|---|
Element | Length / duration | Element Weighting | Resit Opportunity |
General Test | 30 minutes | 33% | |
Exercise | 67% |
Formative Assessment:
Via problem classes.
■ Attendance at all activities marked with this symbol will be monitored. Students who fail to attend these activities, or to complete the summative or formative assessment specified above, will be subject to the procedures defined in the University's General Regulation V, and may be required to leave the University