CS 117 Late-term Exam

Due 8:30AM Monday, March 7

This is an exam. That means you may not speak with anybody other than me (Jeff Ondich) about its contents. You may, however, use your book, your notes, the books in the library, the Internet, and divine guidance (should any be offered to you). If you obtain information from some source other than your own brain, cite your source and use quotation marks where appropriate.

Hand your exam in on paper.

(6 points) The following method sorts an array of integers in increasing order. Show the changes you would make to cause this method to sort an array of String objects into reverse alphabetical order.

public static void sort( int[] a ) { int j, k; int temp; for( j=1; j < a.length; j++ ) { temp = a[j]; for( k=j-1; k >= 0 && temp < a[k]; k-- ) a[k+1] = a[k]; a[k+1] = temp; } }
(6 points) Consider the following method.

public static int Something( int[] a, int N ) { if( N == 1 ) return a[0]; else { int k = Something( a, N - 1 ); if( a[N-1] < k ) return a[N-1]; else return k; } }
- What task does Something accomplish?
- Change the names of Something and k to names that are more descriptive.
- It's possible to pass Something parameters that would cause it to crash your program. Explain.
(5 points) Write a static recursive method that takes an integer N as a parameter and returns the sum of the first N squares.
(6 points) Consider the following method.

public static int factorial( int N ) { int result = 1; for( int k=2; k <= N; k++ ) result = result * k; return result; }
- What is the actual value of 13 factorial?
- What value does factorial(13) return?
- Why does factorial(13) return an incorrect value? More specifically, Why does factorial(13) return this particular incorrect value?
(6 points) The following method is a buggy binary search. For this problem, you will investigate and repair the bug.
- Suppose you pass an array containing 10, 12, 13, 15, 17, 20 and a searchKey equal to 17 to binarySearch. List all the values that left, right, middle and a[middle] pass through as binarySearch tries to find 17. (One convenient way to report this information is as a small table, where each row of the table represents the values of the variables at the beginning of an iteration of the loop.)
- Now suppose you pass the same array (10, 12, 13, 15, 17, 20) and a searchKey equal to 14. Again, report the values of left, right, middle, and a[middle] as binarySearch tries to find 14.
// Returns the index where searchKey is found in the array, // or -1 if searchKey is not in the array. (At least, that's // what it would do if it weren't buggy.) // // Precondition: the array a is sorted in increasing order. public static int binarySearch( int searchKey, int[] a ) { int left = 0; int right = a.length - 1; int middle; while( left <= right ) { middle = (left + right) / 2; if( a[middle] == searchKey ) return middle; else if( a[middle] < searchKey ) left = middle; else right = middle; } return -1; }



    (2 points) I'm all out of jokes.  If you have a good one,
    please tell it to me.

    (2 points) Briefly describe the significance of Charles Babbage
    and Ada Lovelace to the history of computer science.

    (8 points) I have an array a[] of integers,
    and I want to know the distance between the pair of
    these numbers that are furthest apart.
    Elmo suggests the following code, which does the job:

        public static int elmo( int[] a )
    {
        int max = 0;
        for( int i=0; i < a.length; i++ )
        {
            for( int j=0; j < a.length; j++ )
            {
                if( a[i] - a[j] > max )
                    max = a[i] - a[j];
            }
        }
    }

    
         When I used Elmo's code on an array of 2500 integers on my slow
        old computer at home, it took 5.0 seconds (I tried it several
        times--5.0 seconds every time).  Approximately how long will Elmo's
        code take to run if N is 10000 (assuming I use the same computer)?  Justify your answer.
        (It is not sufficient to tell me that you ran the code yourself
        and it took a certain amount of time.  I want you to explain
        why it will take as long as you say it will.)

         Zoe says she thinks Elmo's code is silly.  Describe an
        algorithm that will run significantly faster than Elmo's, and explain why it's faster.