1. Consider memoizing this function: Suppose the memoized version is called with
ID: 3583248 • Letter: 1
Question
1. Consider memoizing this function:
Suppose the memoized version is called with an initial value of 7. What is the irst recursive call that performs a table look up and inds a previously computed value? Do not consider calls which involve the base cases. Assume the f(x-1) call is always performed before the f(x-2) call. Hint: draw a tree of the function calls, as in f(7) calls f(6), then f(5).
Suppose the memoized version is called with an initial value of 7. What is the irst recursive call that performs a table look up and inds a previously computed value? Do not consider calls which involve the base case. Hint: draw a tree of the function calls, as in f(7) calls f(6).
(A) f(3) (B) f(2) (C) f(5)
3. Consider memoizing this function:
(D) f(6)
(E) f(4)
(F) a previously computed value is never found
Is memoization useful (i.e. redundant computations are eliminated) and, if so, what is the dimensionality of the memoization table?
(A) no (C) yes, 3 (B) yes, 2 (D) yes, 1
Consider using dynamic programming to rewrite this function:
Is dynamic programming useful (i.e. redundant computations are eliminated) and, if so, what is the dimensionality of the memoization table?
(A) yes, 1 (C) no (B) yes, 3 (D) yes, 2
Consider using dynamic programming to improve the eiciency of this function:
How would the dynamic programming table be illed, using n as an index?
(A) fromhighntolown (C) fromlowntohighn
(B) n is not used as an index
Consider using dynamic programming to improve the eiciency of this function:
How would the dynamic programming table be illed, using t as an index?
(A) fromlowttohight (C) tisnotusedasanindex
(B) from high t to low t
For counting sort, assume array A holds the data to be sorted, array B holds the sorted data, and array C holds the counts. The index i is used to sweep the array A for counting (phase I), index j is used to sweep array C for summing the counts (phase II), and index k is used to sweep array A when placing elements from A into B (phase III). Assume A[k] is placed at B[C[A[k]]-1] and that the smallest element is placed at B[0].
7. Counting sort is:
(A) stable if i and j sweep from high to low, k low to high (B) stable if i and k sweep from high to low, j low to high (C) stable if i, j, and k sweep from high to low
(D) stable if j and k sweep from low to high, i high to low
(E) stable if i, j, and k sweep from low to high (F) stable under all conditions
(G) unstable under all conditions
(H) none of the other answers are correct
8. Suppose you are to sort n numbers using counting sort. What size should the C array be if the range of numbers is greater than n?
(A) less than n
(B) there’s not enough information
(C) greater than n (D) equal to n
2
Immediately after phase II, the value in the rightmost slot of the C array is:
(A) an A array index, yielding the largest number in A (C) the largest number in the A array
(B) an A array index, yielding the smallest number in A (D) the number of elements in the A array
Consider using a counting sort to sort the input array [4,5,4,3,2,2,2,0]. Immediately after phase I, the C array
looks like:
(A) [1,2,3,4,5,6] (B) [1,0,3,1,2,1] (C) [1,3,2,1]
(D) the correct answer is not given (E) [0,1,2,3,4,5]
(F) [1,1,4,5,7,8]
T or F: Consider sorting two arrays with counting sort. If the C arrays look exactly the same for both inputs just after phase II, then the C arrays must have looked exactly the same just before phase II.
Consider using a stable counting sort to sort the input array [2,5,4,3,1,2,3,1] with destination array B. At start of phase III, the irst element to be placed in B is:
(A) 1,atindex1
(B) 2, at index 4
(C) none of the other answers is correct (D) 5, at index 7
(E) 1,atindex0 (F) 2, at index 3 (G) 2, at index 2
13. Let n be the count of numbers in a collection of base10 numbers. Suppose zero is the minimum number and k is the maximum number in the collection. If k = (log n), then the time complexity of counting sort is:
(A) (nlogk) (B) (n2) (C) (k)
(D) (k2)
(E) (klogn) (F) (n)
14. Let n be the count of numbers in a collection of base10 numbers. Suppose zero is the minimum number and k is the maximum number in the collection. If k = (n), then the time complexity of counting sort is:
(A) (nlogk) (B) (n2) (C) (klogn)
(D) (n) (E) (k2) (F) (k)
15. Consider using counting sort to sort n numbers uniformly distributed over the range of zero to nk. The asymptotic complexity of the sort, in the simplest form, will be
(A) (k) (B) (nk) (C) (n)
16. Consider using radix sort for sorting the following numbers:
After the irst pass, the order of the numbers is:
(A) 774, 744, 447, 477 (B) 477, 447, 774, 744 (C) 447, 477, 744, 774
(D) (n+nk) (E) (klogn) (F) (n+k)
(D) 744, 774, 477, 447
(E) 447, 477, 774, 744
(F) the correct order is not listed
Explanation / Answer
1.
Given f(x) = f(x-1) + f(x-2).
So, f(7) = f(6) + f(5)
= f(5) + f(4) + f(5)
= f(4) + f(3) + f(4) + f(5)
= f(3) + f(2) + f(3) + f(4) + f(5)
= f(2) + f(1) + f(2) + f(3) + f(4) + f(5)
= f(1) + f(0) + f(1) + f(2) + f(3) + f(4) + f(5)
= 1 + f(0) + f(1) + f(2) + f(3) + f(4) + f(5)
= 1 + 0 + f(1) + f(2) + f(3) + f(4) + f(5)
= 1 + 0 + 1 + f(2) + f(3) + f(4) + f(5)
= 1 + 0 + 1 + f(2) + f(3) + f(4) + f(5)
At this point, f(2) refers to the table to access the previous value f(1). Therefore, the answer is b. f(2)
3.
Given f(x) = f(x-2) * f(x-1) + f(x-3).
So, f(7) = f(5) * f(6) + f(4).
= (f(3) * f(4) + f(2)) * f(6) + f(4).
= ((f(1) * f(2) + f(0)) * f(4) + f(2)) * f(6) + f(4).
= ((1 * f(2) + f(0)) * f(4) + f(2)) * f(6) + f(4).
= ((1 * 2 + f(0)) * f(4) + f(2)) * f(6) + f(4).
= ((1 * 2 + 0 ) * f(4) + f(2)) * f(6) + f(4).
= ((1 * 2 + 0 ) * f(4) + f(2)) * f(6) + f(4).
= ((1 * 2 + 0 ) * (f(2) * f(3) + f(1)) + f(2)) * f(6) + f(4).
= ((1 * 2 + 0 ) * (2 * f(3) + f(1)) + f(2)) * f(6) + f(4).
= ((1 * 2 + 0 ) * (2 * f(3) + f(1)) + f(2)) * f(6) + f(4).
At this point, f(4) refers to the table to access the previous value f(3). Therefore, the answer is e. f(4)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.