Greedy Algorithm A greedy algorithm always makes the choice that looks best at the moment Key point Greed makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution Note Greedy algorithms do not always yield optimal solutions but for SOME problems they do Greed When do we use greedy algorithms When we need a heuristic e g hard problems like the Traveling Salesman Problem When the problem itself is greedy Greedy Choice Property CLRS 16 2 Optimal Substructure Property shared with DP CLRS 16 2 Examples Minimum Spanning Tree Kruskal s algorithm Optimal Prefix Codes Huffman s algorithm Elements of the Greedy Algorithm Greedy choice property A globally optimal solution can be arrived at by making a locally optimal greedy choice Must prove that a greedy choice at each step yields a globally optimal solution Optimal substructure property A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems This property is a key ingredient of assessing the applicability of greedy algorithm and dynamic programming Proof of Kruskal s Algorithm Basis T 0 trivial Induction Step T is promising by I H so it is a subgraph of some MST call it S Let ei be the smallest edge in E s t T ei has no cycle ei T If ei S we re done Suppose ei S then S S ei has a unique cycle containing ei and all other arcs in cycle ei because S is an MST Call the cycle C Observe that C with ei cannot be in T because T ei is acyclic because Kruskal adds ei Proof of Kruskal s Algorithm ej ei Then C must contains some edge ej s t ej S and we also know c ej c ei Let S S ei ej S is an MST so T ei is promising Greedy Algorithm Huffman Codes Prefix codes one code per input symbol no code is a prefix of another Why prefix codes Easy decoding Since no codeword is a prefix of any other the codeword that begins an encoded file is unambiguous Identify the initial codeword translate it back to the original character and repeat the decoding process on the remainder of the encoded file Greedy Algorithm Huffman Codes Huffman coding Given frequencies with which with which source symbols e g A B C Z appear in a message Goal is to minimize the expected encoded message length Create tree leaf node for each symbol that occurs with nonzero frequency Node weights frequencies Find two nodes with smallest frequency Create a new node with these two nodes as children and with weight equal to the sum of the weights of the two children Continue until have a single tree Greedy Algorithm Huffman Codes Example A EG I M N O R S T U V Y Blank 1 5 7 9 13 14 15 18 19 20 21 22 24 Frequency 1 3 2 2 1 2 2 2 2 1 1 1 1 3 1 Place the elements into minimum heap by frequency 2 Remove the first two elements from the heap 3 Combine these two elements into one 4 Insert the new element back into the heap Note circle for node rectangle for weight frequency Greedy Algorithm Huffman Codes Step 1 Step 2 2 A Step 3 2 M 4 2 Y Step 4 2 2 V T A T M U 2 U M 4 4 2 V A 2 Y A N 2 M T U Greedy Algorithm Huffman Codes Step 5 4 4 2 V Y Step 6 A M T N O 4 2 2 Y A M T R U 4 2 V 2 2 4 4 N O U 4 R S G Greedy Algorithm Huffman Codes 4 Step 7 4 2 V 2 2 Y Step 8 A M T N O 4 2 2 2 Y A T M 4 R S 5 G I E U 7 4 V 4 4 N O U 4 R S 5 G I E Greedy Algorithm Huffman Codes Step 9 15 9 7 8 4 4 2 V 2 2 Y A M T S 4 N O U 4 R 5 G I E Greedy Algorithm Huffman Codes Finally 0 9 0 0 I 15 0 5 1 G 1 1 4 0 S 24 1 7 1 E 0 0 1 4 0 2 0 V 1 Y 0 1 0 A 2 2 1 M 0 T 8 1 4 4 0 N O 1 R 1 U Note that the 0 s left branches and 1 s right branches give the code words for each symbol Proof That Huffman s Merge is Optimal Let T be an optimal prefix code tree in which a b are siblings at deepest level L a L b Suppose that x y are two other nodes that are merged by the Huffman algorithm x y have lowest weights because Huffman chose them WLOG w x w a w y w b L a L b L x L y Swap a and x cost difference between T and new T is w x L x w a L a w x L a w a L x w a w x L a L x both factors non neg T 0 Similar argument for b y Huffman choice also optimal y x a b Dynamic Programming Dynamic programming Divide problem into overlapping subproblems recursively solve each in the same way Similar to DQ so what s the difference DQ partition the problem into independent subproblems DP breaking it into overlapping subproblems that is when subproblems share subproblems So DP saves work compared with DQ by solving every subproblems just once when subproblems are overlapping Elements of Dynamic Programming Optimal substructure A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems Whenever a problem exhibits optimal substructure it is a good clue that DP might apply a greedy method might apply also Overlapping subproblems A recursive algorithm for the problem solves the same subproblems over and over rather than always generating new subproblems Dynamic Programming Matrix Chain Product Matrix chain multiplication problem Give a chain of n matrices A1 A2 An to be multiplied how to get the product A1 A2 An with minimum number of scalar multiplications Because of the associative law of matrix multiplication there are many possible orderings to calculate the product for the same matrix chain Only one way to multiply A1 A2 Best way for triple Cost A1 A2 Cost A1 A2 A3 or Cost A2 A3 Cost A1 A2 A3 Dynamic Programming Matrix Chain Product How do we build bottom up 1 From last example Best way for triple Cost A1 A2 Cost A1 A2 A3 or Cost A2 A3 Cost A1 A2 A3 Save the best solutions for contiguous groups of Ai 2 Cost of i j j k is ijk E g 3 5 3 10 3 10 Each of 3 10 entries requires 5 multiplies 4 adds …