CS201 S04 FINAL

FINAL
CS201, Spring 2004

Please print out a hard copy of all your java programs and turn it in at the end of the exam. Do not forget to put your name on the hard copy. Before turn in your programs, try to compile and run them and make sure they work correctly. If your program does not even compile, you receive an automatic 50% credit deduction for that problem, no matter how "close" the program seems to be correct.

1. (25pt) Write a Java application ColumnSum.java which creates a 4 by 4 array of integers, initializes the array elements with random integers between 1 and 9 (inclusive), and outputs the array and the sum of each column of the array. For example, assume the array is:

2 5 7 6
1 3 4 4
3 2 8 9
5 6 3 3

the output should be:

2 5 7 6
1 3 4 4
3 2 8 9
5 6 3 3

The sum of column 0: 11
The sum of column 1: 16
The sum of column 2: 22
The sum of column 3: 22

2. (25pt) Write a Java applet Pattern.java which draws the following pattern:

To receive full credit for this problem, you must use loop statement(s) to draw the pattern instead of drawing each shape individually.

3. (15pt) Consider the following code:

// assume a[] is sorted in ascending order
int binarySearch( int a[], int value )
{
    int index = -1;
    int left = 0, right = a.length-1, mid;

    while( left <= right )
    {
        mid = (left+right)/2;
        if( a[mid] > value ) right = mid-1;
        else if( a[mid] < value ) left = mid+1;
        else
        {
            index = mid;
            break;
        }
    }

    return index;
}

Suppose different elements in an array may have the same value. Modify the code above such that the method always return the index of the first element which has the given value; or -1 if the value is not found in the array. For example, if the array a[] is {12, 15, 27, 27, 27, 31, 31, 32}, binarySearch(a,27) should return 2. Write a Java program BSearchTest.java to test the modified method.

To receive full credit for this problem, the modified code must be efficient, e.g. you cannot just rewrite the whole method into a sequential search.

4. Write a Java application Grades.java which includes the following methods:

(10pt) max -- which takes an array of integers as parameter and returns the largest number in the array.
(10pt) min -- which takes an array of integers as parameter and returns the smallest number in the array.
(10pt) average -- which takes an array of integers as parameter and returns the average of the numbers in the array.
(15pt) sort -- which sorts a given array into descending order. To receive any credit at all for this problem, you must implement sort as a recursive method, e.g. no credit if you simply copy and paste the bubble sort code from the class notes.

And in the main method,

(2pt) create an integer array grades with 20 elements, and assign each element in the array a random value between 50 and 99 (inclusive)
(2pt) invoke the max method and outputs the highest grade
(2pt) invoke the min method and outputs the lowest grade
(2pt) invoke the average method and outputs the average grade
(2pt) Invoke the sort method and outputs the grades array after sorting