Algorithms MCQ - Algorithm Design Techniques

46 What is the time complexity of Bellman -Ford single-source shortest path algorithm on a complete graph of n vertices?

Given: A complete graph on n vertices?
To find: Time complexity of Bellman-Ford Single source shortest path.
Analysis: Time complexity of Bellman-ford algorithm on a graph with n vertices and m edges is O(nm) For a complete graph, m = ⁿC₂ = 0(n²) (Since, there is an edge between all pair of vertices)
∴ Time Complexity = 0(n².n) = 0(n³)
∴ Solution is (C)
Note : Include vertex of degree zero in even degree vertices.

47 Four matrices M₁, M₂, M₃ and M₄ of dimensions p x q, q x r, r x s and s x t respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as ((M₁ × M₂ ) × (M₃ × M₄ )), the total number of scalar multiplications is pqr + rst + prt. When multiplied as ((M₁ × M₂ ) × M₃ ) × M₄ ), 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

The problem can be solved using matrix chain multiplication. we get minimum number of multiplication using ((M₁ × M₂ ) × M₃ ) × M₄ )
= 100 × 20 × 5 + 10 × 100 × 5 + 10 × 5 × 80
= 19000.

48 Two matrices M₁ and M₂ are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute M₁ × M₂ will be

The question is asking about the time complexity so it does not depends on storage scheme.

49 Let A₁ , A₂ , A₃ and A₄ be four matrices of dimensions 10 × 5, 5 × 20, 20 × 10, and 10 × 5, respectively. The minimum number of scalar multiplications required to find the product A₁ A₂ A₃ A₄ using the basic matrix multiplication method is _________.

Using matrix chain multiplication the optional way to multiply is
A₁ × (A₂ × A₃ ) × A₄
= (5 × 20 × 10) + (5 × 10 × 5) + (10 × 5 × 5)
= 1500.

50 Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?

All pair shortest path Algorithm is Application of Dynamic Programming