Due: Wednesday 7 June, 6:00 pm
For this project, you are required to implement an algorithm for finding a Minimum Spanning Tree.
Task
Imagine that, as Chief Engineer for the Aztec Empire, you are in charge of laying a series of stepping stones to connect the floating gardens or "chinampas" of a city to be built on a newly settled marsh. The stepping stones must be laid in a configuration which uses as few stones as possible, but allows the people to walk from any island to any other island (if necessary, passing through other islands along the way).
The input to your program (from standard input) will be a map
in which the islands are represented by groups of stars '*'
in a sea of blank spaces, framed by a rectangular border of
straight lines and corners.
An "island" is a group of one or more stars connected
either horizontally, vertically or diagonally.
For example, a map with three islands might look like this:
+-------------------------+ | | | ** | | * ** | | ** | | ** | | | | | | *** | | * | | | +-------------------------+Your program should output a new map which is identical to the original map except that some of the blank spaces are replaced by dots
'.'
representing the stepping stones.
The stones (dots) must be laid out in "causeways" joining one
island to another.
You should assume it is possible to step from one
stone to another either horizontally, vertically or
diagonally.
For example, given the 12-line input above,
your program might produce the following output:
+-------------------------+ | | | ** | | * ** | | ** . | | ** . | | ...... . | | . . | | *** | | * | | | +-------------------------+Note that the answer is not unique: another possible output would be this:
+-------------------------+ | | | ** | | * ** | | ** . | | **..... . | | . . | | . . | | *** | | * | | | +-------------------------+Number of Stones
It is recommended to use a Minimum Spanning Tree algorithm, which minimizes the length of the causeways between successive islands but does not consider overlaps between causeways. In some cases, it might be possible to improve on this, if your algorithm is very clever. For example, with the input shown above, you could actually connect the islands with ten stones instead of eleven, if the two causeways share a stone like this:
+-------------------------+ | | | ** | | * ** | | ** . | | **..... . | | . . | | . | | *** | | * | | | +-------------------------+For assessment purposes, your program will receive full marks provided all the islands are connected and the number of stones is less than or equal to that of the MST algorithm (and may receive up to 2 bonus marks if it does the job with strictly fewer stones than the MST algorithm).
Tools for generating sample inputs and checking the validity of your output will be provided in the tools directory.
Efficiency
Your program will be tested on a variety of inputs of different sizes. You should take note of the efficiency issues discussed in chapter 13 of the textbook, and also the functionality test below.
Once submissions are open, you should submit by typing
give cs2011 hw3 *.java
You can submit as many times as you like - later submissions will overwrite earlier ones.
The submission deadline is Wednesday 7 June, 6:00 pm.
15% penalty will be applied to the (maximum) mark
for every 24 hours late after the deadline.
Additional information may be found in the FAQ and will be considered as part of the specification for the project. The first hints are already there; read them soon!
If you have a question that has not already been answered on the FAQ,
you can email it to cs2011.hw3@cse.unsw.edu.au
Assessment
The assignment will be marked out of 10; of this 2 is for style and 8 for performance. There will be a maximum of 2 bonus marks for programs that do better than the straightforward MST; we refer to such solutions as optimized. Functionality will be assessed in the first instance. This includes a check that programs are reasonably efficient, and therefore any that use a "generate and test" enumeration to find good paths will fail a cpu time limit. Programs failing most of the auto-testing will be examined by a human and may pick up a few marks for style, provided they are clearly written.
Programs that generate compilation errors will receive a very low mark, no matter what other virtues they may have. In general, a program that attempts a substantial part of the job but does that part correctly will receive more marks than one attempting to do the entire job but with many errors.
We will publish the names of the authors of the 10 best optimized submissions, ordered by rank, in the course web page after the marking is complete. In accordance with UNSW privacy provisions, students who intend to submit optimized programs but do not wish to have their names published, should email cs2011.hw3@cse.unsw.edu.au with the subject heading "Do not publish" and inform us so. Should their programs rank in the top 10, their names will be replaced by the place holder anonymous.
Plagiarism Policy
Group submissions will not be allowed. Your program must be entirely your own work. Plagiarism detection software will be used to compare all submissions pairwise. These checks may be run after the automarking and release of marks, so the released marks are not necessarily final.
DO NOT COPY FROM OTHERS; DO NOT ALLOW ANYONE TO SEE YOUR CODE
Please refer to the Yellow Form, or to section on Originality of Assignment Submissions in the Unix Pri mer, if you require further clarification on this matter.
Good luck!