Given a rope of length n meters, cut the rope in different parts of integer lengths...

   

Transcribed Image Text:

Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts. You must make at least one cut. Assume that the length of rope is more than 2 meters. Examples: Input: rope length is 4 Output: 2*2 = 4 Input: rope length is 5 Output: 2*3 = 6 (n = 4) (Maximum obtainable product is 2*2) (n = 5) (Maximum obtainable product is 2*3) Input: rope length is 10 (n=10) Output: 3*3*4= 36 (Maximum obtainable product is 3*3*4) a) Design the recursive sub-problem condition(s) b) Use your solution in (a) to solve the problem of a rope length input equals 10 (n = 10). You have to show the complete solution of the DP steps either by top down or bottom-up approach. c) What is the running time of your algorithm? Note: your solution must not run in exponential time. Given a rope of length n meters, cut the rope in different parts of integer lengths in a way that maximizes product of lengths of all parts. You must make at least one cut. Assume that the length of rope is more than 2 meters. Examples: Input: rope length is 4 Output: 2*2 = 4 Input: rope length is 5 Output: 2*3 = 6 (n = 4) (Maximum obtainable product is 2*2) (n = 5) (Maximum obtainable product is 2*3) Input: rope length is 10 (n=10) Output: 3*3*4= 36 (Maximum obtainable product is 3*3*4) a) Design the recursive sub-problem condition(s) b) Use your solution in (a) to solve the problem of a rope length input equals 10 (n = 10). You have to show the complete solution of the DP steps either by top down or bottom-up approach. c) What is the running time of your algorithm? Note: your solution must not run in exponential time.