Consider a rod of length n inches and an array of prices P[1...n], where P[i] denotes...

 

Transcribed Image Text:

Consider a rod of length n inches and an array of prices P[1...n], where P[i] denotes the price of any i inches long piece of rod. Now suppose we have to pay a cost of $1 per cut. Thus, for example, if we cut the rod into k pieces of lengths ni, n2,..., nk, this means that we made k - 1 cuts, which gives their final selling price as P[n] + + P[nk] (k 1). - Let MAXPRICE(n) denote the maximum selling price we can get this way among all possible options we have to make the cuts (note that one possible option is to make no cut and sell the whole rod of length n). (a) Find the recursion that MAXPRICE (n) satisfies. In other words, you should write MAXPRICE(n) in terms of MAXPRICE(n-1), MAXPRICE (n - 2), MAXPRICE (0). Fully justify your answer. (b) Identify the base case for your recursion in part (a) and find its corresponding value. Justify your answer. (c) Write the pseudo-code for the bottom-up DP algorithm to compute MAXPRICE(n). Find and justify the time complexity of your algorithm in the form of (.). Activate Windows Consider a rod of length n inches and an array of prices P[1...n], where P[i] denotes the price of any i inches long piece of rod. Now suppose we have to pay a cost of $1 per cut. Thus, for example, if we cut the rod into k pieces of lengths ni, n2,..., nk, this means that we made k - 1 cuts, which gives their final selling price as P[n] + + P[nk] (k 1). - Let MAXPRICE(n) denote the maximum selling price we can get this way among all possible options we have to make the cuts (note that one possible option is to make no cut and sell the whole rod of length n). (a) Find the recursion that MAXPRICE (n) satisfies. In other words, you should write MAXPRICE(n) in terms of MAXPRICE(n-1), MAXPRICE (n - 2), MAXPRICE (0). Fully justify your answer. (b) Identify the base case for your recursion in part (a) and find its corresponding value. Justify your answer. (c) Write the pseudo-code for the bottom-up DP algorithm to compute MAXPRICE(n). Find and justify the time complexity of your algorithm in the form of (.). Activate Windows

Answer rating: 100% (QA)

Lets address each part of this problem step by step a Recursion for MAXPRICEn MAXPRICEn represents t... View the full answer