GATE 2018 CS Q.31: solution and answer

GATE 2018 · CSQ.31 · 2 marks · MCQ

Assume that multiplying a matrix $G_{1}$ of dimension $p \times q$ with another matrix $G_{2}$ of dimension $q \times r$ requires $pq r$ scalar multiplications. Computing the product of $n$ matrices $G_{1} G_{2} G_{3} \dots G_{n}$ can be done by parenthesizing in different ways. Define $G_{i} G_{i + 1}$ as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain $G_{1} G_{2} G_{3} G_{4} G_{5} G_{6}$ using parenthesization $(G_{1} (G_{2} G_{3})) (G_{4} (G_{5} G_{6}))$ , $G_{2} G_{3}$ and $G_{5} G_{6}$ are the only explicitly computed pairs.

Consider a matrix multiplication chain $F_{1} F_{2} F_{3} F_{4} F_{5}$ , where matrices $F_{1}, F_{2}, F_{3}, F_{4}$ and $F_{5}$ are of dimensions $2 \times 25$ , $25 \times 3$ , $3 \times 16$ , $16 \times 1$ and $1 \times 1000$ , respectively. In the parenthesization of $F_{1} F_{2} F_{3} F_{4} F_{5}$ that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

(A)
F1F2 and F3F4 only
(B)
F2F3 only
(C)
F3F4 only
(D)
F1F2 and F4F5 only

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The explicitly computed pair is F3F4 only — option (C).

Official answer: CSource: Official answer key, GATE 2018 CS (IIT Guwahati)

Set p = [p0..p5] = [2, 25, 3, 16, 1, 1000] from the given dimensions of F1..F5.
Pairwise (length-2) costs: m[1,2]=p0p1p2=150, m[2,3]=p1p2p3=1200, m[3,4]=p2p3p4=48, m[4,5]=p3p4p5=16000.
Length-3 chains: m[1,3]=min(m11+m23+p0p1p3, m12+m33+p0p2p3)=min(2000,246)=246 at split k=2 → (F1F2)(F3). m[2,4]=min(m22+m34+p1p2p4, m23+m44+p1p3p4)=min(123,1600)=123 at k=2 → F2*(F3F4). m[3,5]=min(m33+m45+p2p3p5, m34+m55+p2p4p5)=min(64000,3048)=3048 at k=4 → (F3F4)*F5.
Length-4 chains: m[1,4]=min over k=1,2,3 of (173,204,278)=173 at k=1 → F1*(F2F3F4). m[2,5]=min over k=2,3,4 of (78048,417200,25123)=25123 at k=4 → (F2F3F4)*F5.
Length-5 (whole chain) m[1,5]=min over k=1,2,3,4 of (75123,9198,48246,2173)=2173 at k=4 → top-level split (F1F2F3F4)(F5).
Unwind the optimal splits: m[1,4] splits at k=1 → F1*(F2F3F4); m[2,4] splits at k=2 → F2*(F3F4); m[3,4] is a base case, the direct product F3*F4.
Full optimal parenthesization: (F1(F2(F3F4)))F5, giving the minimum total cost 2173.
Trace the actual sequence of multiplications performed: (1) F3*F4 — both operands are original matrices, so this IS an explicitly computed pair; (2) F2*(F3F4) — one operand is already a computed product, not a pair of original matrices; (3) F1*(F2(F3F4)) — same; (4) (F1F2F3F4)*F5 — same.
Hence the only explicitly computed pair in the optimal parenthesization is F3F4, giving option (C).

KEY IDEA

Run the standard matrix-chain-multiplication DP to find the optimal parenthesization, then read off only those adjacent pairs of ORIGINAL matrices that end up being multiplied directly against each other (not a pair where one side is already a computed sub-product) — that is the precise meaning of "explicitly computed pair" given in the stem's own example.

WATCH OUT FOR

Confusing "explicitly computed pair" with any two matrices that appear next to each other in the optimal split, instead of tracing the actual multiplication order and keeping only steps where BOTH operands are original (un-combined) matrices. Here F1, F2 and F5 are each eventually multiplied against an already-computed product, not against another lone original matrix, so despite being "adjacent" in the chain, F1F2 and F4F5 are never explicitly computed pairs.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 8 Design techniques questions, with notes

GATE 2018 CS Q.31: solution and answer

Answer and solution

More Design techniques questions