Problem $2($Max Points $50)$:

Given a n $$ n matrix A and a positive integer k$,$ compute S $=$ Ak

$.$

The input contains the following

$$ A matrix A containing n $*$ n nonnegative integers $($each less than $100).$

You can assume that n $32$ and is a power of $2,$ e$.$g$.1,2,4,8,16,32.$

$$ A positive integer k $($k $10).$

You need to do the following tasks:

A$.$ Implement a function to multiply two matrices using Strassen Matrix

Multiplication method Q$($nlog$2$

$7)($Max Points: $20).$

B$.$ Compute S using the function $($from A above$)$ such that the number of

times the above function is called is Q$($k$).($Max Points: $10)$

C$.$ Compute S using the function $($from A above$)$ and the Divide & Conquer

Approach such that the number of times the above function is called is

Q$($log k$).($Max Points: $20)$

Sample Input

$[[0,1],[1,1]],3$

Sample O