WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

CS2223 Algorithms 
Homework 5 - B Term 2005

PROF. CAROLINA RUIZ 

Due Date: December 6th, 2005 at 2:00 PM 
See course policy regarding late homework submissions
------------------------------------------
  1. Read Chapter 5 of the textbook in detail.

  2. Problems: You need to turn in a hard copy of your written solutions to the following exercises at the beginning of class on 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.

    1. (25 points)Chapter 5: exercise 6.

      Remember to:

      • (8 points) Provide a detailed divide-and-conquer algorithm to solve this problem (that is, to find a local minimum in a given such complete binary tree).
      • (8 points) Prove that your algorithm is correct (that is, it always returns a local minimum in the input complete binary tree).
      • (9 points) Prove rigorously that your algorithm uses only O(log n) probes to the nodes in the input complete binary tree.

    2. (20 points) Using the recursion-tree method (or as the texbook calls it, "unrolling" the recurrence), prove that the recurrence
      T(n) = 2T(n/2 + 17) + n
      is O(n log n).

      Note: In case you find the notation above ambigous, T(n/2 + 17) = T((n/2) + 17).

      OPTIONAL PART (20 extra credit points): In addition to using the recursion-tree method above, use the (partial) substitution method to prove that T(n) is O(n log n). Remember that the substitution method involves 2 steps:
      1. (5 points) Guess a good upper bound. Explain why your guess makes sense.
      2. (15 points) Use mathematical induction to refine your guess (i.e., select the appropriate constants and/or add terms to your guess) and to show that the solution works.

    3. (30 points) Consider the recurrence: T(n) = T(n/3) + T(2n/3) + cn.

      • (15 points) Using the recursion-tree method (or as the texbook calls it, "unrolling" the recurrence), find a tight upper bound for T(n). In other words, use the recursion-tree method to find a function f(n) such that T(n) is O(f(n)). The tighter the upper bound you provide, the better.
      • (15 points) Now, use the (partial) substitution method to find a tight upper bound for T(n). Remember that the substitution method involves 2 steps:
        1. (3 points) Guess a good upper bound. You can use the function f(n) that you obtained using the recursion-tree method above as your initial guess.
        2. (12 points) Use mathematical induction to refine your guess (i.e., select the appropriate constants and/or add terms to your guess) and to show that the solution works.

    4. (25 points) Consider the following search problem: 
          Input:
     - An array A of n positions, containing a sorted (in ascending order) sequence of 
       numbers. That is  A[1] ≤ A[2] ≤ ... &le A[n].
     - A value v.
    Output:
     - An index i such that v = A[i], OR
       the message "v is not in A" if v doesn't appear in A.
      Consider the following divide-and-conquer solution to this problem. This solution is called binary search: Compare the midpoint of the array A with v and eliminate half of the array from further consideration, until either v is found in A, or no elements in A remain under consideration.

      • (7 points) Provide a detailed algorithm to solve this problem.
      • (6 points) Prove that your algorithm is correct (that is, it always returns the right answer).
      • (12 points) Analyze the complexity of your algorithm. More precisely, provide a recurrence that captures the runtime T(n) of your algorithm, and provide a tight upper bound for T(n). Here, you can either use results proven in our textbook about upper bounds for your recurrence (make sure to mention precisely what result you are using and why it applies to your recurrence). If no result in our textbook matches your recurrence, use one of the methods (recursion-tree or partial substitution) to solve your recurrence.