A complex linear structure is to be assembled out of n smaller pieces. We will think of each piece as an interval [a; b]. The joining operation takes [a; b] and [b; c] and produces [a; c]. After joining, each subpart must be tested. Assume that the cost to test [u; v] is given by f(u; v) > 0 Different assembly orders potentially have different total testing cost. For example, suppose that we have three pieces corresponding to intervals [1, 2]; [2; 3); and [3; 4], and the cost of testing is given by: f(1; 3) = 3, f(2; 4) = 1, and f(1; 4) = 5. Then assembling the first and second pieces first and then joining them with the third has a total testing cost of f(1; 3) + f(1; 4) = 8, whereas assembling the second and third pieces first and then joining them with the first has a total testing cost of f(2; 4) + f(1; 4) = 6. Therefore, the second assembly order is preferable.

Design an O(n^3) algorithm using dynamic programming methodology to find an optimal (least total testing cost) assembly order. Note that you should

a. Use iterative implementation for the algorithm to find the optimal cost.
b. Show the algorithm for finding the optimal order.
c. Give a brief argument of correctness and analyze the running time.