CSCI 385 Spring 2019
Advanced Data Structures and Algorithms
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 112
CSCI 125
Others

Admin

Homework 3

Details

  1. Give a complete and clear solution to Exercise 5.34 from the textbook.
  2. Use Algoraph to implement an algorithm called MinimumSpanningTree that returns a minimum spanning tree of a weighted graph. Your algorithm should extend AbstractAlgorithm. The output should be the weight of the MST followed by a list of the edges of the MST in increasing order. E.g. something like:

    34;(0,5) (1,3) (2,3) (2,5) (3,4)  
    

    Important Note: The algorithm in the book omits an important detail: The if statement should actually be something like if(cost(z)>w(v,z) && contains(H,z)), the last part being something more like H.contains(z) in Java. This part is saying that the neighbor of v is still in the priority queue so that it has not already been added to the tree. If you are getting the incorrect weights on the puzzles Wikipedia, 7Dudes, and WebOfLies3, this is probably your error.

    By the way, to get the weight of the edge from vertex from to vertex to, use the following code

    Edge e = Edge.createEdge(from, to);
    int weight = puzzle.getWeightForEdge(e);
    

    Important Note: For some reason that I cannot remember, if the edge does not exist in the graph, getWeightForEdge will return 1. Thus, you need to know that e is actually an edge before you call that method since otherwise that method lies to you. If you implement Prim's algorithm correctly, this should not be a problem.

    Also, remember that when you change the cost of a vertex you need to be careful how you do it. The best way is to remove the vertex from the priority queue, change the cost, and then put it back. The slickest way to do all of this is to store the costs in a map (mapped from Vertex objects), use a PriorityQueue and implement a Comparator object that uses the costs in the map to do the comparing (You then create an instance of that object and pass it into the constructor of the priority queue). The other option is to have a new object that has both a Vertex and cost and store those in the priority queue, but that makes removing them to change the cost much more difficult.

    There is a test program on the AlgorithmTests page.

    Your algorithm should be as efficient as possible. You can use any resources you want to find the best algorithm to use, but you must write your own code.

    Hand in your Java file using Webhandin 385-HW3, making sure your Java class name clearly indicate which algorithm is which.

    Describe your algorithm (specifying the name if it is a well known algorithm) and gives a complete complexity analysis of the algorithm. Print out your analysis and bring it to class!.

    Outputting just the tree weight will get you up to 75% credit. Outputting the edges as well will earn you up to 87.5%. Outputting the edges in the specified order (each edge has the vertices in increasing order and the list is also presented in increasing order) will earn you up to 100%.