Homework 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.

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

    The programming part of this homework has two parts:

    • Part-1: Implement Kruskal's algorithm in Kruskal.java.
    • Part-2: Solve a problem using Kruskal's algorithm in CableSolver.java.
    Let's look at these one by one.

    Part-1:Kruskal's Algorithm
    In this part, you will use Kruskal's algorithm (with an adjacency matrix representation) to compute the minimum-spanning tree weight of a given graph.

    • Use the pseudocode 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.
    • Use this properties file for testing your adjacency matrix implementation.

    Part-2: Solve the cable-laying problem.

    • In this problem, we are given a collection of (x,y) points representing geographical locations. The goal is to connect them via cables so that any location can communicate with any other, going via other locations as needed.
    • One approach is to simply lay a straight-line cable from every location to every other. We'll call this all-to-all.
    • A lower-cost approach is to use a minimum spanning tree (MST). Thus, if location A wishes to communicate with B, and there's no direct cable from A to B, then A can communicate via some neighbor C in the MST (which means a cable between A and C), and C can use one of its cables etc until communication is established with B. This creates a path from A to B.
    • Your goal is to calculate the total cable cost of each, and to report the savings obtained by using a minimum spanning tree.
    • For this purpose you can use TestCable.java, which will call your code in CableSolver.java. You will also need UniformRandom.java.

Submission: