CSC300: Homework (Percolation, Sorting Problems): Homework (Percolation)

Read Algorithms 2.1. Also read the discussion of stability in section 2.5 (page 341 in the third printing of the text).

Do these problems on paper, but don't hand them in. Be sure to do the starred ones.

 2.1.1
  Show, in the style of the example trace with Algorithm 2.1,
  how selection sort sorts the array
  E A S Y Q U E S T I O N

2.1.2*
  What is the maximum number of exchanges involving any particular item
  during selection sort? What is the average number of exchanges
  involving an item?

2.1.1
  Show, in the style of the example trace with Algorithm 2.1,
  how insertion sort sorts the array
  E A S Y Q U E S T I O N

2.1.6*
  Which method runs faster for an array with all keys identical,
  selection sort or insertion sort?

2.1.7*
  Which method runs faster for an array in reverse order,
  selection sort or insertion sort?

2.1.8*
  Suppose that we use insertion sort on a randomly ordered array where items 
  have only one of three values. Is the running time linear, quadratic, or 
  something in between? 

2.1.15*
  Expensive exchange. A clerk at a shipping company is charged with the task
  of rearranging a number of large crates in order of the time they are to be
  shipped out. Thus, the cost of compares is very low (just look at the labels)
  relative to the cost of ex- changes (move the crates). The warehouse is
  nearly full --- there is extra space sufficient to hold any one of the crates,
  but not two. What sorting method should the clerk use?

2.1.24
  Insertion sort with sentinel. Develop an implementation of insertion sort
  that eliminates the j>0 test in the inner loop by first putting the
  smallest item into position. Use SortCompare to evaluate the effectiveness
  of doing so. Note : It is often possible to avoid an index-out-of-bounds
  test in this way-the element that enables the test to be eliminated is
  known as a sentinel. 

2.1.25 
  Insertion sort without exchanges. Develop an implementation of insertion
  sort that moves larger elements to the right one position with one array
  access per entry, rather than using exchange(). Use SortCompare to evaluate
  the effectiveness of doing so.

Complete Percolation.java

Here's a song to listen to while you work.

file:Percolation.java [source] [doc-public] [doc-private]

package algs15.perc;

//import stdlib.*;
//import algs15.*;

// Uncomment the import statements above.

// You can test this using InteractivePercolationVisualizer and PercolationVisualizer
// All methods should make at most a constant number of calls to a UF data structure.
// You can use more than one UF data structure.
// You can assume that N>1
//
// Note that you can print out a UF structure using its toString method.
// You can also use the toGraphviz method to draw the UF.
// These may be useful for debugging.
// Try calling them whenever you open a new square.
public class Percolation {
  int N;
  boolean[] open;
  // TODO: more fields to add here
  public Percolation(int N) {
    if (N < 2) throw new IllegalArgumentException();
    this.N = N;
    this.open = new boolean[N*N];
    // TODO: more to do here
  }
  // open site (row i, column j) if it is not already
  public void open(int i, int j) {
    int x = i*N+j;
    if (!open[x]) {
      open[x] = true;
      // TODO: more to do here.
    }
  }
  // is site (row i, column j) open?
  public boolean isOpen(int i, int j) {
    return open[i*N+j];
  }
  // is site (row i, column j) full?
  public boolean isFull(int i, int j) {
    // TODO
    return false;
  }
  // does the system percolate?
  public boolean percolates() {
    // TODO
    return false;
  }
}