22C:21: Computer Science II: Data Structures

Problem Set 5. Posted 3/19. Due on 3/23.


Notes: Problem 1 is your homework and it is due by 5 pm on Friday, 3/23. Of the remaining two problems, one will be solved by your TA in the discussion section meetings on Thursday 3/22. The remaining problem will be your quiz; this will occur at the end of the discussion section meeting (on 3/22), you will have 20 minutes for the quiz and you are allowed to consult your notes and textbook.

  1. Let us use C(n, k) to denote the number of ways in which k objects can be chosen from a set of n objects. This quantity is usually read as "n choose k" and also called a binomial number. There are many recurrence relations that describe binomial numbers, the most famous of these is:

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

    1. Use this recurrence relation to design and implement a recursive function to compute C(n, k) for positive integers, n and k, where n is no smaller than k. Think carefully about the base cases you need for your implementation. Use the following function header:
      	int binomial(int n, int k)
      

    2. Even for fairly small values of n and k, the value of C(n, k) can be huge. Reimplement the above function allowing the returned value of C(n, k) to be arbitrarily large. Use the BigInteger class in java for this. Use your program to calculate the value of C(1000, 500) and report its value.

  2. Recall our discussion in class on the efficiency of the simple recursive function that calculated the nth Fibonacci number. We said that this implementation is extremely inefficient since it solves the same subproblems many, many times because it does not remember the subproblems that have already been solved.

    1. Implement the simple, recursive fibonacci function discussed in class. Use this function header:
      	int fibonacci(int n)
      
      Recall that this function returns the nth Fibonacci number. What is the largest value of n for which the function successfully computes a Fibonacci number in 15 minutes?
    2. To improve the efficiency of this implementation of fibonacci, declare an array called answers that is responsible for storing answers already computed. This could be a global variable, that is initialized to all zeros, with the exception of the first two slots. answers[0] and answers[1] will contain fibonacci(1) and fibonacci(2) respectively and therefore will both be initialized to one. In general, the kth Fibonacci number would be stored in answers[k-1] as soon as it is computed. We could then modify the function fibonacci so that it first checks answers[n-2] for fibonacci(n-1) and answers[n-3] for fibonacci(n-2) and makes recursive calls only if these values have not already been computed. Make this change to the function fibonacci. Does it give us the speedup we expect? Can you use this to calculate the 100th Fibonacci number? What about the 1000th Fibonacci number?

  3. Write a recursive function that takes an integer array and returns the second largest element in the array. If all elements in the array are identical, then let us agree that there is no second largest element. However, if the array contains at least two distinct elements, then it contains a second largest element. To make matters simple assume that no elements in the array are negative and have the array return -1 to indicate that the absence of a second largest element. Use the following function header:
    	int secondLargest(int[] list)
    

    Note: The above function header may not contain all the information needed to successfully control the recursion. So you might have to treat this function as a "wrapper" that calls recursiveSecondLargest with appropriate parameters.