CSE 373 Data Structures 12au, Homework 4

Partner selection due: 11pm Wednesday, 10/31/2012 at the latest - send email to Tanvir.

Electronic Turn-in due: 11pm Thursday, 11/08/2012.

For this assignment, (if you wish) you may work with one partner.  You may be interested in trying pair programming.  Pair programming is a technique that is a part of Extreme Programming approaches used in some software companies.  Here are a few references on pair programming:  [as part of Extreme programming (XP)] [pair programming in Computer Science courses].  Note: You are not required to work in pairs – working individually is fine.

If you plan on working pairs: one partner MUST send email containing the names and email addresses of both partners to Tanvir by 11pm Wednesday October 31st at the latest.

Programming

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!

Part I. Implement a union-find data structure.

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 the total number of elements, each element is initially in its own 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.

·         There is no requirement on the order that elements should be listed for printSet or getElements.  For printSet, elements should be printed with curly braces on each end, and with individual elements separated by comas and spaces as follows: {52, 17, 12, 34}.

Use of Java Collections in MyDisjointSets: You should NOT use anything from the Java Collections for your DisjointSets implementation.  Unlike in previous assignments, this means you also should NOT use calls to methods in the Arrays class like copyOf.  You also should not use toString (you need to write out the code for printSet yourself). It is fine to use the length field of an array.

Efficiency of MyDisjointSets: 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

InvalidSetNameException.java

InvalidElementException.java

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 from the command line 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 (running your code from Eclipse will require you to set program arguments as “15 20 output.txt” similar to how you did for Reverse.java in homework 1).  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 in MazeBuilder: 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 - 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. In general for your maze generation program, it is o.k. to use things from Java collections.  Just be sure you: a) use your implementation of DisjointSets in your solution and b) don’t use Java collections in your DisjointSets implementation.

 

Error Checking in MazeBuilder: 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). We suggest you look at Reverse and see what it does - you can even borrow code from it. Be sure you check for these things: a) Check that the correct number of parameters have been passed and if not, print a message to the user indicating the correct way to use the program and exit. b) If the file name given could not be opened or written to, print the user a message and exit. c) Check that two integer values have been passed for the maze dimensions - you can do this using parseInt and checking for NumberFormatException as is done in Reverse. You should also check that a dimension of zero has not been passed in. In all of these cases you should print an informative message to the user and exit. We won't require that a specific exception be raised for any of these cases, but the code for Reverse should serve as a good starting point for you. We will expect your code to recognize the situations listed above, print out an informative message and exit. 

 

Efficiency of MazeBuilder: One of the design decisions you will need to make for MazeBuilder is how you want to represent a collection of edges, cells, whatever you are going to use both to calculate the maze and then to print it out. How you represent this will have an impact on how fast your MazeBuilder code runs. Do keep efficiency in mind as you implement MazeBuilder.  Think about what we have discussed in class, how many times will this operation be done vs. another operation? What is the tradeoff between two implementations? We do want you to think about these things, but there is not one “perfect” implementation that we are looking for – there are several ways to solve the problem. We won’t be giving efficiency penalties unless your MazeBuilder code is quite inefficient.

 

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. 

 

What to turn in

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.

·         maze15x12.txt - text file showing maze of height 15 and width 12.

·         Maze30x25.txt - text file showing maze of height 30 and width 25.

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.