Strassen\'s Algorithm - this is flutter PDF

Preview

Summary

this is flutter...

Description

Strassen’s Algorithm Multiple Choice Questions and Answers (MCQs) « Prev

Next »

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Strassen’s Algorithm”. 1. Strassen’s algorithm is a/an_____________ algorithm. a) Non- recursive b) Recursive c) Approximation d) Accurate Answer: b Explanation: Strassen’s Algorithm for matrix multiplication is a recursive algorithm since the present output depends on previous outputs and inputs. 2. What is the running time of Strassen’s algorithm for matrix multiplication? a) O(n 2.81) b) O(n3) c) O(n 1.8) d) O(n2) Answer: a Explanation: Strassen’s matrix algorithm requires only 7 recursive multiplications of n/2 x 2 n/2 matrix and Theta(n ) scalar additions and subtractions yielding the running time as O(n

2.81

).

3. What is the running time of naïve matrix multiplication algorithm? 2.81 a) O(n ) 4

b) O(n ) c) O(n) 3

d) O(n ) Answer: d Explanation: The traditional matrix multiplication algorithm takes O(n3 ) time. The number of recursive multiplications involved in this algorithm is 8. 4. Strassen’s matrix multiplication algorithm follows ___________ technique. a) Greedy technique

b) Dynamic Programming c) Divide and Conquer d) Backtracking Answer: c Explanation: Strassen’s matrix multiplication algorithm follows divide and conquer technique. In this algorithm the input matrices are divided into n/2 x n/2 sub matrices and then the recurrence relation is applied. 5. The number of scalar additions and subtractions used in Strassen’s matrix multiplication algorithm is ________ 2.81

a) O(n ) 2 b) Theta(n ) c) Theta(n) 3 d) O(n ) Answer: b Explanation: Using Theta(n2 ) scalar additions and subtractions, 14 matrices are computed each of which is n/2 x n/2. Then seven matrix products are computed recursively. 6. Running time of Strassen’s algorithm is better than the naïve Theta(n3 ) method. a) True b) False Answer: a Explanation: Strassen’s Algorithm requires only 7 recursive multiplications when compared 3

with the naïve Theta(n ) method which reuires 9 recursive multiplications to compute the product. 7. Given the program of naïve method. for i=1 to n do for j=1 to n do Z[i][j]=0; for k=1 to n do ___________________________

Fill in the blanks with appropriate formula a) Z[i][j] = Z[i][j] + X[i][k]*Y[k][j] b) Z[i][j] = Z[i][j] + X[i][k] + Y[k][j] c) Z[i][j] = Z[i][j] * X[i][k]*Y[k][j] d) Z[i][j] = Z[i][j] * X[i][k] + Y[k][j]

Answer: a Explanation: In the naïve method of matrix multiplication the number of iterating statements involved are 3, because of the presence of rows and columns. The element in each row of one matrix is multiplied with each element in the column of the second matrix. The computed value is placed in the new matrix Z[i][j]. 8. Who demonstrated the dierence in numerical stability? a) Strassen b) Bailey c) Lederman d) Higham Answer: d Explanation: The dierence in the numerical stability was demonstrated by Higham. He overemphasized that Strassen’s algorithm is numericaly unstable for some applications. 9. What is the recurrence relation used in Strassen’s algorithm? 2

a) 7T(n/2) + Theta(n ) 2 b) 8T(n/2) + Theta(n ) 2

c) 7T(n/2) + O(n ) 2 d) 8T(n/2) + O(n ) Answer: a Explanation: The recurrence relation used in Strassen’s algorithm is 7T(n/2) + Theta(n2 ) since there are only 7 recursive multiplications and Theta(n2 ) scalar additions and subtractions involved for computing the product. 10. Who discussed techniques for reducing the memory requirements for Strassen’s algorithm? a) Strassen b) Lederman c) Bailey d) Higham Answer: c Explanation: The submatrices formed at the levels of recursion consume space. Hence in order to overcome that Bailey discussed techniques for reducing the memory required. 11. What is the formula to calculate the element present in second row, rst column of the product matrix? a) M1+M7 b) M1+M3

c) M2+M4 – M5 + M7 d) M2+M4 Answer: d Explanation: The element at second row, rst column can be found by the formula M2 + M4, where M2 and M4 can be calculated by M2= (A(2,1) + A(2,2)) B(1,1) M4=A(2,2)(B(1,2) – B(1,1)). 12. Strassen’s Matrix Algorithm was proposed by _____________ a) Volker Strassen b) Andrew Strassen c) Victor Jan d) Virginia Williams Answer: a Explanation: Strassen’s matrix multiplication algorithm was rst published by Volker Strassen in the year 1969 and proved that the n3 general matrix multiplication algorithm wasn’t optimal. 13. How many iterating statements are involved in the naïve method of matrix multiplication? a) 1 b) 2 c) 3 d) 4 Answer: c Explanation: In the naïve method of matrix multiplication the number of iterating statements involved are 3, because of the presence of rows and columns in a matrix. The element in each row of the rst matrix is multiplied with each element in the column of the second matrix. 14. Strassen’s algorithm is quite numerically stable as the naïve method. a) True b) False Answer: b Explanation: Strassen’s algorithm is too numerically unstable for some applications. The computed result C=AB satises the inequality with a unit roundo error which corresponds to strong stability inequality(obtained by replacing matrix norms with absolute values of the matrix elements).

15. Compute the product matrix using Strassen’s matrix multiplication algorithm. Given a11=1; a12=3;a21=5;a22=7 b11=8;b12=4;b21=6;b22=2 a) c11=20;c12=12;c21=100;c22=15 b) c11=22;c12=8;c21=90;c22=32 c) c11=15;c12=7;c21=80;c22=34 d) c11=26;c12=10;c21=82;c22=34 Answer: d Explanation: The solution can be obtained by C11=1*8 + 3*6 =8+18=26 C12=1*4 + 3*2 =4+6=10 C21=5*8 + 7*6 =40+42=82 C22= 5*4 + 7*2=20+14=34. Sanfoundry Global Education & Learning Series – Data Structures & Algorithms. To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers. Participate in the Sanfoundry Certication contest to get free Certicate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs! Telegram | Youtube | LinkedIn | Instagram | Facebook | Twitter | Pinterest « Prev - Euclid’s Algorithm Multiple Choice Questions and Answers (MCQs) » Next - Pseudorandom Number Generators Multiple Choice Questions and Answers (MCQs)...