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 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 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 Greedy Algorithm Minimum Spanning Tree Kruskal s minimum spanning tree algorithm INPUT edge weighted graph G V E with V n OUTPUT T a spanning tree of G touches all vertices and therefore has n 1 edges of minimum cost total edge weight Will grow a set of edges T until it contains n 1 edges Algorithm Start with T empty then iteratively add to T the smallest minimum cost remaining edge in the graph if the edge does not form a cycle in T Claim Greedy MST is correct Proof by induction Define a promising edge set E E to be any edge set that is a subgraph of some MST We will show by induction that as T is constructed T is always promising 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 1 Greedy Algorithm Huffman Codes 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 Prefix codes one code per input symbol no code is a prefix of another Why prefix codes Create tree leaf node for each symbol that occurs with nonzero frequency 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 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 Greedy Algorithm Huffman Codes Example Step 1 A EG I M N O R S T U V Y Blank Step 2 2 2 2 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 A 3 M T U A M 1 Place the elements into minimum heap by frequency Step 3 2 Remove the first two elements from the heap Step 4 4 4 2 4 3 Combine these two elements into one 2 4 Insert the new element back into the heap Note circle for node rectangle for weight frequency V Y Greedy Algorithm Huffman Codes Step 5 A 4 2 2 Y A M T V N O 4 4 2 2 Y Step 8 4 2 V 2 Y A M T A T 4 N U M T N U 4 4 5 O R S G I E U 7 4 4 R S 4 2 G 2 M A N O Step 6 2 Y 2 R U 4 2 4 V V 2 M 2 2 U Greedy Algorithm Huffman Codes Step 7 4 T 2 V 2 Y A T 4 N O 4 R S 5 G I E U M 2 Greedy Algorithm Huffman Codes Greedy Algorithm Huffman Codes Step 9 Finally 15 0 7 8 4 4 4 S 4 G I 0 S E 0 I 15 0 5 1 G 1 1 4 5 24 0 9 9 1 E 0 8 0 1 4 2 V 2 Y A M T N O R 0 V 0 1 2 U 1 4 0 2 1 7 2 2 4 0 N O 1 0 1 0 1 Y A M T U 1 R 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 Dynamic Programming 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 T w a w x L a L x both factors non neg 0 Similar argument for b y Huffman choice also optimal y x a 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 b Elements of Dynamic Programming Dynamic Programming Matrix Chain Product Optimal substructure A problem exhibits optimal substructure if an optimal solution to the problem contains within it optimal solutions to subproblems 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 …