An n-foot tree has fallen down, and you wish to cut it into sections for sale. (a) How many ways are there of cutting it into pieces? (b) You wish to determine how many ways there are of cutting the tree into pieces of size 2, 3, and Write a generating function for this such that the coefficient of x n is the number of ways for size n. You do not need to give a formula for determining the coefficients.

Consider the tree problem again. (a) Suppose the price of a section of size m is p m . Write a recurrence relation for maximizing the amount of money you make. (b) Convert the above divide-and-conquer algorithm into a dynamic programming algorithm. Of course, you should do this with as little extra space as possible.