3. For this question assume that n > 2 is a power of 2. Suppose you are given an array A of n elements on which a total ordering is defined. Suppose you are also given a subroutine Compare (e1,e2) that returns 1 if e is smaller than ez as per the ordering and 0 otherwise. The goal is to design an algorithm for finding the smallest and second smallest element in the array A using the comparison routine Compare provided. The calls to Compare is expensive and we would like to minimise the number of calls. For this problem, we will just focus on analysing the number of calls to Compare. This kind of analysis relevant in many scenarios where comparing elements dominates the other computational costs. Consider the following algorithm: Algorithm-1(A,n) - if (Compare (A[1], A[2]) == 1){min - A[1]; min2 - A[2]} - else {min + A[2]; min2 + A[1]} - For i = 3 to n: - if (Compare (A[i], min) == 1){min2+ min, mint A[i]} - elseif (Compare (A[i], min2) == 1)min2 + A[i] - else continue Let C(n) denote the number of times Compare is called in the worst case by Algorithm-1. Now consider the following divide and conquer algorithm: Algorithm-2(A,n) - if (n == 2) - if (Compare (A[1], A[2]) == 1)return((A[1], A[2])) - else return((A[2], A[1])) - Split the array A in the middle into two arrays A and AR of half the size - (s. 52) + Algorithm-2(AL,n/2) - (t, t2) + Algorithm-2(AR, 1/2) - if (Compare(s, t) == 1) - mins - if (Compare (s2,t) == 1)min2 s2 -else min2t - else - mint - if (Compare(s, t2) == 1)min2S -else min2t2 - return((min, min2)) Let R(n) denote the number of times Compare is called in the worst case by Algorithm-2. Let us now try to see whether the divide and conquer algorithm is better in terms of the number of comparisons. Answer the following questions. (a) (1/2 point) Give the exact value of C(n) as a function of n. (b) (% point) Write the recurrence relation for R(n). Give an exact expression. (c) (1 point) Solve the recurrence relation in part (b) using unrolling of the recursion to obtain the exact value of R(n) as a function of n. 3. For this question assume that n > 2 is a power of 2. Suppose you are given an array A of n elements on which a total ordering is defined. Suppose you are also given a subroutine Compare (e1,e2) that returns 1 if e is smaller than ez as per the ordering and 0 otherwise. The goal is to design an algorithm for finding the smallest and second smallest element in the array A using the comparison routine Compare provided. The calls to Compare is expensive and we would like to minimise the number of calls. For this problem, we will just focus on analysing the number of calls to Compare. This kind of analysis relevant in many scenarios where comparing elements dominates the other computational costs. Consider the following algorithm: Algorithm-1(A,n) - if (Compare (A[1], A[2]) == 1){min - A[1]; min2 - A[2]} - else {min + A[2]; min2 + A[1]} - For i = 3 to n: - if (Compare (A[i], min) == 1){min2+ min, mint A[i]} - elseif (Compare (A[i], min2) == 1)min2 + A[i] - else continue Let C(n) denote the number of times Compare is called in the worst case by Algorithm-1. Now consider the following divide and conquer algorithm: Algorithm-2(A,n) - if (n == 2) - if (Compare (A[1], A[2]) == 1)return((A[1], A[2])) - else return((A[2], A[1])) - Split the array A in the middle into two arrays A and AR of half the size - (s. 52) + Algorithm-2(AL,n/2) - (t, t2) + Algorithm-2(AR, 1/2) - if (Compare(s, t) == 1) - mins - if (Compare (s2,t) == 1)min2 s2 -else min2t - else - mint - if (Compare(s, t2) == 1)min2S -else min2t2 - return((min, min2)) Let R(n) denote the number of times Compare is called in the worst case by Algorithm-2. Let us now try to see whether the divide and conquer algorithm is better in terms of the number of comparisons. Answer the following questions. (a) (1/2 point) Give the exact value of C(n) as a function of n. (b) (% point) Write the recurrence relation for R(n). Give an exact expression. (c) (1 point) Solve the recurrence relation in part (b) using unrolling of the recursion to obtain the exact value of R(n) as a function of n