Caching, Memoization, Tabulation, Dynamic Programming. (Due at class time next Wednesday.)

Binomial coefficients are used in polynomial computations as well as combinatorics. Given an integer i, coefficients for items <i,j>, for 0 < j < i, are defined by function b(i,j).

  b(i,j)    where 0 <= j <= i
  = if j=0 or j=i then 1
    else b(i-1,j-1) + b(i-1,j)

a. What is the program bbar that caches all intermediate results of b in the return value?

b. What is the appropriate + operation, <i',j'> = <i+1,j+1> or <i',j'> = <i+1,j>?

c. Derive an incremental version bbar' of bbar under the appripriate + operation.

d. Prune both bbar and bbar'.

e. Use the resulting incremental version to give a new definition of b(i,j).

f. What is the time and space complexity of the optimized program?