matrices Flashcards
What is the run time to Matrix sum two n by n matrices?
Theta of (n2)
What is the naive algo for matrix mult with the run time?
3 nest loops
for i < n
for j < n
for k < n
c[i][j] += a[i][k] * b[k][j]
Run time: Theta of (n3)
For matrice multiplication, what happens during
Divide
Conquer
Combine
![](https://s3.amazonaws.com/brainscape-prod/system/cm/270/335/572/a_image_thumb.png?1552252989)
What is the run time analysis of divide-and-conquer for multiplying two n-by-b matrices? (in general)
![](https://s3.amazonaws.com/brainscape-prod/system/cm/270/335/628/a_image_thumb.png?1552253049)
User the Master thereom to determine the run time of the divide and conquer algorithm listed below
![](https://s3.amazonaws.com/brainscape-prod/system/cm/270/335/809/q_image_thumb.png?1552253092)
![](https://s3.amazonaws.com/brainscape-prod/system/cm/270/335/809/a_image_thumb.png?1552253128)
what is the recursive formula for Strassen Algorithm.
What is the run time?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/270/339/969/a_image_thumb.png?1552254068)
Strassen Algorithm:
What are the following actions:
Divide
Conquer
Combine
Basecase
![](https://s3.amazonaws.com/brainscape-prod/system/cm/270/340/018/a_image_thumb.png?1552254119)
For matrix multiplication how are each of the C cells determined?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/270/340/069/q_image_thumb.png?1552254168)
![](https://s3.amazonaws.com/brainscape-prod/system/cm/270/340/069/a_image_thumb.png?1552254186)
Using strassed Algorithm
How are the C cells determined?
![](https://s3.amazonaws.com/brainscape-prod/system/cm/270/340/120/a_image_thumb.png?1552254249)
In general, how do you prove the correctness of the Strassen algorithm?
Show that after all the required calculations the c cells equal what they should: see below
![](https://s3.amazonaws.com/brainscape-prod/system/cm/270/340/300/a_image_thumb.png?1552254311)