Data Structures and Algorithms 2


This module builds on Data Structures and Algorithms 1 by introducing students to some of the practical performance concerns in the selection and implementation of parallel algorithms, using a range of case studies drawn from typical real-world applications.


The aim of this Module is to provide the student with : To develop computational and algorithmic thinking and show how data structures and algorithms are used efficiently in real-world applications.

Learning Outcomes

By the end of this module the student should be able to:

1.  Be aware of the standard techniques of software performance measurement, including profiling, and apply these techniques to identify performance bottlenecks in real programs.

2.  Understand the emerging importance of parallel programming in modern software development, and experiment with the performance impact of parallelising parts of an application.

3.  Describe a variety of application-specific algorithms (sorting/numerical/image processing) and associated data structures in common use, and discuss the benefits and limitations of parallelisation.

Indicative Content

1 Measuring performance

Basic techniques, sources of error [round off, range, instability, discretisation], profiling, analysing and presenting results

2 Parallel programming

Why to parallelise, Amdahl's law, high-level approaches to parallelisation, parallel design

3 Low-level programming with threads

Starting and joining threads, sharing data safely, mutual exclusion, synchronisation objects, lock-free

4 High-level parallel programming

Task-based parallelism, data-parallel problems, exploiting locality

5 Instruction-level parallelism

SIMD instructions, automatic vectorisation


GPU architectures, appropriate algorithms for GPUs, GPU profiling

7 Application case studies

Awareness of common sorting, numerical, image processing and searching and optimization algorithms (and associated data structures) and a recognition as to which are relevant for chosen field of study e.g. Spatial trees, pathfinding and AI, database indexing, password hashing, simulation, file carving] and which can benefit from parallelisation.

Statement on Teaching, Learning and Assessment

The module is taught using one or two two-hour lectorials each week, which introduce theoretical material and immediately put it into practice through guided lab exercises. Students demonstrate their attainment of the learning outcomes through the submission of a portfolio of completed lab exercises and a detailed performance analysis of a complex application of their choice based on one (or more) of the case studies.

Teaching and Learning Work Loads

Total 200
Lecture 14
Tutorial/Seminar 0
Supervised Practical Activity 28
Unsupervised Practical Activity 0
Assessment 86
Independent 72

Guidance notes

Credit Value – The total value of SCQF credits for the module. 20 credits are the equivalent of 10 ECTS credits. A full-time student should normally register for 60 SCQF credits per semester.


We make every effort to ensure that the information on our website is accurate but it is possible that some changes may occur prior to the academic year of entry. The modules listed in this catalogue are offered subject to availability during academic year 2019/10 , and may be subject to change for future years.