Homework 4
Document last modified: 

1. Draw the recursion tree and verify a good asymptotic upper bound (i.e. O) for the following recurrence. You will need to use Substitution Subtlety.

    

   æ c                       if n = 1 T(n) =  í            è 3T(ën/2û) + n     if n > 1

    

2. Binary Search of an Unordered Array

   This is not the usual binary search, here the array is unordered. We are searching to determine if a given key is a member of the array A.

   boolean member(int A[], int key, int l, int r) {    if( l > r ) return false;    int mid = (l+r)/2;    if ( A[mid] == key ) return true;    return member( A, key, l, mid-1) || member( A, key, mid+1, r); }

   Give the recurrence equation for member using floor and ceiling.

    

3. Write an divide-and-conquer algorithm to find the maximum of an array.

   Give the recurrence equation.

   Use a recursion tree to determine a good asymptotic upper bound, O, on the recurrence.

   Use substitution to verify your answer.

    

4. Problems 4-1d, e, f, h, g page 85. Use Master Theorem or Chip-and-Conquer from notes.

   Hint: Use change of variables in h, see page 66 of text.
    

5. Problem 4-3a p. 86. Use Master Theorem

Turn in

1. Cover sheet with your name, C455, date, and Homework 4.
2. Typed or neat handwritten answers.