Given:
•
A sequence of n arrival times t0, t1, ..., tn-1,
•
a library of mlogically equivalent gates {(d0, c0), (d1, c1), ..., (dm-1,cm-1)} where d is delay and c is cost
•
a maximum allowable arrival time at the output of the tree tmax
Objective: Construct a legal tree of gates which minimizes the total cost of the tree subject to the constraint that the arrival time at the output is no greater than tmax.
Use dynamic programming to solve this