Homework 3: Due 10/14, 2005

1. A distance-2 neighbor of a vertex x is any vertex y that is neighbor of x or that is a neighbor of a neighbor of x. Write a method of the myGraph class called numDistance2Neighbors that takes a vertex and returns the number of distance-2 neighbors it has.

   For example, in the graph below vertex a has 4 distance-2 neighbors, vertices b and c have 3 distance-2 neighbors each, and vertices d and e have 2 distance-2 neighbors each.

   

   What to submit: A printout of just the function numDistance2Neighbors.

2. Consider the graph given below. For this problem, you need to show the performance of depth first traversal, starting at vertex A. Assume that the neighbors of each vertex are examined in alphabetical order. In particular, I want you to show the following information.
   
   • The order in which vertices in the graph are discovered by depth first traversal. You can show this by simply listing the vertices in the order in which they are discovered.
   • The depth first traversal tree.
   Then show the same two pieces of information for depth first traversal starting at vertex B.
   

   What to submit: For each of the two depth first traversals, the list of vertices of the graph in the order in which they are visited and a picture of the depth first traversal tree. There is no need to submit any code for this problem.

3. For this problem, suppose that Darth Vader has tampered with your implementation of the stack data structure. When you perform a peek or a pop operation, you don't get the top most element from the stack; instead you get the element just below the top most element. Of course, if the stack has only one element, then that is what you get when you perform a peek or a pop.

   Using the stack so maliciously tampered by Lord Vader, perform depth first traversal on the graph shown in Problem 2, starting first from vertex A and then starting from vertex B. Again, for each traversal, show (i) the order in which vertices are discovered by depth first traversal and (ii) the depth first traversal tree.
   

   What to submit: For each of the two depth first traversals, the list of vertices of the graph in the order in which they are visited and a picture of the depth first traversal tree. There is no need to submit any code for this problem.

4. In class we discussed how picking a random pivot to perform partitioning in quick sort is one way to improve the running time of quick sort. Start with Lafore's quickSort1.java and make a small modification to it so that a randomly chosen element from theArray[left..right] is the pivot, rather than the right most element.
   

   What to submit: A printout of the modified program quickSort1.java with your modifications highlighted.