Algorithms
Module aims
This module continues the thread of algorithm design and analysis that was started within your Autumn term programming subjects. You will develop your algorithm design ability by studying and then deploying a series of algorithmic strategies and their related data structures. You will deepen your understanding of formal algorithm analysis, and the way analysis guides design, as you see how the computational complexity of each algorithm is derived.
Learning outcomes
On successful completion of the module, you will be able to:
- Design algorithms to solve well-defined computational problems.
- Design algorithms to satisfy specific performance bounds.
- Design code using key strategies: incremental, divide and conquer, dynamic programming and greedy.
- Derive expressions for computational complexity from coded procedures.
- Analyse complexity using advanced methods such as recurrences, probability and amortisation.
- Implement efficient data structures, and incorporate such data structures into solutions for difficult problems.
Module syllabus
Algorithm Analysis
- Time Complexity, Space Complexity and Auxiliary Space
- Asymptotic Complexity and Highest Order Terms
Incremental Algorithms
- Incremental Sorting
- Aggregate Analysis
- Recurrences and Substitution
Divide and Conquer
- Divide and Conquer Sorting
- Recursion Trees
- The Master Method
Optimisation Problems
- Defining The Optimal Value
- Dynamic Programming
- Greedy Algorithms
Data Structures
- Binary Heaps
- Binary Search Trees
- Hash Tables
- Expected Time Complexity
- Amortised Analysis
Graph Algorithms
- Representing Graphs
- Graph Search
- Spanning Trees
- Kruskal’s Algorithm
- Disjoint Sets
Teaching methods
You will study primarily from a comprehensive set of notes written specifically for this module. This will be provided before teaching begins. Live classes will interleave lecturing and worked problems, following the structure of the notes, with one chapter being presented each week. The notes have short exercises integrated throughout, that you can attempt in advance of the relevant lecture. Solutions to the exercises are provided in the notes to allow you to self-assess, and many of the exercises will also be discussed in class. Each chapter also has an associated set of tutorial problems. These will be more challenging questions, often drawn from past exam papers. Tutorial questions will be published in advance, worked through in class, and model solutions will then be provided.
An online service will be used as a discussion forum for the module.
Assessments
* Simple exercises are integrated into the module notes to reinforce fundamental points of learning alongside their explanation. Selected exercises from the notes will be set and then discussed during live classes. All exercises have provided solutions in the notes to allow self-assessment.
* Sets of formative tutorial problems will also be set weekly. These will be more challenging questions, designed to prepare students for exam-level difficulty. The problems can be attempted independently and will then be worked through within a live session. Model solutions will be published after the class.
* Summative written coursework exercises contributing 20% of the total mark will be set during the module. These will be a combination of writing pseudocode solutions to computational problems, and formal derivations of computational complexity.
* One timed, written examination will contribute 80% of the total mark.
* Feedback on formative problems and tutorial exercises will be given in the form of: model solutions to all exercises for self-assessment; and discussion within live classes. Discussion between classes is also available via an online forum.
* Feedback on the summative coursework exercises will be provided by publishing provisional marks and annotating all submissions with written feedback. Feedback on each exercise will be given in time to feed forward into later exercises.
Reading list
Reading list
-
Introduction to algorithms
Fourth edition., The MIT Press