Summary: In this lab, you will get some refreshing practice with recursion in Java.

Background

One common operation for scientists (and image analysists) is to count the number of blobs in an image. For instance, say we have a bacterial colony in a petri dish like the left image below.


Photo taken by Tami Port, MS, creator of Science Prof Online educational website.

On the right is a processed image that shows each of the things in the petri dish as white blobs. Scientists often want to do things like count the number of blobs, measure how big they are, or get a detailed list of these blobs. Doing these sorts of things manually (or asking graduate students to do them) can be very tedious. Fortunately, you have the tools at your disposal to efficiently handle this problem!

The image on the right is binary--consisting of only zeros and ones--and this is easily represented as a two-dimensional boolean array.

Preparation

Create a directory somewhere for storing the files for this lab.
```
  mkdir somewhere/reclab
```
Go to your new directory
```
  cd somewhere/reclab
```

Copy the files for this lab so that they are modifiable and easily accessible:

  cp ~weinman/public_html/courses/CSC207/2009S/labs/code/recursion/Grid.java .
  cp ~weinman/public_html/courses/CSC207/2009S/labs/code/recursion/grid.txt .
  cp ~weinman/public_html/courses/CSC207/2009S/labs/code/recursion/bookgrid.txt .
  cp ~weinman/public_html/courses/CSC207/2009S/labs/code/recursion/bacgrid.txt .

Exercises

For the purposes of this lab, we will say that two squares in a grid are connected if they share an edge. Thus, each square has up to four neighbors, the squares directly above and below, and to the right and left. Diagonally adjacent squares are not considered connected neighbors. (Note that boundary squares have even fewer neighbors.) If two occupied squares (the individual white pixels of the image above) of the grid are connected, we say they form a group.

Consider the following simple grid.

grid.txt

0 1 0
1 1 0
0 0 1

There is one group of three occupied squares, and one group of an individual occupied square.

Exercise 1

Consider the following grid.

bookgrid.txt

0 0 0 0 0 0 0 0 0 1
0 0 0 1 1 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

How many groups are there?
How big is the largest group?

Exercise 2

Open Grid.java and look it over to see what methods there are. You don't need to understand how they all work, only what they do.
Compile the class.
```
javac Grid.java
```
The Grid.read() method is a factory that takes an input stream and creates a Grid object for you. Verify that this works by running the main method already present in the class, which reads a grid from standard input, and outputs the result of grid.toString() to the terminal.
```
  java Grid < grid.txt
```

Exercise 3

Use recursion to calculate the size of a group (i.e., the number of connected squares), at a given row and column. That is, you should complete the implementation of public int groupSize(int,int).
What is the complexity of your algorithm?

Exercise 4

Complete the implementation of public int getNumGroups, which computes the number of different groups (or blobs) in the grid.
Note: If you implemented the previous exercise appropriately, you can re-use part of your solution for ths problem quite easily!
What is the complexity of your algorithm?

Exercise 5

Complete the implementation of public void listGroups, which should list all the groups/blobs present in the grid. For instance, on the file bookgrid.txt, the output should be something like:
```
GROUP: (0,9) (1,9) 
GROUP: (1,3) (1,4) 
GROUP: (3,4) 
GROUP: (3,7) (4,7) (5,7) (5,8) 
GROUP: (4,3) 
GROUP: (7,4) (7,5)
```
where the square locations in a group are given by (row,col) pairs.
Note: There are several ways to accomplish this. Like the previous exercise, an appopriate implementation of Exercise 3 will allow you to re-use code with little extra effort!
What is the complexity of your algorithm?