Programming Assignment 1 Solution

The purpose of this assignment is to gain experience implementing recursive algorithms in Java. You will write five recursive methods with headings




static void reverseArray1(int[] X, int n, int[] Y)

static void reverseArray2(int[] X, int n, int[] Y)

static void reverseArray3(int[] X, int i, int j)

static int maxArrayIndex(int[] X, int p, int r)

static int minArrayIndex(int[] X, int p, int r)




Functions reverseArray1() and reverseArray2()are similar to the functions of the same names in the example Reverse.java posted on the class webpage




https://classes.soe.ucsc.edu/cmps012b/Spring16/Examples/Lecture/Recursion/Reverse.java




which were discussed in class. These two functions will copy the elements in the input array X[] into the output array Y[] in reverse order (instead of printing them to stdout, like the examples in class.)




Function reverseArray1() will copy the leftmost n elements in X[] into the rightmost n positions in Y[] in reverse order. It will do this by first copying the nth element from the left in X[] into the nth position from the right in Y[], then calling itself recursively to place the leftmost − 1 elements in X[] into the rightmost − 1 positions in Y[] in reverse order. The recursion 'bottoms out' when the length of the subarray being reversed is zero, in which case the function returns without doing anything. To reverse the entire array, one calls reverseArray1() with n equal to the length of the input array X[]. It is assumed that the calling function has allocated the output array Y[] before the function is called.




Function reverseArray2() performs a 'dual' procedure. Its description can be obtained by interchanging the words 'left' and 'right' everywhere you see them in the preceding paragraph.




Function reverseArray3() is very different from the first two functions in that it actually alters the order of the elements in X[], rather than just copying them in reverse order into another array. This function reverses the subarray X[i,..,j] consisting of those elements from index i to index j, inclusive. It does this by first swapping the elements at positions i and j, then calling itself recursively on the subarray X[i+1,...,j-1] from index + 1 to index − 1. To reverse the entire array, one calls reverseArray3() with i equal to 0 and j equal to X.length-1.




Function maxArrayIndex() returns the index of the maximum element in the subarray X[p,..,r], and function minArrayIndex() returns the index of the minimum element in the same subarray. These follow a procedure similar to that of function mergeSort()which can be found on the webpage at




https://classes.soe.ucsc.edu/cmps012b/Spring16/Examples/Lecture/Recursion/MergeSort.java




and which will be discussed in class. Function maxArrayIndex() operates as follows. If subarray X[p...r] contains just one element, its index is returned. If subarray X[p...r] contains more than one element, the middle index is computed as q=(p+r)/2, the indices of the maximum elements in subarrays A[p...q] and A[q+1...r] are computed recursively, then the index of the larger of the two maxima is




1
returned. Function minArrayIndex() follows a similar procedure to return the smallest value in the subarray A[p...r].




All these methods will be inserted into a class called Recursion, and will be called from function main() defined below.




public static void main(String[] args){




int[] A = {-1, 2, 6, 12, 9, 2, -5, -2, 8, 5, 7}; int[] B = new int[A.length]; int[] C = new int[A.length];




int minIndex = minArrayIndex(A, 0, A.length-1); int maxIndex = maxArrayIndex(A, 0, A.length-1);




for(int x: A) System.out.print(x+" ");




System.out.println();




System.out.println( "minIndex = " + minIndex );

System.out.println( "maxIndex = " + maxIndex );




reverseArray1(A, A.length, B);

for(int x: B) System.out.print(x+" ");

System.out.println();




reverseArray2(A, A.length, C);

for(int x: C) System.out.print(x+" ");

System.out.println();




reverseArray3(A, 0, A.length-1);




for(int x: A) System.out.print(x+" ");

System.out.println();




}




The output of this program will be the six lines




-1261292-5-2857

minIndex = 6

maxIndex = 3

758-2-5291262-1

758-2-5291262-1

758-2-5291262-1




Place your functions, along with function main() above in the class Recursion, and place that class definition in a file called Recursion.java. A template for this file will be placed on the examples section of the webpage. As you write your functions, test them on many different input arrays to thoroughly check their operation. When you submit the project though, include function main() exactly as written above.




Write a Makefile that creates an executable jar file called Recursion. Include a clean utility that removes all .class files and the executable jar file from the current directory. (See lab1 to understand how to do all this.) Submit the files README, Makefile, and Recursion.java to the assignment name pa1 by the due date.







2