2 Second largest element In this question, we consider the problem of finding the second largest element of an unsorted array A using as few comparisons as possible. We could use the algorithms developed in worksheet 4 to find this element, but the number of comparisons required would be more than that minimum. 1. [4 marks] First, design a divide-and-conquer algorithm to find the position of the largest element in an unsorted array. Your algorithm should make exactly n-1 comparisons between array elements. 2. [6 marks] Now let us consider the problem of finding the second largest element of A using at most n+ log2 n] 1 comparisons. Here is an outline of an algorithm that can achieve this: Start with your algorithm from part (a). Modify it, by recording some additional information each time a comparison is done. Finally, after finding the position of the largest element of A, use the recorded information to find its second largest element using at most log2 n] additional comparisons. Explain what information needs to be recorded by your algorithm from part (a), and how you would use it to find the second largest element of A using at most log2 n additional comparisons. Hint: think of a tennis tournament, where each player is eliminated as soon as he/she loses a match. What can you say about the second best player? Why did he/she not win the tournament