Why Greedy Works and When It Fails in DSA Typescript - 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

What does it mean when a problem has the 'greedy choice property'?

It means that a locally optimal choice at each step leads to a globally optimal solution.

intermediate

Why can greedy algorithms fail on some problems?

Because making the best local choice at each step does not always lead to the best overall solution if the problem lacks the greedy choice property or optimal substructure.

beginner

What is an example of a problem where greedy algorithms work well?

The activity selection problem, where choosing the earliest finishing activity first leads to the maximum number of non-overlapping activities.

intermediate

What is an example of a problem where greedy algorithms fail?

The coin change problem with arbitrary coin denominations, where greedy choice may not give the minimum number of coins.

What property must a problem have for a greedy algorithm to guarantee an optimal solution?

A Greedy choice property

B Randomness

C Brute force

D Backtracking

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

Which of these problems is a classic example where greedy algorithms work perfectly?

A Subset sum problem

B Traveling salesman problem

C Activity selection problem

D Knapsack problem (0/1)

The activity selection problem has the greedy choice property and optimal substructure.

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

A Because it uses recursion

B Because it always picks the smallest coin

C Because it sorts coins incorrectly

D Because it does not consider future choices

Greedy algorithms pick the best immediate option without considering future consequences, which can fail in coin change.

What is 'optimal substructure' in the context of greedy algorithms?

A Solution requires random guessing

B Optimal solution can be built from optimal solutions of subproblems

C Solution depends on brute force search

D Solution is always unique

Optimal substructure means the problem can be broken down into smaller problems whose optimal solutions combine to solve the bigger problem.

Which approach is better than greedy when greedy fails?

A Dynamic programming

B Random guessing

C Sorting only

D No algorithm needed

Dynamic programming considers all subproblems and can find optimal solutions when greedy fails.

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

Think about how making the best choice now affects the whole solution.

Describe a real-life situation where a greedy approach works and one where it might fail.

Consider choosing tasks or money change scenarios.