1. Given the recurrence relations. Find T(1024).

T(n) = 2T(n/4) + 2n + 4 for n > 1

T(1) = 1

2. Given two matrices A and B.

(a) Calculate the product C (=AxB) using the Strassen's matrix multiplication algorithm.Show all steps.

(b) Count exactly how many basic multiplication operations and basic addition operations are there in your calculation.

3.

(a) Design a variant "binary" search algorithm which splits the set not into 2 sets of equal sizes (½ and ½), but into 2 sets of sizes one quarter (1/4) and three quarters (3/4).

(b) Give the recurrence relations of your algorithm.

(c) How does this algorithm compare with the original binary search in both the best case complexity and the worst case complexity?

4. Solve the following recurrence relations.

(a)

4T(n-1) + 1 if n > 1
T(n) =
1 if n = 1

(b)

3T(n/3) + 4n if n > 1
T(n) =
1 if n = 1