Problem
Let X be a kn times n matrix and Y by an n times kn matrix, for some integer k.
i. Describe an algorithm that computes the product XY using Strassen's algorithm as a subroutine, i.e., use it as a black-box without modifying it. Only describe your algorithm in words; pseudo-code is not required. Justify your answer, i.e., argue that your algorithm does compute XY correctly. Establish its running time.
ii. Repeat part (i) for computing the product YX.