CS2223 Algorithms 
Homework 3 - B Term 2013

PROF. CAROLINA RUIZ 

Due Date: Friday Nov. 22th at 1:00 PM 
See course policy regarding late homework submissions

Homework Instructions:

• Study Sections 2.3, 4.1-4.5 of your textbook.
• See Useful logarithm and exponential facts.
• This is an individual homework. No collaboration is allowed.
• Submit a hardcopy of your written homework solutions at the beginning of class the day the homework is due.
• Remember to show your work and explain your answers. Correct answers without complete explanations won't receive full credit. Incorrect answers with explanations may receive partial credit.
• See the course webpage for the late homework submission policy.

Homework Problems:

---

1. (50 points) Problem 1. Recurrences.

   Assume that given a problem, we come up with 3 different divide-and-conquer algorithms to solve the 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 (= n).

   • 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 quadratic time (= n²).

   1. (10 points, 3.3 for each recurrence) Write a recurrence for the runtime T(n) of each of the algorithms above. Assume that the base case T(1) runs in constant time.

   2. (39 points) Solve each recurrence. That is, for each recurrence, find a function g(n) such that T(n) is O(g(n)) (the tighter the upper bound, the better), following the directions below:
      1. (9 points, 3 for each recurrence) Use the master theorem, if applicable. Explain your work.
      2. (30 points, 10 for each recurrence) In addition, use either the recursion-tree method (= "unrolling" the recurrence), or the substitution method (= "guess + induction") to provide another proof of the result. To make sure you practice with all these methods, you must use the recursion-tree method for at least one of the 3 recurrences, and the substitution method for at least one of the 3 recurrences.

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

   ---

2. (80 points) Problem 2. Multi-Merge.

   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 (where k is a variable) 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.

   1. 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). Let's call this algorithm naive-multi-merge.
      1. (10 points) Construct the runtime function T(n,k) for naive-multi-merge. Explain your work.
      2. (10 points) Calculate the time complexity of this algorithm in terms of k and n. That is, provide a function g(n,k) such that the runtime T(n,k) of this algorithm is O(g(n,k)). Explain your work.

   2. Strategy II. Provide a more efficient, divide-and-conquer approach to solve this problem. Let's call your algorithm smart-multi-merge. This algorithm uses the merge function, but it is smarter than naive-multi-merge about what pairs of arrays to merge. If convenient, assume that k is a power of 2.

      1. (5 points) Explain your algorithm design clearly.

      2. (10 points) Write your smart-multi-merge algorithm in detailed pseudo-code. Your pseudo-code should make calls to the function merge.

      3. (10 points) Prove that your algorithm is correct.
         That is, you need to show that for all inputs: (1) your algorithm terminates; and (2) it produces the correct output. You can assume that the merge algorithm is correct, since its correctness is proven in section 2.3.1 of the textbook.

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

      5. (10 points) Solve the recurrence. That is, find some function g(n,k) such that T(n,k) is O(g(n,k)) (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. Python Implementation.

      1. (5 points) merge Implementation. Implement the merge function in Python. This function should receive two sorted lists as input and output a third list with the elements in the the two lists sorted in ascending order. (Note that to simplify life, the returned list will be a new list, not any of the two input lists.) You can reuse the merge part of the mergeSort code available at mplemented in the online textbook Problem Solving with Algorithms and Data Structures by Brad Miller and David Ranum.

      2. (5 points) naive-merge Implementation. Implement naive-multi-merge in Python.

      3. (5 points) smart-merge Implementation. Implement your smart-multi-merge algorithm in Python.

      4. (5 points) Runtime evalution. Compare the runtime of naive-multi-merge and smart-multi-merge on the following inputs:
         1. n = 100, k = 16. That is, merging 16 lists of size 100 each. Make each of these lists equal to [0,1,...,n-1].
         2. Same as above, but with the following values for n and k:
            n = 100, 200, 300, 400, 500.
            For each value of n above, k = 16, 32, 64, 128, 256, 512 (you might have to stop earlier if your machine runs out of memory).
         3. Include your results in your written reports.
         4. Provide plots/visualizations of your results and your observations about these results.

   ---

3. (20 points) Problem 3. Base of a logarithm.

   State whether the base of a logarithmic expression in each of the cases below can be ignored or not. That is, whether the particular base of the logarithm (log₂, log₁₀, ln, ...) makes a difference or not. If it can be ignored, prove it rigorously. If it cannot be ignored, show an example in which the base of the logarithm makes a difference.

   1. (5 points) O(log_a n), where a is a constant greater than 1.
      That is, you need to show whether or not: O(log_a n) = O(log_c n), for any constants a and c greater than 1.

   2. (5 points) O(n^log_ab), where a and b are constants greater than 1.
      That is, you need to show whether or not: O(n^log_ab) = O(n^log_cb), for any constants a, b, and c greater than 1.

   3. (5 points) O(log_f(n) n), where f(n) is any function of n (e.g., f(n) = √ n).
      For this part, show whether or not: O(log_f(n) n) = O(log_c n), where f(n) is any function of n, and c is any constant greater than 1.

   4. (5 points) O(log_a n), where a is a constant between 0 and 1.
      For this part, show whether or not: O(log_a n) = O(log_c n), a is a constant between 0 and 1, and and c is any constant greater than 1.

   Note: The same results you obtained above for Big-Oh, apply also to Big-Omega Ω and Big-Theta Θ, but you don't need to prove it.