Due dates: This lab is for you (individually) to start on now, work on during the week of September 4-11, work on (with help from the TA if needed) during your lab on September 11, then turn in completed at the beginning of lab on September 18.

Demo:  You will be expected to demo the running program for the TA at the beginning of lab Monday, September 18. Do not think that you will get a bug or two out of the program before your demo on the morning of lab.

VERY IMPORTANT: For this assignment only, the only methods and classes from the Java standard library you may use in your final solutions are:
1. the System.arraycopy method
2. the Math class and any of its methods
3. the Random class and any of its methods

Problem: You are given a Java program, ArrayProblems.java that needs to be modified.

It consists of:
• Five public methods that work with arrays.
  These are just program stubs; Your job is to write the methods
• A main method that tests the five methods above. Some of these tests may have errors in them. You are to fix the errors, and devise additional tests if you think the methods are not throughly tested.
• Several private methods that you may find helpful in writing the above methods.

The methods for you to write:

1. public static boolean isPermutation(int[] listA, int[] listB)
   • Permutations. This method determines if one int array is a permutation of another int array.
   • "A permutation, also called an "arrangement number" or "order," is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself." [mathworld.wolfram.com] For example the list {1, 2} has the following permutations; {1, 2} and {2, 1}.
   • Note the elements of listA and listB are lists, not sets, so duplicate items could appear. So for example given the list {1, 2, 2} the unique permutations are {1, 2, 2}, {2, 1, 2}, and {2, 2, 1}. {2, 1} is not a permutation of {1, 2, 2}. Another example of lists that are not permutations of each other: {2, 1, 1} is not a permutation of {2, 2, 1}.

2. public static int findMajority(int[] list)
   • Majority element. This method determines if an array of ints contains a majority element.
   • A majority element in an array A of size N is an element that appears more than N/2 times. Thus there is at most one such element. For example the array
     
     index 0 1 2 3 4 5 6 7
     element 3, 4, 4, 4, 2, 4, 2, 4
     
     has a majority element equal to 4.
     
   • Note your method returns an index of an element from the array that holds a majority element, not the value of the majority element itself. Your method can return any of the valid indices from the array. In this case the majority element is equal to 4 and any index of an element that holds 4 can be returned, either 1, 2, 3, 5, or 7.
   • The following array does not have a majority element:
     
     index 0 1 2 3 4 5 6 7
     element 3, 3, 4, 4, 2, 4, 2, 4
     
   • To be a majority element it must appear more than N/2 times where N is equal to the list. With a list of length 8 there must be at least 5 elements equal to one another for there to be a majority element. Your method shall return -1 if an array does not contain a majority element.

3. public static int[] shuffle(int[] original)
   • Shuffle. This method shuffles an array of ints.
   • For example if original is equal to the int array {1, 2, 3} there are 6 possible arrays that could be returned:
     1. {1, 2, 3}
     2. {1, 3, 2}
     3. {2, 1, 3}
     4. {2, 3, 1}
     5. {3, 1, 2}
     6. {3, 2, 1}
   • Your method should return one of these with roughly uniform probability of any one of the permutations being chosen. (Note, generating all possible permutations and picking one of them is an extremely inefficient way completing this method.)

   • You will have to generate random integers to complete this method. There two ways to do this:
     1. Use the Math.random method. This returns a double uniformly distributed between 0.0 inclusive and 1.0 exclusive. If you wanted to generate a random number between 0 and 9 inclusive the following code does the job:
        
        int x = (int) ( 10 * Math.random() );
        
        If you wanted to generate a random integer between 1 and 10 the following works:
        
        int x = (int)(10 * Math.random() ) + 1 ;
        
        More generally if you want to generate a random int with a given range and a given first value the code would be:
        int x = (int)(range * Math.random() ) + first_value;

     2. Use the Random class from the Java standard library. The Random class is the the java.util package so you have to include the line
        import java.util.Random;
        outside the ArrayProblems class.
        • To generate Random integers using the Random class create an object of type Random and call its nextInt(int n) method.
        • This method "Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence."
          Random randNumGen = new Random();
int x = randNumGen.nextInt(range);

4. public static boolean nonDecreasing(int[] list)
   Non decreasing elements.  Write a method that determines if the elements of an array are non-decreasing. That is each element is greater than or equal to the previous element. The check begins with index 0 and continues to the end of the array.

5. public static int sudokuStatus(int[][] board)
   • SUDOKU. Sudoku is a puzzle that has become quite popular in the past year. The puzzle consists of a 9 by 9 grid with some elements already filled in with an integer between 1 and 9 inclusive. The goal is to fill in the empty cells with values between 1 and 9 so that every row, column and the nine 3 by 3 sub regions all contain the digits 1 through 9. See the Wikipedia entry for more information.
   • You will write a method that will examine a 9 by 9 matrix of ints representing a Sudoku board. Evaluate the matrix and determine the status of the board. The possible outcomes are:
     • solved. In this case return a 0
     • incorrect due to illegal value. The board should contain integer values between 0 and 9. 0 is used to represent an open space. If any value other than 0 through 9 is present return a 1.
     • incorrect due to repeated value. If a board contains duplicate values between 1 and 9 in any row, column, or any of the nine 3 by 3 sub regions return a 2. Note, duplicate 0s are okay because they represent open spaces.
     • in progress. The board has not been solved but the current configuration is legal. That is there are no duplicates values between 1 and 9 in any row, column, or any of the nine 3 by 3 sub regions. In this case return a 3