Part A:

Remark: In questions 1–4 below we assume that T(n) = c for n < d, for some constants c and d.

The following two questions 1–2 are about the following recurrence relation T(n) = 16 T(n/4) + n3 .

We use the Master Method with a = 16, b = 4, so logb a = log4 16 = 2. Hence nlogba  = n2 . Now we have that f(n) = n3 = 2(n2+∈) with, for instance, i = 0.5.

1.  [4 marks] Which calculation is then correct:

□ A. Then, af(n/b) = 16f(n/4) = 16 . (n/4)3  = f(n) = δf(n), so we are in Case 1 of the Master Method with δ =  =  < 5.

□ B. Then, there is a constant k > 0 such that f(n) = n3  is O(nlogba logk n), so we are in Case

2 of the Master Method.

□ C. Then, for any constant k > 0 we have that f(n) = n3  is O(nlogba logk n), so we are in Case 2 of the Master Method.

□ D.  Then, there is a constant k > 0, for instance k = 5, such that f(n) = n3 is 2(n2+logba logk n), so we are in Case 1 of the Master Method.

□ E.  Then, af(n/b) = 16f(n/4) = 16 . (n/4)3  = f(n) = δf(n), so we are in Case 3 of the Master Method with δ =  =  < 1.

2.  [4 marks] Based on the correct calculation from Question 1 we have that:

□ A.  T(n) is e(n4 )

□ B.  T(n) is e(n3 )

□ C.  T(n) is e(n3 log n)

□ D.  T(n) is e(n16/4)

□ E.  T(n) is e(n3 log2 n)

The following two questions 3–4 are about the following recurrence relation T(n) = 27 T(n/3) + n3 log n.

We use the Master Method with a = 27, b = 3, so logb a = log3 27 = 3. Hence nlogba  = n3 .

3.  [4 marks] Which calculation is then correct:

□ A. Then, we have that f(n) = n3 log n = 2(nlogba-∈ ) with, for instance, i = 1, so we are in Case 2 of the Master Method.

□ B. Then, we have that f(n) = n3 log n = O(nlogba-∈ ) for i = 1, so we are in Case 3 of the Master Method.

□ C. Then, af(n/b) = 27f(n/3) = 27 . (n/3)3 log(n/3) = (n)3 log(n/3) = f(n), so we are in Case

3 of the Master Method with δ = 1.

□ D.  Then, we have that f(n) = n3 log n = e(nlogba logk n), with k = 1, so we are in Case 2 of the Master Method.

□ E.  Then, we have that f(n) = n3 log n = O(nlogba-∈ ) with, for instance, i = 1, so we are in Case 2 of the Master Method.

4.  [4 marks] Based on the correct calculation from Question 3 we have that:

□ A.  T(n) is e(n3 )

□ B.  T(n) is e(n3 log3 n)

□ C.  T(n) is e(n3 log2 n)

□ D.  T(n) is e(n2 log n)

□ E.  T(n) is e(n4 )

The following three questions 5–7 are about the fractional knapsack problem.

5.  [4 marks] An instance of the Fractional Knapsack Problem is given by a set, S, of items, where item i has weight wi  and benefit bi , and there is a maximum allowed weight W. Then the Fractional Knapsack Problem asks the following question:

□ A. Question:  Find a setting for variables xi  (one for each item i), where 0 < xi  < wi  that maximizes    ieS bi , without exceeding the maximum weight W, i.e., where    ieS xi  < W.

□ B. Question:  Find a setting for variables xi  (one for each item i), where 0 < xi  < wi  that maximizes     ieS bixi , without exceeding the maximum weight W, i.e., where     ieS xi  < W.

□ C. Question:  Find a setting for variables xi  (one for each item i), where 0 < xi  < wi  that maximizes     ieS bixi , without exceeding the maximum weight W, i.e., where     ieS wi  < W.

□ D.  Question:  Find a setting for variables xi  (one for each item i), where 0 < xi  < wi  that maximizes     ieS bi , without exceeding the maximum weight W, i.e., where     ieS xi  < W.

□ E.  Question:  Find a setting for variables xi  (one for each item i), where 0 < xi  < wi  that maximizes     ieS wi , without exceeding the maximum weight W, i.e., where     ieS wi  < W.

6.  [4 marks] Solve the following instance of the fractional knapsack problem.  The maximum allowable total weight is Wmax  = 11.

Then, the following is true about the greedy algorithm to optimally solve this problem:

□ A. The greedy algorithm considers the items in the following order: e, c, a, b, d.

□ B. The greedy algorithm considers the items in the following order: d, b, a, c, e.

□ C. The greedy algorithm considers the items in the following order: e, c, d, b, a.

□ D.  The greedy algorithm considers the items in the following order: d, b, a, c, e.

□ E.  The greedy algorithm considers the items in the following order: a, b, c, d, e.

7.  [4 marks] Given the correct order of the greedy algorithm from Question 6 :

□ A. The greedy algorithm completely includes into the final solution items d, b, a and only 1/3 fraction of c and the total benefit of the solution is 27.

□ B. The greedy algorithm completely includes into the final solution items e, c, a and only 3/5 fraction of b and the total benefit of the solution is 36.

□ C. The greedy algorithm completely includes into the final solution items e, c, a and only 2/5 fraction of b and the total benefit of the solution is 34.

□ D.  The greedy algorithm completely includes into the final solution items d, b, a and the total benefit of the solution is 23.

□ E.  The greedy algorithm completely includes into the final solution items a, b, c and the total benefit of the solution is 32.

8.  [4 marks] What statement is true about the data structure (2, 4)-tree:

□ A.  It is a tree whose each internal node has at least 1 and at most 3 children.

□ B.  It is a tree whose each internal node has exactly 2 children.

□ C.  It is a tree whose each internal node has at least 2 and at most 4 children.

□ D.  It is a tree whose each internal node has at least 1 and at most 2 children.

□ E.  It is a tree whose each internal node has exactly 4 children.