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 real-number 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 C-11.3 in the GT textbook
Put your answers in one file and submit to elearning.
