IIIT Hyderabad Practice Quiz : Algorithms-3

In an weighted, directed connected graph, the shortest path between every pair of nodes in graph is computed most efficiently in terms of running time complexity, is given by which of the following algorithm?

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

List-I (Dynamic algorithm)

A) Matrix chain multiplication

B) Travelling salesman problem

C) 0/1 knapsack

D) Fibonacci series

List-II (Average case returning time)

1) O (mn)

2) O(n³)

3) O(nⁿ)

4) O(n)

Which of the following is used in Dynamic programming strategy

I. Optimality structure

II. Memorization

III. Bottom up construction of solution

Suppose that minimum spanning tree of the following edge weighted graph contains the edge weights x as well z.

Then maximum value of x + z is?

In Quick Sort when the level alternate between good and bad splits, what will be the worst case time complexity for this algorithm?

Good split means the sorting of data elements after partition takes minimum time and Bad split means the sorting of data elements after partition takes maximum time.