
A distance2 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 distance2 neighbors it has.
For example, in the graph below vertex a has 4 distance2 neighbors,
vertices b and c have 3 distance2 neighbors each,
and vertices d and e have 2 distance2 neighbors each.
What to submit: A printout of just the function
numDistance2Neighbors.
Solution: Here is the
code for this problem.

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.
Solution: Here is information pertaining to depth first traversal
starting at A.
 Vertices in the order in which they are discovered:
A C D B F E I G H
 Depth first traversal tree:
Here is information pertaining to depth first traversal
starting at B.
 Vertices in the order in which they are discovered:
B D C A G H E I F
 Depth first traversal tree:

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.
Solution: Here is information pertaining to depth first traversal
starting at A.
 Vertices in the order in which they are discovered:
A C G D H B E F
 Depth first traversal tree:
Here is information pertaining to depth first traversal
starting at B.
 Vertices in the order in which they are discovered:
B D F C E A G H I
 Depth first traversal tree:

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.
Solution: Here is a
version of quick sort that picks a pivot element, uniformly at random, from
the current array.