Textbook : Introduction to Algorithms (3rd edition) by T. Cormen, C. Leiserson,

Question

Textbook: Introduction to Algorithms (3rd edition) by T. Cormen, C. Leiserson, R. Rivest and C. Stein, MIT Press, 2009
Possible Chapters: 4.2 (Strassen's algorithm), 6 (Heapsort) , 7 (Quicksort), 22 (Graph Algorithms), 23 (Minimum Spanning Trees)

Show all work (if necessary).

Only do part (B).

2. a) Using Figure 7.1 in CLRS as a model, illustrate the operation of PARTITION on the array A- (9,5,2,6,3,4 Solution. Your solution here. 1 2 5 3 b) Use Strassen's algorithm to compute the matrix product () ( Give the intermediate steps with respect to each ± and x operation. How inany operations are there? How many × operations are there? Solution. Your solution here.

Explanation / Answer

A=|a b| B = |e f| C = | |   // C is the reult of A X B
|c d|      |g h|     | |

Given two matrices above, the starssen's method works by dividing the matrices(of size N) into sunmatrices of size N/2

1.A, B, C are matrices of size 2 X 2
2.a,b,c,d are four submatrices A of size 1 X 1
3.e,f,g,h are four submatrices of B of size 1 X 1
4.p1,p2,p3,p4,p5,p6 and p7 are submatrices of size 1 X 1

So we have the method as follows:

p1 = a(f-h) = -5        p2 = (a+b)h = 24
p3 = (c+d)e = 75       p4 = d(g-e) = -9
p5 = (a+d)(e+h) = 130   p6 = (b-d)(g+h) = -84
p7 = (a-c)(e+f) = -40

C = | p5+p4-p2+p6   p1+p2 |
    | p3 + p4       p1 + p5 -p3 - p7|

So C = |13 19|
       |66 90|

There are total 7 subtractions, 11 additions, 7 Multiplications

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.