Exams › GATE › Technical

Assume that multiplying a matrix G1 of dimension p × q with another matrix G2 of dimension q × r requires pqr scalar multiplications. Computing the product of n matrices G1 G2 G3... Gn can be done by parenthesizing in different ways. Define G_i G_(i+1) as an explicitly computed pair for a given parenthesization if they are directly multiplied. For example, in the matrix multiplication chain G1 G2 G3 G4 G5 G6 using parenthesization ((G1(G2G3))(G4(G5G6))), G2G3 and G5G6 are the only explicitly computed pairs. Consider a matrix multiplication chain F1 F2 F3 F4 F5, where matrices F1, F2, F3, F4 and F5 are of dimensions 2×25, 25×3, 3×16, 16×1 and 1×1000, respectively. In the parenthesization of F1 F2 F3 F4 F5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

1. F1F2 and F3F4 only
2. F2F3 only
3. F3F4 only
4. F1F2 and F4F5 only

Correct answer: F3F4 only

Solution

With dimensions 2x25, 25x3, 3x16, 16x1, 1x1000, the optimal parenthesization is ((F1(F2(F3F4)))F5) with 2173 scalar multiplications. The only directly multiplied adjacent pair is F3F4, so option 2 is correct; the stored answer (F1F2 and F3F4) is wrong.

Related GATE Technical questions

• We want to design a synchronous counter that counts the sequence 0-1-0-2-0-3 and then repeats. The minimum number of J-K flip-flops required to implement this counter is
• A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are performed efficiently. Which one of the following statements is CORRECT (n refers to the number of items in the queue)?
• Consider the following C program. void f(int, short); void main() { int i = 100; short s = 12; short *p = &s; ________; // call to f() } Which one of the following expressions, when placed in the blank above, will NOT result in a type checking error?
• The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
• Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE? P: Minimum spanning tree of G does not change Q: Shortest path between any pair of vertices does not change
• Consider the following C program. #include<stdio.h> void mystery(int *ptra, int *ptrb) { int *temp; temp = ptrb; ptrb = ptra; ptra = temp; } int main() { int a=2016, b=0, c=4, d=42; mystery(&a, &b); if (a < c) mystery(&c, &a); mystery(&a, &d); printf("%d ", a); } The output of the program is _________.

⚔️ Practice GATE Technical free + battle 1v1 →