Textbook

CS 3343/3341  Analysis of Algorithms  Fall 2012  Recitation 9  In-Class Problems     Week 9: Oct 23-25

You must follow the Rules for In-Class Recitations. Problem 1 is mainly present to give you a sample program that calculates the sum of a series. Of course the two series in Problem 2 differ is several ways from the series in Problem 1.

1. Use the Master Theorem to analyze the following recurrences. (The theorem may not work for some of them.) [Note that the Master Method may not apply in some cases, as explained in the bottom of page 95 and on to 96. Exercise 4.6-2 (page 106) gives a solution in this case, but the material is too technical to come up often.]
   1. T(n) = 3 T(n / 2) + n²

   2. T(n) = 2 T(n / 2) + n²

   3. T(n) = 64 T(n / 4) + √n

   4. T(n) = 9 T(n / 3) + n² log(n)

   5. T(n) = 32 T(n / 2) + n² log(n)

   6. T(n) = 125 T(n / 5) + 1

   7. T(n) = 16 T(n / 4) + n⁴

   8. T(n) = 2 T(n / 4) + √n

   9. T(n) = 2 T(n / 4) + √n log(n)

   ---

2. Suppose we use divide and conquer strategy and ordinary multiplication of 2-by-2 matrices, which require 8 multiplications. The recurrence T(n) = 8 T(n / 2) + Θ(n²) applies in this situation. Use the Master Theorem to find the big-Θ performance of this recurrence.

   ---

3. Suppose we use the same approach using 3-by-3 matrices: a divide and conquer strategy for this case, where one will divide a 9-by-9 matrix into nine 3-by-3 matrices, and so on for larger powers of 3. First examine the standard way to multiply two 3-by-3 matrices, and see that this takes 27 multiplications. Write a recurrence for this situation. Again use the Master Theorem to find the big-Θ for your new recurrence.

---

Revision date: 2012-10-22. (Please use ISO 8601, the International Standard.)

---