1 given the recurrence relations find

Question

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

Answer 1

Make use of the computer basics; write a paper responding to the following questions: Q1. Provide two matrices A and B. a) Compute the product C (=AxB) by using the Strassen's matrix multiplication algorithm. Describe all the steps. b) Count precisely how many fundamental multiplication operations and fundamental addition operations are there in your computation. Question 2: a) Design a variant binary search algorithm that splits the set not into 2 sets of equivalent sizes (1/2 and 1/2), however to 2 sets of sizes one quarter (1/4) and three quarters (3/4). b) Provide the recurrence relations of your algorithm. c) Explain how does this algorithm distinguish with the original binary search in both the best case and the worst case complexity?