代做MATH2014 Algorithms SEMESTER 2 EXAMINATION 2022/23代做留学生SQL语言

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]