SEMESTER 2 EXAMINATION 2021/22
MATH2014 Algorithms
Duration: 120 min
This paper contains five questions.
Answer ALL questions.
An outline marking scheme is shown in brackets at the end of each question.
All students: This is an open book assessment. You may consult books, notes or internet
sources. You are permitted to use calculators or mathematical software, but to obtain full
marks, you must show and explain your working as well as the final answer.
The assessment must be carried out in accordance with the University Academic integrity
regulations. It is not permitted to communicate with anyone else (be it private or online)
about the content of this exam during the whole time it is open.
Start a new question on a fresh sheet of paper.
Make sure your page is in portrait orientation.
Write in Black or Blue pen.
On each page, write your page number in the top left and your module and student ID
in the top right.
Show all working
In addition to the given duration of this paper (2 hours), you have an hour to scan and
upload your work.
Page 1 of 4
Copyright 2022 University of Southampton Page 1 of 4
2 MATH2014W1
1. (a) Compute a minimum cost spanning tree using the Jarnik-Prim-Dijkstra algorithm
on the following graph:
[10 marks]
(b) Consider now the problem of, given an undirected graph G = (V, E) with a cost
function c : E → Z
+ {0}, finding a spanning tree minimizing the product of the
costs of the edges it contains.
Explain how to solve this problem using one of the algorithms presented in the
module.
[10 marks]
2. Consider the following weighted undirected bipartite graph G = (V, E).
(a) Find a maximum-weight matching in the graph using the algorithm seen in the
lectures. Report, for each iteration of the algorithm, a copy of the graph G (in
which the current matching is highlighted) and the corresponding auxiliary graph
G0 (in which the augmenting path you have found is highlighted).
[10 marks]
(b) State and justify the complexity of the algorithm you used.
[10 marks]
Copyright 2022 University of Southampton Page 2 of 4
3 MATH2014W1
3. Consider the problem of finding a maximum flow from node 1 to node 6 in the
following directed graph G = (V, A). The two numbers on each arc are,
respectively, the flow currently on that arc and the arc capacity.
