GATE 2011 CS (CS1) – Question 48

Algorithms · Dynamic Programming · 2 marks · Multiple choice

Matrices M₁,M₂,M₃,M₄ have dimensions p×q,q×r,r×s,s×t. With p=10,q=100,r=20,s=5,t=80, find minimum scalar multiplications.

248000
44000
19000
25000

Practise this question in The GATE Grind →

Show answer and explanation

Explanation

Pair costs are 20000,10000,8000. Triple minima are m₁₃=min(10000+5000,20000+1000)=15000 and m₂₄=min(8000+160000,10000+40000)=50000. Final splits cost 130000,44000,19000. The optimum ((M₁(M₂M₃))M₄) costs 10000+5000+4000=19000, C.

More Dynamic Programming questions

GATE 2010 CS (CS1) Q44 – The weight of a sequence a 0,,a n-1 is a 0+a 1/2++a n-1/2n-1. Subsequences preserve order…
GATE 2026 CS (CS2) Q39 – Consider a table T where the entries T[i][j], 0 i,j n, represent costs of subproblems in a…
GATE 2024 CS (CS2) Q35 – Let A be an array containing integer values. The distance of A is defined as the minimum…
GATE 2024 CS (CS2) Q42 – Consider an array X of n positive integers. The C code below computes the length of the…
GATE 2021 CS (CS1) Q50 – Define R n to be the maximum amount earned by cutting a rod of length n meters into one or…
GATE 2018 CS Q41 – Assume that multiplying a matrix G 1 of dimension p q with another matrix G 2 of dimension…

All Dynamic Programming questions →