MATH2014 Algorithms
SEMESTER 2 EXAMINATION 2022/23
1. Consider the undirected, unweighted graph Guu shown in Figure 1.
Figure 1: the undirected, unweighted graph Guu
[THIS QUESTION IS WORTH 20 marks IN TOTAL]
(a) Verify that Guu is bipartite. [5 marks]
(b) Using the algorithm as given in the lecture slides and the lectures, find a matching M for Guu satisfying |M| = ν(Guu ). [15 marks]
2. Show that the Ford Fulkerson algorithm can be used to find a matching M for a bipartite graph G satisfying |M| = ν(G).
[THIS QUESTION IS WORTH 20 marks IN TOTAL]
3. Consider the undirected, weighted graph Guw shown in Figure 2.
Figure 2: the undirected, weighted graph Guw
[THIS QUESTION IS WORTH 20 marks IN TOTAL]
(a) Use the Jarnik Prim Dijkstra algorithm to find a minimum cost spanning tree T in Guw, starting at the node 1. [15 marks]
(b) Is the spanning tree obtained in part (a) uniquely determined? Be sure to justify your answer. [5 marks]
4. Consider the directed, weighted graph Gdw shown in Figure 3. The weight on each edge is its capacity.
Figure 3: the undirected, weighted graph Gdw
[THIS QUESTION IS WORTH 20 marks IN TOTAL]
(a) Use the Ford Fulkerson algorithm to find the net flow value on Gdw with s = 5 and t = 8. For this question, please use the starting flow x that takes the value of 0 to each edge. [15 marks]
(b) Is the net flow value independent of the choice of s and t? Be sure to justify your answer. [5 marks]
5. Let {a1 , a2, . . . , an } be a list of n ≥ 2 distinct positive integers. We sort this list into a list in ascending order as follows. We first pass through the list from a1 to an , find the smallest element and interchange this smallest list element and a1 . We then pass through the list from a2 to an, find the smallest element and interchange this smallest list element with a2 . We continue in this way until we have our list in ascending order.
[THIS QUESTION IS WORTH 20 marks IN TOTAL]
(a) Write out the pseudocode for this sorting algorithm. [5 marks]
(b) Determine the computational complexity of this sorting algorithm, in terms of n. [10 marks]
(c) By use of a specific example, show that the estimate given in part (b) is best possible. [5 marks]