1. Let be a potential function that satises (Di) (D0) for all i 0, but (D0) 6= 0. Show that there exists another potential function (Di) such that (D0) = 0, (Di) 0 for all i 1, and the amortized cost (computed as actual cost plus change in potential) using is equal to the amortized cost using

2. In the vector solution to the problem of maintaining resizable arrays shown in class, we allocate a new array with twice the size as the old one when inserting into a full array. In this question, we use a dierent solution. The only dierence is that instead of doubling the array size, we allocate a new array with three times the size as the old one upon inserting into a full array. Suppose that no deletion is performed over the resizable array. With this simplication, perform amortized analysis to show that insertion still uses O(1) amortized time. Hint: One solution uses the potential method. Reviewing the potential function in the analysis shown in class may be helpful. This time you may wish to design a dierent potential function based on the same idea. (This does not imply that you are required to use potential method.)