1 answer

# Analysis of algorithms

###### Question:

The square of a matrix A is its product with itself, AA.
(a) Show that ve multiplications are sufcient to compute the square of a 2 2 matrix.
What is wrong with the following algorithm for computing the square of an n n matrix?
?Use a divide-and-conquer approach as in Strassen's algorithm, except that instead
of getting 7 subproblems of size n=2, we now get 5 subproblems of size n=2
thanks to part (a). Using the same analysis as in Strassen's algorithm, we can
conclude that the algorithm runs in time O(nlog2 5).?
(c) In fact, squaring matrices is no easier than matrix multiplication. In this part, you will
show that if n n matrices can be squared in time S(n) = O(nc), then any two n n
matrices can be multiplied in time O(nc).
i. Given two n n matrices A and B, show that the matrix AB + BA can be computed in
time 3S(n) + O(n2).

## Answers

#### Similar Solved Questions

1 answer
##### Problem 07.004 - Source-free RC circuit The switch in the given figure has been in position...
Problem 07.004 - Source-free RC circuit The switch in the given figure has been in position A for a long time. Assume the switch moves instantaneously from A to B at t = 0. Find v for t> 0. Assume R = 1 k12. 5 kΩ Α + B 10 uF V 40 V E SR The voltage v(t) v(0) e-t/t, where v(0) = V and ...
1 answer
##### Please provide detailed answer, thank you! The scores of 8 students on the midterm exam and...
please provide detailed answer, thank you! The scores of 8 students on the midterm exam and final exam were as follows. Final Student Anderson Bailey Cruz DeSana Erickson Francis Gray Harris Midterm 100 98 96 96 87 80 78 73 85 94 93 71 99 76 88 95 Find the value of the (Spearman's) rank correlat...
1 answer
1 answer
##### Is it true that sperm does not get digested by the stomach and therefore just sits there for the rest of your life?
Is it true that sperm does not get digested by the stomach and therefore just sits there for the rest of your life?...