Greedy Algorithms

# CHAPTER 19

Greedy Algorithms #

1. Introduction #

2. Learning Objectives #

• Define the Greedy algorithmic paradigm.

• Identify the "Greedy Choice Property".

• Execute the classic Coin Change algorithm.

• Identify scenarios where Greedy algorithms fail catastrophically.

• Contrast Greedy architecture against Dynamic Programming.

3. The Philosophy of "Local Optimum" #

When an algorithm encounters a decision matrix:

1. 1. It scans the immediate, currently available options.

1. 2. It aggressively selects the highest-value (or lowest-cost) option.

1. 3. It adds the option to the solution sequence.

1. 4. The Law of No Returns: Once a Greedy algorithm makes a decision, it *never* changes its mind. It never backtracks. It never analyzes alternate timelines.

4. Code Example: The Coin Change Problem #

# Python Example: Greedy Coin Change
def greedy_coin_change(amount):
    coins = [25, 10, 5, 1] # MUST be sorted largest to smallest!
    result = []
    
    for coin in coins:
        # Greedily grab as many of the massive coins as physically possible
        while amount >= coin:
            amount -= coin
            result.append(coin)
            
    return result

print(greedy_coin_change(87)) 
# Output: [25, 25, 25, 10, 1, 1] (Total 6 coins. Optimal!)

5. The Catastrophic Failure of Greed #

The Counter-Example: Imagine a bizarre monetary system where coins are [25, 20, 1]. The target is $0.40.

1. 1. Greedy Logic: The algorithm instantly grabs the largest coin: 25.

1. 2. Target remaining: 15.

1. 3. Next available coin: 1. The algorithm grabs 1 fifteen times.

1. 4. Greedy Output: [25, 1, 1, 1... 1] (Total 16 coins).

The Reality: The actual optimal solution was [20, 20] (Total 2 coins). The Greedy algorithm completely failed because grabbing the massive 25 at the very beginning permanently locked the algorithm into a terrible mathematical path! To solve this, you must abandon Greed and use *Dynamic Programming*.

6. The Two Mandatory Properties #

1. 1. The Greedy Choice Property: Making a locally optimal choice is mathematically proven to never harm the global solution (e.g., standard US coin denominations are mathematically designed so that grabbing a quarter is always safe).

1. 2. Optimal Substructure: The optimal solution to the problem contains the optimal solutions to the subproblems.

7. Real-World Applications #

1. 1. Dijkstra's Shortest Path: Google Maps uses a Greedy algorithm to find the fastest driving route. At every intersection, the algorithm simply selects the physically closest unvisited neighborhood.

1. 2. Data Compression (Huffman Coding): MP3 files and ZIP files use Greedy algorithms to build compression trees, aggressively assigning the shortest binary codes to the most frequently used letters.

1. 3. Fractional Knapsack: A thief is stealing liquid gold and silver. Since liquids can be split (fractions), the thief greedily pours the fluid with the absolute highest "Price Per Ounce" into the bag until it is full.

8. Common Mistakes #

• Applying Greed to the 0/1 Knapsack Problem: If a thief is stealing flat-screen TVs and Laptops (solid objects that cannot be fractured), Greedy algorithms fail! Grabbing a massive $1,000 TV might fill the entire bag, when the optimal choice was grabbing four $300 Laptops. Solid objects require Dynamic Programming.

9. Exercises #

1. 1. Using the Greedy logic [100, 50, 20, 10, 5, 1], trace the exact coins outputted for $1.43.

1. 2. Why does the input array in a Greedy algorithm almost always require $O(N \log N)$ Sorting before the logic can execute?

10. MCQs with Answers #

13. Interview Preparation #

• *Algorithmic Coding:* "Activity Selection Problem: You are given 5 meeting times (Start, End). You have 1 conference room. Maximize the number of meetings held." *(Answer: Sort the meetings purely by their END TIMES. Greedily select the very first meeting that finishes, then grab the next compatible meeting. This guarantees maximum room availability!)*

14. Summary #

15. Next Chapter Recommendation #