Given a rod of length n inches and an array which contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 40 (by cutting the rod in 8 pieces).

 

Length	1	2	3	4	5	6	7	8
Price	5	6	8	11	15	17	19	22

 

1. Design an algorithm and write a pseudocode to solve the above problem using dynamic programming.
2. Calculate the time complexity of your algorithm. Show step by step calculation.
3. Implement Rod Cutting algorithm you designed in part A using python programming language. Take the above array as an input to your program.
4. A detailed report discussing your implementation along with results of running the code against the examples given (screenshots must be included). A detailed readme file that should explain how to run the code should be submitted in a separate file. Submit all your implemented code in separate files.