Virtual Labs

Greedy Algorithms 1: Coin Change Problem

For which type of coin systems does the greedy coin change algorithm always produce an optimal solution?

a: Any arbitrary coin system Explanation

Explanation

b: Canonical coin systems Explanation

Explanation

c: Coin systems with prime denominations Explanation

Explanation

d: Coin systems with equal gaps Explanation

Explanation

Why does the greedy algorithm sort coin denominations in descending order for the coin change problem?

a: To reduce time complexity Explanation

Explanation

b: To ensure larger coins are chosen first Explanation

Explanation

c: To remove duplicate denominations Explanation

Explanation

d: To simplify implementation Explanation

Explanation

Given denominations {1, 7, 10} and amount 14, what result will the greedy algorithm produce?

a: 7 + 7 Explanation

Explanation

b: 10 + 1 + 1 + 1 + 1 Explanation

Explanation

c: 1 + 1 + 1 + 1 + 10 Explanation

Explanation

d: No solution Explanation

Explanation

Why is the greedy solution for denominations {1, 3, 4} and amount 6 considered suboptimal?

a: It uses repeated coins Explanation

Explanation

b: It ignores smaller denominations Explanation

Explanation

c: It minimizes value instead of coin count Explanation

Explanation

d: It makes a locally optimal choice that blocks a global optimum Explanation

Explanation

Which property is required for a greedy algorithm to guarantee optimality in the coin change problem?

a: Overlapping subproblems Explanation

Explanation

b: Greedy choice property Explanation

Explanation

c: Recursive structure Explanation

Explanation

d: Backtracking capability Explanation

Explanation

In greedy coin change, what happens if a denomination exactly equals the remaining amount?

a: The algorithm terminates immediately Explanation

Explanation

b: The coin is selected and the process ends Explanation

Explanation

c: The coin is skipped Explanation

Explanation

d: The algorithm restarts Explanation

Explanation

Why are greedy algorithms generally faster than dynamic programming for the coin change problem?

a: Greedy explores all combinations Explanation

Explanation

b: Greedy avoids recursion Explanation

Explanation

c: Greedy makes one decision per step without revisiting subproblems Explanation

Explanation

d: Greedy stores intermediate results Explanation

Explanation

For denominations {1, 5, 6, 9} and amount 11, which solution will the greedy algorithm produce?

a: 6 + 5 Explanation

Explanation

b: 9 + 1 + 1 Explanation

Explanation

c: 5 + 5 + 1 Explanation

Explanation

d: 6 + 1 + 1 + 1 + 1 + 1 Explanation

Explanation

What is the time complexity of the greedy coin change algorithm if there are n coin denominations and the amount is A?

a: O(n × A) Explanation

Explanation

b: O(A) Explanation

Explanation

c: O(n log n) Explanation

Explanation

d: O(n + A) Explanation

Explanation

Which statement correctly compares greedy and dynamic programming approaches for coin change?

a: Greedy is always optimal and faster Explanation

Explanation

b: Dynamic programming is faster but less accurate Explanation

Explanation

c: Greedy is faster but may be suboptimal, while DP guarantees optimality Explanation

Explanation

d: Both always produce the same result Explanation

Explanation