Question $5$: $(20$ Points$).$

a$.$ The input list of binary search is $L=(3,6,9,12,18,21,24,27,30,36)$

For each target value x given below, give the values for variables low and high for each call to BinarySearch. Then give the final return value. $(6$ points$)$

$($a$)x=18$

$($b$)x=4$

b$.$ Give the recursion tree for a call to MergeSort with the input list $(10,7,25,4,18,3,12,8).$ For each call to MergeSort, provide the input list for that call, the input and output for the recursive calls made and the final output list for that call. $(7$ points$)$

c$.$ Give a recursive algorithm whose input is a real number $r$ and a non$-$negative integer $n,$ and whose output is $r^{3^n}.$ Your algorithm should only use addition and multiplication operations and should not contain any iterative loops. $(7$ points$)$