Name Choose and solve six out of the points, Clearly mark the problems you select. following eight problems. Each problem counts for three . Write down an implementation of a recursive function that returns 3 raised to the power k for any input argument k 1,2,3,.... Your function should accomplish the computation for all arguments k in the range [3", 3n 1) with just n+ 1 calls. Justify correctness of your implementation. 2. Solve the following recurrence equations. Assume T(O) 1 (i) T(n) 2T (n/2) + logn, assume that n 2 (ii) T(n)-8T(n/3) + n", assume that n-3k write down a detailed implementation of the operation CREATE3 of the Tree ADT. Assume that trees are represented by lists of children. Make use of the following structures. 3, var nodespace: arrayl1.maxnodes] of record label: labeltype; header: integer cursor to cellspace) end; var cellspace: arrayl1..maxnodes] of record node: integer; next: integer end; 4. A full BST of height k containing numbers 1,2,. k1-1 is given. Draw the resulting BSTs after operations described below are applied to it. Justify correctness of your drawings (i) Delete operation is applied to all even numbers 2,4,6, , 2 2. (i) Delete operation is applied to all odd numbers 1,3,5,., 21. k+1 function DELETEMIN( var A: SET): elementtype; var minimum: integer