B2Q4

When a top-down approach of dynamic programming is applied to a problem, it usually _____________ compared to the recursive approach

• Decreases both, the time complexity and the space complexity

• Decreases the time complexity and increases the space complexity

• Increases the time complexity and decreases the space complexity

• Increases both, the time complexity and the space complexity

• none of these

Which of the following problems should be solved using dynamic programming in order to get better efficiency?

• Mergesort

• Binary search

• Finding nth Fibonacci number

• Quicksort

• all of these

How do you determine the cost of a spanning tree?

• By the sum of costs of the edges of the tree

• By the sum of the costs of the edges and vertices of the tree

• By the sum of the costs of the vertices of the tree

• By the sum of costs of the edges of the graph

• none of these

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

• It is a greedy algorithm

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

• It never accepts cycles in the MST

• It can be efficiently implemented using the linear queue