# Data Structures and Algorithms

## Workshop 3 - Minimum Spanning Trees

For the assignments which follow from this workshop, you are expected to produce a program which reads a description of a problem from a file, calculates the minimum spanning tree and prints out the tree and its cost.

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

#### File format

LinesContentFormat Notes
FromTo
11n%dNumber of nodes
2n+1labeli %sNode Label
n+2EOF labeli labelj cij%s %s %gEdge descriptor and weight

Notes:

• Fields are separated by spaces.
• The remainder of a line is to be ignored and may be used for comments.
• Costs are real numbers: you may assume costs are less than 106.

#### Submission

Follow the same submission procedure used for the previous assignments.

#### Dates

 Designs Checked and Signed Off 5pm, Thu 19th Sept Designs submitted by this deadline will be checked and returned by the following day. Assignment 3ADTs programmed and verified 5pm, Tue 8th Oct Assignment 4Full program verified Time complexity verified 5pm, Thu 24th Oct

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.