Problem 1.

(a) Determine the strongest asymptotic relation between the functions

f (n) =^logn   and   g(n) = n

i.e., whether f (n) = o(g(n)), f (n) = O(g(n)), f (n) = Ω(g(n)), f (n) = ω(g(n)), or f (n) = Θ(g(n)). Remember to prove the correctness of your choice. (15 points)

Solution. The correct answer is f (n) = o(g(n)). We now prove this as follows.             Firstly, ^log n < log n so we can instead prove log n = o(g(n)) by transitivity. Secondly, 2lcg lcg n = log n (you can do a change of variable m = log n to see this easily).

So our goal is to prove that log n = o(), which require us to show that limn →)o = 0.  We

have,

log n log2 n

n o = n o       n     = 0,

where the last equation is because log2 (n) = o(n) (generally, logc (n) = o(n) for all constants c > 0).

(b)  Use the recursion tree  method to solve the following recurrence T (n) by finding the tightest function

f(n) such that T (n) = O(f(n)). (10 points)

T (n) s 2 . T (n/3) + O(n)

Solution. The correct answer is T (n) = O(n). We prove this as follows.

We first replace O(n) with c . n and then draw the following recursion tree:

The root is at level 1. At level i of the tree, we have 2i -1  nodes each with a value of c . , hence the total value of level i is ( )i -1 . c . n.  The total number of levels in this tree is also  [log3 n].  As such, the total value is:

( )i . c . n = c . n           ( )i  s c . n      ( )i  = c . n . = 3 . c . n.

(the second last equality is by using the formula for sum of geometric series) Hence, T (n) = O(n), finalizing the proof.

Problem 2. Consider the algorithm below for reversing a string represented as a character array A.

REVERSE-STRING(A[1 : n]):

1. If n = 0 or n = 1: return A.

2.  Otherwise, create a new array, B[1 : n].

3.  Set B[1] = A[n], and set B[2 : n] = REVERSE-STRING(A[1 : n _ 1]).

4.  Return B[1 : n].

We analyze REVERSE-STRING in this question.

(a)  Use induction to prove the correctness of this algorithm. (15 points)

Solution. Our induction hypothesis is that REVERSE-STRING is correct for all input arrays A of any length n 2 1, i.e., it returns the reverse of the given array.

Base case .  For n = 0 and n = 1, the original array is also its own reverse, so REVERSE-STRING outputs the correct answer.

Induction step .  Suppose the induction hypothesis is true for all n s k and we prove it for n = k + 1. In REVERSE-STRING(A[1 : k + 1]), we set B[1] = A[k + 1], i.e., the first element of the returned array is the last element of the original array. Moreover, by induction hypothesis, B[2 : k+1] becomes the reverse of A[1 : k], i.e., B[2 : k +1] = A[k], A[k _ 1], . . . , A[1]. Thus, we have B[1 : k +1] = A[k +1], A[k], . . . , A[1], which is the reverse of A. This proves the induction step.

The correctness of the algorithm follows directly from the induction hypothesis.

(b) Write a recurrence for this algorithm and solve it to obtain a tight upper bound on the worst case runtime of this algorithm. You can use any method you like for solving this recurrence. (10 points)

Solution. Let T (n) denote the worst case runtime of the algorithm on inputs of length  n.   The algorithm involves calling itself on a subproblem of size n _ 1 and then spends O(1) time to return the solution. Thus, T (n) = T (n _ 1) + O(1). By replacing O(1) with some unspecified constant C > 0, we have,

T (n) = T (n _ 1) + C = T (n _ 2) + C + C = T (n _ 3) + C + C + C = . . . = n . C = O(n). This proves that the runtime of the algorithm is O(n) as desired.

Problem 3. You are given an unsorted array A[1 : n] of n real numbers with possible repetitions.  Design an algorithm that in O(n log n) time finds the largest number of time any entry is repeated in the array A.

Remember to separately write your algorithm (10 points), the proof of correctness (10 points), and runtime analysis (5 points).

Example .  For A = [1, 7.5, 2, 5.5, 7.5, 7.5, 1, 5, 9.5, 1] the correct answer is 3 (1 and 7.5 are repeated 3 times). Solution. Algorithm:  The algorithm is as follows:

1.  Use merge sort to sort the array A.

2.  Let COUNTER = 1 and MAX = 1.

3.  For i = 2 to n:

(a)  if A[i] A[i _ 1], set COUNTER = 1;

(b) otherwise let COUNTER = COUNTER + 1 and MAX = the larger of MAX and COUNTER.

4.  Return MAX.

Proof of correctness:  After sorting A, all copies of the same number would appear right after each other. Hence, to count how many times the number A[i] appears in the array A, we only need to consider the entries in the immediate neighborhood of A as is done in the algorithm.  More precisely, the value of COUNTER right before it gets reset due to the condition A[i] A[i _ 1] is equal to the number of times A[i _ 1] is repeated in A.  Since MAX is simply maintaining the maximum value of COUNTER throughout the algorithm, we obtain that the final answer is correct.

Runtime  analysis:   The algorithm involves running merge sort in O(n log n) time and then a single n _ 1 iteration for-loop with each iteration taking O(1) time, hence O(n) in total for the for-loop.  As such, the total runtime is O(n log n).

Problem 4. You are given a set of n items with weights w1 , . . . , wn  and values v1 , . . . , vn .  You are also given two  knapsacks with sizes W1 , W2 .  The goal is to pick a subset of items with maximum value such that we can place each of the chosen items in one of the two knapsacks with the restriction that the total weight of items in each knapsack should be smaller than its size.  Design an O(n . W1  . W2 ) time dynamic programming algorithm that outputs the maximum value we can obtain by picking a subset of items that fits the two knapsacks.

Remember to separately  write your specification of recursive formula in plain English (7.5 points), your recursive solution for the formula  and its proof of correctness  (10 points),  the  algorithm using either memoization or bottom-up dynamic programming (7.5 points), and runtime analysis (5 points).

Example:  For items with weights [1, 4, 2, 5, 1] and values [2, 3, 1, 10, 1], and knapsacks of size 4 and 3, the correct output is 6: this is achieved by picking items 1 and 3 in knapsack two and picking item 2 in knapsack one – note that we cannot fit item 4 in either knapsack as its weight is larger than the size of each one.

Solution.

Specification:  For every 0 s i s n, 0 s j s W1 , and 0 s k s W2 , we define:

● K(i, j, k): the maximum value we can obtain by picking a subset of items {1, . . . , i} that fits a knapsack of size j and another knapsack of size k .

The solution to our original problem is then K(n, W1 , W2 ).

Recursive formula:  We design the following recursive formula:

We now prove the correctness of this algorithm:

if i = 0 or j = k = 0 if wi  > j and wi  > k if wi  s j but wi  > k if wi  > j but wi  s k otherwise

● If i = 0 there is no item to pick and if both j = k = 0 then there is no way we can fit any item in either of the knapsacks; hence, K(i, j, k) = 0 here is the correct value.

● If both wi   > j  and wi   >  k,  item i will not fit either knapsacks;  so the only thing we can do is to skip this item altogether and from the items {1, . . . , i _ 1}, pick the best  solution (corresponding to K(i _ 1, j, k) by definition) so that we maximize the value for items  {1, . . . , i} as well.   Hence, K(i, j, k) = K(i _ 1, j, k) in this case is the correct value.

● If wi  s j but wi  > k, we only have two options:  (1) we still ignore picking item i and hence collect the total value K(i _ 1, j, k)  (as described in the previous part), or  (2) we pick item i in the first knapsack (thus collect value vi ), reduce the size of knapsack one to j _ wi  (as now item i with weight wi  is in the knapsack), and then pick the best solution from the remaining items (corresponding to K(i _ 1, j _wi , k)); so with this option, we collect K(i _ 1, j _wi , k)+vi value. As our goal is to maximize the value obtained, the correct choice in this case is max {K(i _ 1, j, k), K(i _ 1, j _ wi , k) + vi } (note that we cannot fit item i in the second knapsack in this case).

● If wi  > j but wi  s k, we can do exactly as in the previous case with the difference that we now need to pick item i in the knapsack two instead.

● If wi   s j  and wi   s k, we can either skip picking i and get K(i _ 1, j, k) value, pick i in the first knapsack and (by the argument above) get K(i _ 1, j _ wi , k) + vi , or pick i in the second knapsack and (by the argument above) get K(i _ 1, j, k _ wi ) + vi ; thus returning the maximum of these three terms gives the correct answer.

Algorithm:   We give  a bottom-up dynamic programming  algorithm for the problem  (you could  also do memoization and that is absolutely fine). We have to pick an evaluation order: since each K(i, j, k) is only updated from K(i\ , j\ , k\ ) where i\  < i, j\ s j, and k\ s k, we only need to make sure we iterate over all i, j, k in increasing order of their values. The algorithms is as follows:

(1)  Let T [0 : n][0 : W1][0 : W2] be a 3D array of size (n + 1) × (W1 + 1) × (W2 + 1) initialized with 0’s (this takes care of the base case automatically).

(2)  For i = 1 to n:

For j = 1 to W1 :

For k = 1 to W2 :

If wi  > j and wi  > k, then T [i][j][k] = T [i _ 1][j][k];

Else if wi  s j but wi  > k, then T [i][j][k] = max {T [i _ 1][j][k], T [i _ 1][j _ wi][k] + vi }; Else if wi  > j but wi  s k, then T [i][j][k] = max {T [i _ 1][j][k], T [i _ 1][j][k _ wi] + vi }; Else T [i][j][k] = max {T [i _ 1][j][k], T [i _ 1][j _ wi][k] + vi , T [i _ 1][j][k _ wi] + vi }.

(3)  Return T [n][W1][W2].

Runtime  analysis:   The first line of the algorithm above takes  O(n . W1  . W2 ) to initialize the array T. Moreover, we do a for-loop of length n, inside it another for-loop of length W1 , and inside that another for-loop of length W2 , where each iteration of the inner most loop takes O(1) time; thus the total runtime is O(n . W1 . W2 ).

(For a memoization algorithm, the runtime analysis spells out that there are O(n . W1  . W2 ) subproblems K(i, j, k) for all valid choices of i, j, k, and each one takes O(1) time to compute, hence the total runtime again would be O(n . W1 . W2 ).)