Greedy Algorithms Quiz

Which of the following is a characteristic of a greedy algorithm?

• Solves subproblems recursively

• Always finds the globally optimal solution

• Makes the best choice at each step without considering future consequences

• Uses backtracking to find the solution

What is the time complexity of the Kruskal’s algorithm using a union-find data structure with path compression?

• O(V log V)

• O(E log V)

• O(V²)

• O(E log E)

Which of the following is NOT a property of a greedy algorithm?

• Greedy choice property

• Optimal substructure

• Dynamic programming approach

• Local optimal choice leads to a global optimum

Prim’s algorithm is used for solving which type of problem?

• Single-source shortest path

• Minimum spanning tree

• Maximum flow

• Topological sorting

Which of the following data structures is used to efficiently implement Prim’s algorithm?

• Stack

• Queue

• Priority Queue (Min Heap)

• Hash Table

Prim’s algorithm starts with:

• The edge with the lowest weight

• The highest weighted edge

• Any arbitrary vertex

• A randomly chosen edge

In Prim’s algorithm, how do we decide which edge to add next to the growing Minimum Spanning Tree (MST)?

• The edge with the minimum weight that connects a new vertex to the MST

• The edge with the maximum weight that connects a new vertex to the MST

• Any random edge from the graph

• The edge that forms a cycle in the MST

What is the main difference between Prim’s algorithm and Kruskal’s algorithm?

• Prim’s algorithm works for directed graphs, while Kruskal’s does not

• Prim’s algorithm grows a single tree, while Kruskal’s algorithm builds multiple trees and merges them

• Kruskal’s algorithm always runs faster than Prim’s algorithm

• Kruskal’s algorithm does not guarantee an MST

What is the main criterion for selecting edges in Prim’s algorithm?

• The edge with the minimum weight that does not form a cycle

• The edge with the maximum weight that does not form a cycle

• The edge that connects two unvisited vertices

• Any edge from the graph