**What tools can you provide ?**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.**What is a good way to begin thinking about the problem?**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.

**In the answer above isn't there a some choice of which star to choose for the (x,y) for an island?**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.

**Can you provide any code to get us started ?**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.**Can you outline our main implementation obligations?**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.**Will there be a limit on the size of the map ?**There will be a maximum of

**128**rows and**128**columns.**What is the main file and how many files can I submit?**You must submit one main file named

**hw3.java**and up to five (5) optional helper java files.

**Will there be always correct input, so I do not have to provide error handling ?**Yes, you can assume that all input has the correct format.

**Can you say more about efficiency? Will there be a limit on the number of islands, or the size of each island?**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).

**I think I have implemented the Kruskal's MST algorithm correctly because I followed the exact algorithm described in the text but for some reason my output's number of stones is always 5-20 more than the target's on large maps.**We will allow your version to place up to 10% more stones than ours. Do not use absolute numbers, look at percentages.

**Also what is the efficiency limit?**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.

**How many CPU seconds should we think is an upper bound on acceptable efficiency even when we choose to optimize?**10 seconds for most inputs, but no more than a couple more seconds for fancy optimizations or complicated inputs.

**Do I have to compute all inter-island distances at the beginning?**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.