Compsci 100e, Fall 2009, Blobs & Union-Find

Blobs

Questions based on blob code whose operation is described.

In initializing a BlobModel two copies of the grid are created: myGrid and myCopy. The code in BlobModel.blobFill fills myGrid with characters representing blobs, removing the asterisks representing data that appeared before blobs were counted and replacing the asterisks with either blob-representing characters or with whitespace if the data aren't part of a blob.

  1. In method process of BlobModel what's the purpose of the System.arraycopy code?
  2. Explain the line below (part of the else {} code) in the process method. 
       blobFill(j,k,bcount+1, BLOB_OFF);
  3. Modify the code in BlobModel.process to display only one blob: the largest blob found.

  4. Explain why a String would be a worse choice in BlobModel.display than the StringBuilder local variable used for building up asterisks and whitespace.
  5. In BlobModel.process this line occurs int minSize = Integer.parseInt((String) o); explain what parseInt does and why the cast is needed.

Union-Find

Suppose we are given a sequence of pairs of integers, where each integer represents an object of some type and we are to interpret the pair p-q as meaning "p is connected to q." Our goal is to represent all transitive relationships and filter out extraneous pairs. We want to create a structure to represent these disjoint sets.

public class DisjointSets { public DisjointSets() { // ... } // replace the two given items by their union public void union(int root1, int root2) { // ... } // find the set for a given item public int find(int item) { // ... } What are the important considerations?