3. Algorithms

Greedy Methods — Quiz

Test your understanding of greedy methods with 5 practice questions.

Practice Questions

Question 1

Consider the problem of finding the minimum number of coins to make change for an amount $V$ using coin denominations $C = \{c_1, c_2, \dots, c_k\}$. If a greedy algorithm is used, which of the following properties of the coin system guarantees an optimal solution?

Question 2

When proving the correctness of a greedy algorithm, the 'greedy stays ahead' argument is often employed. Which of the following statements accurately describes the core idea of this proof technique?

Question 3

Consider the Fractional Knapsack Problem. Given a set of items, each with a weight $w_i$ and a value $v_i$, and a knapsack with a maximum capacity $W$. The goal is to maximize the total value of items in the knapsack, where fractions of items can be taken. Which greedy strategy guarantees an optimal solution?

Question 4

Dijkstra's algorithm finds the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights. At each step, it selects the unvisited vertex with the smallest known distance from the source. This decision exemplifies which property of greedy algorithms?

Question 5

Consider the Activity Selection Problem, where you have a set of activities, each with a start time $s_i$ and a finish time $f_i$. The goal is to select the maximum number of non-overlapping activities. Which greedy strategy yields an optimal solution?