Greedy Algorithms - Quiz

Q: What is the main idea behind the Huffman coding algorithm?

A. Making the locally optimal choice at each step to obtain a globally optimal solution
B. Breaking a problem down into smaller subproblems
C. Generating all possible solutions and selecting the best one
D. Searching for a solution by gradually eliminating possibilities

Correct Option: A
Explanation:

Answer: Making the locally optimal choice at each step to obtain a globally optimal solution

Explanation: The Huffman coding algorithm is a greedy algorithm that constructs a variable-length prefix code for a set of characters based on their frequencies, with the goal of minimizing the average code length.

Q: What is the time complexity of the greedy algorithm for the coin change problem?

A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)

Correct Option: A
Explanation:

Answer: O(n)

Explanation: The greedy algorithm for the coin change problem has a time complexity of O(n), where n is the number of coins used to make the change.

Q: Which of the following is a disadvantage of the Huffman coding algorithm?

A. It always guarantees the optimal solution
B. It can be slow for large input sizes
C. It requires a lot of memory
D. It may not always find the globally optimal solution

Correct Option: D
Explanation:

Answer: It may not always find the globally optimal solution

Explanation: The Huffman coding algorithm may not always find the globally optimal solution since it makes locally optimal choices at each step.

Q: Which of the following is an example of a problem that cannot be solved using a greedy algorithm?

A. Finding the shortest path between two nodes in a graph
B. Computing the greatest common divisor of two numbers
C. Sorting a list of integers
D. The traveling salesman problem

Correct Option: D
Explanation: Answer : The traveling salesman problem

Explanation: The traveling salesman problem is a well-known problem that cannot be solved using a greedy algorithm since it requires examining all possible permutations of the cities to find the shortest possible route.

Q: Which of the following is a disadvantage of a greedy algorithm?

A. It always guarantees the optimal solution
B. It can be slow for large input sizes
C. It requires a lot of memory
D. It may not always find the globally optimal solution

Correct Option: D
Explanation:

Answer: It may not always find the globally optimal solution

Explanation: A greedy algorithm may not always find the globally optimal solution since it makes locally optimal choices at each step without considering the future consequences. This can lead to suboptimal solutions for some problems.

Q: Which of the following is an example of a problem that can be solved using a greedy algorithm?

A. Finding the shortest path between two nodes in a graph
B. Computing the greatest common divisor of two numbers
C. Sorting a list of integers
D. The coin change problem

Correct Option: D
Explanation:

Answer: The coin change problem

Explanation: The coin change problem can be solved using a greedy algorithm, where the algorithm selects the largest denomination of coin possible at each step until the total amount is reached.

Q: Which of the following is an example of a problem that can be solved using a greedy algorithm with a proof of optimality?

A. The knapsack problem
B. The minimum spanning tree problem
C. The job scheduling problem
D. The longest common subsequence problem

Correct Option: B
Explanation:

Answer: The minimum spanning tree problem

Explanation: The minimum spanning tree problem can be solved using a greedy algorithm called Kruskal's algorithm, which has a proof of optimality.

Q: What is the main idea behind a greedy algorithm?

A. Solving a problem by breaking it down into smaller subproblems
B. Generating all possible solutions and selecting the best one
C. Repeating the same steps over and over until a solution is found
D. Making the locally optimal choice at each step to obtain a globally optimal solution

Correct Option: D
Explanation:

Answer: Making the locally optimal choice at each step to obtain a globally optimal solution

Explanation: A greedy algorithm makes the locally optimal choice at each step in the hope of finding a globally optimal solution. The algorithm chooses the best option available at each step without considering the future consequences.

Q: What is the time complexity of the Huffman coding algorithm?

A. O(n)
B. O(n log n)
C. O(n^2)
D. O(log n)

Correct Option: B
Explanation:

Answer: O(n log n)

Explanation: The Huffman coding algorithm has a time complexity of O(n log n), where n is the number of characters to be encoded.

Q: What is the main idea behind the interval scheduling problem?

A. Selecting a subset of intervals that do not overlap
B. Sorting the intervals by start time and selecting the earliest start time
C. Sorting the intervals by end time and selecting the earliest end time
D. Generating all possible subsets of intervals and selecting the one with the most intervals

Correct Option: A
Explanation:

Answer: Selecting a subset of intervals that do not overlap

Explanation: The interval scheduling problem involves selecting a subset of intervals that do not overlap, with the goal of selecting the maximum number of intervals possible. A greedy algorithm can be used to solve this problem by selecting the interval with the earliest end time, and then selecting the next interval with the earliest end time that does not overlap with the previously selected intervals.