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)
Write a definition of function sum that has the same meaning as before, but use recursion for this definition instead of a loop.
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?
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.
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?
To within a constant factor, how much time does it take to sort an array of n integers using quicksort, in the average case?
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?
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.
With an error of no more than 1, what is log base 2 of 2000?
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.)