22C:21 Computer Science II: Data Structures: Homework 3

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

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:
- Add the depthFirstTraversal method to this class. It is fine if the version of depthFirstTraversal that you add to the class is recursive and you should feel free to use the code depthFirstSearch that I posted.
- Make new data members
```
		int[] BFTParent;  // stores the parent indices for a BFT tree
		int[] distances;  // stores shortest path distances from source
		String BFTSource; // source of the most recent BFT
		boolean BFTFresh; // whether the graph has changed since the most recent BFT
		int[] DFTParent;  // stores parent indices for a DFT tree
		String DFTSource; // source of the most recent DFT
		boolean DFTFresh; // whether the graph has changed since the most recent DFT
```
  The idea behind this is that both BFT and DFT will update relevant class data members as part of their task and will not return anything. For example, the breadthFirstTraversal method will update the data members BFTParent, distances, BFTSource, and BFTFresh. The data members BFTSource, and BFTFresh can be used to avoid redundant breadth-first traversals. Specifically, BFTFresh should be true as long as the graph has not changed sine the last call to the breadth-first traversal method. Then, at the beginning of a breadth-first traversal call from source s, we check is BFTSource is s and if BFTFresh is true. If so, there is no need to do the breadth-first traversal because the most recent call to breadth-first traversal did use source s and this information is fresh. depthFirstTraversal updates relevant data members in a similar manner.
- Update all the member functions of the class to appropriately deal with the new data members. This includes the constructors, the methods that change the graph, and of course the methods relating to breadth-first traversal and depth-first traversal.
What to submit: A much improved myListGraph class defined in a file called myListGraph.java.
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.
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.
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.