Strassen’s Algorithm Multiple choice Questions and Answers (MCQs)

Click on any option to know the CORRECT ANSWERS

 Question 1
Strassen's algorithm is a/an..... algorithm.
 A Non- recursive B Recursive C Approximation D Accurate

Question 1 Explanation:
Strassen's Algorithm for matrix multiplication is a recursive algorithm since the present output depends on previous outputs and inputs.

 Question 2
What is the running time of Strassen's algorithm for matrix multiplication?
 A O(n2.81) B O(n3) C O(n1.8) D O(n2)

Question 2 Explanation:
Strassen's matrix algorithm requires only 7 recursive multiplications of n/2 x n/2 matrix and Theta(n2) scalar additions and subtractions yielding the running time as O(n2.81).

 Question 3
What is the running time of naive matrix multiplication algorithm?
 A O(n2.81) B O(n4) C O(n) D O(n3)

Question 3 Explanation:
The traditional matrix multiplication algorithm takes O(n3) time. The number of recursive multiplications involved in this algorithm is 8.

 Question 4
Strassen's matrix multiplication algorithm follows ..... technique.
 A Greedy technique B Dynamic Programming C Divide and Conquer D Backtracking

Question 4 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.

 Question 5
The number of scalar additions and subtractions used in Strassen's matrix multiplication algorithm is .....
 A O(n2.81) B Theta(n2) C Theta(n) D O(n3)