Algorithm Design and Analysis
Module aims
In this module you will have the opportunity to:
- Explore the main algorithmic design paradigms
- Apply algorithmic techniques to practical and unseen problems
- Quantitatively analyse the performance of algorithms
- Model the mathematical structure of computational tasks and apply the right algorithmic tools on them
- Develop your algorithmic thinking and problem solving skills.
Learning outcomes
Upon successful completion of this module you will be able to:
- Compare, characterise and evaluate different implementations of basic algorithms
- Analyse algorithms using quantitative evaluation
- Formulate algorithmic abstractions of computational problems
- Design and implement efficient algorithms for practical and unseen problems
- Specify which algorithms can be applied to which classes of problems
Module syllabus
- Quantitative Analysis of Algorithms and Growth Order
- Divide and Conquer
- Dynamic Programming
- Greedy Algorithms
- Randomised Algorithms
- Advanced Graph Algorithms
- String Processing Algorithms
Teaching methods
The material will be taught through traditional lectures, backed up by in-class tutorial sessions addressing unassessed, i.e. formative, tutorial problems designed to reinforce the material as it is taught. The lectures will also include occasional demonstrations of algorithms in action using various tools, such as Jupyter notebooks.
An online service will be used as a discussion forum for the module.
Assessments
There will be two assessed courseworks, both including a practical programming element, that contribute 20% of the mark for the module. There will be a final written exam, which counts for the remaining 80% of the marks.
Feedback will be given on the two assessed courseworks in form of annotated electronic submissions.
Reading list
Core
-
Introduction to algorithms [electronic resource]
Fourth edition., The MIT Press
-
Algorithm design with Haskell
Cambridge ; New York, NY : Cambridge University Press
-
Algorithm design with Haskell / Richard Bird, Jeremy Gibbons
-
Purely functional data structures
Cambridge University Press
-
Purely Functional Data Structures
-
Algorithms: A Functional Programming Approach
Addison-Wesley Longman Incorporated
Supporting
-
Algorithms
4th ed., Boston, Mass. ; London : Addison-Wesley
-
Algorithms
McGraw-Hill Higher Education
-
Programming in Haskell
Second edition., Cambridge : Cambridge University Press
-
Thinking functionally with Haskell / [eletronic resource]
Cambridge University Press