Designing and Implementing Algorithms_Solution

Specification 1: Designing and Implementing Algorithms
Method Descriptions:

1. Hamming Distance: "The 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.

/* Determine the Hamming distance between two arrays of ints. 
   pre: aList != null, bList != null, aList.length == bList.length
   post: return the Hamming Distance between the two arrays of ints. 
   Neither the parameter aList or bList are altered as a result of this method.
*/ 
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, 8, 4, 5, 4, 3, 5, 1} the Hamming distance is 2.

2. isPermutation: 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}.

/* Determine if listA is a permutation of listB.   
   pre: listA != null, listB != null
   post: return true if listB is 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)

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 too inefficient except for arrays with a very small number of items.

3. mostVowels: On method mostVowels you can use any and all parts of the String class and native arrays.

The mostVowels methods takes in an array of Strings as a parameter and determines which String has the most vowels.

For this method vowels are the characters '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". The String "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 the index of the String that has the largest number of vowels. 
   Vowels are defined as 'A', 'a', 'E', 'e', 'I', 'i', 'O', 'o', 'U', and 'u'.
   The parameter list is not altered as a result of this method.
   pre: list != null, list.length 0, there is an least 1 non null element in list
   post: return the index of the non-null element in list that has the largest number of characters that
   vowels. If there is a tie return the index closest to zero. 
   The empty String, "", has zero vowels. It is possible for the maximum number of vowels to be 0.
*/
public static int mostVowels(String[] list)

4. sharedBirthdays: The birthday problem is a question where most people's intuition is proved incorrect by mathematics. The problem is: Given a group of N people, how large must N be so that there is a 50% chance that at least 2 of the N people have the same birthday?

Write a method with two parameters, the number of people in a group and the number of days in the year. The method will generate random birthdays for the number of people and then determine how many pairs of people have the same birthday. You don't have to generate actual days of the year for the birthdays. You can simply use ints.

Here are two ways to generate random ints in Java. One uses an object of type Random and the other uses the random method from the Math class.

// fist approach
Random r = new Random();
int max = 10;
int x = r.nextInt(max);
// x will now hold a value between 0 and 9 inclusive.
// The distribution of values in uniform.

// second approach
int max = 10;
int x = (int) (Math.random() * max);
// x will now hold a value between 0 and 9 inclusive.
// The distribution of values in uniform.

If three people (Olivia, Kelly, Isabelle) who share the same birthday, that is 3 pairs of people:

pair 1: Olivia and Kelly
pair 2: Olivia and Isabelle
pair 3: Kelly and Isabelle
/* Perform an experiment simulating the birthday problem. 
   Pick random birthdays for the given number of people.   
   Return the number of pairs of people that share the same birthday.
   pre: numPeople 0, numDaysInYear 0
   post: The number of pairs of people that share a birthday after randomly assigning birthdays.
*/
public static int sharedBirthdays(int numPeople, int numDaysInYear) {

After completing the method run the following experiments:

Perform 1,000,000 experiments with 365 days per year and 182 people per experiment . What is the average number of pairs of people with shared birthdays? (Write a method to automate this experiment and put the code in CodeCamp.java.). Include your answer in a comment at the top of your CodeCampTester.java program.

How many people do you think it takes so there is a 50% chance that at least 2 of the people have a shared birthday in a 365 day year?

Perform 50,000 experiments with 365 days per year and vary the number of people from 2 to 100. 50,000 runs with 365 days, and 2 people, 50,000 runs with 365 days and 3 people, ... 50,000 runs with 365 days and 100 people. Total of 4,950,000 runs, 50,000 runs per experiments * 99 experiments = 4,950,000 runs. For each of the given number of people determine the percentage of experiments where at least one pair of people shared a birthday. At what number of people (between 2 and 100) does the percentage first exceed 50%? Does the answer surprise you? How did it compare to your predicted answer?

Include a table in a comment in your CodeCampTester.java program with the results of this experiment using the following format::

Num people: 2, number of experiments with one or more shared birthday: 120, percentage: 0.24
.....
Num people: 100, number of experiments with one or more shared birthday: 50000 , percentage: 100.0

At the top of the table state how many people it requires to have a 50% chance of there being at least 1 shared birthday, given a 365 day year.

5. queensAreSafe: 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.

.. 

Here is an example with 8 queens that are all safe:



Complete the method that checks if a given board represents a safe placement of Queens. Note, the board size may be different that 8 by 8.

/* Determine if the queens on the given board are safe.
   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)

6. valueOfMostValuablePlot: For this problem a 2d array of ints represents the value of each block in a city. Each element in the array is a city block. The value of a block could be negative indicating the block is a liability to own. Complete a method that finds the value of the most valuable contiguous sub rectangle in the city represented by the 2d array. The sub rectangle must be at least 1 by 1. (If all the values are negative "the most valuable" rectangle would be the negative value closest to 0.)

Consider the following example. The 2d array of ints has 6 rows and 5 columns per row, representing an area of the city. The cells with the white background represent the most valuable contiguous sub rectangle in the given array. (Value of 15.)

 

0
-2
-7
0
-1
9
2
-6
2
0
-4
1
-4
1
0
-1
8
0
-2
1
-10
1
1
-5
6
-15
-1
1
5
-4
Here is another example with the almost same 2D array with a single change. The value of the block at row 4, column 2 has been changed from 1 to 6. Given that configuration the most valuable contiguous sub rectangle in the given array has a value of 17 and is the cells with the white background.

 

0
-2
-7
0
-1
9
2
-6
2
0
-4
1
-4
1
0
-1
8
0
-2
1
-10
6
1
-5
6
-15
-1
1
5
-4
Another example. The whole 2d array is the most valuable sub plot:

3
2
13
7
9
2
0
6
14
1
5
4
Hint: Implement a brute force approach. The brute force approach is still complicated, but use helper methods to break the problem down into smaller, more manageable pieces.

/* Given a 2D array of ints return the value of the most valuable contigous sub rectangle 
   in the 2D array. The sub rectnagle must be at lest 1 by 1. 
   pre: mat != null, mat.length 0, mat[0].length 0, mat is a rectangular matrix.
   post: return the value of the most valuable contigous sub rectangle in city. 
   the 2d array city, is not altered as a result of this method call.
*/
public static int mostValuablePlot(int[][] city){

Expected length of solutions: My solutions to the problems above added about 210 lines to CodeCamp.java. That  includes many blank lines, lines with a single brace, and comments. About 130 actual lines of new code in my solution.