- Computer Science Engineering (CSE)
- Design and Analysis of Algorithms
- Prim’s algorithm can be efficiently impl...

Q. |
## Prim’s algorithm can be efficiently implemented using for graphs with greater density. |

A. | d-ary heap |

B. | linear search |

C. | fibonacci heap |

D. | binary search |

Answer» A. d-ary heap | |

Explanation: in prim’s algorithm, we add the minimum weight edge for the chosen vertex which requires searching on the array of weights. this searching can be efficiently implemented using binary heap for dense graphs. and for graphs with greater density, prim’s algorithm can be made to run in linear time using d-ary heap(generalization of binary heap). |

View all MCQs in:
Design and Analysis of Algorithms

- Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure.
- Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm.
- Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.
- Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
- Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?
- Fractional knapsack problem is solved most efficiently by which of the following algorithm?
- Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them?
- In graphs, in which all vertices have an odd degree, the number of Hamiltonian cycles through any fixed edge is always even.
- Which algorithm is the most efficient numerical algorithm to obtain lcm?
- Is Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity?

Login to Continue

It will take less than 2 minutes

Report MCQ