Peer Credit Assignment

1. Please list the names of the other members of your peer group for this week and the number of extra credit points you think they deserve for their participation in group work on Tuesday and Thursday combined.

• If all three members besides yourself were present at some time, you have a total of 3 points to allocate.
• If only two members besides yourself were present, you have a total of 4 points to allocate.
• If only one other member was present, you have a total of 6 points to allocate.
• You need not allocate all the points available to you. Points allocated to yourself will not be recorded.

Master Method Practice

**2. ** (6 pts) Use the Master Method to give tight Θ bounds for the following recurrence relations. Show a, b, and f(n). Then explain why it fits one of the cases, if any. If it fits a case, write and _ simplify _ the final Θ result

a. T(n) = 2_T_(n/4) + √n

b. T(n) = 2_T_(n/4) + n

c. T(n) = 4_T_(n/3) + n

Substitution Method

3. (7 pts) Use substitution as directed below to solve

T(n) = 4_T_(n/3) + n

It is strongly recommended that you read page 85-86 “Subtleties” before trying this!

a. First, use the result from the Master Method in 2c as your “guess” and inductive assumption. We will do this without Θ and c: just use the algebraic portion. Take the proof up to where it fails and say where and why it fails. (See steps below.)

b. Redo the proof, but subtracting d__n from the guess to construct a new guess. This time it should succeed.

As a reminder, to do a proof by substitution you:

1. Write the definition T(n) = 4_T_(n/3) + n
2. Replace the T(n/3) with your “guess” instantiated for n/3 (you can do that by the inductive hypothesis because it’s smaller than n).
3. Operating only on the right hand side of the equation, transform that side into the exact form of your “guess”.
4. Determine any constraints on the constants involved.
5. Show the base case holds.