CSE373 Winter 2014: Homework 4 - A-Maze-Ing Union-Find

We have discussed efficient implementations of the union-find ADT and how to use the ADT to build mazes. For this assignment, you will do both.

Outline

Due Dates, Turn-In, and Rules

Partner Selection Due 11:00PM Wednesday February 12, 2014

Assignment Due 11:00PM Thursday February 20, 2014

For this assignment, you may work with one partner. If you do so, the two of you will turn in only one assignment and, except in extraordinary situations, receive the same grade (and, if applicable, have the same number of late days applied). Working with a partner is optional; it is fine to complete the assignment by yourself.

If you choose to work with a partner, one of you must complete this web form before the partner-selection due date. If you choose to work alone, do not complete the form. If you make a mistake filling out the form, email the course staff.

If you choose to work with a partner, you may divide the work however you wish, but both partners must understand and be responsible for everything that is submitted. Beyond working with a partner, all the usual collaboration policies apply.

Read What to Turn In before you submit — poor submissions may lose points.

Turn in your assignment here

Provided Code

Download these files into a new directory:

Programming, Part 1

Create a class MyDisjSets that implements the interface defined in DisjointSets.java. Your class should be a correct implementation of the union-find ADT. Furthermore, the documentation in DisjointSets.java requires specific error-checking and exceptions to throw in many situations. Your implementation should 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) { ... } 

You should use an array implementation of the up-tree structure. You should implement weighted union (also known as union-by-size) and path compression, as discussed in lecture.

Additional details:

Programming, Part 2

For Part 2, you should generate a maze using the method based on disjoint sets discussed in lecture and in Section 8.7 of the textbook. Your maze should obey the constraints discussed in class: there should be only one solution, all cells should be reachable, and only walls allowing cells to be reachable should be removed. Edges should be considered in a random order so that the resulting maze is interesting. 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 have a main method that takes three command-line parameters in this order: 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, it can help to look at the implementation in 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 ease of grading, you need to use exactly the characters we expect for priting your maze:

For example, here is a legal maze of height 2 and width 5:

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

Using Java Collections: While you should use your DisjointSets implementation in your solution, you do not need to use it to represent the set of edges E to be processed or the set of edges M to include in the final maze. For these two sets, feel free to use something similar: an array, an ArrayList, or something else from the Java library is fine. You should also use the Java Random class in your solution. In general, for Part 2 (but not Part 1!) it is okay to use things from the Java library provided you use your DisjointSets implementation appropriately.

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. You may borrow and adapt code from Reverse.java. A maze dimension less than or equal to 0 is illegal. However, dimensions of size 1 are legal (and produce boring mazes). Be sure you check for these things:

Efficiency of maze-building: One of the design decisions you will need to make is how to represent a collection of edges and cells. You will use these collections when you build the maze and when you 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 different operations be done? What is the tradeoff among different 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 with different trade-offs. So any reasonable solution can receive full points; only particularly inefficient implementations will be penalized.

Write-Up 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. 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 worked together. If you divided up the tasks, explain how you did so. If you worked on parts together, describe the actual process. Discuss how much time you worked together and how you spent that time (planning, coding, testing, ...). Be sure to describe at least one good thing and one bad thing about the process of working with a partner.
  5. Discuss whether your implementation can build a 1000 x 1000 maze in a reasonable amount of time (and discuss what you consider reasonable). If not, describe what part of your implementation you believe is taking too much time and why you think that is the problem. If so, describe how a change to your code might slow down the creation of a maze of this size and why you expect such a change to matter.

Above and Beyond

What to Turn In

If you work with a partner, only one partner should submit the files. Be sure to list both partners' names in your files.

You will turn in everything electronically. This should include:


Valid CSS! Valid XHTML 1.1