Consider the following 3 divide-and-conquer algorithms to solve the same problem:

• Algorithm I: finds a solution to its input problem by dividing it into 5 subproblems, each of half the size of its input problem, recursively solves each of these 5 subproblems, and then combines their solutions to form the solution of the input problem in linear time.

• Algorithm II: finds a solution to its input problem of size n by recursively solving 2 subproblems of size n-1, and then combines their solutions to form the solution of the input problem in constant time.

• Algorithm III: finds a solution to its input problem of size n by recursively solving 9 subproblems of size n/3, and then combines their solutions to form the solution of the input problem in O(n²) time.

For each of the algorithms above:

1. (9) Write the recurrence for the runtime T(n) of the algorithm for each of the 3 algorithms.

2. (18 Points) Solve each recurrence. That is, for each recurrence, find some function g(n) such that T(n) is O(g(n)) (the tighter the upper bound, the better). For this, either use the recursion-tree method (= "unrolling" the recurrence), the substitution method (= "guess + induction"), or the master theorem. Show your work and explain your answer.

3. (3 Points) Everything else being equal, which one of the 3 algorithms would you choose to solve the problem? Explain your answer.

Consider the merge procedure used in MergeSort. It receives two sorted arrays each of n elements, and outputs a single array of size 2n containing all the elements of the two input arrays sorted in the right order. merge runs in linear time O(n).

In this problem, we'll create an extended version of this merge procedure, called multi-merge that receives k sorted arrays each of size n, and returns a single array of size kn containing all the elements of the k input arrays in the right order.

• (10 Points) Strategy I. Consider solving this problem by calling the merge procedure from MergeSort to merge the first 2 input arrays, and then call it again to merge this resulting array with the 3rd input array, and then this resulting array with the 4th input array, and so on until you're done merging all the k arrays. (Assume that merge works as expected even if the 2 input arrays are not of the same size). What is the time complexity of this solution, in terms of k and n? That is, provide function g(k,n) such that the runtime of this algorithm is O(g(k,n)). Explain your answer in detail.

• (25 Points) Strategy II. Provide a more efficient, divide-and-conquer approach to solve this problem.

  • (5 Points). Explain your algorithm design clearly.

  • (5 Points). Write the algorithm in detailed pseudo-code. There is no need to write code for merge, you can just invoke this procedure.

  • (5 Points). Prove that your algorithm is correct.

  • (5 Points) Write a recurrence for the runtime T(k,n) of the algorithm.

  • (5 Points) Solve the recurrence. That is, find some function g(k,n) such that T(k,n) is O(g(k,n)) (the tighter the upper bound, the better). For this, either use the recursion-tree method (= "unrolling" the recurrence), the substitution method (= "guess + induction"), or the master theorem. Show your work and explain your answer.

Consider an array A[1,...] that is "infinite to the right". Assume that first n positions of the array are filled with numbers in increasing order, and the remaining positions of the array are filled with ∞.

Without knowing what the value of n is, write an algorithm that given an infinite-to-the-right array A, and a number k, but NOT the value of n, returns the position of number k in the array A, if k appears in A, or 0 if k doesn't appear in A. Your algorithm must run in time O(log n).

• (5 Points). Explain the design of your algorithm clearly.

• (10 Points). Write the algorithm in detailed pseudo-code.

• (10 Points). Prove that your algorithm is correct.

• (5 Points) Write a recurrence for the runtime T(n) of the algorithm.

• (5 Points) Solve the recurrence to show that your algorith is O(log n). For this, either use the recursion-tree method (= "unrolling" the recurrence), the substitution method (= "guess + induction"), or the master theorem. Show your work and explain your answer.