Follow Us :

Algorithms - Algorithm Design Techniques

Avatto > > GATE COMPUTER SCIENCE > > Practice Questions > > Computer Science And Information Technology > > Algorithms > > Algorithm Design Techniques

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

  • Option : C
  • Explanation :
    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 = nC2 = 0(n2) (Since, there is an edge between all pair of vertices)
    ∴ Time Complexity = 0(n2.n) = 0(n3)
    ∴ Solution is (C)
    Note : Include vertex of degree zero in even degree vertices.
Cancel reply
Cancel reply

47. Four matrices M1, M2, M3 and M4 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 ((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

  • Option : C
  • Explanation :
    The problem can be solved using matrix chain multiplication. we get minimum number of multiplication using ((M1 × M2 ) × M3 ) × M4 )
    = 100 × 20 × 5 + 10 × 100 × 5 + 10 × 5 × 80
    = 19000.
Cancel reply
Cancel reply

48. Two matrices M1 and M2 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 M1 × M2 will be

  • Option : D
  • Explanation :
    The question is asking about the time complexity so it does not depends on storage scheme.
Cancel reply
Cancel reply

49. Let A1 , A2 , A3 and A4 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 A1 A2 A3 A4 using the basic matrix multiplication method is _________.

  • Option : A
  • Explanation :
    Using matrix chain multiplication the optional way to multiply is
    A1 × (A2 × A3 ) × A4
    = (5 × 20 × 10) + (5 × 10 × 5) + (10 × 5 × 5)
    = 1500.
Cancel reply
Cancel reply

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

  • Option : A
  • Explanation :
    All pair shortest path Algorithm is Application of Dynamic Programming
Cancel reply
Cancel reply
Related Quiz.
Algorithm Design Techniques