2. (a) Write an algorithm in pseudo-code that takes as input an array A[1...n), and an item M which occurs at least once in A. returns the index (position) of the last occurrence of the item M in array A. The following table shows some examples with the expected output of the algorithm (the last occurrences of M is underlined): Net input: A M output (1,8,1, 7, 1,9] 1 5 [4, 3, 2, 2, 2,3] 2 5 [9,9 9 2 (3,3,3,3 3 4 [4,3,3,3] 4 Your algorithm should perform as few comparisons as possible. [25 marks) (b) Consider using the following algorithm on an array A = [5,3,6,4,1]. Input: Array A[1...n] Output: ?? i for i + 2 to n do 2 K+ A[i] ji-1 while j> 0 and A[j] > K do A[j+1] - [j] ; j-1 7 A[j] K 8 return A i. Write the array A after each iteration of the outer For-loop, and state what you think the algorithm does. Show all your working. [15 marks] ii. How many times will line 5 be executed for the array A? How many times for an array of length n? [5 marks) iii. How many times will line 4 be executed in the worst case for the array A? How many times for an array of length n? 3 5 6 ir