Module overview
This module teaches the basic data structures and algorithms which underpins modern software engineering. Without these algorithms most software would be hopelessly slow to the point of unusability. The course also teaches the principles behind the algorithms and data structures and the software engineering lessons which data structures and algorithms teach us.
Aims and Objectives
Learning Outcomes
Subject Specific Intellectual and Research Skills
Having successfully completed this module you will be able to:
- Choose an appropriate algorithmic strategy to solve a problem
- Understand how to evaluate an algorithm for efficiency
- Understand the operation of a number of important computer algorithms using those structures
- Solve problems algorithmically
- Choose the most appropriate data structure for a particular problem
Knowledge and Understanding
Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:
- Common data structures and algorithms
- Time complexity
- The implementation of common data structures
Syllabus
Introduction to Data Structures
- Data Objects, Data Structures, Complex Data Structures
Algorithm Analysis
- Time Complexity
Simple Data Structures
- List, Stack, Queue, Tree, Tree traversal
Sorting
- Selection Sort, Insertion Sort, MergeSort, QuickSort, Radix sort
Searching
- Sequential Search, Binary Search, Binary Tree Search
Advanced Tree Structures
- AVL Trees, B-trees
Hash tables
- Hash table size, Collision resolution, Separate chaining
- Open addressing, Re-hashing
Priority Queues (Heaps)
- Simple implementations, Binary heaps, Heap sort
Graphs
- Adjacency Matrix and List, Connectivity, Breadth vs Depth first search
- Shortest path algorithms
- Minimum Spanning Tree, Prim's algorithm
Learning and Teaching
Teaching and learning methods
The content of this module is delivered through lectures, the module website, directed reading, pre-recorded materials and tutorials.
Students work on their understanding through a combination of independent study, preparation for timetabled activities, tutorials, and problem classes, along with formative assessments in the form of problem sheets.
| Type | Hours |
|---|---|
| Preparation for scheduled sessions | 6 |
| Lecture | 36 |
| Wider reading or practice | 50 |
| Completion of assessment task | 10 |
| Revision | 18 |
| Tutorial | 12 |
| Follow-up work | 18 |
| Total study time | 150 |
Resources & Reading list
Textbooks
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2009). Introduction to Algorithms. MIT Press.
Weiss MA (2006). Data Structures and Algorithm Analysis in Java. Addison-Wesley.
Robert Sedgewick and Kevin Wayne (2011). Algorithms. Addison-Wesley.
Assessment
Assessment strategy
This module is assessed by a combination of problem sheets and a final assessment in the form of a written examination.Summative
This is how we’ll formally assess what you have learned in this module.
| Method | Percentage contribution |
|---|---|
| Quizzes | 10% |
| Examination | 90% |