CS575 Analysis Warm Up Exercise
                       ===============================

This exercise requires you to understand analysis of algorithms using
recurrence relations. Background can be found in, amongst others,
 
   T. H. Cormen, C. E. Leiserson and R. L. Rivest,
   Introduction to Algorithms, MIT Press, 1990


In this exercise you are to analyse the time complexity of a recursive
approach to multiplying n-digit numbers. Usually we think of
multiplication as a one time step operation, but imagine here that 
very large numbers are made up of lists of words containing "digits" 
of some radix R. For the sake of simplicity take R to be 10.

Let us count the number of digit digit multiplications. Multiplying e.g.
 
                    1 2 3 4
                    5 6 7 8
                   --------  *

requires four multiplications of a digit times a four digit number. This 
suggests that multiplication requires O(n ** 2) digit digit multiplications.

Now consider this recursive approach:

  Split the numbers in two n/2 digit numbers. In the example:
  
       1234 = 12*100 + 34

  Use the following observation:

       G =  G1 * Rhalf + G2      
       H =  H1 * Rhalf + H2

       G*H = G1*H1*Rfull + (G1*H2+G2*H1)*Rhalf + G2*H2  

       where Rhalf = R ** (n/2), Rfull = R ** n, and R is the digit
       radix

       G1*H2 + G2*H1 = (G1+G2)*(H1+H2) - G1*H1 - G2*H2

  So we need only three multiplications of n/2 digit numbers to compute
  the product of two n digit numbers plus a number of adds and subtracts.

  1. Create a recurrence relation describing the number of digit digit
     multiplication required for the recursive method described above.
 
  2. Solve the recurrence relation, using the Master method.

  3. Find a description of Strassen's matrix multiply algorithm. Briefly 
     discuss its complexity, relating it to the above exercise.


Except as otherwise noted, the content of this presentation is 
licensed under the Creative Commons Attribution 2.5 license.