Question $9$

Give the recursion tree for a call to MergeSort with the input list $(8,4,12,16,3,10,2,14).$ For each call to MergeSort, give: The input list to that call, the input and output for the recursive calls made, and the final output list for that call.

Question $10$

a$)$ The input list of binary search is $(3,7,12,16,22,29,34,43,48,60)$ For each target value $\backslash ($ x $\backslash )$ given below, give the values for variables low and high for each call to BinarySearch. Then give the final value return value by the function.

i$.\backslash (\backslash$mathrm$\{$x$\}=16\backslash )$

ii$.\backslash ($ x$=29\backslash )$

b$)$ The input to a recursive binary search algorithm is target $\backslash ($ x $\backslash )$ and list $\backslash ($ L $\backslash )$ :

$\backslash [$

$\backslash$mathrm$\{$L$\}\backslash$equiv$(4,7,12,15,20,25,30,35,40,45)$

$\backslash ]$

The algorithm sets the variables low and high so that if $\backslash ($ x $\backslash )$ occurs in the list, then $\backslash ($ x $\backslash )$ is guaranteed to occur somewhere in locations low through high. What updates should be made to the low and$/$or high variables to maintain the correct properties? Explain your reasoning.$|$

i$.\backslash (15$