CS 331 Design and Analysis of Algorithms | Homework 2 | Complete Solution

CS 331 Design and Analysis of Algorithms

Homework #2

Note: Turn in your homework with a cover sheet including your name and last 4 digits of your
student ID # so that your grade can be correctly recorded. Write on only one side of each page.
(Total: 100 points)

1. (20 points) Given the recurrence relations. Find T(1024).
T(n) = 2T(n/4) + 2n + 4 for n > 1
T(1) = 1

2. (25 points) 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. (25 points)
(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. (30 points) 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