CIT 590 Assignment 8: Saddle Points
Fall 2015, David Matuszek

# Purposes of this assignment

• To give you some experience with arrays
• To give you more practice with Java and JUnit

# General idea of the assignment

Min
0 1 2
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

You should have two classes, `SaddlePoint` and `SaddlePointTest`. These should be in separate files in the `src` subdirectory of your project.

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

Write the tests first.

 To write tests first: 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; }``` In Eclipse, select your class, then go to File --> New... --> Java --> JUnit --> JUnit Test Case, make sure the `setUp()` method is checked, click Next>, and 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. If you have to find it, pick the Libraries tab, choose Add External JARs, and find it. It is probably in a place like eclipse > plugins > org.junit_3.8.1 > junit.jar. 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 methods and unit tests you should have (where each test is for a single method):

```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 range `minValue` to `maxValue`, inclusive. (To get random integers, first import `java.util.Random.*;`, then create an object of type `Random`, then ask the object to give you the `nextInt(bound)`. This will give you a random integer `x` in the range ```0 <= x < bound```.
`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, return the row number of any 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. If there is more than one saddle point, return the column number of any one saddle point.

Each of these methods can be declared `public` (but they don't have to be) and should be `static` (but they don't need to be).

 Important note: The JUnit method `assertEquals` does not work for arrays. However, there is a method      ```static boolean equals(int[] array1, int[] array2) ```in the `java.util.Arrays` class.

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.

## The main program

Your class should be named `SaddlePoint`, and it should have these methods:

`public static void main(String[] args)`
Creates arrays of 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.)

## Testing notes

Write unit tests for all except the `main`, `printArray`, and printArrayInfo methods.

Testing methods that use randomness is interesting, since you cannot know exactly what they will produce. However, you can test whether the result satisfies the required conditions. Specifically, the `testCreateRandomArray` method should test that:

• The array has the requested number of rows and columns.
• All the numbers in the array are in the specified range.
• Not all the numbers in the array are equal. (This could happen even if your code is correct; but by choosing a larger array or a larger range of values, you can make it extremely unlikely--say, once in a trillion times.)
• The rows are not all the same row.

# Due date

Turn in your one zip file to Canvas by 6am Wednesday, October 28.