CSE 373 Data Structures 09wi, Homework 5

Last Updated: 6pm 2/17/09 (in red)

Electronic Turn-in due: 11:45pm Tuesday, 2/24/09.

For this assignment, (if you wish) you may work with one partner for the programming portion of the assignment.  Although it is possible to split the implementation into two pieces, 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 Sean by 11:45pm Friday Feb 20th 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) and path compression as described below.  What is expected is an array implementation of the uptree structure discussed in class 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 needed.  Your implementation (named DisjSets.java) should also include a public constructor as follows:

    /**
     * Required constructor.
     * @param numElements is number of elements in the set.
     */
    public DisjSets(int numElements);

Here is the interface you are required to implement:

interface DisjointSets {

    /**
     * Union two disjoint sets using union by size (number of nodes).
     * root1 and root2 are assumed to be roots and represent set names.
     * @param root1 the root of set 1.
     * @param root2 the root of set 2.
     */
    void union(int root1, int root2);

    /**
     * Perform a find with path compression.
     * Assumes elements in the set are unique and numbered starting at 0, ending at numElements-1
     * @param x the element being searched for.
     * @return the set containing x.
     */
    int find(int x);

    /**
     * Returns the total number of sets.
     * @return the current number of sets.
     */
    int numSets();

    /**
     * Returns the total number of elements in the given set.
     * setNum is assumed to be a root and represents the name of a set.
     * @param setNum the name of a set
     */
    int numElements(int setNum);

    /**
     * Prints out the elements in the given set.
     * setNum is assumed to be a root and represents the name of a set.
     * @param setNum the name of a set
     */
    void printElements(int setNum);

    /**
     * Returns an array containing the elements in the given set.
     * setNum is assumed to be a root and represents the name of a set.
     * @param setNum the name of a set
     */
    int [] getElements(int setNum);

}

 

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 Chapter 8 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 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.  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.  The following would be a legal maze of height 2 and width 5.

 

+-+-+-+-+-+
          |
+ +-+ + +-+
| |   |    

+-+-+-+-+-+

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.  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.

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.

·        DisjSets.java - your implementation of DisjointSets.java

·        maze10x10.txt - text file showing maze of size 10 x 10.

·        maze20x10.txt - text file showing maze of height 20 x width 10.

If you work with a partner, 1) only one partner needs to submit the code electronically, be sure that both partners’ names are listed in all files.  2) Include a text file (submit electronically and print out) that describes 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.