Module overview
Aims and Objectives
Learning Outcomes
Subject Specific Intellectual and Research Skills
Having successfully completed this module you will be able to:
- Solve problems algorithmically
- Choose an appropriate algorithmic strategy to solve a problem
- Understand the operation of a number of important computer algorithms using those structures
- Understand how to evaluate an algorithm for efficiency
- 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 |
|---|---|
| Follow-up work | 18 |
| Tutorial | 12 |
| Completion of assessment task | 10 |
| Lecture | 36 |
| Revision | 18 |
| Wider reading or practice | 50 |
| Preparation for scheduled sessions | 6 |
| Total study time | 150 |
Resources & Reading list
Textbooks
Weiss MA (2006). Data Structures and Algorithm Analysis in Java. Addison-Wesley.
Robert Sedgewick and Kevin Wayne (2011). Algorithms. Addison-Wesley.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2009). Introduction to Algorithms. MIT Press.
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 |
|---|---|
| Examination | 90% |
| Quizzes | 10% |