1. Which of the following problems can be efficiently solved using a greedy strategy?
a) Sorting a list of integers
b) Finding the longest path in a graph
c) Huffman coding
d) Solving a system of linear equations
Answer: c) Huffman coding
Explanation: Huffman coding is a classic example of a problem that can be efficiently solved using a greedy algorithm to generate optimal prefix codes.
2. What is the primary characteristic of a greedy algorithm?
a) It always guarantees the optimal solution
b) It makes the locally optimal choice at each step
c) It explores all possible solutions exhaustively
d) It relies on dynamic programming principles
Answer: b) It makes the locally optimal choice at each step
Explanation: Greedy algorithms make the best choice at each step without considering the overall problem, aiming to find a global optimum.
3. Which problem can be solved using the greedy strategy of selecting the smallest unused edge at each step?
a) Shortest path problem
b) Minimum spanning tree problem
c) Knapsack problem
d) Job sequencing with deadlines
Answer: b) Minimum spanning tree problem
Explanation: The greedy strategy of selecting the smallest unused edge at each step is commonly used in algorithms such as Prim’s and Kruskal’s algorithms for finding minimum spanning trees.
4. In the knapsack problem, which approach does a greedy algorithm typically follow?
a) Selecting items randomly
b) Choosing items with the maximum weight
c) Selecting items with the maximum value-to-weight ratio
d) Including items based on their value alone
Answer: c) Selecting items with the maximum value-to-weight ratio
Explanation: Greedy algorithms in the knapsack problem often prioritize items with the maximum value-to-weight ratio to maximize the value without exceeding the weight capacity.
5. Which problem can be efficiently solved using Dijkstra’s algorithm, a type of greedy algorithm?
a) Finding the minimum spanning tree
b) Job sequencing with deadlines
c) Single source shortest path
d) Optimal merge patterns
Answer: c) Single source shortest path
Explanation: Dijkstra’s algorithm efficiently finds the shortest path from a single source vertex to all other vertices in a weighted graph, making it suitable for the single source shortest path problem.
6. What is the key concept behind Huffman coding?
a) Maximizing compression ratio
b) Minimizing encoding time
c) Achieving lossless compression
d) Employing a dynamic programming approach
Answer: a) Maximizing compression ratio
Explanation: Huffman coding aims to achieve optimal data compression by assigning shorter codes to more frequent symbols, thereby maximizing the compression ratio.
7. Which of the following problems is NOT typically solved using a greedy strategy?
a) Optimal merge patterns
b) Job sequencing with deadlines
c) Shortest path problem
d) Traveling salesman problem
Answer: d) Traveling salesman problem
Explanation: The traveling salesman problem typically requires more complex techniques such as dynamic programming or branch and bound, rather than a simple greedy approach.
8. What does the greedy choice property state in the context of greedy algorithms?
a) The globally optimal solution can be reached by making locally optimal choices
b) The locally optimal choice may lead to a globally optimal solution
c) All possible choices must be explored exhaustively to find the optimal solution
d) Greedy algorithms always produce suboptimal solutions
Answer: b) The locally optimal choice may lead to a globally optimal solution
Explanation: Greedy algorithms rely on the assumption that making locally optimal choices at each step can lead to a globally optimal solution.
9. Which greedy algorithm is used for solving the job sequencing with deadlines problem?
a) Prim’s algorithm
b) Kruskal’s algorithm
c) Huffman coding
d) Earliest Deadline First (EDF) algorithm
Answer: d) Earliest Deadline First (EDF) algorithm
Explanation: In job sequencing with deadlines, the Earliest Deadline First (EDF) algorithm is commonly used to prioritize jobs based on their deadlines.
10. What is the primary limitation of greedy algorithms?
a) They are computationally expensive
b) They always guarantee the optimal solution
c) They may not always produce the optimal solution
d) They are only applicable to a limited range of problems
Answer: c) They may not always produce the optimal solution
Explanation: Greedy algorithms may not always produce the optimal solution as they make locally optimal choices without considering the global context of the problem.