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
• Provided Code
• Programming, Part 1
• Programming, Part 2
• Write-Up Questions
• Above and Beyond
• What to Turn In

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:

• DisjointSets.java
• InvalidSetNameException.java
• InvalidElementException.java

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:

• Note that union should throw an exception if either of its two parameters are not valid names of sets. A different approach would be to have union call find on its parameters and use the results. While this is a reasonable way to implement union, this is not what we are asking for in this assignment.
• There is no requirement on the order elements are listed for printSet or getElements. For printSet, elements should be printed with curly braces on each end and with individual elements separated by commas and spaces as follows: {52, 17, 12, 34}.
• In this part of the assignment, you should not use anything from the Java Collections library in your implementation. 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.
• 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 union-find operations, but it turns out having it is useful in some cases, including for testing. So while you should try to implement all operations efficiently, do not sacrifice the efficiency of union and find operations to improve the runtime of other operations.

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:

• Put a + at the corner of each cell.
• Use - for a horizontal wall.
• Use | for a vertical wall.
• Use spaces for all cells and absent-walls.

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:

• The correct number of parameters have been passed and, if not, print a message indicating the correct way to use the program and exit.
• The file name given can be opened or written to, and, if not, print a message and exit.
• Two integer values greater than 0 have been passed for the maze dimensions -- you can do this using parseInt and checking for NumberFormatException as is done in Reverse. For any errors, print an informative message and exit.

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

• Create a program that reads in a maze and solves it efficiently. Write a report documenting what data structures you used to keep track of searching through the maze and what the run-time complexity of solving a maze is.
• Create a program that reads in a maze and checks whether it contains any cycles. Write a report documenting what data structures you used to keep track of searching through the maze and what the run-time complexity of solving a maze is.

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:

• Code:
  • MyDisjSets.java
  • MazeBuilder.java
  • Any other files you created for implementing Part 1 or Part 2 (you may not have any, which is fine)
  • All Java files you created for testing
• Example outputs:
  • A file named maze16x14.txt containing a maze of height 16 and width 14
  • A file named maze30x15.txt containing a maze of height 30 and width 15
• Report: Electronic version of your write-up questions. We prefer pdf format, but we will also accept plain text or Microsoft Word. Check with us in advance for any other formats.