a. Solve the recurrence relation for computing the binomial coefficients (seen below) C(n,k - C(n - 1, k-1) +C(n - 1,k) for n > k > 0, Algorithm Binomial(n, k) //Computes C(n, k) by the dynamic programming algorithm //Input: A pair of nonnegative integers n k0 //Output: The value of C(n, k) for i-0 to n do for j -0 to min(i, k) do if j-0 or j-i else Cli.j] Cli-1, j-1] + C[i-19) return C[n, k] Hint: Think about the "shape" of a table that records values for binomial coefficient, that has n+1 rows and k+1 columns. b. The time and space efficiency for part a) is e(nk). Rewrite the Binomial (n, k) function with@ (n) space efficiency a. Solve the recurrence relation for computing the binomial coefficients (seen below) C(n,k - C(n - 1, k-1) +C(n - 1,k) for n > k > 0, Algorithm Binomial(n, k) //Computes C(n, k) by the dynamic programming algorithm //Input: A pair of nonnegative integers n k0 //Output: The value of C(n, k) for i-0 to n do for j -0 to min(i, k) do if j-0 or j-i else Cli.j] Cli-1, j-1] + C[i-19) return C[n, k] Hint: Think about the "shape" of a table that records values for binomial coefficient, that has n+1 rows and k+1 columns. b. The time and space efficiency for part a) is e(nk). Rewrite the Binomial (n, k) function with@ (n) space efficiency