GATE 2024 algorithm Rank Booster Quiz 24

Match the following groups.
Group-I (Method)
A- Divide and conquer.
B- Greedy.
C- Dynamic programming.
Group-II
1- Independent sub problems can be solved in any order to solve the given problem.
2- Always chooses the right subproblem to solve the given problem.
3- An optimal solution to a problem contain optimal solutions to subproblems.
4- Every optimal solution to a subproblem will contribute to the main problem solution.

Consider the following matrices with the given dimension:
A₀ (4 × 6), A₁ (6 × 8), A₂ (8 × 4), A₃ (4 × 5)
Which of the following multiplication order gives an optimal solution of the above matrices?

Match List-I (Dynamic algorithm) with List-II (Average case running time) and select the correct answer using the codes given below the lists:

Let A1, A2, A3 and A4 be the matrices with the following dimension 10 X 3, 3 X 20, 20 X 10, 10 X 5 respectively. Which of the following two matrices should be multiplied first so that minimum scalar multiplication occur?