Answer the following questions about computing the function $f(n,k)$ below:

$f(n,k)=\{\begin{array}{ccc}k,& if& n=1\\ f(n,& k+1),if& k=0\\ f(n-1,& k-1)+f(n-1,k+1),\text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}& \end{array}$

$($a$)$ Give a short example demonstrating why dynamic programming would be effective in computing $f(n,k).$

$($b$)$ What implementation would you recommend for a dynamic programming data structure to compute $f(n,k)?$ Briefly justify your answer.

$($c$)$ Sketch the data structure you would use to compute $f(6,3).$

$($d$)$ Add a B to every cell in your data structure representing a base case.

$($e$)$ Draw arrows from the cell $f(6,3)$ representing all recursive calls made by this instance. Do not trace the entire subtree, only the immediate children of $f(6,3).$

$($f$)$ Describe a valid iteration order for a dynamic programming algorithm to compute $f(n,k).$ You may give your answer in terms of direction or as one or more for loops.

$($g$)$ Give pseudocode for an iterative dynamic programming algorithm to compute $f(n,k).$

$($h$)$ Can the space complexity of your algorithm be reduced? If so$,$ describe how you would reduce the space complexity. If not, justify why it cannot be reduced.