LAB 12

[1] Suppose that we have an array called list initialized as follows: (1 pts)

int[] list = {-2, 8, 13, 22, 25, 25, 38, 42, 51, 103};

This would construct the following array:

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]

+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+

| -2 | 8 | 13 | 22 | 25 | 25 | 38 | 42 | 51 | 103 |

+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+

The following explains two types of binarySearch method in the Arrays class.

public static int binarySearch(int[] a, int target) {

return binarySearch(a, target, 0, a.length - 1);

}

public static int binarySearch(int[] a, int target,

int min, int max) {

if (min > max) {

return -1; // target not found

} else {

int mid = (min + max) / 2;

if (a[mid] < target) { // too small; go right

return binarySearch(a, target, mid + 1, max);

} else if (a[mid] > target) { // too large; go left

return binarySearch(a, target, min, mid - 1);

} else {

return mid; // target found; a[mid] == target

}

}

}

Please write complete BinarySearch class program with the above methods and the method call as follows and give the answer for the following questions.

System.out.println(binarySearch(list, 103, 0, 9)); System.out.println(binarySearch(list, 30, 2, 8));

[1.1] What values would min, max and mid take on for the following call in recursive fashion:

binarySearch(list, 103, 0, 9);

and what value would be returned?

[1.2] What values would min, max and mid take on for the following call in recursive fashion:

binarySearch(list, 30, 2, 8);

and what value would be returned?

[2] Approximate the value of sum after the following code fragment, in terms of variable n in Big-Oh notation. (2 pts)

[2.1] Please answer the estimated run time of the following program segment in Big-Oh notation.

int sum = 0;

for (int i = 1; i <= n - 3; i++) {

for (int j = 1; j <= n + 4; j += 5) {

sum += 2;

}

sum++;

}

for (int i = 1; i <= 100; i++) {

sum++;

}

[2.2] Please answer the estimated run time of the following program segment in Big-Oh notation.

int sum = 0;

for (int i = 1; i <= n; i++) {

sum++;

}

for (int j = 1; j <= n / 2; j++) {

sum++;

}

[3] Consider the following array of int values. Please write TestSort class which includes the following selectionSort() and mergeSort() program and try to call both methods on the following array. (2 pts.)

[7, 1, 6, 12, -3, 8, 4, 21, 2, 30, -1, 9]

[3.1] Explain the contents of the array after 4 passes of the outermost loop of selectionSort(). Please refer to the following selectionSort() method.

public static void selectionSort(int[] a) {

for (int i = 0; i < a.length - 1; i++) {

// find index of smallest remaining value

int min = i;

for (int j = i + 1; j < a.length; j++) {

if (a[j] < a[min]) {

min = j;

}

}

// swap smallest value its proper place, a[i]

swap(a, i, min);

}

}

// Swaps a[i] with a[j].

public static void swap(int[] a, int i, int j) {

if (i != j) {

int temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}

[3.2] Write the contents of the array during each of the the recursive calls of mergeSort(). Please refer to the following mergeSort() method.

public static void mergeSort(int[] a) {

if (a.length >= 2) {

// split array into two halves

int[] left = Arrays.copyOfRange(a, 0, a.length/2);

int[] right = Arrays.copyOfRange(a, a.length/2, a.length);

// sort the two halves

mergeSort(left);

mergeSort(right);

// merge the sorted halves into a sorted whole

merge(a, left, right);

}

}

// Merges the left/right elements into a sorted result.

// Precondition: left/right are sorted

public static void merge(int[] result, int[] left,

int[] right) {

int i1 = 0; // index into left array

int i2 = 0; // index into right array

for (int i = 0; i < result.length; i++) {

if (i2 >= right.length ||

(i1 < left.length && left[i1] <= right[i2])) {

result[i] = left[i1]; // take from left

i1++;

} else {

result[i] = right[i2]; // take from right

i2++;

}

}

}