1. (2 points) An ATM can only dispense $1 bills, $5 bills, and $10 bills. How many ways are there to withdraw n dollars (given we have described our bases suitably)?
a. F(n) = n*F(n) + (n/5)*F(n) + (n/10)*F(n)
b. F(n) = n*F(n - 1) + (n/5) * F(n - 5) + (n/10) * F(n - 10)
c. F(n) = F(n - 1)^1 + F(n - 5)^5 + F(n - 10)^10
*d. F(n) = F(n - 1) + F(n - 5) + F(n - 10)
2. (2 points) As above, an ATM can only dispense $1 bills, $5 bills, and $10 bills. What should F(0) be set to for the correct recurrence from Q1 to work?
a. F(0) can be defined as anything
b. F(0) = 0
*c. F(0) = 1
d. F(0) = -1
3. (2 points) In year one you save $100. Every year thereafter you save $100 more and also you receive 5% interest on what you already had in the bank.
What is the recurrence relation giving your savings after n years?
a. T(1) = 100; T(n) = 1.05 * T(n - 1)
b. T(1) = 100; T(n) = 100 + T(n - 1)
*c. T(1) = 100; T(n) = 100 + 1.05 * T(n - 1)
d. T(1) = 100; T(n) = 100 + 1.05 * T(n)
4. (2 points) What is the big O of the following equation? T(n) = 8T(n / 8) + n
*a. O(n log n)
b. O(n)
c. O(n^(log n))
d. O(n^2)
5. (2 points) What is the big O of the following equation? T(n) = 5T(n / 2) + n^2
a. O(n log n)
b. O(n)
c. O(n^(log n))
*d. O(n^2.32)
6. (2 points) Let f(x) = f(x - 1) + 3, for all positive integers x > 3, and let f(3) = 2. What is f(8)?
a. 14
*b. 17
c. 16
d. 20
f(8) = f(7)+3
f(7) = f(6)+3
f(6) = f(5)+3
f(5) = f(4)+3
f(4) = f(3)+3
f(3) = 2
So, f(4) = f(3)+3 = 5
f(5) = f(4)+3 = 8
f(6) = f(5)+3 = 11
f(7) = f(6)+3 = 14
f(8) = f(7)+3 = 17
7. (2 points) Suppose n is a positive integer divisible by 3 and f(1)= 4. For the recurrence relation f(n) = 3 f(n/3) + 2, find f(3) and f(27):
a. 6, 20
*b. 14, 134
c. 12, 132
d. 134, 12
8. (2 points) For the recurrence relation, T(n) = 2T(n/2) + 6n − 1, use the master theorem give an expression using Big-Theta notation for the runtime, T(n). Assume T(1) = Θ(1).
a. Θ(6n)
b. Θ(n)
*c. Θ(n log n)
d. Master theorem doesn't apply.
9. (2 points) Use the master theorem to give the runtime for the recurrence T(n) = 2T(n) + 6n − 1
a. Θ(6n)
b. Θ(n)
c. Θ(n log n)
*d. Master theorem doesn't apply.
10. Let f(n) = 5 * f(n−2) − 4*f(n−4) .
Find f(10) if f(0) = 3,f(1) = 2, f(2) = 6, and f(3) = 8.
*a. 1026
b. 258
c. 324
d. 1284
Solution :
f(10)= 5 * f(8) - 4 * f(6)
f(8)= 5 * f(6) - 4 * f(4)
f(6)= 5 * f(4) - 4 * f(2)
f(4)= 5 * f(2) - 4 * f(0)
f(4) = (5 * 6) - (4 * 3) = 30 - 12 = 18
f(6) = (5 * 18) - (4 * 6) = 90 - 24 = 66
f(8) = (5 * 66) - (4 * 18) = 330 - 72 = 258
f(10) = (5 * 258) - (4 * 66) = 1290 - 264 = 1026
11. Find the solution of f(5) for the given recurrence relation
f(n) = 2 * f(n−1) + 3 * 2^(n-1). Here for all n>0 , f(1) = 3.
a. 144
b. 288
*c. 240
d. 96
Solution :
f(5) = 2 * f(4) + 3 * 2^4
f(4) = 2 * f(3) + 3 * 2^3
f(3) = 2 * f(2) + 3 * 2^2
f(2) = 2 * f(1) + 3 * 2^1
f(2) = 2 * 3 + 3 * 2^1 = 6 + 6 = 12
f(3) = 2 * 12 + 3 * 2^2 = 24 + 12 = 36
f(4) = 2 * 36 + 3 * 2^3 = 72 + 24 = 96
f(5) = 2 * 96 + 3 * 2^4 = 192 + 48 = 240
12. Following is the simultaneous recurrence relations
f(n) = 3*f(n−1) + 2*g(n−1)
g(n) = f(n−1) + 2*g(n−1)
with f(0) = 1 and g(0) = 2. Find the values of f(3) and g(4).
a. 65 , 65
*b. 127 , 257
c. 127 , 65
d. 31 , 65
Solution :
f(3) = 3*f(2) + 2*g(2) g(4) = f(3) + 2*g(3)
f(2) = 3*f(1) + 2*g(1) g(3) = f(2) + 2*g(2)
f(1) = 3*f(0) + 2*g(0) g(2) = f(1) + 2*g(1)
g(1) = f(0) + 2*g(0)
f(1) = 3 * 1 + 2 * 2 = 3 + 4 = 7 g(1) = 1 + 2 * 2 = 1 + 4 = 5
f(2) = 3 * 7 + 2 * 5 = 21 + 10= 31 g(2) = 7 + 2 * 5 = 7 + 10 = 17
f(3) = 3*31 + 2*17 =93 + 34=127 g(3) = 31 + 2 * 17 = 31 + 34 = 65
g(4) = 127 + 2 * 65 = 127 + 130 = 257