CLRS - Amortized Analysis PDF

# Chapter 15: Greedy Algorithms ## 15.2: Elements of the Greedy Strategy A greedy algorithm obtains an optimal solution by making a sequence of choices. At each decision point, it makes the choice that appears best at the moment. This approach doesn't always produce an optimal solution, but sometim...

# Chapter 15: Greedy Algorithms ## 15.2: Elements of the Greedy Strategy A greedy algorithm obtains an optimal solution by making a sequence of choices. At each decision point, it makes the choice that appears best at the moment. This approach doesn't always produce an optimal solution, but sometimes it does. **The process for developing a greedy algorithm involves the following steps:** 1. Determine the optimal substructure of the problem. 2. Develop a recursive solution (optional). 3. Show that if you make the greedy choice, then only one subproblem remains. 4. Prove that it is always safe to make the greedy choice. 5. Develop a recursive algorithm. 6. Convert the recursive algorithm to an iterative algorithm (optional). **An alternative approach to designing greedy algorithms involves the following steps:** 1. Cast the optimization problem as one in which you make a choice and are left with one subproblem to solve. 2. Prove that there is always an optimal solution to the original problem that makes the greedy choice. 3. Demonstrate optimal substructure by showing that, having made the greedy choice, what remains is a subproblem with the property that if you combine an optimal solution to the subproblem with the greedy choice you have made, you arrive at an optimal solution to the original problem. ### Greedy-Choice Property 1. You can assemble a globally optimal solution by making locally optimal (greedy) choices. 2. When considering which choice to make, you make the choice that looks best in the current problem, without considering results from subproblems. 3. In contrast to dynamic programming, choices in greedy algorithms usually depend on the solutions to subproblems. ### Optimal Substructure 1. Substructure describes the idea that an optimal solution to the problem contains within it optimal solutions to subproblems. 2. It is important for both dynamic programming and greedy algorithms. 3. The scheme implicitly uses induction on the subproblems to prove that making the greedy choice at every step produces an optimal solution. ### Greedy versus Dynamic Programming Both greedy and dynamic programming strategies exploit optimal substructure. - When a greedy solution suffices, you might be tempted to generate a dynamic-programming solution to a problem. - Conversely, you might mistakenly think that a greedy solution works when in fact a dynamic-programming solution is required. ## 15.3: Huffman Codes - Huffman codes compress data well, with typical savings of 20% to 90%. - They work by using a table to determine how often each character occurs. **Character Coding:** * A fixed-length code uses [lgn] bits to represent n ≥ 2 characters. * A variable-length code gives frequent characters short codewords and infrequent characters long codewords. **Prefix-Free Codes:** - No codeword is a prefix of some other codeword. - They are desirable because they simplify decoding. **Constructing a Huffman Code:** - Huffman invented a greedy algorithm that constructs an optimal prefix-free code. - The algorithm uses a min-priority queue keyed on the freq attribute. - It merges the two least-frequent objects together and repeats this process until the final tree is created. ### Correctness of Huffman's Algorithm - In the optimal prefix-free code, the codewords for the characters with the lowest frequencies have the same length and differ only in the last bit. - This is because the codewords of these characters form a subtree of maximum depth in the new tree. - Optimal prefix-free codes have the optimal-substructure property. ## 15.4: Offline Caching **Cache Configurations:** - A cache holds a subset of the main memory, organized into blocks. - The goal is to minimize the total number of *cache misses* (where the requested data is not in the cache). **Furthest-in-Future Algorithm:** - This algorithm evicts the block in the cache whose next access in the request sequence comes furthest in the future. ### Optimal Substructure of Offline Caching - Subproblem (C, i) represents processing requests for blocks *bi, bi+1, ... bn* with cache configuration *C* at the time that the request for block *bi* occurs. **Greedy Choice Property:** - In optimal offline caching, the furthest-in-future strategy yields optimal solutions by repeatedly making the greedy choice of evicting the block in the cache whose next access is furthest in the future. ## Problems **15.1: Coin Changing** - Describes the problem of making change for n cents using the smallest number of coins. - Discusses a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. - Proves that this algorithm yields an optimal solution for this specific set of coin denominations. - Discusses the use of the greedy algorithm when the coin denominations are powers of c. - Defines coin denominations scenarios where the greedy algorithm does not yield an optimal solution. - Provides an O(nk)-time algorithm that makes change for any set of k different coin denominations using the smallest number of coins, assuming that one of the coins is a penny. **15.2: Scheduling to Minimize Average Completion Time:** - Describes the problem of scheduling n tasks, where task *ai* requires *pi* units of processing time. - The goal is to minimize the average completion time (how long it takes on average to complete all tasks). - Discusses the problem of scheduling nonpreemptively (a task must complete before another task can start) and preemptively (a task can be suspended and restarted at a later time). **15.3: Huffman Codes:** - Presents a set of exercises relating to Huffman's greedy algorithm implementation. **15.4 Offline Caching:** - Presents a set of exercises concerning the implementation of offline caching and analysis of various strategies used to select eviction policies. These exercises involve exploring the relationship between the furthest-in-future strategy and the least-recently-used strategy and analyzing the effectiveness of different eviction strategies in various scenarios.