Algorithms Test...

Let String x be of length m and String y be of length n. What is the time complexity to find the longest common subsequence of the String x and y using Dynamic programming?

Consider the following table:

Algorithms	Design Paradigms
(A) Minimum spanning tree	(I) Divide and Conquer
(B) Binary Search	(II) Greedy
(C) Fibonacci numbers	(III) Dynamic Programming

 

Choose the appropriate algorithms to the design paradigms they are based on.

Let ‘m’ and ‘n’ be the number of edges and vertices in a graph G, respectively. Which of the following is the time complexity of the Kruskal’s algorithm to find minimum spanning tree of G?

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 ______.

Consider a graph G(V, E) in which the V is the total number of vertices and E is the total number of edges in the graph. What is the total number of spanning tree of G in which V = 7 and E = 21?

Consider two sequences A and B:

A = <0,1,2,1,3,0,1 >

B = <1,3,2,0,1,0 >

If the length of the longest common subsequence x and number of longest common subsequence is y then the value of x³ + y³ + 3x²y + 3xy² is _____ 

Consider a person having 1 rupee coin, 4 rupee coin, 5 rupee coin, 10 rupee coin, and 20 rupee coin. Assume a person have an infinite number of all such coins. What is the absolute difference between the minimum number of coins needed to take the sum of 78 using the Greedy method and Dynamic Programming?