**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.