Union- Find

Introduction

The labs in CSC172 follow a pair programming paradigm. Every student is encouraged (but not strictly required) to have a lab partner. Labs will typically have an even number of components. The two partners in a pair programming environment take turns at the keyboard. This paradigm facilitates code improvement through collaborative efforts, and exercises the programmers cognitive ability to understand and discuss concepts fundamental to computer programming. The use of pair programming is optional in CSC172. It is not a requirement. You can learn more about the pair programming paradigm, its history, methods, practical benefits, philosophical underpinnings, and scientific validation at http://en.wikipedia.org/wiki/Pair_programming.

Every student must hand in his own work, but every student must list the name of the lab partner (if any) on all labs.

This lab has three parts. You and your partner(s) should switch off typing each part, as explained by your lab TA. As one person types the lab, the other should be watching over the code and offering suggestions. Each part should be in addition to the previous parts, so do not erase any previous work when you switch.

The textbook should present examples of the code necessary to complete this lab. However, collaboration is allowed. You and your lab partner may discuss the lab with other pairs in the lab. It is acceptable to write code on the white board for the benefit of other lab pairs, but you are not allowed to electronically copy and/or transfer files between groups.

Smart Finds: Blob Coloring (three parts)

Input is an NxN integer "image array" A[N,N] of 0 and 1. 0's mean "white", 1's mean "black". Count the individual blobs in the image and relabel each one with a unique "color" integer from 2 to some M. Output is the "labeled blob array". After that a find(i,j) will return the color of the relevant blob (or background). 

Input (. for 0 for visibility)
1 . 1 . 1
1 . 1 . ,
. . 1 . 1
1 . . . 1
1 1 1 1 1

Colors array after 4th row:
2 . 3 . 4
2 . 3 . .
. . 3 . 5
6 . . . 5

Output: final colors array: 
2 . 3 . 4
2 . 3 . .
. . 3 . 5
5 . . . 5
5 5 5 5 5

We use the O(1) find O(N) union algorithms described in Weiss p. 333.

Let our blobs be "four-connected", so Up, Down, Left, Right neighbors are connected but up-and-left, etc. are not (touching corners diagonally doesn't count). For a pixel x, call its upper neighbor xU, its left neighbor xL. So if x is A(i,j), xU is A(i-1,j) for instance.

Part 1:
Then a simplified algorithm skeleton is the following. It needs checks for array bound violations (or add a top row and left column of 0s to the input array?), and maybe other details ;-}. 

 using indices i and j,  scan the image  rowwise from upper left
   to lower right:  call x = A(i,j).
  If x == 0 continue
    elseif xU == 0 and xL == 0, color(x) = new(color);
    elseif xU == y and xL == 0, color(x) = y;
    elseif xL == y and xU == 0, color(x) = y;
    elseif xL == y and xU == z,
      {  color(x) = y;
         UNION!  y is equiv. to z;
      }

Part 2:
As Weiss points out, to UNION! color y and color z sets, use the brute-force approach of scanning the entire array and setting all y's to z or vice-versa.

Part 3: Joint Work:
Use an editor and make some nice, nasty, complete, and convincing cases (needn't be big) for input and submit the results in your hand-in.

Hand In

Hand in the source code from this lab at the appropriate location on the blackboard system at my.rochester.edu. You should hand in a single compressed/archived (i.e. zipped) file that contains the following.) You will need to include the images of any plotted results you made.
  1. A README that includes your contact information, your partner's name, a brief explanation of the lab (A one paragraph synopsis. Include information identifying what class and lab number your files represent.).
  2. Several JAVA source code files representing the work accomplished for this lab. All source code files should contain author and partner identification in the comments at the top of the file.
  3. A plain text file named OUTPUT that includes author information at the beginning and shows the compile and run steps of your code. The best way to generate this file is to cut and paste from the command line. Also present your experimental results here.

      Grading

      172/grading.html

      Each section (1-6) accounts for 15% of the lab grade (total 90%) (README file counts for 10%)

      This page is maintained by Deer Boy

      Last update: 10/13/12