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.
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.
There are a number of well known identities for binomial coefficients. Here are two:
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.
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.