This will be a closed book quiz. You may bring one 8.5x11 page of prepared notes, written on both sides.
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;
}
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);
}
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);
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);
}
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?
n2
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 log2(n)
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
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.
log2(n)
With an error of no more than 1, what is log base 2 of 2000?
10 < log2(2000) < 11, so either 10 or 11 are acceptable answers.
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 = x1...xn and Y = y1...ym 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.)