Learning Outcomes:
On completion of this module, students will be able to:
1. Model real-world problems in terms of graphs
2. Understand the basic graph algorithms and the algorithm design process
3. Be able to mathematically analyse simple graph algorithms
4. Competently apply the basic graph algorithms to solve problems in various domains
Indicative Module Content:
This module is an introduction to basic graph algorithms. It will cover:
1. Modelling industry and scientific problems in terms of graphs
2. Graph Traversal Algorithms: Breadth-First search, Depth-First search, Topological ordering
3. Path-based Optimisation: Shortest paths, All-pair shortest paths
4. Connectivity Problems: Minimum spanning trees, Connected components, Strongly connected components
5. Approximation Algorithms: Vertex cover, Travelling salesman problem