Help with 15.1-3 only please!

Recursive top-down implementation The following procedure implements the com on implicit in equation (15.2) in a straightforward, top-down, recursive manner. CUT-RoD(p,n) 1 if n return 0 3 4 for to n max (a, plil CUT-RoD(p, 6 return Procedure CUT-RoD takes as input an array pl1..nl of prices and an integer n and it returns the maximum revenue possible for a rod of length n. If n 0, no revenue is possible, and so CUT-ROD returns 0 in line 2. Line 3 initializes the maximum revenue q to -oo, so that the for loop in lines 4 5 correctly computes maxi Sisn (pi +CUT-RoD(p, n -i)); line 6 then returns this value. A simple nduction on n proves that this answer is equal to the desired answer r, using equation (15.2). If you were to code upCUT-RoDin your favorite programming language and run it on your computer, you would find that once the input size becomes moderately large, your program would take a long time to run. Forn 40, you would find that your program takes at least several minutes, and most likely more than an hour. In fact, you would find that each time you increase n by 1 your program's running time would approximately double Why is CUT-ROD so inefficient? The problem is that CUT ROD calls itself recursively over and over again with the same parameter values, it solves the same subproblems repeatedly. Figure 15.3 illustrates what happens for n CUT-RoD(p,n) calls CUT-RoD(p,n i) for i 1,2 n. Equivalently, CUT-RoD(p, n) calls CUT-RoD(p, j) for each 0,1 When this process unfolds recursively, the amount of work done, as a function of n, grows explosively. To analyze the running time of CuT-RoD, let T(n) denote the total number of calls made to CUT-ROD when called with its second parameter equal to n. This expression equals the number of nodes in a subtree whose root is labeled n in the recursion tree. The count includes the initial call at its root. Thus, TO) 31 and