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 DFTThe 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.
What to submit: A much improved myListGraph class defined in a file called myListGraph.java.
What to submit: A new version of playLadders.out, obtained using depth-first search paths rather than shortest paths via breadth-first search.
C(n, k) = C(n-1, k-1) + C(n-1, k)
int binomial(int n, int k)
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.
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.