Description
Question 1: Let (1) = . Find the closed form of each of the following recurrence equations:

( ) = 2 (_{2}) + log

( ) = 8 (_{2}) + ^{2}

( ) = 16 (_{2}) + ( log )^{4}

( ) = 7 (_{3}) +

( ) = 9 (_{3}) + ^{3} log
Question 2: Given two complex numbers, = + , = + , where a,b,c,d are real numbers.
Compute × by using only three realnumber multiplications.
Question 3: Show the steps of Strassen’s algorithm to multiply the following two 4 X 4 matrices:

2
2
2
1
5
4
2
1
X=[^{5}
8
3
^{2}], Y=[^{7}
1
4
^{4}] .
3
3
5
9
4
8
6
3
1
3
4
2
5
7
4
2
To keep your answer shorter, you do not have to recursively apply Strassen’s algorithm to the subproblem on 2X2 matrices.
Question 4: Problem C11.3 in the GT textbook
Put your answers in one file and submit to elearning.