Problem Set 7. Posted 3/17

Notes: Of the three problems given below, one will be solved by the TAs in next week's discussion section, you will have to solve one in class, and the remaining problem is due in the lecture on Friday, 3/24.

1. Consider the methods in the myGraph class. Assume that by using an appropriate data structure, we are able to implement the function getIndex in O(1) time. Write down the worst running time for each of the methods addVertex, deleteVertex, addEdge, deleteEdge, and getNeighbors. Express your answer in Big-Oh notation and as a function of n, the number of vertices in the graph and m, the number of edges in the graph. For simplicity, assume that there is no need to resize the data structures during any of these methods.

   Now imagine that the adjacency matrix implementation of the myGraph class is replaced by the adjacency list representation. Answer the above question for this new implemention.

   Finally, assume that each vertex in the graph has at most 10 neighbors. Redo your calculations for the adjacency matrix representation and for the adjacency list representation. Note that now your answers will be functions of n alone.

2. Let n and k be positive integers such that n >= k. The number of ways of choosing k objects out of n, is denoted by C(n, k). C(n, k) is called a binomial coefficient and is sometimes read as "n choose k." For example, two objects can be chosen from the set {1, 2, 3, 4} as follows: {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, and {3, 4}. Thus C(4, 2) is 6.

   There are a number of well known identities for binomial coefficients. Here are two:

   1. C(n, k) = C(n-1, k) + C(n-1, k-1).

   2. C(n, k) = C(n, k-1) * (n - (k-1))/k.

   Implement two recursive functions to compute the binomial coefficient C(n, k ), given positive integers n and k, n >= k. Use the first identity for the first implementation and the second identity for the second implementation. I have deliberately not provided any base cases for these identities. Make sure that you provide appropriate base cases for your recursive implementation of these identities.

3. Implement the recursive algorithm for the knapsack problem described on pages 305-306 in your textbook. Use the following function header:

   	int[] knapSack(int[] items, int target)
   

   The int array items contains the weights of the given items. The int parameter target gives the target weight permitted in the knapsack. The function should return an array of item weights that fit exactly in the given knapsack.

   It is quite possible that you may need additional parameters just to control the recursion. In that case, use the above function header for a "wrapper" function and define a function called recursiveKnapSack.