HW#5 --- last modified January 16 2019 00:35:12..

A solution set is posted here.

Due date: Nov.19 (start of class)
========= 

Files to be submitted: cs146sec6hw5file1.java (or cs146sec8hw5file1.jav)
======================                         if that's your section
                       (Do NOT submit any other files)

Purpose: To gain more experience with the sorting algorithms
======== we've talked about. To use the union/find algorithm

Specification:
==============
First do the following problems: (a) 7.4, (b) 7.15,
(c) Prove Quick selection has O(N) expected running time. These are due
on paper start of class. Then write a program that uses the algorithm
from chapter 8 to generate and draw mazes. Your program will be
run from the command line with a line like:

java cs146sec6hw5file1 300 200 5 6

This would pop up a 300 x 200 sized JFrame on which a randomly
generated according to the books algorithm 5x6 cells
maze is drawn. (If instead do 5x6 vertices okay too). Changes these
command-line arguments appropriately modifies the JFrame that appears. 

Some hints on how you can use union find to implement the maze
drawing:

(1) Imagine that the nxm cells are laid out as one one dimensional array
    of length n*m. A given internal cell i is adjacent to the cells at
    location i-1, i+1, i-m, i+m. (You figure out the special cases when a
    cells is on one of the 4 sides of the maze.)

(2) Use this array to represent the equivalence relation of which cells
    are connected to which cells. Keep track of the total number
    of distinct trees in this array in the variable numTrees. Every time
    you do a union this will decrease by one. When you get down to one you
    know you are done. 

(3) It might be easier to draw the maze with all the edges and delete them
    (by painting over them with the background) as you do the algorithm.

(4) One way to generate the maze would be to repeatedly generate x's less
    than n*m. Then do find(x) and then pick at random one of the up to
    four adjacent cells (say cell y) and do a find(y). This corresponds to
    choosing an edge at random as described in class. If find(x)==find(y)
    do nothing. Otherwise, union(x,y) and draw over the edge between these
    cells.

Point Breakdown
===============
(a)...................................1pt
(b)...................................1pt
(c)...................................2pt
  (1pt formulation of result; 
   1pt correctness)
Coding guidelines followed............1pt
Frame appears with maze on it.........1pt
Books algorithms is implemented 
 correctly............................1pt
Chnagin command line arguments
 appropriately affects the maze.......1pt


Total.................................8pts                          

A solution set is posted here.