Data Structures and Algorithms 1

Building on students' knowledge of programming facilities taught in Level 7 programming modules (e.g. arrays, structures, simple collections), this module introduces the standard data structures and algorithms that form the core of algorithmic thought in computer science, and introduces students to the idea of reasoning about the behaviour and performance of a computer program.

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

1. Describe abstract and concrete requirements for data structures and algorithms.
2. Describe a range of standard data structures and algorithms, in terms of both functionality and performance characteristics.
3. By reasoning about behaviour and performance, be able to critically select appropriate data structures and algorithms for a given application within a software project.

1 Reasoning about performance

The idea of an algorithm, time and space complexity, abstract data types, benchmarking and profiling, statistics for software performance, architecture and performance

2 Basic data structures

Linked lists, stacks, queues, maps, hash tables, stack lists.

3 Sorting and searching

Exhaustive and binary search, sorting algorithms. hashing algorithms, collision detection and prevention.

4 Trees

Simple trees, binary trees, tree search algorithms, tree representations in memory.

5 Graphs

Simple and directed graphs, graph algorithms, shortest path algorithms, matching and allocation problems.