Introduction to the Design and Analysis of Algorithms
Textbook.
 CS 3343/3341
 Analysis of Algorithms
 Fall 2012
 Recitation 9
 Strassen Etc.
    Week 9: Oct 23-25
 Due (on time): 2012-10-29  23:59:59
 Due (late):        2012-11-02  23:59:59

Recitation 9 should be submitted following directions at: submissions with deadlines
  • 2012-10-29  23:59:59 (that's Mon, 29 Oct 2012, 11:59:59 pm) for full credit.
  • 2012-11-02  23:59:59 (that's Fri, 02 Nov 2012, 11:59:59 pm) for 75% credit.

In-class Problems: The first problems will be made accessible during the Recitation hour: Rec 9, In-Class Problems (password protected, use "CS3343" without quotes for "User Name" and password from class just before the recitation).

Remaining Problems:

  1. 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 Θ(n1.585) ). Consider the expression (a + b)*(c + d).]

  2. Suppose one tried to mimic Strassen's approach to 2-by-2 and looked 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.
  3. According to your text, V. Pan discovered a way of multiplying 68-by-68 matrices in 132464 scalar multiplications. Consider a divide-and-conquer strategy for multiplying matrices based on this discovery. Give the recurrence equation for such a divide-and-conquer algorithm. Give an expression for the Θ performance of this algorithm. (You don't need to use a calculator to work out the value of this expression.) [Hint: Don't let the big numbers intimidate you -- they're just numbers.]

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