Learning Outcomes:
On successful completion of this module, the student should be able to:
1. Demonstrate an understanding of the general notion of complexity classes, P and NP, completeness and hardness, and the relationships between classes by reduction.
2. Demonstrate an understanding of the theory underlying exact and heuristic approaches to combinatorial optimisation problems.
3. Prove and interpret standard results in graph theory.
4. Develop, implement, and critically evaluate the correctness and performance of standard graph and combinatorial optimisation algorithms.
5. Select and implement appropriate formulations and algorithms from graph theory and combinatorial optimisation to analyse problems from computing, engineering, and operations research.
Syllabus Content:
The module will introduce the students to the fundamental concepts and techniques in graph theory and network based combinatorial optimisation, focusing on the relationships between algorithms and associated data structures. The module also includes discussions of applications to problems from computing, engineering, and operations research thus illustrating the broad applicability of the theory.
Pre-requisites:
á Basic programming skills (graduate of a BSc or BEng involving significant programming experience)
á Moderate mathematical ability (at least one year of undergraduate mathematics), in particular, basic linear algebra (including eigenvalues and eigenvectors) and an understanding of simple combinatorial counting processes involving permutations and combinations.
Indicative syllabus content:
1. Algorithmic Complexity
Order notation (O, Θ). Analysis of algorithms. Greedy heuristics and approximate algorithms. Classification of decision problems: complexity classes of P, NP and Co-NP. NP-completeness. NP-hardness.
2. General Graph Theory
Core concepts and definitions: connectivity, dimension, graph traversal. Special graphs and their properties: complete, regular, interval vertex-transitive, and circulant graphs.
Directed graphs and weighted graphs.
3. Optimal Routes in Graphs
Graph traversal: DFS, BFS and hybrid traversal. Applications of shortest routes in graphs: determination of shortest paths in non-negatively weighted graphs via the methods of Dijkstra and of Floyd.
Estimation of the algorithmic complexities of Dijkstra's method & Floyd's method.
Applications of longest routes in directed acyclic graphs.
4. Minimum Spanning Trees
Applications of trees and of rooted trees.
Properties of rooted trees and of m-ary trees (with binary trees as a special case).
Determination of minimum spanning trees by Kruskal's, Prim's and Boruvka's method. Analysis of MST algorithms.
5. Planarity
Euler's formula. Applications of graph planarity with respect to optimal facility lay-outs. Kuratowski's theorem. Crossing numbers of graphs embedded in the plane.
6. Centres and Medians
Vertex eccentricity; radius and diameter of a graph. Graph centre and a graph median.
Applications to optimal facility placement in communication networks.
7. Vertex and Edge Colourings
Vertex and edge chromatic numbers.
Heuristic methods for graph colourings.
Applications of vertex & edge colourings with respect to scheduling.
8. Eulerian Graphs
The Kšnigsberg bridge problem. Chinese postman problem and variants. DeBruijn sequences and gray codes. Application to model based testing.
9. Hamiltonian Graphs
The travelling salesman problem (TSP): heuristics for the travelling salesman problem (such as the method of nearest neighbours and Christofides' method of cheapest insertion). Post-optimisation methods for the travelling salesman problem (such as 2-opt).
10. Network Flow
The Matching problem. Matching and augmenting paths. The network flow problem. Assignment problem. Weighted Edge cover problem. Multi-commodity flow problem.
11. Emerging Topics
Dynamic graph algorithms: clustering and topology trees, sparsification. Randomised algorithms. Graph drawing algorithms. On-line algorithms: paging scheduling and load balancing.
Practical Programme:
The practical component will involve studying a number of problems and adapt algorithms from the module into solving these problems, as well as a practical implementation of the relevant data-structures and algorithms. This way the students get practical, hands-on experience with techniques from graph theory and combinatorial optimisation. The ability to apply the theory covered in this module in terms of progressing from a problem, to selecting and implementing an appropriate solution strategy, and ultimately interpreting the results is a fundamental learning objective of this module. This ability is assessed primarily through the practical component.