Module overview
Aims and Objectives
Learning Outcomes
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
Subject Specific Intellectual and Research Skills
Having successfully completed this module you will be able to:
- Understand how to evaluate an algorithm for efficiency
- Choose the most appropriate data structure for a particular problem
- Understand the operation of a number of important computer algorithms using those structures
- Choose an appropriate algorithmic strategy to solve a problem
- Solve problems algorithmically
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 |
---|---|
Completion of assessment task | 10 |
Preparation for scheduled sessions | 6 |
Follow-up work | 18 |
Tutorial | 12 |
Lecture | 36 |
Revision | 18 |
Wider reading or practice | 50 |
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 |
---|---|
Examination | 90% |
Quizzes | 10% |