DAA Lab Viva

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

What is the worst case time complexity of merge sort?

• O(n log n)

• O(n²)

• O(n² log n)

• O(n log n²)

Time Complexity of Breadth First Search is?

(V – number of vertices, E – number of edges)

• O(V + E)

• O(V)

• O(E)

• O(V*E)

Consider the given graph.

What is the weight of the minimum spanning tree using the Kruskal’s algorithm?

• 24

• 23

• 15

• 19

In a Flow Network what is the source?

• Vertex with no leaving edges

• Centre vertex

• Vertex with no incoming edges

• Vertex with the least weight

Which of the following methods can be used to solve n-queen’s problem?

• greedy algorithm

• divide and conquer

• iterative improvement

• backtracking

Problems that can be solved in polynomial time are known as?

• intractable

• tractable

• decision

• complete

Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively. What is the number of multiplications required to multiply the two matrices?

• 10*20*30

• 10*30

• 10*20

• 20*30

Floyd Warshall’s Algorithm is used for solving ____________

• All pair shortest path problems

• Single Source shortest path problems

• Network flow problems

• Sorting problems

Which of the following is/are property/properties of a dynamic programming problem?

• Optimal substructure

• Overlapping subproblems

• Greedy approach

• Both optimal substructure and overlapping subproblems