HW5 Solutions Page
Return to
homework page.
7.4 Short the result of first 7-sorting, then 3-sorting then 1-sorting:
9, 8, 7, 6, 5, 4, 3, 2, 1
7-sorting above gives
2, 1, 7, 6, 5, 4, 3, 9, 8
3-sorting this gives
2, 1, 4, 3, 5, 7, 6, 9, 8
Finally, 1-sorting produces the sorted list
1, 2, 3, 4, 5, 6, 7, 8, 9
7.15 Sort 3, 1, 4, 1, 5, 9, 2, 6 using mergesort.
We would first sort the two halfs 3, 1, 4, 1
and 5, 9, 2, 6 and merge the result.
Sorting 3, 1, 4, 1 involves sorting 3, 1 and
4, 1 and merging the result.
Sorting 3, 1 involves sorting 3 and then 1 and
merging the result. These are already sorted
and after the merge we get 1, 3.
Similarly, sorting 4, 1 involves sorting 4 and then 1
and merging the result giving 1, 4.
Merging 1,3 and 1, 4 yields 1, 1, 3, 4 and completes the
the sorting of 3, 1, 4, 1.
Sorting 5, 9, 2, 6 involves sorting 5, 9 then
2,6 and merging the result.
Sorting 5, 9 involves sorting 5 and then 9 and
merging the result. These are already sorted
and after the merge we get 5, 9.
Similarly, sorting 2, 6 involves sorting 2 and then 6
and merging the result giving 2, 6.
Merging 5, 9 and 2, 6 yields 2, 5, 6, 9 and completes the
the sorting of 5, 9, 2, 6.
Finally, we merge A= 1, 1, 3, 4 and B= 2, 5, 6, 9. To illustrate
how merge is done we describe this in more detail
We have three counters Actr, Bctr, and Cctr which start at
the start of the arrays A, B and the target arrays respectively.
Since 1 < 2 we write 1 into the target array and do Actr++, Cctr++,
since 1 < 2 we write again 1 into the target array and do Actr++, Cctr++,
since ! 3 < 2 we write 2 into the target array and do Bctr++, Cctr++,
since 3 < 5 we write 3 into the target array and do Actr++, Cctr++,
since 4 < 5 we wrtie 4 into the traget array and do Actr++, Cctr++.
At this point A is finished and we write the raminder of B into
the target array giving the sorted list 1, 1, 2, 3, 4, 5, 6, 9.
Prove quickselect has O(N) expected running time.
By analogy with equation 7.14 in the book the running time of
QuickSelect is:
T(N) = 1/N[Sum^{N-1}_{j=0}T(j)] + cN (*)
The fact of 2 from the first term on the write becomes a factor of 1
because we only look at the partition which has the kth element and not
both partitions as in Quicksort.
Multiplying both sides of (*) by N give
NT(N) = Sum^{N-1}_{j=0}T(j) + cN^2. (**)
Subtracting the N-1 version of eqn (**) from the above version gives:
NT(N) - (N-1)T(N-1) = T(N-1) + 2cN - c.
which is equivalent to
NT(N) = NT(N-1) + 2cN - c.
We can now divide both sides by N to get
T(N) = T(N-1) + 2c - c/N.
Since c > 0 and we just want an upper bound we have
T(N) < T(N-1) + 2c < T(N-2) + 2c +2c < ... < T(1) + (N-1)2c
as T(1) is a constant this shows T(N) is O(N).
//cs146sec6hw5file1.java - an application to make random mazes
import java.awt.*; // for drawing
import java.awt.event.*; // for window closing
import javax.swing.*; // for JFrame
import java.util.*; // for Random
/**
This application is used to draw randomly generated mazes
in a JFrame.
*/
public class cs146sec6hw5file1 extends JFrame
{
/**
The constructor used to create JFrame. Has on it a
MazePanel where the maze where the maze is acutally drawn.
@param width - how wide in pixels frame is
@param height- how high in pixels frame is
@param mazeWidth - how many cells wide the maze is
@param mazeHeight - how many cells high the maze is
*/
public cs146sec6hw5file1(int width, int height,
int mazeWidth, int mazeHeight)
{
super("Maze Drawer");
Container c = getContentPane();
c.add(new MazePanel(width, height, mazeWidth, mazeHeight));
setBackground(Color.white);
setSize(width, height);
}
/**
Set-up frame and window closing listener.
@param args - command line arguments used to determine
size of frame and maze
*/
public static void main(String[] args)
{
if( args.length < 4 )
{
System.err.println("You need four command line arguments:");
System.err.println("sizeX sizeY maze_width maze_height");
System.exit(1);
}
cs146sec6hw5file1 app = new cs146sec6hw5file1(
Integer.parseInt(args[0]),
Integer.parseInt(args[1]),
Integer.parseInt(args[2]),
Integer.parseInt(args[3]));
app.addWindowListener( new WindowAdapter() //anonymous inner class
{
public void windowClosing( WindowEvent e)
{
System.exit(0);
}
}
);
app.show();
}
} //end cs146sec6hw5file1.java
class MazePanel extends JPanel
{
/*
Constructor for MazePanel. Sets up both its size in pixels and
the number of cells wide and high it is.
*/
MazePanel(int width, int height, int mazeWidth, int mazeHeight)
{
this.width = width;
this.height = height;
this.mazeWidth = mazeWidth;
this.mazeHeight = mazeHeight;
xOffset = width/(mazeWidth+2);
yOffset = height/(mazeHeight+2);
}
/*
Method called when maze needs to be drawn to a graphics context
g - graphics constext on which maze is drawn.
*/
public void paintComponent(Graphics g)
{
g.setColor(Color.black);
drawFullGrid(g);
mazifyGrid(g);
}
/*
returns the preferred size of the MazePanel so that
it will be drawn correctly of frame.
*/
public Dimension getPreferredSize()
{
return new Dimension(width,height);
}
/*
This method draws the complete grid with four walls around
each cell.
g - graphics context we are drawing to.
*/
void drawFullGrid(Graphics g)
{
for(int y = yOffset, i = 0; i <= mazeHeight ; i++, y += yOffset)
{
for(int x = xOffset, j = 0 ; j <= mazeWidth; j++, x += xOffset)
{
g.fillOval(x-2, y-2, 4, 4);
if(j < mazeWidth) g.drawLine(x, y, x+xOffset, y);
if(i < mazeHeight) g.drawLine(x, y, x, y+yOffset);
}
}
}
/*
This method uses randomness and the disjoint Set ADT to delete
edges from the full grid that has already previously been drawn
to create a maze. To ensure that our maze doesn't change under
repaints our random number generator always starts with the
same seed.
*/
void mazifyGrid(Graphics g)
{
int gridSize = mazeWidth*mazeHeight;
int numComponents = gridSize;
DisjSetsFast connectedCells= new DisjSetsFast(gridSize);
Random random = new Random(randomSeed);
while(numComponents > 1)
{
int cell = random.nextInt(gridSize);
int direction = random.nextInt(2);
int neighbour = cell;
int tmp;
if(direction > 0)
{
if((tmp = cell + mazeWidth) < gridSize)
neighbour = tmp;
}
else if( cell % mazeWidth < mazeWidth - 1 )
neighbour++;
int nRoot = connectedCells.find(neighbour);
int cRoot = connectedCells.find(cell);
if(nRoot != cRoot)
{
connectedCells.union(nRoot, cRoot);
deleteLine(g, cell, neighbour);
numComponents--;
}
}
}
/*
Used to delete the edge between cell and neighbour in the
maze image that has already been drawn to g.
*/
void deleteLine(Graphics g, int cell, int neighbour)
{
int cRow = cell/mazeWidth;
int cColumn = cell % mazeWidth;
int nRow = neighbour/mazeWidth;
int nColumn = neighbour % mazeWidth;
if( cRow == nRow)
{
cRow ++;
nRow += 2;
cColumn += 2;
nColumn = cColumn;
}
else
{
cColumn ++;
nColumn += 2;
cRow += 2;
nRow = cRow;
}
g.setColor(Color.white);
g.drawLine(cColumn*xOffset, cRow*yOffset, nColumn*xOffset, nRow*yOffset);
}
int width; // width of panel in pixels
int height; // height of panel in pixels
int mazeWidth; // number of cells width the maze is
int mazeHeight; // number of cells high the maze is
int xOffset; // length of a horizontal edge
int yOffset; // height of a vertical edge
protected long randomSeed = 101; /* fixed seed for our random
number generator */
}
/*
Below is essentially code from Weiss' book for the
disjoint set class, using union by rank
and path compression.
Elements in the set are numbered starting at 0.
*/
class DisjSetsFast
{
/*
Construct the disjoint sets object.
numElements is the initial number of disjoint sets.
*/
DisjSetsFast( int numElements )
{
s = new int [ numElements ];
for( int i = 0; i < s.length; i++ )
s[ i ] = -1;
}
/*
Union two disjoint sets using the height heuristic.
For simplicity, we assume root1 and root2 are distinct
and represent set names.
root1 is the root of set 1.
root2 is the root of set 2.
*/
void union( int root1, int root2 )
{
if( s[ root2 ] < s[ root1 ] ) // root2 is deeper
s[ root1 ] = root2; // Make root2 new root
else
{
if( s[ root1 ] == s[ root2 ] )
s[ root1 ]--; // Update height if same
s[ root2 ] = root1; // Make root1 new root
}
}
/*
Perform a find with path compression.
Error checks omitted again for simplicity.
x is the element being searched for.
*/
int find( int x )
{
if( s[ x ] < 0 )
return x;
else
return s[ x ] = find( s[ x ] );
}
private int [ ] s;
}