Homework 09

Assignment: 2 problems, 30 points for #1 and 20 points for #2 (plus up to 20% extra credit, 10% for additional modifications to each), due on

• 11:59 pm on Sunday, October 30, 2005 (M/T sections)
• 11:59 pm on Monday, October 31, 2005 (W/Th sections)

Reading: Your CS5 lecture notes and the online readings for week 9.

Problem 1     Gaussian Elimination     (30 points)     [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 main program should be structured as follows:

1. Ask the user how many rows and columns to include in the desired 2d array.
2. Create a 2d array of doubles with the desired number of rows and columns.
3. 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. 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.
4. Enter a loop that presents the user with the menu:

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

The bulk of this problem's work lies in implementing the different options on this menu. In doing so, you should implement the following methods:

• public static void printMenu() should simply print out the above menu. The loop around this menu and user's choice should be handled in main.
• public static void enterValues(double[][] A) should 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) 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) 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) 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) 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) 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 
  

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:

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.

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

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):

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:

Thus, the solution of these equations is:

Important Notes:

• 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.
• 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.

Submission: Be sure to submit your CS5App.java file under homework 9, problem 1. If you decide to also do the extra credit, simply add that code to this file when you submit it (and indicate in the header comments that you did the extra credit).

Extra Credit (up to 5 points): Add another option to the menu:

      (6) Inverse!

1. 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!
2. 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 provides a slightly simpler explanation if you're not familiar with matrices, inverses, etc.
   • http://www.richland.cc.il.us/james/lecture/m116/matrices/inverses.html is a bit more complicated, but explains why the technique 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).

Problem 2     Life     (20 points)     [topics: 2d arrays]

Problem 2 is this homework's Pair Programming problem and should be worked on in groups of two as described at http://www.cs.hmc.edu/cs5/pair_programming.html.

LIFE Part 1:    John Conway's Original Game of Life is worth 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. This simplification is your friend because it means you can run your loops from 1 up to but not including length-1, eliminating the need to handle the more complicated "boundary cases" in which a cell is not always surrounded by exactly 8 neighbors.

Below are some examples that demonstrate the rules of life in action. In each example, we only focus what happens to the center cell.

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.

The Life Problem Set Up:

Be sure to get the files from Hw9Pr2.zip for this problem! The CS5App.java file from Hw9Pr2.zip will have a bogus update method that currently just toggles the cells from alive to dead.

public void update(int[][] last, int[][] next) gets called whenever the program needs to compute the next generation of life cells, based on the last generation. As discussed briefly in class, the update function is called periodically (every p milliseconds) by a periodic timer that is provided with the GrLife object. You don't need to worry about the details---the main point is that each time update is called, the most recent values of the grid are stored in last and your job is to apply the rules of life to these most-recent values in order to create the next generation of values, storing them in next. In this method, values of zero correspond to dead (white) cells; values of one are alive (black).

But my LIFE ain't running!?!?!?! The simulation does not start immediately when you run the program: you need to type r in the simulation window to start running. s will step one generation at a time, and q will quit. To aid in debugging, you can also toggle the value of a cell (by shift-clicking). 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.

LIFE: Part 2: For another 10 points, extend the original game to accommodate multiple species---in particular two (as opposed to just one) type of "living" organism. To do this, you need to fill in the provided method public static void updateMulti(int[][] last, int[][] next).

Your task in this part includes devising a set of rules that allows the life cells to cohabit 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, however, requires rules that enable the species to coexist at least somewhat -- so that neither of the two takes over the whole world nor goes extinct. Of course, this coexisting is a an "average" goal --- it is always possible to get unlucky if one gets a "bad" random initial configuration.

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

• 0 representing no species alive (Color.white)
• 1 representing species 1 alive (Color.black)
• 2 representing species 2 alive (Color.red)

Submission: Be sure to submit your CS5App.java file under homework 9, problem 2. If you decide to also do the extra credit, simply add that code to this file when you submit it (and indicate in the header comments that you did the extra credit).

Extra Credit (up to 5 points): For this extra credit part, the possibilities are wide open! The main criteria is that you 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. The tricky part about this change is handling all of these "boundary cases" properly (and not getting out-of-bounds errors!).

Another possibility would be to extend your multiple-species life to allow more than 2 species and/or to put more energy/effort into the rules each species uses to propagate itself. If you do this, please add a paragraph at the top of your file in the comment that explains what you've done! Both biological and medical sciences 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. And Prof. Adolph pointed 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! There are also active independent research fields called "cellular automata" and "artificial life" that explore the fundamental properties of such systems.