F28JE - Data Structures and Algorithms

Course leader(s):

Christos Chrysoulas (Edinburgh, January)

Aims

To introduce core algorithms and data structures used in a wide range of applications in Computer Science.

To further develop skills in algorithm and data structure design, and the development of medium sized programmes.

Syllabus

1. Computational complexity (1.1 1. Definition of time and space complexity bounds, 1.2 2. Applications: working with the definition, 1.3 3. Amortised complexity)

2. Algorithm design techniques (2.1 1. Brute force, 2.2 2. Divide-and-conquer, 2.3 3. Greedy algorithms, 2.4 4. Dynamic programming)

3. Text algorithms (3.1 1. Text searching and substring problems, 3.2 2. Text compression)

4. Graph algorithms (4.1 1. Graphs and their representations, 4.2 2. Graph searching, 4.3 3. Spanning trees, 4.4 4. Shortest paths)

5. Finite set and map representations (5.1 1. Hashing and hash tables, 5.2 2. Balanced search trees)

Learning outcomes

By the end of the course, students should be able to do the following:

design Abstract Data Type (ADT) interfaces of data structures necessary to solve a computational problem.
implement a concrete realisation of an ADT choosing appropriate representation of the data.
discuss the key attributes of an algorithm to ensure adherence to its specification.
analyse the runtime behaviour of an algorithm or data structure in terms of time and memory complexity.
select an appropriate realisation of an ADT based on the requirements and constraints of a problem.
adapt a known algorithm/data structure to solve a new computational problem.

Further details

Curriculum explorer: Click here

SCQF Level: 8

Credits: 15