Part A:

1. Assume that T(1) = c for some fixed constant c > 0. What are the correct statements below if function T satisfies the following recurrence:

T(n) = n . T(n/2).

NOTE: More than one answer is correct. The base of log is 2. Recall that we learned about at least two methods to solve recurrences: the Substitution Method and the Master Method.

■ A. T(1) = 1, that is c = 1

□ B. T(n) = n(log(n)+1)/3

□ C. T(n) = n(log(n))/2

■ D. T(n) = n(log(n)+1)/2

□ E. T(1) = 2, that is c = 2

□ F. T(1) = 3, that is c = 3

Solution: Let us first observe that if we take as T(n) any of the formulas in B, C or D, then using any of those formulas gives us T(1) = 1.  This suggests that we should choose A as one of the correct answers, that is, T(1) = 1.

Now, how to decide which of B, C , D is correct?  There are two ways to do this, one is to use the Substitution Method to solve the above recurrence. The second, quicker and easier, method is to directly try these three formulas B, C, D, under the assumption that T(1) = 1. Let us indeed do that (I am doing it here for the right formula only). Assume that T(n) = n(log(n)+1)/2 , then:

n . T(n/2) = n . (n/2)(log(n/2)+1)/2  = n . (n/2)(log(n)_log(2)+1)/2  = n . (n/2)(log(n)_1+1)/2  = n . (n/2)(log(n))/2

= n . (n/2)(log(n))/2  = n . ╱ ∶ = n . ╱ ∶ = n . ╱ ∶ = n . ╱ ∶

= ,n . n(log(n))/2  = (n)1/2  . n(log(n))/2  = n1/2+(log(n))/2  = n(1+log(n))/2  = T(n).

2. Assume that T(n) = c for n s d, for some constants c and d. What is the correct asymptotic solution to the following recurrence:

T(n) = 4 T(n/2) + n2 log n.

NOTE: Only one answer is correct. The base of log is 2. Recall that we learned about at least two methods to solve recurrences: the Substitution Method and the Master Method.

□ A. T(n) is ←(n2 )

■ B. T(n) is ←(n2 log2 n)

□ C. T(n) is ←(n2 log n)

□ D. T(n) is ←(n log2 n)

□ E. T(n) is ←(n log n) Hint: Use Master Method.

3. Assume that T(n) = c for n s d, for some constants c and d. What is the correct asymptotic solution to the following recurrence:

T(n) = 4 T(n/3) + n2 log n.

NOTE: Only one answer is correct. The base of log is 2. Recall that we learned about at least two methods to solve recurrences: the Substitution Method and the Master Method.

□ A. T(n) is ←(nlog3 4 log n)

□ B. T(n) is ←(nlog3 4 log2 n)

□ C. T(n) is ←(n2 log2 n)

■ D. T(n) is ←(n2 log n)

□ E. T(n) is ←(nlog3 4 ) Hint: Use Master Method.

4. Assume that T(n) = c for n s d, for some constants c and d. What is the correct asymptotic solution to the following recurrence:

T(n) = T(n/2) + 2 log n.

NOTE: Only one answer is correct. The base of log is 2. Recall that we learned about at least two methods to solve recurrences: the Substitution Method and the Master Method.

□ A. T(n) is ←(n)

□ B. T(n) is ←(n log n)

□ C. T(n) is ←(log n)

□ D. T(n) is ←(n log2 n)

■ E. T(n) is ←(log2 n)

Hint: Use Master Method. You can also use the Substitution Method, or just observe that we can halve n under T(n/2) in the recurrence log(n) times until we reach constant n s d and each time we halve n, we add 2 log(n) in the recurrence.  This means that we add 2 log(n), log(n) times, and at the end T(n) = c for constant n s d, so we obtain that T(n) = ←(log2 n).

5. NOTE: Only one answer is correct.

An instance of the Fractional Knapsack Problem is given by a set, S, of items, each item i has weight wi and benefit bi , and the knapsack weight is W. This problem asks the question: Find a setting for variables xi (one for each item i), where 0 s xi s wi that

6. What is the solution to the following instance of the Fractional Knapsack problem with knapsack weight W = 11.

NOTE: Only one answer is correct.

□ A. The optimal solution includes items a, b, c and d for the total benefit of 33.

□ B. The optimal solution includes items a, b, c and 1/3 of item d for the total benefit of 30 .

□ C. The optimal solution includes items a, b, d and 1/2 of item c for the total benefit of 27.

□ D. The optimal solution includes items a, b, d and 1/3 of item c for the total benefit of 25.

■ E. The optimal solution includes items a, b, c and 1/2 of item d for the total benefit of 31.

7. NOTE: More than one answer is correct.

The data structure AVL tree is a binary search tree with the

■ A. height-balance property: for each internal node its two subtrees have heights differing by at most 1.

□ B. height-balance property: for each external node its two subtrees have heights differing by at most 1.

□ C. length-balance property: for each internal node its two subtrees have lengths differing by at most 1.

□ D. length-balance property: for each external node its two subtrees have lengths differing by at most 1.

□ E. height-balance property: for each internal node its two subtrees have the same heights.

■ F. height-balance property: for each internal node its two subtrees have lengths of their longest path from their root to a leaf differing by at most 1.

8. NOTE: More than one answer is correct.

What statement is true about sorting algorithms:

□ A. MergeSort is a comparison-based sorting algorithm which sorts an array of n numbers always in O(n log log n) time.

■ B. MergeSort is a comparison-based sorting algorithm which sorts an array of n numbers always in O(n log n) time.

□ C. QuickSort is a comparison-based sorting algorithm which sorts an array of n numbers always in O(n log n) time.

□ D. QuickSort is a comparison-based sorting algorithm which sorts an array of n numbers in O(n) expected time.

■ E. HeapSort is a comparison-based sorting algorithm which sorts an array of n numbers in O(n log n) worst-case time.

□ F. HeapSort is a comparison-based sorting algorithm which sorts an array of n numbers in O(n) expected time.

Part B:

9. NOTE: Write down answers to this question in an editor and convert the file to PDF. You may also hand-write your answers on a piece of paper, take a good quality picture and convert it to PDF. Submit the PDF file as your solution.

We consider the following problem:  Given an unsorted array of n >  4 distinct integers A[1, ..., n] (where both positive and negative integers are allowed), you want to find two dis- tinct indices i,j e {1, ... , n}, i j, for which the product A[ i ] . A[j ] is as large as possible.  It suffices if, as output, the value of such largest product is returned.

(a) [6 marks] Design a divide-and-conquer algorithm that solves this problem using at most n comparisons between elements of array A.  Observe that there might be more than one pair of indices i,j which maximise the product A[ i ] . A[j ], and in such a case it suffices to find one such pair and output the maximum value of the product.

Remark: You should include an explanation of the ideas and reasons why your algorithm is correct.  If your algorithm will use c . n comparisons, where constant c is larger than , this will lead to less marks for such a solution.  You may assume for simplicity that n = 2k for some positive integer k > 2.  For the purpose of this problem, if your algorithm computes two products x . y and z . w of elements x, y, z, w of array A and then compares these two products, then we assume that it uses one comparison between elements of array A.

(b) [5 marks] Give an argument that your algorithm indeed uses at most n comparisons between elements of array A, by formulating and solving an appropriate recurrence equation.

Solution:

(a) Let us first observe that the solution to this problem is to first find the two largest integers in array A, denote them max1  < max2 , and the two smallest integers in array A, denote them min1  < min2 . Then the solution is given by the pair max1 , max2  and has value of max1 . max2 if max1  . max2  > min1  . min2 , and the solution is given by the pair min1 , min2  and has value min1  . min2 , if max1  . max2  < min1  . min2 .

Observe here that the product min1  . min2  of the two smallest integers can be the solution to this problem in case if both min1 , min2  are negative, because then their product is positive.

We will design a divide-and-conquer algorithm that uses the required number of comparisons and computes these four integers min1 , min2  and max1 , max2 . The final algorithm compares max1  . max2  and min1  . min2 , and outputs the larger of these products.

Solution sketch I: The base of the recursive algorithm is the case when n = 4 and suppose that in this case A = [a, b, c, d].  We will show that at most 5 comparisons suffice to solve this problem. We execute one recursive step of MergeSort, followed by a single merge step. Namely, the algorithm first compares a, b and c, d and suppose without loss of generality (w.l.o.g.) that a < b and c < d (this uses 2 comparisons). Now we merge these two sub-lists into one sorted list: compare a, c and let w.l.o.g. a < c, then compare b, c and then if b < c, then a < b < c < d and we are done (with 4 comparisons). Else, if b > c, then a < c are the

two smallest elements, and the final 5th comparison b, d decides the two largest elements.   In the recursive step, suppose now that n > 4 and, for simplicity suppose that n = 2k for some positive integer k > 2. The algorithm solves recursively two subproblems on A[1, 2, ... , n/2] and A[n/2 + 1, n/2 + 2, ... , n] and let the solutions to these two subproblems be min1  < min2  < max1   < max2  and min1(_)   < min2(_)   < max1(_)   < max2(_), respectively.  We will first show how the algorithm finds the two global maximums for the original problem A[1, 2, ... , n], denoted by max1(__)  < max2(__), using only 2 comparisons. We compare max2 , max2(_)  and let w.l.o.g. max2  < max2(_), then max2(__)  := max2(_). Then, we compare max2 , max1(_), and if max2  < max1(_), then max1(__)  := max1(_); else, if max2  > max1(_), then max1(__)  := max2 . This uses 2 comparisons.

In a completely analogous and symmetric way, we can use 2 comparisons to find the two global minimums for the original problem A[1, 2, ... , n] from min1   < min2  and min1(_)   < min2(_) . Thus, the recursive step uses a total of 4 comparisons.

Very detailed solution (not expected in class test submission): Let us first consider the base case when n = 4 and suppose that in this case A =  [a, b, c, d].  The algorithm first compares a, b and c, d and suppose without loss of generality that a < b and c < d (this uses 2 comparisons).  Then, we compare b, c and if b < c, then the outcome is min1   = a, min2  = b, max1  = c, max2  = d (3 comparisons in total).  If, on the other hand, b > c, then we compare b, d and if b < d, then we also compare a, c and if a < c then the outcome is min1  = a, min2  = c, max1  = b, max2  = d (5 comparisons in total) and if a > c then the outcome is min1  = c, min2  = a, max1  = b, max2  = d (5 comparisons in total).  If, on the other hand, under assumption that b > c, we have that b > d, then we also compare a, c and if a < c then the outcome is min1  = a, min2  = c, max1  = d, max2  = b (5 comparisons in total); and if a > c then the outcome is min1  = c, min2  = a, max1  = d, max2  = b (5 comparisons in total).    Summarising, we have an algorithm in case when n = 4 which uses 5 comparisons and computes these four integers min1 , min2  and max1 , max2  in the array A.

Suppose now that n > 4 and, for simplicity suppose that n = 2k for some positive integer k > 2. The algorithm solves recursively two subproblems on A[1, 2, ... , n/2] and A[n/2 + 1, n/2 + 2, ... , n] and let the solutions to these two subproblems be min1  < min2  < max1  < max2  and min1(_)   < min2(_)   < max1(_)   < max2(_), respectively.  We will first show how the algorithm finds the two global maximums for the original problem A[1, 2, ... , n], denoted by max1(__)  < max2(__).  We compare first max2 , max2(_) and if max2  < max2(_), then compare max2 , max1(_) and if max2  < max1(_) , then we obtain as outcome max1(__)  = max1(_) , max2(__)  = max2(_)  (two comparisons); and if max2  > max1(_), then we obtain as outcome max1(__)  = max2 , max2(__)  = max2(_)  (two comparisons). If, on the other hand, max2  > max2(_), then compare max1 , max2(_)  and if max1  < max2(_), then we obtain as outcome max1(__)  = max2(_) , max2(__)  = max2  (two comparisons); and if max1  > max2(_), then we obtain as outcome max1(__)  = max1 , max2(__)  = max2  (two comparisons).

Summarising, we only need two comparisons to find max1(__) , max2(__) from max1 , max2 and max1(_) , max2(_).  Similarly, and completely symetrically, we can also use only two comparisons to find the two global minimums for the original problem A[1, 2, ... , n], denoted by min1(_)_  < min2(__), from min1 , min2  and min1(_) , min2(_).  This means that the algorithm uses a total of 4 comparisons, to find the solution to the whole problem A[1, 2, ... , n] from the solutions to the two subproblems A[1, 2, ... , n/2] and A[n/2 + 1, n/2 + 2, ... , n].

Solution sketch II: (The main idea of this solution is due to Haochen Luo.) We have seen in one of the Q and A sessions that we can find the two largest elements in an array of n numbers by using only (3/2)n comparisons between elements in this array.  This is just a standard divide and conquer algorithm similar to the above one. Now we can first divide the input array A into two subarrays: A+ of only positive integers from A, and A_ of all non-positive integers from A.  Let A+  have n1  elements, and let A_  have n2  elements, where n = n1 + n2 . Note, that it is possible that n1  s or n2  s 1. If n1  > 2, use the above algorithm to find the two largest elements max1 , max2  in A+ , using at most (3/2)n1  comparisons.  Similarly, if n2  > 2, use this same algorithm to find the two smallest elements min1 , min2  in A_ , using at most (3/2)n2 comparisons. Compare the two products max1 . max2  and min1 . min2 , and return the larger of these as the solution.