Union-Find Exercises

___________________     ___________________


___________________

1. Show the result of the following sequence of instructions: unite(1,2), unite(3,4), unite(3,5), unite(1,7), unite(3,6), unite(8,9), unite(1,8), unite(3,10), unite(3,11), unite(3,12), unite(3,13), unite(14,15), unite(16,0), unite(14,16), unite(1,3), unite(1,14) when the unite operations are performed accoring to:
   1. Quick-Find
   2. Quick-Union
   3. Weighted quick union with path compression

2. Consider the random maze generation algorithm given in Weiss (refer to the text for more details):

     Start with each cell in the grid in its own set numbered [0, N^2-1], 
     Create all interior and exterior walls
     Repeat 
       Choose an interior wall at random
       If the two cells (call them x and y) adjacent to this wall 
         are in different sets, remove the wall and perform a union
         on x and y 
     until all cells are in the set
   

   Explain the following:
   1. What does a set represent as the algorithm progresses?

   2. Why do we not stop performing unions once the beginning cell and the end cell are in the same equivalence class?

   3. How does the algorithm guarantee that there will be only one path from the beginning cell to the end cell?

   4. Exactly how many unions are performed? Explain your answer.

3. Review Maze.java. Currently, the code below produces the following grid. for (int i=0; i < 10; i++) { for (int j=0; j < 10; j++) { maze.drawHorizontal(i, j); maze.drawVertical(i, j); } }

   How would you add code to draw the bottom and right edges?

4. Create a class MazeCreator that generates and draws a random maze according to the above algorithm.