(Textbook. Click for information.)

CS 3343/3341  Analysis of Algorithms  Spring 2012  Recitation 6  Recurrences, etc.     Week 6: Feb 21-23  Due (on time): 2012-02-27  23:59:59  Due (late):        2012-03-02  23:59:59

Note: the submissions program is ready for you to submit this Recitation

Recitation 6 should be submitted following directions at: submissions with deadlines 2012-02-27  23:59:59 (that's Monday, 27 February 2012, 11:59:59 pm) for full credit. 2012-03-02  23:59:59 (that's Friday, 02 March 2012, 11:59:59 pm) for 75% credit.

• Asymptotic notation. (As a background) [Text, pp. 43-52]
• Recursion Trees and Cost Analysis. (One way to solve a recurrence.) [Text, pp. 88-92, pp. 174-178]
• Master Theorem. ("Cookbook" method for solving many recurrences.) [Text, pp. 94-97]

1. Use the Master Theorem to analyze the following recurrences. (The theorem may not work for some of them.)
   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. Text, Exercise 6.5-1 on page 164. [Illustrate the operation of Heap-Extract-Max on the heap A = {15,13,9,5,12,8,7,4,0,6,2,1}.]

3. Text, Exercise 6.5-2 on page 165. [Illustrate the operation of Max-Heap-Insert(A, 10) on the heap A = {15,13,9,5,12,8,7,4,0,6,2,1}.]

4. Text, Exercise 6.5-4 on page 165. [Why do we bother setting the key of the inserted node to -∞ in line 2 of Max-Heap-Insert when the next thing we do is increase its key to the desired value?]

5. Use mathematical induction to prove the following. (It will not suffice to show that the formula is true for some specific values of n, such as n = 5, but you must prove it in general. Don't forget the basis. This is easier than you might expect.)
   

6. Text, Exercise 4.2-7 on page 83. [Show how to multiply the complex numbers a + bi and c + di using only three multiplications of real numbers. The algorithm should take a, b, c, and d as input and produce the real component ac - bd and the imaginary component ad + bc separately. Hint: This is the same as the trick in the method for multiplying integers faster ( Multiply in Θ(n^1.585) ). Consider the expression (a + b)*(c + d).]

7. Suppose we want to mimic Strassen's approach using 3-by-3 matrices. Use 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. Use the Master Theorem to show that T(n) = Θ(n³) for your new recurrence.
   [Hints: The new recurrence is similar to the one for ordinary 2-by-2 matrices, which was T(n) = 8 T(n / 2) + Θ(n²), as explained in your text, page 78.]

8. Continuing the previous problem, one might look for a clever way to multiply 3-by-3 matrices, using fewer than 27 individual multiplications. We might work very hard and find a way to do this in, say, 23 multiplications, only to find that the work was useless, because the asymptotic bound in this case was worse that Strassen's bound for the 2-by-2 case. What is the biggest integer k that has the property that if we can multiply 3-by-3s in k multiplications, we would have a better bound than Strassen? [In other words, how far would we have to push the number down? What's the biggest k that would still improve on Strassen?] You should solve this problem by writing a recurrence for 3-by-3 matrices involving the variable k. Use the Master Theorem to solve this recurrence.