Explain

Designing and analysing a divide-and-conquer algorithm: - The input is an increasing array A[0]A[1]A[n1] of integers, with n1 and A[n1]0. - The task is to compute the smallest index 0in1 with A[i]0. - For example with A=(2,1,0,0,1,3) (so n=6, and the indices are 0,,5) the answer is i=2. 1. Give a divide-and-conquer algorithm solving this problem, as a recursive algorithm. Clearly show the division and recombination steps, and the handling of the base cases. The essential ideas should be clearly given, but a full formal description is not needed. [7 marks] 2. Write down a recurrence which describes the run-time of your algorithm. [2 marks] 3. Solve the recurrence by using the (simplified) Master Theorem (state which case applies), obtaining a -expression. [1 marks] 4. Explain in a few words an alternative algorithm for solving this problem, and state the asymptotic runtime for it. Compare the run-time for your above divide-and-conquer algorithm with the rum-time of the alternative algorithm. State which algorithm is asymptotically better, or whether they are asymptotically equally good. [3 marks]