Module Catalogues

Complexity of Algorithms

Module Title Complexity of Algorithms
Module Level Level 2
Module Credits 5.00
Academic Year 2021/22
Semester SEM2

Aims and Fit of Module

To demonstrate how the study of algorithmics has been applied in a number of different domains.
To introduce formal concepts of measures of complexity and algorithms analysis.
To introduce fundamental methods in data structures and algorithms design.
To make students aware of computationally hard problems and possible ways of coping with them.

Learning outcomes

On successful completion of the module, students are expected have an appreciation of the diversity of computational fields to which algorithmics has made significant contributions; have fluency in using basic data structures (queues, stacks, trees, graphs, etc) in conjunction with classical algorithmic problems (searching, sorting, graph algorithms, security issues) and be aware of basic number theory applications, etc.; be familiar with formal theories providing evidence that many important computational problems are inherently intractable, e.g., NP-completeness; be able to apply the knowledge gained in this module to the specification and analysis of data structures and algorithms.

Method of teaching and learning

Students will be expected to attend three hours of formal lectures as well as to participate in one hour of supervised problem classes in a typical week. Lectures will introduce students to the academic content and practical skills which are the subject of the module, while problem classes will allow students to practice those skills.
In addition, students will be expected to devote three hours of unsupervised time to solving continuous assessment tasks and private study. Private study will provide time for reflection and consideration of lecture material and background reading.
Continuous assessment will be used to test to what extent practical skills have been learnt. A written examination at the end of the module will assess the academic achievement of students.