Greedy Algorithms Quiz

For the greedy coin change algorithm to always produce an optimal solution, what must be true about the coin denominations?

• Arithmetic progression

• Geometric progression

• Greedy choice property (canonical set)

• Prime numbers

What is the time complexity of greedy coin change assuming sorted coins?

• O(n²)

• O(n log n)

• O(n)

• O(1)

Which statement is FALSE about greedy coin change?

• Always minimal coins for any coin set

• Picks largest coin possible each step

• May fail for some coin sets

• Efficient in time complexity

Using coins {25,10,5,1}, how many coins does greedy pick to make 30?

• 3

• 2

• 4

• 5

When does the greedy coin change fail?

• Coins {1,3,4}, amount 6

• Coins {1,5,10}, amount 15

• Coins {1,2,5,10}, amount 7

• Coins {1,10,25}, amount 35

If coin denominations are unsorted, what is the impact?

• No effect

• May not pick largest coin first

• Algorithm runs faster

• Algorithm is always incorrect

Greedy coin change picks coins in what order?

• Ascending by value

• Descending by value

• Random order

• Based on frequency

Greedy coin change algorithm can fail to find minimum coins for which coin set?

• {1,2,5}

• {1,4,5}

• {1,3,4}

• {1,5,10}

The coin changing problem is an example of:

• Divide and conquer

• Dynamic programming (in general)

• Greedy algorithm only

• Backtracking

For amount 63, coins {25,10,5,1}, greedy picks how many coins?

• 6

• 7

• 5

• 4