Why Greedy Works and When It Fails in DSA C - Quick Recap

Recall & Review

beginner

What is the main idea behind the greedy algorithm approach?

A greedy algorithm makes the best choice at each step, hoping to find the overall best solution by building it piece by piece.

intermediate

When does a greedy algorithm guarantee an optimal solution?

When the problem has the greedy-choice property and optimal substructure, meaning local best choices lead to a global best solution.

intermediate

What is the greedy-choice property?

It means that a locally optimal choice can be extended to a globally optimal solution without reconsidering previous choices.

intermediate

Give an example of a problem where greedy algorithms fail to find the optimal solution.

The coin change problem with arbitrary coin denominations can fail with greedy algorithms because picking the largest coin first may not lead to the fewest coins overall.

intermediate

Why does the greedy algorithm fail in some problems?

Because the problem lacks the greedy-choice property or optimal substructure, so local best choices do not lead to the global best solution.

Which property must a problem have for a greedy algorithm to always work?

A Randomness

B Greedy-choice property

C Brute force

D Backtracking

The greedy-choice property ensures that local optimal choices lead to a global optimal solution.

What does optimal substructure mean in the context of greedy algorithms?

A Problem has no solution

B Problem requires random guessing

C Problem can be divided into smaller subproblems with optimal solutions

D Problem needs backtracking

Optimal substructure means the optimal solution can be built from optimal solutions of subproblems.

Why might greedy algorithms fail on the coin change problem with arbitrary coins?

A Because picking the largest coin first may not minimize total coins

B Because coins are unlimited

C Because greedy algorithms always work on coin change

D Because coins have the same value

Greedy choice of largest coin first can lead to more coins than necessary.

Which of these is NOT a characteristic of problems solved by greedy algorithms?

A Requires checking all combinations

B Optimal substructure

C Local choices lead to global optimum

D Greedy-choice property

Greedy algorithms do not check all combinations; they rely on local choices.

What is a key difference between greedy algorithms and dynamic programming?

A Greedy uses recursion; dynamic programming does not

B Greedy algorithms always fail

C Dynamic programming is always faster

D Greedy makes local choices; dynamic programming considers all subproblems

Dynamic programming solves all subproblems and combines solutions, while greedy makes local choices.

Explain why greedy algorithms work for some problems but fail for others.

Think about how local best choices relate to the overall best solution.

Describe the greedy-choice property and give an example of a problem that has it.

Focus on how choosing the best option at each step leads to the best total result.