Course Description
This module introduces data structures, algorithms, and the principles of computational complexity. Learners will become familiar with a variety of data structures and understand their similarities and differences. Both linear data structures such as arrays and lists, and non-linear data structures including graphs and trees, will be introduced. Time and space complexity, including notation for and analysis of complexity, are introduced as core considerations for algorithmic design. A range of popular sort, search, and pathfinding algorithms are introduced. Learners will gain practical experience in writing pseudocode for algorithms and using this to write, test, and debug programmed implementations of algorithms.
Course Objectives
This module introduces data structures, algorithms, and the principles of computational complexity. Learners will become familiar with a variety of data structures and understand their similarities and differences. Both linear data structures such as arrays and lists, and non-linear data structures including graphs and trees, will be introduced. Time and space complexity, including notation for and analysis of complexity, are introduced as core considerations for algorithmic design. A range of popular sort, search, and pathfinding algorithms are introduced. Learners will gain practical experience in writing pseudocode for algorithms and using this to write, test, and debug programmed implementations of algorithms.
Key Topics
- LO1: Understand a range of essential data structures.
- LO2: Understand algorithmic complexity and appreciate its importance.
- LO3: Understand a range of algorithmic techniques.
- LO4: Be able to write algorithms in popular programming languages.
Course Outline
| Week | Topics |
|---|
| 1 | Data structures: arrays, lists, stacks, queues, sets and dictionaries |
| 2 | Choosing data structures, with a Python refresher |
| 3 | Measuring complexity: Big O notation |
| 4 | Problem classes: computability and Turing machines, P and NP, NP-completeness and NP-hardness, quantum computing and open problems |
| 5 | Recursion and memoisation (e.g. Tower of Hanoi); the memory vs. complexity trade-off |
| 6 | Algorithmic paradigms: divide and conquer, backtracking, greedy algorithms and dynamic programming |
| 7 | Sort, search and pathfinding algorithms compared by time and space |
| Midterm | Midterm evaluation |
| 9 | Writing pseudocode as a universal template for algorithms |
| 10 | Checking algorithms are correct: tracing, testing and timing |
| 11 | Debugging and testing implementations; review and practice problems |
| 12 | Applying Algorithms and Data Structures in practice: case studies |
| 13 | Assignment workshop: research, planning and referencing |
| 14 | Assignment workshop: drafting, feedback and improvement |
| 15 | Review and coursework completion |
| Final | Final assessment and submission |
Learning Outcomes
- LO1 Understand a range of essential data structures.
- 1.1 Describe a data structure.
- 1.2 Explain a range of linear and non-linear data structures.
- 1.3 Analyse the impact of the choice of data structure on algorithmic performance.
- LO2 Understand algorithmic complexity and appreciate its importance.
- 2.1 Demonstrate an ability to write Big O and little o notation to describe algorithmic complexity.
- 2.2 Explain the impact of algorithmic design choice on computational complexity for a variety of examples.
- 2.3 Explain the difference between P and NP.
- 2.4 Evaluate open problems in problem classification and the impacts of future technologies on the difficulty in solving different classes algorithms.
- LO3 Understand a range of algorithmic techniques.
- 3.1 Use recursion and memoisation as tools to design solutions to problems.
- 3.2 Describe a range of sort, search, and pathfinding algorithms.
- 3.3 Explain the trade-off between memory and computational complexity in algorithmic design.
- 3.4 Critically analyse algorithmic paradigms such as the greedy approach and divide and conquer approach.
- 3.5 Evaluate sort, search, and pathfinding algorithms in terms of their space and time complexity.
- LO4 Be able to write algorithms in popular programming languages.
- 4.1 Explain how to write pseudo-code for algorithmic design.
- 4.2 Implement pseudocode in a programming language.
- 4.3 Evaluate the correctness and speed of an algorithm.
- 4.4 Use debugging to correct errors in algorithmic implementation.
