CS 313/CS 351- Design and Analysis of Algorithms Assignment-2 Submit by : Monday, March 2, 2020 (At start of class: 10AM) Instructions: Answer all questions. You may write your answers legibility by hand NOTE: Plagiarism will result in 0 grade. Qu 1: Solve the following recurrence relation by first using the Recursive Tree Method to obtain the solution (showing details of your work) then use the Substitution method to prove the correctness of your solution (2 Marks) T(n)= 4T(n 2) + n? (3 Marks) Ou 2: Use Master Theorem to solve each of the following recurrence relations (1) Tin) = 4Tin 2) + n- (ii) Tin) - 3T(n/2) +n (iii) Tn) = 7T(n/3) + n