In class we have discussed the implementation of the union-find data structure, and also a fun use of the data structure – to build mazes. For this assignment you are to implement both of these!
You should implement the DisjointSets interface using union by size (total number of elements, referred to as weighted union in the slides) and path compression as described in in the book and in lecture. You should use an array implementation of the uptree structure as discussed in the book and in lecture. You may wish to use Weiss’s disjoint sets as a starting point, however notice that this code uses union by height and leaves off the checking of many error conditions. Your implementation of the DisjointSets interface should add in error checking and throw exceptions as described in the interface. Your implementation (named MyDisjSets.java) should also include a public constructor as follows:
/**
* Required constructor.
* @param numElements is number of
elements in the set.
*/
public MyDisjSets(int numElements);
Notes:
· Your union operation should be implemented using union by size (number of nodes in each set). Note that union throws an exception if either of its two parameters are not valid names of sets. Another way of implementing this would be to have union call find on each parameter that is passed in. While this is a reasonable way of implementing union, this is NOT what we are asking for in this assignment. For this assignment we ask that you throw an exception.
· Your find operation should use path compression.
· You should NOT use anything from the Java Collections for your DisjointSets implementation. This includes calls to methods in the Arrays class like copyOfRange.
· Efficiency: Your primary objective is to optimize your union and find operations. The DisjointSets interface includes several other methods that you need to implement. For example, getElements is not one of the standard operations for disjoint sets, but it turns out having a method like this is very useful in some cases - testing you code is one of those! So while you should try to implement all operations as efficiently as you can, do not sacrifice the efficiency of your union and find operations to improve the runtime of other operations.
Files you will need:
DisjointSets.java interface
Your implementation should be called MyDisjSets.java
Part II. Generate a maze (as described in
lecture and in Weiss).
For part II, you should generate a maze using the method based on disjoint sets discussed in lecture and in Section 8.7 of Weiss. Your maze should obey the constraints discussed in class – e.g. have only one solution, all cells should be reachable, only walls allowing cells to be reachable should be removed. The starting point of the maze should always be the upper left corner and the ending point should be the lower right corner.
Your program should take three parameters: maze height, maze width, and an output file name that the maze will be written to. If you are rusty on command line parameters or writing to files, you might look back at the implementation of Reverse.java in homework #1.
Your program should be in a class called MazeBuilder.java. For example, you should be able to call your program as follows:
java MazeBuilder 15 20 output.txt
to write a maze 15 cells high and 20 cells wide to a file called output.txt. For the code you turn in, you must use the following characters for walls in your maze: put a * at each corner, and use – for horizontal walls and | for vertical walls when they exist. (If you decide to go into the business of printing out mazes and selling them to your roommate and find that these characters do not print out nicely on paper, feel free to use other characters. HOWEVER, for ease of grading and full points, you must stick with *, -, and | for the code you submit. ) The following would be a legal maze of height 2 and width 5.
*-*-*-*-*-*
|
* *-* * *-*
| | |
*-*-*-*-*-*
Use of Java Collections: While we expect you to use your DisjointSets implementation in your solution, you do not necessarily need to use it to represent the sets of edges in the set E or in the final set Maze. For E and Maze only - feel free to use something simpler for this: an array, ArrayList or something else from the Java collections will be o.k. here. It is also fine to use the Java Random class in your solution.
Error Checking: For your maze generation program you should do error checking similar to the extent that is done in Reverse.java for homework #1. A maze dimension of 0 should be illegal. You may handle a maze of size 1 x 1 however you would like (as legal or illegal).
Part III.
Writeup Questions
1. For your DisjointSets implementation, what is the worst case running time of a single union operation?
2. For your DisjointSets implementation, what is the worst case running time of a single find operation?
3.
Please briefly discuss how you went about testing your
disjoint sets. Feel free to refer to your submitted test files.
4. If you worked with a partner, describe how you developed and tested your code. If you divided it into pieces, describe that. If you worked on everything together, describe the actual process used – how long you talked about what, how long and in what order you wrote and tested the code. Be sure to describe at least one good thing and one bad thing about the process of working together.
You should submit these files:
· MazeBuilder.java – the main routine in this class should create a maze and be callable as shown above.
· MyDisjSets.java - your implementation of DisjointSets.java
· Your test code for your DisjointSets implementation.
· ReadMe.txt – text file containing your answers to the writeup questions.
· maze10x15.txt - text file showing maze of height 10 and width 15.
· maze25x20.txt - text file showing maze of height 25 and width 20.
If you work
with a partner, only one partner needs to
submit the files electronically, be sure that both partners’ names are
listed in all files.