subject
Engineering, 05.05.2020 08:50 20jhutchinson

The conventional way of multiplying two n-by-n matrices requires O(n3) time. There are much better ways of multiplying large matrices, bascd on a dividc-and-conquer approach. For example, Strassen's algorithm breaks cach n-by-n matrix into four submatrices of sizc n/2- by-n/2 each, and computes the result by performing 7 recursive multiplications on n/2-by-n/2 matrices plus a constant number of additions of n/2-by-n/2 matrices. Since addition of n-by-n matrices only requires O(n2) time, you get a recurrence for the running time of T(n) = 7T(n/2) + cn2 for some constant c (which, asymptotically, doesn't matter). Hypothetically, we can beat Strassen's approach if we can break our two n-by-n matrices into y2 submatrices of size n/y-by-n/y cach, and perform the multiplication of n-by-n matrices by using x recursive multiplications of n/y-by-n/y matrices plus any constant number of additions of n/y-by-n/y matrices. What is the relationship between x and y that would make this hypothetical algorithm have a lower running time than Strassen's algorithm? Identify one such pair below. Note, because the exact calculation requires the computation of logarithms, you may wish to find and use a scientific calculator of some sort. x=344: y-8. x=153; y=6.none of above

ansver
Answers: 3

Another question on Engineering

question
Engineering, 04.07.2019 18:10
Carbon dioxide gas expands isotherm a turbine from 1 mpa, 500 k at 200 kpa. assuming the ideal gas model and neglecting the kinetic and potential energies, determine the change in entropy, heat transfer and work for each kilogram of co2.
Answers: 2
question
Engineering, 04.07.2019 18:10
Assuming compressible flow of air and that the measurements are done at flagstaff a pitot static tube that gives the difference of total and static pressure measures 0.35 m of mercury. what is the velocity of air? assume the temperature to be 300k. (submit your excel or matlab calculation sheet)
Answers: 1
question
Engineering, 04.07.2019 18:10
The flow rate of air through a through a pipe is 0.02 m5/s. a pitot static tube is placed in the flow. the radius of the pitot static tube is 1 mm. assuming the flow to be steady and the air to be at 300k, calculate the difference in total and static pressure if the diameter of the pipe is: (a) d 0.1 m d 0.05 m (c) d 0.01 m
Answers: 2
question
Engineering, 04.07.2019 18:20
Select any two (2) areas of applications of chain-drive. (clo4) a)-permanent lubrication necessary b)-hydraulic forklift truck operation c)-rigging and heavy moving materials d)-relatively high maintenance costs e)-costlier than belt drives
Answers: 2
You know the right answer?
The conventional way of multiplying two n-by-n matrices requires O(n3) time. There are much better w...
Questions
question
English, 06.10.2019 09:01
question
Health, 06.10.2019 09:01
question
History, 06.10.2019 09:01
Questions on the website: 13722361