State the rod cutting problem and write down the recurrence relation for finding the maximum revenue, r n , of a rod of length n. 5 marks b) Show that the rod cutting problem exhibits optimal substructure property 5 marks c) The following table shows the length and the corresponding prices for a particular kind of rod. Length / i 1 2 3 4 Price / pi 1 20 33 36 Using the table given above, determine whether the rod cutting problem exhibits greedy choice property. 5 marks d) Compute r 4 using dynamic programming