Homework 3, Due Monday, 11/10 by 5:00 pm via ICON.

  1. Now that we have studied breadth-first traversal and depth-first traversal, I would like you to reorganize the myListGraph class to better incorporate these traversals into the class. Here is a list of things I want you to do:

    What to submit: A much improved myListGraph class defined in a file called myListGraph.java.

  2. Test the new myListGraph class as follows. Temporarily modify the shortestPath method to use the depth-first tree instead of the breadth-first tree. With this modification, the shortestPath method will no longer accurately return shortest paths. Run the program playLadders.java with this new version of the shortestPath method. Produce output similar to playLadders.out, but now you should see much longer path.

    What to submit: A new version of playLadders.out, obtained using depth-first search paths rather than shortest paths via breadth-first search.

  3. 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. Call the new function bigBinomial. Use the BigInteger class in java for this. Use your program to calculate the value of C(1000, 500) and report its value.

    What to submit: A program called BinomialTester.java that contains the implementation of the binomial function and the bigBinomial function along with a main method that appropriately calls these function to test its behavior.

  4. 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.

    What to submit: A program called SecondLargestTester.java that contains the implementation of the secondLargest function along with a main method that appropriately calls this function to test its behavior.