Programming question for Homework 5

Part A

Implement a Java method that computes a minimum spanning tree of a connected undirected weighted graph. In particular, you should implement a version of Kruskal's MST algorithm that differs from the one described on pages 568-570 of your textbook as follows: instead of sorting the whole list of edges at the beginning, it initially arranges all edges in a priority heap, where edges of smaller weight have higher priorities. Whenever the algorithm needs to get an edge with the smallest weight among the remaining edges, it just performs an extractTop() operation on the heap.

Part B

Write a Java method that implements the depth-first search algorithm (described on pages 540-547 of your textbook). The input graph may be directed or undirected, and fully connected or not fully connected. Your depth-first search algorithm should list the nodes of the input graph in two possible ways, depending on a given input parameter: (1) in order of increasing discovery time (PRE_ORDER) or (2) in order of increasing finishing time (POST_ORDER). 

Part C

Implement a Java method for computing a 2-approximate solution to the Traveling Salesman Problem (TSP). In particular, the algorithm you should implement is very similar to the one described on pages 1028-1031 of the textbook, but instead of Prim's algorithm for computing the minimum spanning tree of the graph, you should use your algorithm from Part A. You can assume that the input graph is fully connected and satisfies the triangular inequality.

To implement the methods described in parts A, B, and C you will have to use classes that you previously implemented in the programming part of the first four assignments (Assignment 1&2, Assignment 3, Assignment 4). You can use your own implementations, or, if you are not sure that your code works correctly, you can use the binary files of these classes found here.

For more details, including the exact specification of the methods that you should implement, see the starter code. All of your work must be done inside the Mst, GraphTraversal, and DeltaTSP classes, where indicated by comments that start with: "// TODO:". You may also add appropriate instance variables or helper methods.

Submission Instructions:

  1. Submit your code using the "submit" mechanism on fissure (by 5:30pm on Thursday, April 5). Use the following command from the directory containing your solution:
    submit -N PGM5 cscb63s Mst.java GraphTraversal.java DeltaTSP.java
    The command "man submit" contains general instructions for submitting your code electronically.

  2. Submit only three .Java file: Mst.java, GraphTraversal.java and DeltaTSP.java (after you have implemented the missing parts) to the directory called PGM5. All the code that you implement should be inside those three files.

  3. Do not submit any other files, and in particular, do not submit any class files. If you do, we will delete them before we compile your code.

  4. Do not submit any printout of the code.

  5. Do not rename the files, or any of the methods and variables found in our starter code.

  6. Fill in your name, student number and login name in the comment at the top of the Mst.java file. If you have a partner, you should also fill in the corresponding information about your partner.

  7. We will test your code using our own tester code. The tester that we provide is very basic, running it successfully does not guarantee that your code is correct or will pass our marking tester routine. You are encouraged to derive your own  test cases.

  8. Your code must compile and run on the standard Unix/Linux system of your campus (cdf/fissure/cslinux). Test it there! Programs that do not compile and run get 0 marks.