ITI 1220 Assignment 7

Available: Wednesday November 9

Due: Monday November 21, noon

Instructions

This assignment is to be done in TEAMS OF TWO PEOPLE. The assignment should be submitted only once by a member of your team, but please ensure that the identification material contains the information for both team members. Follow the assignment submission instructions and coding guidelines from the course lab manual.

For this assignment, if the question asks for a recursive algorithm, there will be a major penalty for not using recursion.

Marking scheme:

Regulations and standards: 10 marks
Question 1: 25 marks
Question 2: 35 marks
Question 3: 30 marks

Question 1 (25 marks total)

Suppose that you have an array that is known to be sorted already. A method known as binary search is an efficient method of determining whether or not a given value is contained within the array.

Here is how it works. Suppose we want to determine if the value findMe is in the array or not. Start with the value in the array that is in the “middle” position; let’s call this midValue. [The exact point will depend on whether the array length is even or odd.] Compare findMe with midValue. If findMe is greater than midValue, then the value would have to be in the second half of the array. If findMe is less than midValue, the value would have to be in the first half of the array. If findMe is equal to midValue, then we have found the value we are looking for.

If we did not locate the value findMe on the first try, we can reduce the size of the problem to locating the value in just half of the original array, since we know which side of the middle the value would be located on, if it were present. We can continue this process recursively until the part of the array we need to search is so small that it is a base case where the result can be determined immediately.

It may be that findMe is not in the array. If the array size is reduced to 2, the value findMe is larger than the value at position 1, and the value findMe is smaller than the value at position 2, findMe is not contained in the array. Likewise, if the array size is reduced to 1, and findMe is not the single value in the array, findMe is not contained in the entire array.

Part a) (20 marks)

Write a recursive method to perform a binary search for a given integer findMe between the indices leftIndex and rightIndex of an array of integers valueList.

You can assume that leftIndex <= rightIndex, and that valueList has length sufficiently large that valueList[rightIndex] exists.

Your method should be in the class BinarySearch and have the following header:

public static boolean searchRec( int[] valueList, int findMe, int leftIndex, int rightIndex )

Part b) (5 marks)

Sometimes, recursive methods need extra information when they call themselves and a “starter” method is used to make the interface simpler for a user. For example, if the recursive method wants to search for a value in part of the array specified by two end points, we do not want to have to require the user of the recursive method to specify “search between positions 0 and n – 1” when starting the search. Instead, we can use a “starter” method that has a simpler interface, and it has the function of starting the recursion by making the initial call to the recursive method.

Write a starter method to start the recursive binary search for a given integer within an array of integers. The method should be in the class BinarySearch, and should have the following header:

public static boolean search( int[] valueList, int findMe )

For this question, you do not have to provide a main() method. However, it is strongly recommended to run some JUnit tests on your search() method. When testing, remember that valueList has to be a sorted array.

Question 2 (35 marks total)

Permutations are re-arrangements of a set of items, where each member of the set must appear in an ordering of the items. For example, if we have the three letters A, B, and C, these letters can appear in the following orders:

ABC

ACB

BAC

BCA

CAB

CBA

Therefore, there are 6 different permutations of the letters ABC.

The number of permutations of n items is known to be n! Suppose that p(n) is the number of ways to order n items. Clearly, there is only 1 way to order items in a set of size 0, and so p(0) = 1. For larger sets of size n > 0, one can choose n items for the first possible letter, and then you have p(n – 1) ways of re-ordering the remaining letters. Therefore, p(n) = n × p(n – 1). This is essentially the definition of the factorial function, and so p(n) = n!

The strategy in the above argument can be used to generate the entire set of permutations of a string of letters, and that is your task in this question. Suppose that the original string is ABC. We can create the set of permutations as follows:

Select one of the letters. For example, choose B. The remaining letters are AC.
Find all permutations of the remaining letters. For example, find all permutations of the smaller string AC (recursion!)
For each permutation of AC, concatenate B onto the end.
Repeat this for every letter in the original string.

For the example ABC:

Choose A. Remaining string is BC. Permutations of BC found recursively are { BC, CB }. Add A to each giving { BCA, CBA }
Choose B. Remaining string is AC. Permutations of AC found recursively are { AC, CA }. Add B to each giving { ACB, CAB}
Choose C. Remaining string is AB. Permutations of AB found recursively are { AB, BA }. Add C to each giving { ABC, BAC }

Therefore, the set of permutations of ABC is { BCA, CBA, ACB, CAB, ABC, BAC }

Part a) (25 marks)

Design a recursive method to generate all permutations of a string using the strategy described above. Your method should be in the class A7Q2 and have the following header:

public static String[] permute( String aString )

Note that your method will need to create the array to be returned, and this array should have the correct length for the number of permutations to be generated.

Part b) (10 marks)

Write a main() method in class A7Q2 that will ask the user to enter a string, and then print all permutations of the string, one on each line.

Question 3 (30 marks)

Suppose that we have a metallic plate, and we are sampling the temperatures of the plate at 100 points arranged in a 10 ×10 grid. A small part of the plate is being exposed to heat, and the edges of the plate are cooled by a refrigeration system. We would like to determine the “steady state” temperature of the points on the plate; these are the temperatures at which the sample points will eventually stabilize after the heat source is applied.

The following are the initial conditions:

Points at any edge of the grid are constrained to have a fixed temperature of 20.0 degrees Celsius.
The point at row 2, column 7 (indices numbered from 0 to 9) is exposed to the heat source, and is always at 100.0 degrees Celsius
All other points on the plate have initial temperatures of 50.0 degrees Celsius.

	0	1	2	3	4	5	6	7	8	9
0	20.0	20.0	20.0	20.0	20.0	20.0	20.0	20.0	20.0	20.0
1	20.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	20.0
2	20.0	50.0	50.0	50.0	50.0	50.0	50.0	100.0	50.0	20.0
3	20.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	20.0
4	20.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	20.0
5	20.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	20.0
6	20.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	20.0
7	20.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	20.0
8	20.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	50.0	20.0
9	20.0	20.0	20.0	20.0	20.0	20.0	20.0	20.0	20.0	20.0

A method of estimating the steady state temperatures is as follows. Recalculate the temperature at each point in the grid by taking the average of the four nearest points (left, right, up, down) on the grid. In particular:

This calculation is performed for every point in the interior of the sample grid. The fixed points – the points on the edges, plus the point with the heat source – do not change.

This process is applied repeatedly until the temperature change between two consecutive matrices is sufficiently small at every sample point on the grid. Specifically, if the absolute value of the difference between the old temperature and the new temperature is calculated at every sample point, the maximum of any such differences should be less than 0.01 degree.

Be careful not to mix the new temperature values with the previous temperature values. That is, you should put the new values in a second matrix so that the original values are still available for use to calculate other nearby average values. Once you have finished the entire matrix, then the “new” matrix becomes the “original” matrix for the next repetition.

Write a program that will set up the initial conditions in a matrix, and print the matrix. Each value should have 3 digits to the left of the decimal, and two digits to the right of the decimal. The program should use the averaging formula to update the temperatures (except for the fixed points), and keep going until the maximum update at any point is less than 0.01. Each time the entire matrix is updated, the maximum temperature difference should be printed. Then, the final steady state matrix should be printed.

Sample output:

Initial conditions:

020.00 020.00 020.00 020.00 020.00 020.00 020.00 020.00 020.00 020.00

020.00 050.00 050.00 050.00 050.00 050.00 050.00 050.00 050.00 020.00

020.00 050.00 050.00 050.00 050.00 050.00 050.00 100.00 050.00 020.00

020.00 050.00 050.00 050.00 050.00 050.00 050.00 050.00 050.00 020.00

020.00 020.00 020.00 020.00 020.00 020.00 020.00 020.00 020.00 020.00

Maximum difference is 15.00

Maximum difference is 6.25

(…many more lines…)

Maximum difference is 0.01

Steady state:

020.00 020.00 020.00 020.00 020.00 020.00 020.00 020.00 020.00 020.00

020.00 020.90 022.02 023.67 026.38 031.06 038.89 048.25 034.13 020.00

(... and the rest of the steady state grid)

The following code can be used print a matrix of double values with 3 mandatory digits to the left of the decimal point, and 2 mandatory digits to the right of the decimal point:

import java.text.DecimalFormat;

public static void printMatrix( double[][] aMatrix )

{

// DECLARE VARIABLES / DATA DICTIONARY

DecimalFormat df; // Used to format numbers

int row;

int col;

// BODY OF ALGORITHM

// In the format string, 0 represents a mandatory digit

df = new DecimalFormat( "000.00" );

// Print each value in matrix

for ( row = 0; row < aMatrix.length; row = row + 1 )

{

for ( col = 0; col < aMatrix[row].length; col = col + 1 )

{

System.out.print( df.format( aMatrix[row][col] ) + " " );

}

System.out.println();

}

// RETURN RESULT

return;

}