Salient features of divide-and-conquer algorithms, derivation of recurrence relation for divide-and-conquer algorithm and the solution of...

 

Transcribed Image Text:

Salient features of divide-and-conquer algorithms, derivation of recurrence relation for divide-and-conquer algorithm and the solution of recurrence relation using two approaches, (i) Master theorem and (ii) backward substitution, have already been discussed. For this class, you will work on Strassen's algorithm for matrix multiplication, a divide-and-conquer algorithm, to accomplish the following: (a) Derive the recurrence relation using multiplication operations and solve it using backward substitution. (b) Derive the recurrence relation using addition operations and solve it using Master theorem (c) Finally, find the complexity of Strassen's algorithm, which is the sum of the complexity of (a) and (b). Salient features of divide-and-conquer algorithms, derivation of recurrence relation for divide-and-conquer algorithm and the solution of recurrence relation using two approaches, (i) Master theorem and (ii) backward substitution, have already been discussed. For this class, you will work on Strassen's algorithm for matrix multiplication, a divide-and-conquer algorithm, to accomplish the following: (a) Derive the recurrence relation using multiplication operations and solve it using backward substitution. (b) Derive the recurrence relation using addition operations and solve it using Master theorem (c) Finally, find the complexity of Strassen's algorithm, which is the sum of the complexity of (a) and (b).