CSE 373, Autumn 2002: Homework 6

Due Monday, 12/2/2002

For all program or data structure design problems such as the two below you must provide pseudocode (see the manual) and an adequate explanation of the methods. It is often helpful to include small examples demonstrating the methods. Straight pseudocode with no additional documentation is not enough.  Your pseudocode can contain English if needed.  Each problem should be answered on a separate sheets of paper so they can be graded by different TAs.  Your name should be at the top of every page.
 
  1. (10 points) Use disjoint union/find to design an algorithm to design random mazes which have the property that there is no path from start to end.  The maze must have no cycles and from each cell there is a path from it to one of start or end.   You can assume that the cells are numbered 1 to n, with 1 being the start cell and n being the end cell.  The edge set E contains all possible pairs of edges in the maze not including the boundary edges.  A good property of your solution, the most frustrating to users of the maze, would be that the number of cells reachable from the start approximately be n/2.  Your solution does not have to have this good propery, but it is a challenge to achieve it.
  2. (10 points)  Suppose we have an unsorted array A[1..n] of integers with possible duplicates.  Design a version of Quicksort that instead of partioning into two sets, one whose elements are less than or equal to the pivot and a second whose elements are greater than or equal to the pivot, the new algorithm partitions into three sets, one whose elements are strictly less than the pivot, a second whose elements are stricktly more than the pivot, and a third whose elements are equal to the pivot. Your algorithm should be in-place. One idea is that in the partitioning phase that as we move the two pointers i and j toward each other we maintain the invariant that the array looks like;
                                                                                i                              j
    [elements equal to pivot] [elements less than pivot] [unknown elements] [elements greater than pivot] [elements equal to pivot]

    When there are no unknown elements left then the elements can be rearranged to be of this form:

    [elements less than pivot][elements equal to pivot][elements greater than pivot]
  3. (10 points)  There are two strategies for handling small arrays in Quicksort.  The first strategy is the one described in class.  Apply Quicksort recursively until the array are smaller than a CUTOFF size, then call Insertionsort to sort the small array.  A second strategy is to apply Quicksort recursively unitl the array is smaller than the CUTOFF, the return.  In this strategy after Quicksort(A[],1,n) is completed, the array A[1,n] is almost sorted.  Now call Insertionsort(A[],1,n) to finish the job.  Since A[1..n] is almost sorted then Insertionsort should do a good job.