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.
- Nodes are labelled with an arbitrary string.
In the present problem, this string will not be longer than
However, it would be a mistake to submit a program in which
you cannot trivially change this requirement!
- Node labels have no spaces in them.
- For simplicity, edges have the same cost in both
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.
- All edge costs are positive.
- Unspecified edges are assumed to be impossible.
(Your program should use a suitable representation!)
- You may print out the resulting MST in any intelligible
format, but your report should obviously explain the format.
- Find a partner and decide how to split
the work for this assignment between yourself and your
- 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
- 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.
- For assignment 3,
- 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.
- For assignment 4,
- Submit a program which will read the test file and
find and print out the MST.
- Design (or automatically generate) additional test sets
to formally test the whole program.
- 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.
- Both submissions should be accompanied by an
- 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.
- Your report (and the program file prologues) should clearly
identify the contributions of each partner to the joint submission.
|1||1||n||%d||Number of nodes|
||labeli labelj cij||%s %s %g||Edge descriptor and weight|
- 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.
A sample of the format may be found in
Follow the same
used for the previous assignments.
|Designs Checked and|
|5pm, Thu 19th Sept|
Designs submitted by this deadline will be
and returned by the following day.
ADTs programmed and verified
|5pm, Tue 8th Oct|
Full 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.