Three executables have now been provided in the
tools directory:
hw3gen, hw3 and hw3check.
hw3gen can be used to generate sample data.
The number of rows and columns in the map can be specified as
command-line arguments.
Note that hw3gen can be run multiple times,
and will generate a different map each time.
hw3 is a compiled C version of the assignment.
Note that your program need not produce exactly
the same output as hw3.
Instead, hw3check
has been provided to test the validity of your output.
hw3check takes the original map from a specified file
and reads the output of your program from standard input.
Here is an example of how these programs might be used:
$ hw3gen 20 30 > s1.in $ hw3 < s1.in > s1.tgt $ hw3check s1.in < s1.tgt Islands connected with 17 dots. (target 17) $ java hw3 < s1.in > s1.out $ hw3check s1.in < s1.out Islands connected with 17 dots. (target 17)(of course the exact number of dots will depend on the map that was generated.)
The source code for hw3gen.c
has also been provided.
Think of the number of stepping stones (dots) as the distance. A cluster of stars (an island) does not need dots between them, hence may be considered to be a single vertex. Then consider the simplest case of two clusters on the positive X-Y quadrant, one with coordinate (x1,y1) and the other (x2,y2). There is a minimum distance between them equal to the minimum number of dots. Once you have figured out the formula, it should also give you an algorithm for the distance. Then you can pick any MST algorithm for the many cluster case by using these distances as keys in the prioriy queue needed.
Yes. There will be small variations in the total MST weight as the result of this. We will allow for such variations in the marking.
It is a good idea to transfer the map into an
array of char.
Slide 6 of the 01_Programming
slides explains how to allocate space row-by-row
for a two-dimensional array.
Only the broad outlines, as you have design responsibilities
that are part of the learning experience in this course. Outlines:
(i) the I-O to convert the ascii map into a nice representation for
calulating the distances (already implied above in several places) (ii)
the priority queue (do your own, not the default Java one), suggest
a heap implementation (iii) the reverse I-O to convert the representation
back to ascii map (iv) any other nice features you want.
If you decide to optimize, there are no hints. Use your ingenuity.
In either case it will be judicious to watch CPU usage as we will later
tell you what are reasonable limits for efficiency.
There will be a maximum of 128 rows and 128 columns.
You must submit one main file named hw3.java and up to five (5)
optional helper java files.
Yes, you can assume that all input has the correct format.
The map will be no larger than 128 by 128. You should, however, be able to handle any number of islands, and islands of any size, by using expandable data structures (for example, a Vector of islands and each island is a linked list of some kind).
We will allow your version to place up to 10% more stones than ours. Do not use absolute numbers, look at percentages.
There will be two ways we check this. One is your code. For instance, if you do not use a priority queue but do a primitive sort each time, marks will be deducted. And simply maintaining a queue and searching linearly in it each time to re-order it is NOT a proper implementation of a priority queue. (People should NOT take these remarks as invitations to start quibbling on what other bad designs constitute silly inefficiencies. We will ignore quibbles.) The other way is CPU time. Although the particular server that is used, and its load then, can somewhat affect that, we will allow your program a generous increment of the CPU time of our program, particularly if you are trying to optimize.
10 seconds for most inputs, but no more than a couple more seconds for fancy optimizations or complicated inputs.
Depends. If you use Kruskal, yes. If you use Prim-Jarnik many can be delayed to later. In any case, even for a 20 island input the number of initilization computations is at most 400 if you use the formula, and it is fast.