Exercise 4

 

  1. Pen-and-paper (PDF) exercises:
    1. In each of the graph examples below, your graph should have at least 6 nodes.
      1. Draw an example of a graph such that if you remove any one edge, the resulting graph remains connected.
      2. Draw an example of a graph such that if you remove any edge, the resulting graph is not connected.
      3. Draw an example of a graph such that only one edge in the graph has the property that if you remove it, the resulting graph will not be connected.

    2. For the graph below, show the steps in executing Kruskal's algorithm and Prim's algorithm. Draw the graph with the MST edges identified at each step.

    3. This question is about whether a graph can have multiple possible solutions to the minimum spanning tree problem.
      • Draw an example of a 4-node graph that has two different minimum spanning trees. That is, two spanning trees that are different (there's at least one edge in one that's not in the other), but they have the same total weight AND both are minimum spanning trees. Confirm that they are minimum spanning trees by showing how they could arise from running Prim's algorithm starting at different nodes.
      • Suppose a graph has unique edge weights: no two edges have the same weight. Argue that in this case you can't have two different minimum spanning trees. Start by assuming there are two solutions and show that it leads to a contradiction.

    Note: Credit will not be given only for answers - show all your work: your reasoning, steps you took to get your answer etc.

  2. [Optional: for Bonus points] This part of the exercise is optional. The extra points earned here will be applied in some way to the previous exercise/assignment on which you have the lowest score amongst those submitted thus far. Thus, for example, if your submission of Exercise 2 has the lowest score amongst all your submissions up to and including this one, we will add the bonus points (if this part is complete) earned here to your total for Exercise 2, without exceeding 85% of the total for that exercise. Another way to think about it: if you received what looked to be a C or lower in a previous exercise/assignment, this is a way to bump that grade up.

    In this part, you will use Kruskal's algorithm (with adjacency matrices) to estimate the minimum-spanning tree weight of a randomly-created set of points. The points will be n random points in the unit square.

    • Consider a set of random points in the plane. For example, suppose these were pegs nailed to a board. Suppose you had to connect these pegs with the least amount amount of string. Note that this is just the minimum spanning tree problem. (You need to think about this for a few minutes). The goal is to compute the weight of the minimum spanning tree for a random set of points. Here, you can assume an "edge" between each pair of points with the distance between as the weight.
    • How do you generate n random points in the unit square? And just what is the unit square?
      The unit square is the square with one corner at the origin (0,0) and opposite corner at (1,1). To generate a point randomly, we can use UniformRandom.uniform() to generate a value randomly between 0 and 1 for the X value, and call it once again for the Y value. So, to generate n such X and Y values, you can use this code: 
          for (int i=0; i < n; i++)
      X[i] = UniformRandom.uniform();
    for (int i=0; i < n; i++)
      Y[i] = UniformRandom.uniform();
    • Modify the code given to you in Module 8 for Kruskal's algorithm. Read through this carefully.
    • Name your class Kruskal.java.
    • Your class will need to implement the SpanningTreeAlgorithm interface. In particular, you will need to provide implementations for these methods: initialize(), minimumSpanningTree(double[][] adjMatrix) and getTreeWeight().
    • The classes and interfaces involved in this exercise are:
      The Algorithm interface
      The SpanningTreeAlgorithm interface
    • Also, Kruskal's algorithm will need an implementation of Union-Find. For this purpose, you should create a class called UnionFindInt. You can intuit what this class needs to have from its use in the Module 8 examples.
    • Use the test environment to test your minimum spanning tree algorithm. However, it does not compute the average tree weight. Simply submit your hardcopy and evidence that your code worked for the average-weight problem.
    • Use this properties file for testing your adjacency matrix implementation.
    • Also submit the output for the following experiments in your jar file (as PDFs):
      • Run your algorithm once with n=10 points. For this particular case, draw by hand the actual points on a unit square (draw the square to be at least 3 inches per side), labeling the points 0, ... n-1, and indicate which edges were in the spanning tree your algorithm computed.
      • Plot a graph of the average MST weight vs n (the number of points) for n=10, 20, ..., 100. To get the data point for n=10 points, you should take an average of a 100 MSTs.

    Next, use your implementation for the following:

    • Suppose we have n random points, and suppose a minimum-spanning tree has already been computed.
    • We now want a second MST that does not use any of the edges of the first one.
    • Clearly, the second MST is not going to have a weight that is as low as the first MST's weight.
    • Your goal is to evaluate "how much worse" (as a percentage increase) the second MST is over the first one. Do this by calculating an average over lots of random points. Thus
      • For n=10, generate a hundred sets of 10 random points. For each set, compute the two MSTs, and the weight of the second one Compute the average over the 100 sets.
      • Repeat for n=20.
      • Do this for n=30, .., 100, and plot a graph that will show both MST weights.

Submission: