Homework 09

Due: 11:59 pm on Friday, November 5, 2004

Reading: CS 5 notes, week 9.

2 problems, 30 points for #1 and 20 points for #2

Problem 1 Gaussian Elimination [topics: practice with 2d arrays]

In this assignment you will write a series of methods which, taken together, will implement a linear equation solver based on a technique called Gaussian Elimination. It turns out that this is simply a natural end result from writing a few short functions that handle 2d arrays.

Your program should do the following:

First, ask the user how many rows and columns to include in the desired 2d array.
Second, create a 2d array of doubles with the desired number of rows and columns.
Third, prompt the user to type in values for the entries in the array. This should be done in a call to a separate method named enterValues, as covered in class. You should assume that the user (you!) will be typed in "row-major order", that is, left-to-right and top-to-bottom, as you would read them on a page.

Finally, enter a loop that presents the user with the following menu:

      
      (0) Change the values in the array
      (1) Print the array
      (2) Multiply an array row 
      (3) Add one row to another
      (4) Add a multiple of one row to another
      (5) Solve!
      (6) Invert! [This is optional]
      (9) Quit
  Which choice would you like?

Of course, you will need to implement the different options on this menu. In doing so you should write the following methods.

Methods to Write

public static void printMenu()

This method should simply print out the above menu. The loop around this menu and user's choice should be handled in the main method.

public static void enterValues(double[][] A)

This method should first remind the user of the dimensions of the array and then prompt the user to type in values for the entries in the array. The entries should be doubles and you may assume they will be typed in "row-major order", that is, left-to-right and top-to-bottom, as you would read them on a page. For example,

	 
Please enter values for a 3 row, 4 column array in row-major order:




     2 4 5 34.0
     2 7 4 36
     3 5 4 35

public static void print(double[][] A)

This method should print out the doubles in the array. It should use H.fmt to display two places of precision for each of the doubles -- we will discuss in class exactly how this works, but the key to aligning the matrix columns is

    H.p( H.fmt(A[r][c], 2, 8, HMCOutput.RIGHT) );

Here, the 2 represents the desired precision; the 8 represents the field width or space occupied by the number, and the fourth input indicates that we want the values aligned to the right. For example, the above matrix would look like

    
    2.00    4.00    5.00   34.00
    2.00    7.00    4.00   36.00
    3.00    5.00    4.00   35.00

public static void multRow(double[][] A, int r, double m)

This method should multiply all of the elements in row r of the input array A by the value m. It should not change anything else in the array, nor should it print anything. (The prompts for input and all output printing should be in main.) Here is an example -- note that we start counting at 0:

     Which row would you like to multply ? 0
     What value would you like to multiply by ? 0.25

   Result:
    0.50    1.00    1.25    8.50
    2.00    7.00    4.00   36.00
    3.00    5.00    4.00   35.00

public static void addRowaIntoRowb(double[][] A, int ra, int rb)

This method should add each element of row ra into row rb. Row ra should remain unchanged! Row rb will change (unless row ra is all zeros). This method should not change anything else in the array, nor should it print anything. The prompts for input and all output printing should be in main. For example,

     Which row would you like to add into another ? 0
     Which row would you like to add row 0 into ?   1

   Result:
    0.50    1.00    1.25    8.50
    2.50    8.00    5.25   44.50
    3.00    5.00    4.00   35.00

public static void addMxRowaIntoRowb(double[][] A, double m, int ra, int rb)

This method should add each element of row ra -- multiplied by m into row rb. Row ra should remain completely unchanged! Row rb will most likely change, however. This method should not change anything else in the array, nor should it print anything. The prompts for input and all output printing should be in main. Here is an example:

     Which row would you like to add into another ? 0
     Row 0 times what constant ? -5
     Which row would you like to add -5 times row 0 into ? 1

   Result:
    0.50    1.00    1.25    8.50
    0.00    3.00   -1.00    2.00
    3.00    5.00    4.00   35.00

public static void solve(double[][] A)

This method should use the previous row-operation methods in order to solve the system of equations represented by the 2d array. If the number of columns is not exactly one greater than the number of rows, this method should simply print a message and return.

However, when the number of columns is one greater than the number of rows, this method should diagonalize the left-hand side of the array so that every diagonal entry is 1 and every off-diagonal entry is 0. You should use only row operations (the row methods defined above) to do this. Note that the right-hand column will not, in general consist of zeros and ones -- it will hold the solution to the original set of equations. Here is the result of choosing solve with the previous array (above) as the starting point (there is no additional user input):

   Result:
    1.00    0.00    0.00    3.00
    0.00    1.00    0.00    2.00
   -0.00   -0.00    1.00    4.00

The following provides a thorough and step-by-step example of how solve should work. Basically, solve uses the two methods multRow and addMxRowaToRowb repeatedly in order to diagonalize all but the right column of the array:

Suppose we have three linear equations in three unknowns (the variables x, y, and z):

2x	+	4y	+	5z	=	34
2x	+	7y	+	4z	=	36
3x	+	5y	+	4z	=	35

Our goal is to do a series of operations such that the coefficients along the diagonal all end up 1, and all the other coefficients end up 0. When we have reached this configuration, we will be able to read off the values of the variables directly. Obviously, the operations we perform must be such that they do not disturb the meaning of the equations.

Throughout this example, we'll always show all the variables and coefficients, even when the coefficient is 0 or 1, just to make things clear. Also, in each step we'll draw a pointer in front of each equation that has changed since the previous step.

The first step is to divide the zeroth equation by 2, which is the coefficient of x in that equation. That will make the coefficient of x in the zeroth equation 1:

-->	1x	+	2y	+	2.5z	=	17
	2x	+	7y	+	4z	=	36
	3x	+	5y	+	4z	=	35

Now, notice that if we add negative two times the new zeroth equation to the first equation, the coefficient of x in the first equation will become 0. To the same end we add negative three times the zeroth equation to the second equation.

	1x	+	2y	+	2.5z	=	17
-->	0x	+	3y	+	-1z	=	2
-->	0x	+	-1y	+	-3.5z	=	-16

Next we repeat the process, dividing the first equation by 3 so that its y coefficient becomes 1:

	1x	+	2y	+	2.5z	=	17
-->	0x	+	1y	+	-0.33z	=	0.66
	0x	+	-1y	+	-3.5z	=	-16

Then we add negative two times the first row to the zeroth row, and we add one first row to the second row. This will get the coefficient of y to be 0 in the zeroth and second equations (notice that since we have zeroed out the coefficients of x in all but the first equation, we won't mess up the x coefficients by doing this):

-->	1x	+	0y	+	3.16z	=	15.66
	0x	+	1y	+	-0.33z	=	0.66
-->	0x	+	0y	+	-3.83z	=	-15.33

Finally, we divide the second equation by -3.83 to get its z coefficient to be 1, and add -3.16 and 0.33 times the result from the zeroth and first equations, respectively, to obtain:

-->	1x	+	0y	+	0z	=	3
-->	0x	+	1y	+	0z	=	2
-->	0x	+	0y	+	1z	=	4

Thus, the solution of these equations is:

x	=	3
y	=	2
z	=	4

Now, the thing to notice is that the variables play no role in this process; only the coefficients matter! If we take the variables out, all we are doing to solve a system of 3 equations in 3 unknowns is manipulating a 3 by 4 array of coefficients.

NOTE 1: In general Gaussian Elimination can be tricky as the input may not be well behaved. In particular, you may find that you don't actually have n distinct equations because one may be a linear combination of some of the others. If this happens there is not enough information to solve the system completely, and Gaussian elimination will lead one of the rows of the array to be all zeroes. This in turn will likely lead to a division by zero error. You need not worry about this and related problems. Just implement the naive algorithm; we will only test it on well behaved input.

NOTE 2: You may find your results include the value -0 in some places where you expect the value 0. This is ok, and is the result of the finite precision of computer arithmetic.

NOTE 3: For extra credit, you can implement a matrix inverter. See the end of this assignment for details.

Be sure to submit your CS5App.java file under homework 9, problem 1.

Problem 2 Life [topics: 2d arrays]

Pair Programming Problem
    You are encouraged to work with a partner on this problem (both parts of it).
    If you prefer to work alone, you may certainly do so.

Part 1    John Conway's Original Game of Life    [10 points]

The "game of life" was invented by mathematician John Conway in the late 1960's as an example of a simulation in which a simple model gives rise to some interesting emergent properties. A nice online reference exists for the game of life at http://www.math.com/students/wonders/life/life.html. This problem asks you to implement the part of this simulation in which cells "evolve."

In the game of life, the universe is a two-dimensional grid world made up of square cells. Some of the cells are "alive" or "on" (black cells, by default), while other cells are "empty" or "off" (white cells, by default). We will assume and ensure that the outermost edge of the grid world is always empty.

At each time step, each cell in the grid is reevaluated according to the following rules:

If an empty "off" cell has exactly 3 "on" neighbors, it springs to life and turns "on".
If an empty cell has 0, 1, 2, 4, 5, 6, 7, or 8 neighbors, it remains "off".
If a living "on" cell has either 2 or 3 "on" neighbors, it stays alive and remains "on".
If a living "on" cell has 0, 1, 4, 5, 6, 7, or 8 "on" neighbors, it dies (either of isolation or overcrowding) and becomes an empty "off" cell.

What's a neighbor?

The number of live neighbors is based on the cells that were present before the current evolution step. That is, you should check only the last array to determine the neighbors. You should not change the last array however, only the next array, which represents the next generation of cells. Also, note that a cell is NOT considered a neighbor of itself.

Important Simplification!

Unless you'd like to extend the problem for extra credit, do not change the outermost edge of cells. This edge will always start out at all empty and -- if you do not change that -- it will always remain empty. As a result, the outermost edge of cells will be a kind of "fence" within which the life simulation will proceed. Thus, run your loops from 1 up to but not including length-1.

How does this help? This helps because when you ignore the outer edge, each cell has exactly 8 possible neighbors -- in the eight principal compass directions. There are no exceptions, and so adding up the contents of the neighbors is completely uniform!

Here are a few examples. As above, assume all of these examples are away from the edge of the grid:

Springing to life

In each of these two cases, the center cell (which was previously off) turns on because it has exactly three living neighbors.

Staying Alive

In each of these three cases, the center cell (which was previously on) remains on, because it has exactly two or three living neighbors.

Dying Off

In these three situations, the center cell dies off, because it is either overcrowded or too isolated.

Setting Up

Be sure to get the files from Hw9Pr2.zip for this problem! The CS5App.java file from Hw9Pr2.zip will have an empty update method for you to write. Its signature is

      public void update(int[][] last, int[][] next)

This method gets called whenever the program needs to compute the next generation of life cells, based on the last generation.

The 2d array last contains a 1 wherever there is a living cell and it contains a 0 wherever there is an empty (dead) cell. You need to use that information to fill the 2d array named next with the appropriate pattern of living and dead cells, based on the information in last. You will notice that the default colors for the cells are black (living) and white (empty). You may choose other colors if you'd prefer. See the main method where the colors are set, and feel free to experiment. (Don't change other code in main, however -- at least not without some caution... .)

It's not working! Keep in mind that the simulation does not start immediately when you run the program. You need to type r into the simulation window to start running. s will step one generation at a time, and q will quit. It's a good idea to maximize the window (the middle upper right button in Microsoft Operating Systems) so that it redraws fully before starting.

Part 2 Multi-species life! [10 points]

For this part, you need to fill in the provided method named updateMulti whose signature is

    public static void updateMulti(int[][] last, int[][] next)

This time, however, your task is to devise a set of rules that demonstrates two species of life cells (or "organisms") cohabitating in the life world. You may devise the rules however you like, and 1/2 credit will go to any working solution that has at least two species alive for some time. Full credit will go to solutions that enable the species to coexist at least somewhat -- so that neither of the two takes over the whole world nor goes exinct. Of course, this is a general goal -- unlucky, "bad" starting scenarios may lead to extinction.

Each cell's integer represents its contents (species) with

0 representing off (Color.white)
1 representing species 1 (Color.black)
2 representing species 2 (Color.red)

Your updateMulti method should assign the value of each next[r][c] cell, based on the values in the last[r][c] cells. I would suggest leaving the outermost edge as empty cells, just as in Part 1 to simplify the neighbor-counting.

Extra Credit The possiblities are wide-open. You may change the number of species (up to 10 or even further) -- you may experiment with predatory/prey-type behaviors or other biologically inspired rules. See below for additional extra credit possibilities. As a side note, this problem was a variant of John Conway's Game of Life suggested by Prof. Adolph, who points out that maintaining and modeling the balance required to have more than one species survive in an ecosystem remains an open research area in biology... .

Be sure to submit your CS5App.java file under homework 9, problem 2.

Extra Credit

Part 1: matrix inverse...

Specifically, you should add another option to the menu:

(6) Inverse!

and when that option is chosen, your program should

Check if the array (matrix) is currently square. That is, if the number of rows equals the number of columns. If not, you should print a warning message and return to the menu -- only square matrices have inverses!
If the array is square, you should compute its inverse and replace the current array with its inverse. How? One way to do this is to create an array with the same number of rows and twice as many columns as described at either of these URLs:
- http://www.tutor.ms.unimelb.edu.au/inverse/inverse_basic.html
- http://www.richland.cc.il.us/james/lecture/m116/matrices/inverses.html
(I found the first one a slightly simpler explanation if you're not familiar with matrices, inverses, etc. The second link explains why the technique actually works... .) You can then use the row operations for which you've already created methods in order to find the inverse. Finally, be sure to replace the original matrix with its inverse.

As with the solve method, you can assume that the matrix will have an inverse (it will not be singular or otherwise poorly behaved).

Part 2: more life!

For this part of the extra credit, you should extend the life program in some interesting or unusual way. One option is to let the life world "wrap around" so that the border cells are considered in updating the life generations (in the basic problem, the top and bottom rows and left and right columns are always intended to be empty). Then, consider the top row to be a neighbor to the bottom row and the left column to be a neighbor to the right column. This is tricky because you need to be sure you're not going out of bounds!

Alternatively, you could be more ambitious with your multiple-species life: you could use more species or put extra effort into your rules. If you do this, please add a paragraph at the top of your file in the comment that explains what you've done! Both the biological and medical sciences that use these kinds of cellular models -- for example, Lisette DePillis of the mathematics department uses 2d cellular automata of this sort to model tumor growth. In addition, there are active independent research fields called "cellular automata" and "artificial life" that explore the fundamental properties of such systems.

Submitting

You don't need to submit either extra credit separately -- simply submit them as the ordinary problem 1 or 2.