quiz_module 2

Time complexity of fractional knapsack problem is ____________

• O(n log n)

• o(n)

• O(n2)

• O(log n)

Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of knapsack=20. Find the maximum value output assuming items to be divisible.____________

• 60

• 80

• 100

• 40

The main time taking step in fractional knapsack problem is ___________

• a) Breaking items into fraction

• b) Adding items into knapsack

• c) Sorting

• d) Looping through sorted items

Consider a complete graph G with 4 vertices. The graph G has ____ spanning trees.

• 15

• 16

• 14

• 12

If all the weights of the graph are positive, then the minimum spanning tree of the graph is a minimum cost subgraph.

• a) True

• b) False

• may be

• do not say

Kruskal’s algorithm is a ______

• a) divide and conquer algorithm

• b) dynamic programming algorithm

• c) greedy algorithm

• d) approximation algorithm

What is the time complexity of Kruskal’s algorithm?

• a) O(log V)

• b) O(E log V)

• c) O(E2)

• d) O(V log E)

Which of the following is true?

• a) Prim’s algorithm can also be used for disconnected graphs

• b) Kruskal’s algorithm can also run on the disconnected graphs

• c) Prim’s algorithm is simpler than Kruskal’s algorithm

• d) In Kruskal’s sort edges are added to MST in decreasing order of their weights

Prim’s algorithm is a ______

• a) Divide and conquer algorithm

• b) Greedy algorithm

• c) Dynamic Programming

• d) Approximation algorithm

Which of the following is false about Prim’s algorithm?

• a) It is a greedy algorithm

• b) It constructs MST by selecting edges in increasing order of their weights

• c) It never accepts cycles in the MST

• d) It can be implemented using the Fibonacci heap