CIT 591 Assignment 7: Saddle Points
Fall 2010, David Matuszek

Purposes of this assignment

General idea of the assignment

   
Min
   
012
Max
0
1
2
3
 -9  12  -6
  7  14   5
 10  -8   3
  6  17 -10

Consider the following very simple "game." There is a two-dimensional array of numbers, and two players, Max and Minnie. At each turn, Max chooses some row and Min chooses some column. Where they intersect is the amount of money Min pays to Max (if it's negative, Max pays Min).

For example, if Max chooses row 1 and Min chooses column 1, then Max wins $14 from Min. But if Max chooses row 3 and Min chooses column 2, then Max pays Min $10. In general: Max wants larger numbers, Min wants smaller numbers.

How should they play?

Details

Name your class SaddlePoints.

Saddle points

   
Min
 
   
0 1 2
 
Max
0
1
2
3
 -9  12  -6
  7  14   5
 10  -8   3
  6  17 -10
-9
5
-8
-10
  
10 17 5

For each player, we pick the "best of the worst." In this example, the worst Max can do if he picks row 0 is -9; if row 1, then 5; if row 2, then -8; and if row 3, then -10. Of these possible worst outcomes, Max prefers the largest, which is 5 (row 1).

Similarly, Min wants smaller numbers. The worst she can do if she picks column 0 is 10; if column 1, then 17; and if column 2, then 5. Of these possible worst outcomes, Min prefers the smallest, which is 5 (column 2).

Since the "best of the worst" (the maximum of the minimums) for Max is 5, and the "best of the worst" (the minimum of the maximums) for Min is also 5, then Max should always choose row 1, and Min should always choose column 2. This is called a saddle point.

Here's why: If Min does choose column 2, then Max will do worse by choosing any other row. And if Max does choose row 1, then Min will do worse by choosing any other column.

It is possible for there to be more than one saddle point, in which case they will all have the same value (for example, they will all be 5), and we don't care which one we find.

JUnit tests for saddle points

This program is a lot easier to test if it consists of a lot of little methods. Write the tests first!

To write tests first:

  1. Write "stub" methods. A stub method is a method that has the correct name and parameters, but returns a fixed (preferably nonsense) value. For example:
         int getLargestValue(int[] array) { return 9999; }
  2. In Eclipse, select your class, then go to File → New... → JUnit Test Case, choose New JUnit 4 Test, enter a name for your test class, make sure the setUp() method is checked, then click Next>. Check the methods for which you want to create test cases. Then click Finish.

The first time you try to create a JUnit test, Eclipse will tell you that JUnit isn't on your "build path," and will offer to add it. Let Eclipse add it. Depending on your installation, Eclipse may already know where to find it, or it may ask you to find it.

You don't have to create your unit tests this way. It's just a normal Java file--to add tests, just imitate the tests that are already there.

Here are the computational methods you should have. You should have unit tests for each of these methods.

int[][] createRandomArray(int numberOfRows, int numberOfColumns, int minValue, int maxValue)
Creates and returns an array of the given size and fills it with random values in the specified range.

int largest(int[] array)
Finds the largest value in an array of integers.

int smallest(int[] array)
Finds the smallest value in an array of integers.

int[] largestValues(int[][] array)
Takes a two-dimensional array of integers and returns a one-dimensional array containing the largest values in each column (such as the array [10, 17, 5] in the above example).

int[] smallestValues(int[][] array)
Takes a two-dimensional array of integers and returns a one-dimensional array containing the smallest values in each row (such as the array [-9, 5, -8, -10] in the above example).

boolean hasSaddlePoint(int[][] array)
Takes a two-dimensional array of integers and returns true if it has a saddle point and false if it does not.

int saddlePointRow(int[][] array)
Takes a two-dimensional array of integers that is known to have a saddle point, and returns the row number of that saddle point. If there is more than one saddle point,

int saddlePointColumn(int[][] array)
Takes a two-dimensional array of integers that is known to have a saddle point, and returns the column number of that saddle point.

Here are the methods for which you do not need unit tests:

public static void main(int String[] args)
Calls a run method to create arrays various sizes (including some 2x2 arrays and some larger), fills them with random values, and prints each array and information about it. Keeps generating arrays until it has printed at least one with and one without a saddle point. (Smaller arrays are more likely to have a saddle point; about half of randomly generated 2 by 2 arrays will have one.)

public static void printArray(int[][] array)
Prints the array.

public static void printArrayInfo(int[][] array)
Prints whether the given array has a saddle point, and if so, where it is (row and column) and what its value is. (If there are multiple saddle points, just print any one.)

Arrays in Java

Arrays in Java are like lists in Python, and are indexed the same way. However, the size of an array is specified when you create the array, and you can't add or delete elements. (You can, however, assign a different array to the variable.) You can declare arrays like this:

Declared in this way, all locations in the new array contain null, zero, or false, depending on the type of the array. You can put specific values in an array when you declare it (but not later) like this:

To use a literal array in a statement, rather than in a declaration, the syntax is a little different:

For testing purposes, you can use the above game,

     int[][] with = {{-9, 12, -6},
                     { 7, 14,  5},
                     {10, -8,  3},
                     { 6, 17,-10}};


which has a saddle point, and the game

     int[][] without = {{ 1, -2,  3},
                        {-6,  5, -4},
                        { 7, -8,  9}};

which does not.

JUnit tests in Java

Here's the general structure you need. This is a separate class, so Eclipse will put it in a separate file.

package saddlepoints;

import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;

/**
 * @author Your name goes here
 * @author Your partner's name goes here
 *
 */
public class SaddlePointsTest {
    SaddlePoints sp = new SaddlePoints(); // create an instance variable
    // If you use the same variables in multiple tests,
    //  declare them here
    
    @Before
    public void setUp() throws Exception {
        // If you use the same variables in multiple tests,
        //  assign values to them here
    }
    
    @Test
    public void testSomeMethod() {
        // Put tests here
        // Put sp. in front of every call to a method in SaddlePoints
    }
}

Here are some of the more useful JUnit methods:

The method createRandomArray(numberOfRows, numberOfColumns, minValue, maxValue) should return a different value every time, but you can still test it. Testing whether it's "really random" is difficult, but the following tests are pretty easy:

Grading

No more Mr. Nice Guy. Grading is difficult enough when students do what the assignment says to do. It's much harder to grade program that are "loosely based" on the assignment. Programs either do what they are supposed to, or they don't. If the assignment isn't clear about something, ask, and ask early; you may forestall a lot of problems that way.

The majority of points that have been lost on programming assignments, have been lost because students did not read the assignment carefully. If your "one little mistake" causes you to fail a lot of my tests, you will lose a lot of points.

This really isn't that difficult. When I specify what the parameters to a method should be, make sure it accepts exactly those parameters. (It's okay if your method is prepared to handle additional values, such as uppercase as well as lowercase, but it should accept at least what I say it should accept!) When I say what the result should be, return that result. Oh, and use the method name as given. That isn't so much to check.

If there is an error in my tests, then you have something to complain about, and I will listen. If you think I should give you a good grade because your program "seems to work," even though it fails correctly-written tests, I'm not likely to be very sympathetic.

Due date

Thursday, October 29, before midnight. Zip your entire project folder and submit it via Blackboard. Email submissions will go directly into the trash bin.