Computer Science 2610
Fall 2004
Solutions to practice questions for quiz 4

This will be a closed book quiz. You may bring one 8.5x11 page of prepared notes, written on both sides.

1. Write a function that computes the sum of all of the numbers in an array of integers. There should be two parameters, the array A and the logical size n of the array. A function heading is provided. Use a loop for this function.

     int sum(int A[], int n)
     {
       int sm = 0;
       int k;
       for(k = 0; k < n; k++) {
         sm = sm + A[k];
       }
       return sm;
     }
   

2. Write a definition of function sum that has the same meaning as before, but use recursion for this definition instead of a loop.

     int sum(int A[], int n)
     {
       if(n == 0) return 0;
       else return A[n-1] + sum(A, n-1);
     }
   

3. You would like to set variable s to the sum of all of the integers in array Fish, which has 12 members. What statement would you write to use function sum to do the computation?

       s = sum(Fish,12);
   

4. Write a function that has a single null-terminated string parameter. It should return 1 if the string contains the letter 'b', and 0 if it has no occurrences of the letter 'b'. Call it anyBs. For example, anyBs("bat") = 1, anyBs("rabbit") = 1, but anyBs("dog") = 0.

   Using a loop:

     bool anyBs(char s[]) 
     {
       for(int k = 0; s[k] != '\0'; k++) {
         if(s[k] == 'b') return 1;
       }
       return 0;
     }
   

   Using recursion and pointers:

     bool anyBs(char s[])
     {
       if(*s == '\0') return 0;
       else if(*s == 'b') return 1;
       else return anyBs(s+1);
     }
   

5. To within a constant factor (that is, in terms of proportionality) how much time does it take to sort an array of n integers using insertion sort, in the worst case?

   n²

6. To within a constant factor, how much time does it take to sort an array of n integers using quicksort, in the average case?

   n log₂(n)

7. To within a constant factor, how long does it take to do a linear search of an array of n integers, in the worst case?

   n

8. To within a constant factor, how long does it take to do a binary search of a sorted array of n integers, in the worst case? Assume that the array is already sorted.

   log₂(n)

9. With an error of no more than 1, what is log base 2 of 2000?

   10 < log₂(2000) < 11, so either 10 or 11 are acceptable answers.

10. We developed two algorithms to solve the edit distance problem. Both algorithms were based on the same facts; they just used the facts differently. Suppose that X = x₁...x_n and Y = y₁...y_m are two strings, and that D[i][j] is the edit distance between the length i prefix of X and the length j prefix of Y. (Notice that the string indices start at 1.) Which of the following is a correct equation? (= means equal and != means not equal.)

    1. D[i][0] = 0
    2. D[i][j] = D[i-1][j] + D[i][j-1] when x_i = y_j
    3. D[i][j] = D[i-1][j] + D[i][j-1] when x_i != y_j
    4. D[i][j] = D[i-1][j-1] when x_i = y_j
    5. D[i][j] = D[i-1][j-1] when x_i != y_j