Teaching HPSC Lecturer (Technical) Mock Test 2024 Algorithms Algorithm Design Techniques Greedy Algorithms
Four matrices M1, M2, M3 and M4 of dimensions p×q, q×r, r×s and s×t respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as [(M1 × M2) × (M3 × M4)] the total number of scalar multiplications is pqr + rst + prt. When multiplied as [((M1 × M2)× M3)) × M4], the total number of scalar multiplications is pqr + prs + pst.
If p = 10, q = 100, r = 20, s = 5 and t = 80, then the minimum number of scalar multiplications needed is:
1
248000
2
44000
3
19000
4
25000
5
Question Not Attempted