Problem 1.  The product of two n × n matrices X and Y is a third n × n matrix Z = XY, where the (i, j) entry of Z is Zij  = ∑k(n)=1 XikYkj . Suppose that X and Y are divided into four n/2 × n/2 blocks each:

X = [C(A)   D(B)] and Y = [G(E)   H(F)] .

Using this block notation we can express the product of X and Y as follows

XY = ] .

In this way, one multiplication of n × n matrices can be expressed in terms of 8 multiplications and 4 additions that involve n/2 × n/2 matrices.  Let T(n) be the time complexity of multiplying two n × n matrices using this recursive algorithm.

a) Derive the recurrence for T(n).   (Assume adding two k × k matrices takes O(k2 ) time.)

b) Solve the recurrence by unrolling it.

Problem 2. Similar to the integer multiplication algorithm, there are algebraic iden- tities that allow us to express the product of two n × n matrices in terms of 7 mul- tiplications and O(1) additions involving n/2 × n/2 matrices. Let T(n) be the time complexity of multiplying two n × n matrices using this recursive algorithm.

a) Derive the recurrence for T(n).   (Assume adding two k × k matrices takes O(k2 ) time.)

b) Solve the recurrence by unrolling it.

Problem 3. Your friend Alex is very excited because they have discovered a novel algorithm for sorting an array of n numbers. The algorithm makes three recursive calls on arrays of size  and spends only O(1) time per call.