Q.1 Which algorithm is typically used to multiply two matrices using divide and conquer?
Strassen’s Algorithm
Dijkstra’s Algorithm
Kruskal’s Algorithm
Floyd-Warshall Algorithm
Explanation - Strassen’s Algorithm is a divide and conquer method that reduces the number of multiplications required for matrix multiplication.
Correct answer is: Strassen’s Algorithm
Q.2 What is the time complexity of the naive matrix multiplication algorithm?
O(n^2)
O(n^3)
O(n log n)
O(n^4)
Explanation - The naive matrix multiplication algorithm requires three nested loops, leading to O(n^3) complexity.
Correct answer is: O(n^3)
Q.3 Strassen’s Algorithm reduces the multiplication count from 8 to how many?
6
7
5
9
Explanation - Strassen’s method cleverly reduces the required number of multiplications from 8 to 7, speeding up computation.
Correct answer is: 7
Q.4 In divide and conquer matrix multiplication, the matrix is divided into how many submatrices?
2
4
8
16
Explanation - A matrix is divided into four quadrants (submatrices) in divide and conquer techniques.
Correct answer is: 4
Q.5 The recurrence relation for Strassen’s algorithm is:
T(n)=7T(n/2)+O(n^2)
T(n)=8T(n/2)+O(n)
T(n)=7T(n/2)+O(n)
T(n)=n^3
Explanation - Strassen’s method splits matrices into halves and performs 7 multiplications and O(n^2) additions.
Correct answer is: T(n)=7T(n/2)+O(n^2)
Q.6 What is the asymptotic complexity of Strassen’s algorithm?
O(n^2.81)
O(n^2)
O(n^3)
O(n log n)
Explanation - Strassen’s algorithm has a time complexity of O(n^log2(7)) ≈ O(n^2.81).
Correct answer is: O(n^2.81)
Q.7 Which operation is more in Strassen’s algorithm compared to naive method?
Multiplications
Additions
Subtractions
Exponentiations
Explanation - Strassen reduces multiplications but increases the number of additions and subtractions.
Correct answer is: Additions
Q.8 What is the base case for recursive divide and conquer matrix multiplication?
1x1 matrices
2x2 matrices
n=log n
n=0
Explanation - The recursion stops when the submatrices are of size 1x1, at which point multiplication is direct.
Correct answer is: 1x1 matrices
Q.9 Which of the following is an advantage of Strassen’s algorithm?
Lower space requirement
Fewer multiplications
Less addition
Simpler implementation
Explanation - Strassen’s algorithm is designed to reduce the multiplication count, which is costlier than additions.
Correct answer is: Fewer multiplications
Q.10 Divide and conquer matrix multiplication splits the problem into:
n subproblems
2 subproblems
4 subproblems
7 subproblems
Explanation - The divide and conquer approach splits each n×n matrix into 4 smaller n/2×n/2 submatrices.
Correct answer is: 4 subproblems
Q.11 The master theorem can be applied to Strassen’s recurrence. What is the result?
O(n^3)
O(n^2.81)
O(n^2)
O(log n)
Explanation - By applying the Master Theorem to T(n)=7T(n/2)+O(n^2), we get O(n^log2(7)) ≈ O(n^2.81).
Correct answer is: O(n^2.81)
Q.12 The naive matrix multiplication requires how many multiplications for 2x2 matrices?
4
6
7
8
Explanation - Each element of the resulting 2x2 matrix requires two multiplications, resulting in 8 total multiplications.
Correct answer is: 8
Q.13 Strassen’s method computes matrix multiplication using how many recursive multiplications for 2x2 matrices?
8
6
7
4
Explanation - Strassen reduces the number of recursive multiplications from 8 to 7.
Correct answer is: 7
Q.14 Which of the following is NOT true about Strassen’s algorithm?
It uses fewer multiplications
It requires more additions
It is simpler to implement
It is faster than naive method asymptotically
Explanation - Strassen’s algorithm is more complex to implement compared to the naive method.
Correct answer is: It is simpler to implement
Q.15 Which divide and conquer principle is used in Strassen’s algorithm?
Decrease and conquer
Split and combine
Transform and conquer
Dynamic programming
Explanation - Strassen’s algorithm splits matrices into parts, solves them, and combines the results.
Correct answer is: Split and combine
Q.16 What is the main disadvantage of Strassen’s algorithm in practice?
It is slower for large matrices
It has numerical instability
It increases multiplications
It uses O(n^4) time
Explanation - Strassen’s algorithm may cause numerical errors due to increased additions and subtractions.
Correct answer is: It has numerical instability
Q.17 For which matrix size does Strassen’s algorithm become beneficial compared to naive multiplication?
Very small matrices
Large matrices
1x1 matrices
2x2 matrices only
Explanation - The overhead of recursion makes Strassen’s method efficient only for larger matrices.
Correct answer is: Large matrices
Q.18 Which algorithm improved Strassen’s algorithm further?
Coppersmith-Winograd
Dijkstra’s Algorithm
Bellman-Ford
Prim’s Algorithm
Explanation - The Coppersmith-Winograd algorithm further reduced the exponent of matrix multiplication.
Correct answer is: Coppersmith-Winograd
Q.19 What is the complexity of Coppersmith-Winograd algorithm?
O(n^2.81)
O(n^2.376)
O(n^3)
O(n^2)
Explanation - Coppersmith-Winograd reduced the matrix multiplication complexity exponent to approximately 2.376.
Correct answer is: O(n^2.376)
Q.20 Matrix multiplication is associative. What does this mean?
(AB)C = A(BC)
(AB)C = AC(B)
(A+B)C = A(BC)
A^T B = AB^T
Explanation - Associativity means grouping of operations does not affect the result in matrix multiplication.
Correct answer is: (AB)C = A(BC)
Q.21 In divide and conquer, each recursive step reduces the matrix size by:
Half
Quarter
One-third
Remains same
Explanation - The matrices are divided into four submatrices of half the size at each recursive step.
Correct answer is: Half
Q.22 Which type of algorithm design strategy does Strassen’s algorithm follow?
Greedy
Dynamic Programming
Divide and Conquer
Backtracking
Explanation - Strassen’s algorithm is a classic example of divide and conquer applied to matrix multiplication.
Correct answer is: Divide and Conquer
Q.23 What is the primary bottleneck of the naive O(n^3) algorithm?
Additions
Multiplications
Subtractions
Memory access
Explanation - Multiplications are computationally more expensive than additions in naive matrix multiplication.
Correct answer is: Multiplications
Q.24 What type of matrices are suitable for Strassen’s algorithm?
Sparse matrices
Large dense matrices
Diagonal matrices
Triangular matrices
Explanation - Strassen’s algorithm is best applied to large, dense matrices where multiplications dominate.
Correct answer is: Large dense matrices
Q.25 How many recursive calls are made in Strassen’s method per step?
8
7
6
4
Explanation - Strassen’s method makes 7 recursive calls per divide and conquer step.
Correct answer is: 7