SB CSE 675
Fall 2000 |
Program Transformation and Program Analysis
Annie Liu Exercises 6 |
Handout E6
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

**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?