1. Recall that xy = (xy/2)2 if y is even. Use this to write a function that computes xy, assuming that y is a power of 2. Use the principle of divide-and-conquer to perform the minimum number of multiplications.
2. Write a function to compute the following recurrence using dynamic programming. PN = PN-1 + 2PN-2, with P1 = P0 = 1.
3. The following refer to breadth-first traversals of graphs and trees. a. What is the purpose of the queue in breadth-first traversal? b. Suppose you had a function call displayAtDepthN, which when given a tree and depth would display only the nodes at that depth. Explain how this could be used to give a breadth-first traversal of the tree, and why it would not be as efficient as one using a queue.
4. Short programming assignment. Write a function that takes a tree (a link to the root) as the parameter. The tree's item type is int. The function should return the number of leaves in the tree.