Objectives: Divide and Conquer Solving recurrence relations Problems Q1. The following algorithm finds the maximum element in the given array. Prove the correctness of the algorithm. In addition, analyze its time complexity in the worst-case and best-case scenarios. def max (A) m = A[0] for i = 1 to n-1 do if A[i] >m then m = A[i] return (m) Q2. The following algorithm returns the product of two numbers, a and b. The parameters x and y are natural numbers. First, prove the correctness of the algorithm. Then, analyze the time complexity of the algorithm in the worst case scenario. function mult(a, b) if b = 0 : return 0 else if bis odd: return (mult (2a, b/2 ) +a) else: return (mult(2a, b/2)) Q3: Solve the following recurrence using substitution method and then prove the correctness using induction: T(1) = 1 ns2 T(n) = 2 T(n-1) + n - 1 n > 2 Q4: Solve the following recurrence relation using recursion tree and master theorem: T(n) = C ns2 T(n) = 7T(n/2) + n? n> 2 Q5: In the merge-sort algorithm we studied in the class, a problem is divided into two subproblems. Design and analyze a new version where each problem is divided into n subproblems. Write the pseudocode of the algorithm and analyze its time complexity. Q6: In the polynomial multiplication algorithm we did in the class, we divided each polynomial into two parts. Design a new algorithm which divides each polynomial into three parts. Analyze the runtime of the algorithm you design. Do you get an algorithm with better complexity