Please do not copy-paste from others and make sure to answer the question one by one.

Exercise 6.20 You are given a stick of length n units. Your goal is to cut the stick into different pieces (each piece should be of integer length only) so that the total value of all the pieces is maximized. A piece of length i units has value vi, for i = 1, 2, ..., n. You should design a dynamic programming algorithm that determines the maximum total value that is possible. (i) Consider the sequence of 7 numbers: 2,3,4,5,6,7,9. Let the ith number in the sequence represents the value of piece of length i, i.e., the value of piece of length 1 is 2, of length 2 is 3, length 3 is 4 and so on. What is the best way to cut the pieces for a stick of length 7? What is the maximum value ? (i) Define the subproblems for your DP solution on a general instance of the problem where the stick is of length n and a piece of length i has value vj. (iii) Give a recursive formulation to solve the subproblems. Don't forget the base cases. (iv) What is the running time of your solution? (v) Write a DP algorithm (give pseudocode) that outputs the maximum value. (vi) Describe an algorithm to output the sizes of the pieces of the cut that corresponds to the maximum value