multiplies two square matrices A and B
This assignment is about the following algorithm, which multiplies two square matrices A and B to produce a new square matrix C. Each matrix has size n × n. The algorithm uses a notation similar to that of the Rosen text.
1 for i := 1 to n
2 for j := 1 to n
3 cij := 0
4 for k := 1 to n
5 cij := cij + aik × bkj
1. (5 points.) Suppose that a primitive operation is either an assignment (:=), an addition (+), or a multiplication (×). How many primitive operations does the algorithm perform? You must count only the primitive operations in lines 3 and 5.
2. (5 points.) Prove that the algorithm performs O(n3) primitive operations. You must find constants C and k according to the definition of O on page 205 of the Rosen text.
3. (10 points.) Prove that the algorithm performs more than O(n) primitive operations. You must use the definition of O on page 205 of the Rosen text.
*Big-O definition (Page 205):
I1145224.pdf
Let f and g be functions from the set of integers or the set of real numbers to the set of real numbers. We say that f (x) is O(g(x)) if there are constants C and k such that
|f (x)| ≤ C|g(x)|
whenever x > k. [This is read as “f (x) is big-oh of g(x).”]
Answers
Status NEW
Posted 29 May 2017 04:05 AM
My Price 9.00
-----------
Attachments
file 1496033151-Solutions file 2.docx preview (51 words )
H-----------ell-----------o S-----------ir/-----------Mad-----------am
-----------
Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------.
-----------
Th-----------ank----------- yo-----------u
-----------
Not Rated(0)