Algorithms and Analysis

Learning Outcomes

Subject Specific Practical Skills

Having successfully completed this module you will be able to:

• Empirically evaluate the performance of algorithms for a given data-set
• Be able to use data structures to build complex algorithms
• Load real-world data into data structures and apply analysis and transformations
• Be able to implement simple data structures in code

Subject Specific Intellectual and Research Skills

Having successfully completed this module you will be able to:

• Understand the operation of a number of important computer algorithms using particular structures
• Understand how to evaluate an algorithm for efficiency
• Discuss the real-world impact of asymptotic complexity
• Choose the most appropriate data structures and algorithmic strategies for a particular problem

Knowledge and Understanding

Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:

• Show an understanding of time complexity
• Demonstrate knowledge of common data structures and algorithms
• Understand how to implement algorithms and data structures in code

Algorithmic Complexity:

• Big-O
• Space vs time
• Asymptotic vs real-world behaviour
• NP completeness and approximations/good-enough solutions

Basic data structures, such as:

• Vectors/lists/queues
• Multi-dimensional arrays and matrices/tensors
• Trees
• Hash-tables & maps
• Sets

Basic algorithms, including:

• Searching
• Sorting
• Dynamic programming

Graphs:

• Representation (vertices and edges, (sparse) matrix representations, etc)
• Breadth vs depth search
• Shortest paths, minimum spanning trees, etc with algorithms including Dijkstra, Prim’s, Kruskal,...

Random number generation:

• Uniform variate generation
• Security: cryptographic/strong versus weak
• Simple reparameterisations
• Inverse transform mapping
• Rejection methods

The module consists of:

• Lectures
• Guided self-study
• Labs as part of the AICE Lab Programme which will cover practical aspects

Summative

This is how we’ll formally assess what you have learned in this module.

Referral

This is how we’ll assess you if you don’t meet the criteria to pass this module.

Repeat

An internal repeat is where you take all of your modules again, including any you passed. An external repeat is where you only re-take the modules you failed.