Placed online: Friday, September 5
20 points, ~2% of final grade
Due: no later than 11 pm, Thursday, September 18
General Assignment Requirements

1. Design and implement algorithms involving arrays and 2D arrays.

Complete the 8 methods in ArrayProblems.java. The methods are explained in further detail in the Tips section of this page. When completing the methods you are encouraged to break the problem up into smaller problems and create helper methods of your own to solve these smaller problems.

VERY IMPORTANT: For this assignment the only methods and classes from the Java standard library you may use in your final solutions are:

• any methods in the System class
• any methods in the Math class
• any methods in the Random class
• on the mostVowels method you can use any and all methods from the String class.
• Of course you can use the length field on native arrays(arr.length) and create and use other native arrays if you want to.

Note all the methods require that the parameter not be altered.
You can create local copies of the parameters and alter them if you would like.

ArrayProblems.java includes a main method with some tests for the methods. Some of these tests may be incorrect. You are required to find and fix any incorrect tests. Use the class listserv to share information about other students about which tests are in error and how to correct them. Your methods must pass the corrected tests. Add many more tests to the main method of ArrayProblems.java. You are encouraged to send your tests to the class listserv for other students to use.

Fill in the header for ArrayProblems.java. Replace <NAME> with your name. Note, you are stating, on your honor, that you did the assignment on your own, as required.

When finished turn in your ArrayProblems.java program using the turnin program.

• review the general assignment requirements?
• work on the assignment individually?
• fill in the header in your file ArrayProblems.java?
• implement the eight required methods?
• ensure your program does not suffer a compile error or runtime error?
• identify and correct any incorrect tests provided with the assignment?
• ensure your program passes the tests in the main method of ArrayProblems.java?
• add your own tests to the main method of ArrayProblems.java?
• turn in your Java source code in a file named ArrayProblems.java to the proper account in the Microlab via the turnin program before 11 pm, Thursday, September 18?

1. Hamming Distance. "Hamming distance between two strings of equal length is the number of positions for which the corresponding symbols are different. Put another way, it measures the number of substitutions required to change one into the other, or the number of errors that transformed one string into the other." From the Wikipedia article on Hamming Distance. For this problem you will be working with arrays of ints instead of String objects. Complete the following method in ArrayProblems.java

/**
* Determine the Hamming distance between two arrays of ints.
* Neither the parameter aList or
* bList are altered as a result of this method.
* @param aList != null, aList.length == bList.length
* @param bList != null, bList.length == aList.length
* @return the Hamming Distance between the two arrays of ints.
*/
public static int hammingDistance(int[] aList, int[] bList){

For example given the array {1, 2, 3, 4, 5, 4, 3, 2, 1} and the array {1, 2, 2, 4, 5, 4, 3, 1, 1} the Hamming distance is 2.

2. Permutations. This method determines if one int array is a permutation of another int array.

/*
  pre: listA != null, listB != null
  post: return true if listB is simply a permutation of listA, false otherwise. 
  neither listA or listB are altered as a result of this method.
*/
public static boolean isPermutation(int[] listA, int[] listB)

"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}.

Hint: Do not try to solve the problem by taking one the arrays and generating all the permutations of that array and then check to see if the other array is one of those permutations. That is much too inefficient except for arrays with a very small number of items.

3. Majority element.  This method determines if an array of ints contains a majority element.

/**
* Determine if there is a majority element in an array of ints.
* The parameter list is not altered as a result of this
* method.
* @param list != null
* @return the first index of the value of the majority element if it exists.
* If a majority element does not exist return -1.
*/

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 the index of the first occurrence of the majority element if one exists. If there is no majority element your method returns -1.

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.

4. Nearest Neighbor. Given an array of ints, find the indices of the pair of integers that have the smallest difference between them.

/** Find the two values in an array that are closest to
* each other. On other words find the two nearest neighbors.
* The parameter nums is not altered as a result of
* this method.
* @param nums The array of ints to find the nearest neighbors in.
* nums != null, nums.length >= 2
* @return Returns an array of length 2.
* The elements of the result are the indices of ints in
* nums that have the smallest distance (absolute value of
* difference) of any pair of ints in nums.
* If there is more than one pair of ints that meet this
* criteria returns the indices of the pair with the minimum index.
* If there is more than one pair of ints with the minimum
* index, returns the indices of the pair with the smaller s
* second index.
* The first element of the result is the smaller of the two indices.
* For example given the array {5, 3, 7, 10, 12} the method
* would return {0, 1}.
*/
public static int[] nearestNeighbors(int[] nums){

For example, consider the following array: {19, 0, -5, 4, 7, 10}

Here are the distances (absolute value of the difference) between the various pairs of elements.
 

Given the above values there are two pairs of ints that have a distance of 3 apart. The pairs are 4 and 7, and 7 and 10. The method would return an array with the indices 3 and 4 which are the indices of 4 and 7 in the array named nums.

5. String with the most vowels.  That determines which String in an array of Strings contains the most vowels. For this method vowels are defined to 'A', 'a', 'E', 'e', 'I', 'i',  'O', 'o', 'U', and 'u'. The method is not trying to determine which String has the largest number of distinct vowels. Thus "aaaaaa" has more vowels that "aeiou". "aaaaaa" has 6 vowels while the String "aeiou" only has 5 vowels. You can use whatever String methods you want when completing this method.

/**
* determine which String has the largest number of vowels.
* Vowels are defined to 'A', 'a', 'E', 'e', 'I', 'i', 'O', 'o', 'U', and 'u'.
* pre: list != null, list.length > 0, there is an least 1 non null element in list
* post: return the String in list that has the largest number of characters that are vowels.
* If there is a tie return any of the Strings that has the greatest number of vowels.
* param list the array to check
* return the String in list that has the greatest number of vowels.
*/
public static String mostVowels(String[] list)

6. Max Sum. Complete a method that determines which row or column in a 2d array of ints has the largest sum.

/**
* determine which row or column in a matrix has the largest sum.
* <p>pre: mat != null, mat.length > 0,
* mat is a rectangular matrix, mat[0].length > 0
* <p>post: determine which row or column of ints has the maximum sum in max.
* If a row contains the maximum sum, return a string starting with "R" and
* then the number of the row with no spaces. For example "R0" or "R12". If a
* column contains the maximum sum, return a string starting with "C" and then
* the number of the column with no spaces. For example "C0" or "C12".
* If there is more than one row or column with the maximum sum
* return rows over columns first, then smaller indices over
* larger indices.
* Thus if rows 3, 5, * and 12, and columns 0 and 2 all contained
* the same maximum sum the method would return "R3".
*/

7. Are the queens Safe? There is a chess and programming problem called the 8 queens problem. The goal is to place eight queens on a chess board so that none of them may attack any other queen. That is, no two queens are in the same row, column, or diagonal. In chess a queen may move any number of spaces straight up, down, left, right, or along any of the 4 diagonals. In the method you are completing the board is square (same number of rows as columns) but is not necessarily 8 by 8.

Consider the following board:

A queen's position is designated with the Q. The red arrows show the squares that queen can attack. Thus if there were a queen in any of those squares this would be an unsafe board. So the following set up is unsafe.

The following set up is safe, but the number of other safe squares is going down fast.

..

Complete a method that checks if a given board represents a safe placement of Queens.

/*
 pre: board != null, board.length > 0, board is a square matrix. (In other words all rows in board have board.length columns.), all elements of board == 'q' or '.'. 'q's represent queens, '.'s represent open spaces.
 post: return true if the configuration of board is safe, that is no queen can attack any other queen on the board. Return false otherwise.
 The parameter board is not altered as a result of this method.
*/
public static boolean queensAreSafe(char[][] board)

8. Skyline. (Based on a problem developed by James Goodwin.)  Given a 2 dimensional array of ints that represents the height of the buildings  in a downtown area create and return a String that shows what the what the downtown area would like when viewed from the West towards the East.

The top, left corner of the 2d array of ints that contains the height of the buildings is the Northwest corner of the area.

Instead of using true perspective (where buildings would look smaller in the distance), show a simple projection of the buildings. Each visible building should be represented with an integer from 1 to 9 (inclusive) indicating the distance of the building from the observer, with 1 being the closest possible building (i.e., one that's in the leftmost column of the overhead view). The 2d array of ints that contains the heights of the building will have between 1 and 9 columns inclusive. All elements of the 2d array will be between 0 and 9 inclusive.

The output view should always be as high as the tallest building, with periods used to fill in space above buildings that are not as tall as the tallest building.

Here is an example. Consider the following 2d array of ints of the heights of the buildings.
 

3	1	5	0	4
1	4	1	1	4
1	2	5	0	0

Recall that the character for a building is its distance from the viewer. Thus all buildings in the left most column will be represented with 1s, all buildings in the next columns will be represented with 2s and so forth.

The resulting String would be:

3.3
323
123
122
111

/**
* Given an overhead map of a city, show what the
* city would look like from the West.
* @param heights The city as viewed from above.
* heights != null, heights is a rectangular
* matrix. heights.length > 0, 0 < heights[0].length < 10
* All elements of heights will be between 0 and 9 inclusive.
* @return A String that shows what the town represented
* by heights would like like from the West.
*/
public static String skyline(int[][] heights){