PYQs / GATE CS / 2016 / Set 2 / Q48 GATE CS 2016 Set 2 — Question 48 Go beyond PYQs with Success Tracker AI-powered personalised practice and doubt support. Unlimited practice on eligible plans; AI usage limits apply. NAT +2 / -0 Medium Matrix Chain Multiplication Dynamic Programming Algorithms
Algorithms → Dynamic Programming → Matrix Chain Multiplication
Last updated 5 September 2026
Question Let
A 1 , A 2 , A 3 A_1, A_2, A_3 A 1 , A 2 , A 3 , and
A 4 A_4 A 4 be four matrices of dimensions
10 × 5 , 5 × 20 , 20 × 10 10 \times 5, 5 \times 20, 20 \times 10 10 × 5 , 5 × 20 , 20 × 10 , and
10 × 5 10 \times 5 10 × 5 , respectively. The minimum number of scalar multiplications required to find the product
A 1 A 2 A 3 A 4 A_1 A_2 A_3 A_4 A 1 A 2 A 3 A 4 using the basic matrix multiplication method is
______ .
Correct answer 1500 to 1500
Solution Matrix dimensions:
d 0 = 10 , d 1 = 5 , d 2 = 20 , d 3 = 10 , d 4 = 5 d_0=10, d_1=5, d_2=20, d_3=10, d_4=5 d 0 = 10 , d 1 = 5 , d 2 = 20 , d 3 = 10 , d 4 = 5 .
Cost
M [ i , j ] = min k ( M [ i , k ] + M [ k + 1 , j ] + d i − 1 d k d j ) M[i,j] = \min_k (M[i,k] + M[k+1,j] + d_{i-1}d_k d_j) M [ i , j ] = min k ( M [ i , k ] + M [ k + 1 , j ] + d i − 1 d k d j ) .
Chain Length 2: M [ 1 , 2 ] = 10 × 5 × 20 = 1000 M[1,2] = 10 \times 5 \times 20 = 1000 M [ 1 , 2 ] = 10 × 5 × 20 = 1000 M [ 2 , 3 ] = 5 × 20 × 10 = 1000 M[2,3] = 5 \times 20 \times 10 = 1000 M [ 2 , 3 ] = 5 × 20 × 10 = 1000 M [ 3 , 4 ] = 20 × 10 × 5 = 1000 M[3,4] = 20 \times 10 \times 5 = 1000 M [ 3 , 4 ] = 20 × 10 × 5 = 1000 Chain Length 3: M [ 1 , 3 ] = min ( M [ 1 , 1 ] + M [ 2 , 3 ] + 10 ⋅ 5 ⋅ 10 , M [ 1 , 2 ] + M [ 3 , 3 ] + 10 ⋅ 20 ⋅ 10 ) M[1,3] = \min(M[1,1]+M[2,3]+10\cdot 5\cdot 10, M[1,2]+M[3,3]+10\cdot 20\cdot 10) M [ 1 , 3 ] = min ( M [ 1 , 1 ] + M [ 2 , 3 ] + 10 ⋅ 5 ⋅ 10 , M [ 1 , 2 ] + M [ 3 , 3 ] + 10 ⋅ 20 ⋅ 10 ) = min ( 0 + 1000 + 500 , 1000 + 0 + 2000 ) = 1500 = \min(0+1000+500, 1000+0+2000) = 1500 = min ( 0 + 1000 + 500 , 1000 + 0 + 2000 ) = 1500 M [ 2 , 4 ] = min ( M [ 2 , 2 ] + M [ 3 , 4 ] + 5 ⋅ 20 ⋅ 5 , M [ 2 , 3 ] + M [ 4 , 4 ] + 5 ⋅ 10 ⋅ 5 ) M[2,4] = \min(M[2,2]+M[3,4]+5\cdot 20\cdot 5, M[2,3]+M[4,4]+5\cdot 10\cdot 5) M [ 2 , 4 ] = min ( M [ 2 , 2 ] + M [ 3 , 4 ] + 5 ⋅ 20 ⋅ 5 , M [ 2 , 3 ] + M [ 4 , 4 ] + 5 ⋅ 10 ⋅ 5 ) = min ( 0 + 1000 + 500 , 1000 + 0 + 250 ) = 1250 = \min(0+1000+500, 1000+0+250) = 1250 = min ( 0 + 1000 + 500 , 1000 + 0 + 250 ) = 1250 Chain Length 4: M [ 1 , 4 ] = min ( M[1,4] = \min( M [ 1 , 4 ] = min ( k = 1 : M [ 1 , 1 ] + M [ 2 , 4 ] + 10 ⋅ 5 ⋅ 5 = 0 + 1250 + 250 = 1500 , k=1: M[1,1]+M[2,4]+10\cdot 5\cdot 5 = 0+1250+250 = 1500, k = 1 : M [ 1 , 1 ] + M [ 2 , 4 ] + 10 ⋅ 5 ⋅ 5 = 0 + 1250 + 250 = 1500 , k = 2 : M [ 1 , 2 ] + M [ 3 , 4 ] + 10 ⋅ 20 ⋅ 5 = 1000 + 1000 + 1000 = 3000 , k=2: M[1,2]+M[3,4]+10\cdot 20\cdot 5 = 1000+1000+1000 = 3000, k = 2 : M [ 1 , 2 ] + M [ 3 , 4 ] + 10 ⋅ 20 ⋅ 5 = 1000 + 1000 + 1000 = 3000 , k = 3 : M [ 1 , 3 ] + M [ 4 , 4 ] + 10 ⋅ 10 ⋅ 5 = 1500 + 0 + 500 = 2000 k=3: M[1,3]+M[4,4]+10\cdot 10\cdot 5 = 1500+0+500 = 2000 k = 3 : M [ 1 , 3 ] + M [ 4 , 4 ] + 10 ⋅ 10 ⋅ 5 = 1500 + 0 + 500 = 2000 ) ) ) Minimum cost is 1500.
Turn this into a strength. Explore AI-powered practice and doubt support with Success Tracker. Review answer and solution without JavaScript Interactive answer checking needs JavaScript. The published solution is available below.
Correct answer 1500 to 1500
Solution Matrix dimensions:
d 0 = 10 , d 1 = 5 , d 2 = 20 , d 3 = 10 , d 4 = 5 d_0=10, d_1=5, d_2=20, d_3=10, d_4=5 d 0 = 10 , d 1 = 5 , d 2 = 20 , d 3 = 10 , d 4 = 5 .
Cost
M [ i , j ] = min k ( M [ i , k ] + M [ k + 1 , j ] + d i − 1 d k d j ) M[i,j] = \min_k (M[i,k] + M[k+1,j] + d_{i-1}d_k d_j) M [ i , j ] = min k ( M [ i , k ] + M [ k + 1 , j ] + d i − 1 d k d j ) .
Chain Length 2: M [ 1 , 2 ] = 10 × 5 × 20 = 1000 M[1,2] = 10 \times 5 \times 20 = 1000 M [ 1 , 2 ] = 10 × 5 × 20 = 1000 M [ 2 , 3 ] = 5 × 20 × 10 = 1000 M[2,3] = 5 \times 20 \times 10 = 1000 M [ 2 , 3 ] = 5 × 20 × 10 = 1000 M [ 3 , 4 ] = 20 × 10 × 5 = 1000 M[3,4] = 20 \times 10 \times 5 = 1000 M [ 3 , 4 ] = 20 × 10 × 5 = 1000 Chain Length 3: M [ 1 , 3 ] = min ( M [ 1 , 1 ] + M [ 2 , 3 ] + 10 ⋅ 5 ⋅ 10 , M [ 1 , 2 ] + M [ 3 , 3 ] + 10 ⋅ 20 ⋅ 10 ) M[1,3] = \min(M[1,1]+M[2,3]+10\cdot 5\cdot 10, M[1,2]+M[3,3]+10\cdot 20\cdot 10) M [ 1 , 3 ] = min ( M [ 1 , 1 ] + M [ 2 , 3 ] + 10 ⋅ 5 ⋅ 10 , M [ 1 , 2 ] + M [ 3 , 3 ] + 10 ⋅ 20 ⋅ 10 ) = min ( 0 + 1000 + 500 , 1000 + 0 + 2000 ) = 1500 = \min(0+1000+500, 1000+0+2000) = 1500 = min ( 0 + 1000 + 500 , 1000 + 0 + 2000 ) = 1500 M [ 2 , 4 ] = min ( M [ 2 , 2 ] + M [ 3 , 4 ] + 5 ⋅ 20 ⋅ 5 , M [ 2 , 3 ] + M [ 4 , 4 ] + 5 ⋅ 10 ⋅ 5 ) M[2,4] = \min(M[2,2]+M[3,4]+5\cdot 20\cdot 5, M[2,3]+M[4,4]+5\cdot 10\cdot 5) M [ 2 , 4 ] = min ( M [ 2 , 2 ] + M [ 3 , 4 ] + 5 ⋅ 20 ⋅ 5 , M [ 2 , 3 ] + M [ 4 , 4 ] + 5 ⋅ 10 ⋅ 5 ) = min ( 0 + 1000 + 500 , 1000 + 0 + 250 ) = 1250 = \min(0+1000+500, 1000+0+250) = 1250 = min ( 0 + 1000 + 500 , 1000 + 0 + 250 ) = 1250 Chain Length 4: M [ 1 , 4 ] = min ( M[1,4] = \min( M [ 1 , 4 ] = min ( k = 1 : M [ 1 , 1 ] + M [ 2 , 4 ] + 10 ⋅ 5 ⋅ 5 = 0 + 1250 + 250 = 1500 , k=1: M[1,1]+M[2,4]+10\cdot 5\cdot 5 = 0+1250+250 = 1500, k = 1 : M [ 1 , 1 ] + M [ 2 , 4 ] + 10 ⋅ 5 ⋅ 5 = 0 + 1250 + 250 = 1500 , k = 2 : M [ 1 , 2 ] + M [ 3 , 4 ] + 10 ⋅ 20 ⋅ 5 = 1000 + 1000 + 1000 = 3000 , k=2: M[1,2]+M[3,4]+10\cdot 20\cdot 5 = 1000+1000+1000 = 3000, k = 2 : M [ 1 , 2 ] + M [ 3 , 4 ] + 10 ⋅ 20 ⋅ 5 = 1000 + 1000 + 1000 = 3000 , k = 3 : M [ 1 , 3 ] + M [ 4 , 4 ] + 10 ⋅ 10 ⋅ 5 = 1500 + 0 + 500 = 2000 k=3: M[1,3]+M[4,4]+10\cdot 10\cdot 5 = 1500+0+500 = 2000 k = 3 : M [ 1 , 3 ] + M [ 4 , 4 ] + 10 ⋅ 10 ⋅ 5 = 1500 + 0 + 500 = 2000 ) ) ) Minimum cost is 1500.
Understand the concept, then try another question Revisit Algorithms with concept notes, common mistakes and an original worked example before your next attempt.
More questions on Dynamic Programming 2026 Set 1 Q17 Consider the following recurrence relations: For all n > 1 n > 1 n > 1 2026 Set 2 Q24 Consider the following functions, where n n n 2026 Set 2 Q25 Which of the following can be recurrence relation(s) corresponding to an algorithm with time… 2026 Set 2 Q32 Consider an array A = [ 10 , 7 , 8 , 19 , 41 , 35 , 25 , 31 ] A = [10, 7, 8, 19, 41, 35, 25, 31] A = [ 10 , 7 , 8 , 19 , 41 , 35 , 25 , 31 ] 2026 Set 2 Q37 Let G G G m m m n n n G G G ← Q47 Full paper Q49 → 