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] > 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(l: 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^2) algorithm using dynamic programming methodology to find an optimal (least total testing cost) assembly order. Give a brief argument of correctness, and analyze the running time. 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] > 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(l: 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^2) algorithm using dynamic programming methodology to find an optimal (least total testing cost) assembly order. Give a brief argument of correctness, and analyze the running time