SB CSE 675
Program Transformation and Program Analysis
Oct. 26, 2000
Due Nov. 1
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)We would like to derive an efficient program for computing b(i,j) via effective caching using the cache-and-prune method.
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?