Data Structures and Algorithms

Workshop 3 - Minimum Spanning Trees

Rules

1. Nodes are labelled with an arbitrary string. In the present problem, this string will not be longer than 100 characters. However, it would be a mistake to submit a program in which you cannot trivially change this requirement!
2. Node labels have no spaces in them.
3. For simplicity, edges have the same cost in both directions, ie the cost of edge "abc"->"pqr" is the same as that for "pqr"->"abc". A program which can be trivially extended to handle asymmetric costs will attract a small bonus. You should indicate in your report the changes that are necessary.
4. All edge costs are positive.
5. Unspecified edges are assumed to be impossible. (Your program should use a suitable representation!)
6. You may print out the resulting MST in any intelligible format, but your report should obviously explain the format.

Procedure

1. Find a partner and decide how to split the work for this assignment between yourself and your colleague.

2. In the tutorial session preceding the lab session, start the design of the ADTs that you will need for this assignment. By now, you should interpret "design" as meaning "design and formally specify".

3. Get the full design checked off by the lecturer or tutor before proceeding to implement your solution.

   Note that, for graphs, there are a number of ways of implementing the graph structure. You should understand by now that the specification and the implementation details are quite separate. You can derive a specification by looking at the requirements of the problem which specify abstract operations that will be needed.

4. For assignment 3,
   1. Formally test each ADT used by performing an equivalence class analysis on it and generating a program (or programs) to check each class.

      Note that while you may have constructed the full MST program at this point, it is not required for this submission.

5. For assignment 4,
   1. Submit a program which will read the test file and find and print out the MST.
   2. Design (or automatically generate) additional test sets to formally test the whole program.
   3. Confirm that the running time of the whole algorithm is as expected.
      Running time of the algorithm does not include the time to load the data from the test file.

   For 2 and 3, you may generate the test data within the test programs themselves, ie it is not necessary to read data from a file. A script which automatically runs the test program with a set of test files is also acceptable.

6. Submissions
   1. Both submissions should be accompanied by an appropriate report.
   2. You should make one submission with your partner. Either one of you can make the actual submission: just make sure that you have collected all the relevant files into the submission directory.
   3. Your report (and the program file prologues) should clearly identify the contributions of each partner to the joint submission.

A sample of the format may be found in mst.test.

Submission

Dates

Proceeding to the coding stage without having your design checked is not likely to be productive. For a quick review and sign-off, you may bring your design to me any time before the deadline: otherwise, submit it using the normal submission procedure as the "3des" assignment. The submission procedure automatically sends me an email message when you have submitted - I will attempt to review all designs within 24 hours and will email you my comments.