Greedy algorithms are a fundamental approach in computer science and optimization, where decisions are made by selecting the best available option at each step, with the aim of achieving an overall optimal solution. These algorithms prioritize immediate, locally optimal choices without reconsidering past decisions, making them simple and efficient for certain problems.
For instance, in the activity selection problem, a greedy algorithm sorts activities by their end times and selects the one that finishes earliest, then continues with the next compatible activity to maximize the number of selections.
Greedy algorithms shine in scenarios like Kruskal’s algorithm for finding minimum spanning trees or Dijkstra’s algorithm for shortest paths in graphs, as they often yield quick results with low computational overhead.
However, their key limitation is that they don’t always produce the global optimum, as seen in the fractional knapsack problem versus the 0-1 knapsack, where greediness works for the former but fails for the latter without additional checks.
Despite this, greedy strategies are valued for their speed and ease of implementation, making them ideal for real-time applications and as a baseline for more complex methods.
Table of Contents
- Part 1: OnlineExamMaker AI Quiz Generator – Save Time and Efforts
- Part 2: 20 Greedy Algorithms Quiz Questions & Answers
- Part 3: AI Question Generator – Automatically Create Questions for Your Next Assessment
Part 1: OnlineExamMaker AI Quiz Generator – Save Time and Efforts
Still spend a lot of time in editing questions for your next Greedy Algorithms assessment? OnlineExamMaker is an AI quiz maker that leverages artificial intelligence to help users create quizzes, tests, and assessments quickly and efficiently. You can start by inputting a topic or specific details into the OnlineExamMaker AI Question Generator, and the AI will generate a set of questions almost instantly. It also offers the option to include answer explanations, which can be short or detailed, helping learners understand their mistakes.
What you may like:
● Automatic grading and insightful reports. Real-time results and interactive feedback for quiz-takers.
● The exams are automatically graded with the results instantly, so that teachers can save time and effort in grading.
● LockDown Browser to restrict browser activity during quizzes to prevent students searching answers on search engines or other software.
● OnlineExamMaker API offers private access for developers to extract your exam data back into your system automatically.
Automatically generate questions using AI
Part 2: 20 Greedy Algorithms Quiz Questions & Answers
or
1. Question: What is a greedy algorithm?
Options:
A) An algorithm that makes the locally optimal choice at each step with the hope of finding a global optimum.
B) An algorithm that explores all possible solutions.
C) An algorithm that uses recursion to solve problems.
D) An algorithm that requires dynamic programming for optimization.
Answer: A
Explanation: Greedy algorithms work by making the best choice at the moment, assuming that this will lead to the best overall solution, though it may not always guarantee optimality.
2. Question: In the Activity Selection Problem, which activity should be selected first if activities are sorted by finish times?
Options:
A) The one with the earliest finish time.
B) The one with the latest start time.
C) The one with the longest duration.
D) The one with the earliest start time.
Answer: A
Explanation: Sorting by earliest finish time allows for maximizing the number of non-overlapping activities by greedily selecting the activity that ends first.
3. Question: For the Fractional Knapsack Problem, how is the item selection decided?
Options:
A) By the highest value-to-weight ratio.
B) By the highest weight.
C) By the highest value.
D) Randomly among items.
Answer: A
Explanation: Greedy choice selects items with the maximum value per unit weight, allowing fractions, which optimizes the total value.
4. Question: In Kruskal’s algorithm for Minimum Spanning Tree, how are edges sorted?
Options:
A) In non-decreasing order of their weights.
B) In non-increasing order of their weights.
C) By the number of vertices they connect.
D) Alphabetically by vertex labels.
Answer: A
Explanation: Sorting edges by weight and adding the smallest ones that don’t form a cycle ensures the minimum total weight for the spanning tree.
5. Question: In Prim’s algorithm, what does the algorithm start with?
Options:
A) A single vertex and grows the MST by adding the smallest edge.
B) All vertices and removes edges iteratively.
C) The edge with the highest weight.
D) A random subset of edges.
Answer: A
Explanation: Prim’s starts from an arbitrary vertex and greedily adds the nearest vertex not yet in the MST, minimizing the total edge weight.
6. Question: What is the primary goal of Dijkstra’s algorithm?
Options:
A) To find the shortest path from a source vertex to all other vertices in a graph.
B) To find the longest path in a graph.
C) To detect cycles in a graph.
D) To sort the vertices of a graph.
Answer: A
Explanation: Dijkstra’s uses a greedy approach by always selecting the vertex with the smallest distance from the source that hasn’t been processed yet.
7. Question: In Huffman Coding, how are codes generated?
Options:
A) By combining the two nodes with the lowest frequencies repeatedly.
B) By assigning fixed-length codes to characters.
C) By randomly assigning bits to characters.
D) By using the order of characters in the input.
Answer: A
Explanation: The greedy method merges the least frequent nodes to build a binary tree, resulting in optimal prefix codes for data compression.
8. Question: For Job Sequencing with Deadlines, how are jobs prioritized?
Options:
A) By the highest profit.
B) By the earliest deadline.
C) By the longest execution time.
D) Randomly.
Answer: A
Explanation: Jobs are sorted by decreasing profit and scheduled greedily into the latest possible slot before their deadline to maximize total profit.
9. Question: Why might a greedy algorithm fail to produce the optimal solution?
Options:
A) Because it makes locally optimal choices that don’t lead to a global optimum.
B) Because it always requires more memory.
C) Because it only works on undirected graphs.
D) Because it is slower than other algorithms.
Answer: A
Explanation: Greedy algorithms prioritize immediate benefits, which can lead to suboptimal results if future choices are affected negatively.
10. Question: What is a key difference between greedy algorithms and dynamic programming?
Options:
A) Greedy makes choices without considering the overall problem, while dynamic programming considers all subproblems.
B) Greedy is always optimal, unlike dynamic programming.
C) Dynamic programming is faster than greedy.
D) Greedy uses recursion, while dynamic programming does not.
Answer: A
Explanation: Greedy focuses on local optima at each step, whereas dynamic programming solves overlapping subproblems to ensure global optimality.
11. Question: In the Coin Change Problem (greedy version), what assumption makes it work?
Options:
A) The coin denominations are canonical (e.g., 1, 5, 10).
B) All coins have the same value.
C) The amount is always even.
D) Coins can be used negatively.
Answer: A
Explanation: Greedy works by always picking the largest denomination first, which is optimal only if the denominations follow a specific order like in standard currency.
12. Question: For Interval Scheduling, how are intervals selected?
Options:
A) By selecting the interval that ends first.
B) By selecting the longest interval.
C) By selecting intervals randomly.
D) By selecting the interval that starts first.
Answer: A
Explanation: Greedy selection of the earliest-ending interval maximizes the number of non-overlapping intervals.
13. Question: What is the time complexity of Kruskal’s algorithm?
Options:
A) O(E log E), where E is the number of edges.
B) O(V^2), where V is the number of vertices.
C) O(1).
D) O(V + E).
Answer: A
Explanation: Sorting the edges takes O(E log E), and union-find operations add a negligible cost, making it efficient for sparse graphs.
14. Question: In the Minimum Number of Platforms problem, how are trains scheduled?
Options:
A) By greedily assigning the platform that frees up the earliest.
B) By assigning platforms based on train numbers.
C) By using all platforms simultaneously.
D) By delaying all trains.
Answer: A
Explanation: Sorting arrival and departure times and using a greedy approach minimizes the number of platforms needed.
15. Question: Why is greedy choice property important for algorithms like Prim’s?
Options:
A) It ensures that the locally optimal substructure leads to a global optimum.
B) It reduces the algorithm’s memory usage.
C) It makes the algorithm randomized.
D) It eliminates the need for graphs.
Answer: A
Explanation: The greedy choice property guarantees that selecting the best option at each step will result in an optimal solution for the entire problem.
16. Question: In Egyptian Fraction representation, how are fractions decomposed?
Options:
A) By greedily subtracting the largest unit fraction less than or equal to the remaining fraction.
B) By dividing the numerator and denominator equally.
C) By using random fractions.
D) By multiplying the fraction by 2 repeatedly.
Answer: A
Explanation: The greedy algorithm selects the largest possible unit fraction at each step to represent the given fraction.
17. Question: For Huffman Coding, what does the final tree represent?
Options:
A) A binary tree where the path from root to leaf gives the code.
B) A linear list of characters.
C) A cycle in a graph.
D) A matrix of frequencies.
Answer: A
Explanation: The greedy construction of the Huffman tree assigns shorter codes to more frequent characters, minimizing the overall length.
18. Question: When does the greedy algorithm for Activity Selection guarantee an optimal solution?
Options:
A) When activities are sorted by finish times.
B) When all activities have the same duration.
C) When there are no overlapping activities.
D) When activities are unsorted.
Answer: A
Explanation: Sorting by finish times ensures that the greedy selection maximizes the number of activities without conflicts.
19. Question: What advantage does a greedy algorithm have over exhaustive search?
Options:
A) It is generally faster and more efficient for certain problems.
B) It always finds the exact solution.
C) It uses less memory than exhaustive search.
D) Both A and C.
Answer: D
Explanation: Greedy algorithms avoid exploring all possibilities, making them quicker and more memory-efficient while still solving problems optimally in many cases.
20. Question: In Dijkstra’s algorithm, what happens if there are negative weights in the graph?
Options:
A) It may not work correctly.
B) It runs faster.
C) It produces multiple shortest paths.
D) It converts weights to positive.
Answer: A
Explanation: Dijkstra’s greedy approach assumes non-negative weights; negative weights can lead to incorrect results by altering the order of vertex selection.
or
Part 3: AI Question Generator – Automatically Create Questions for Your Next Assessment
Automatically generate questions using AI