1. (15 points) Binomial Coefficients. Given the following dynamic programming algo- rithm for calculating C(n, k), the number of subsets of k elements from an n-element set (0 k n):

ALGORITHM Binomial(n, k)

// Computes C(n, k) by the dynamic programming algorithm

// Input: A pair of non-negative integers 0 k n

// Output: The value of C(n, k)

fori 0tondo

forj 0tomin(i,k)do

if j = 0 or j = i

C[i, j] 1

else

C[i,j] C[i-1,j-1]+C[i-1,j]

return C[n, k]

(a) (10 points) Compute Binomial(4, 2). Show all of your work and include your completed C table.

(b) (5 points) What is the space efficiency of Binomial? How can the space efficiency be improved