Page 1 Greed "Greed is good. Greed is right. Greed works. Greed cuts through, clarifies, and captures the essence of the evolutionary spirit." Gordon Gecko (Michael Douglas) 2 Greedy Algorithms Some possibly familiar examples: ¦ Gale-Shapley stable matching algorithm. ¦ Dijkstra’s shortest path algorithm. ¦ Prim and Kruskal MST algorithms. ¦ Huffman codes. ¦ . . . 3 Selecting Breakpoints Minimizing breakpoints. ¦ Truck driver going from Princeton to Palo Alto along predetermined route. ¦ Refueling stations at certain points along the way. ¦ Truck fuel capacity = C. Greedy algorithm. ¦ Go as far as you can before refueling. Princeton Palo Alto 1 C C 2 C 3 C 4 C 5 C 6 C 7 4 Sort breakpoints by increasing value: 0 = b 0 < b 1 < b 2 < ... < b n . S ‹ {0} x = 0 while (x „ b n ) let p be largest integer such that b p £ x + C if (b p = x) return "no solution" x ‹ b p S ‹ S ¨ {p} return S Greedy Breakpoint Selection Algorithm Selecting Breakpoints: Greedy Algorithm S = breakpoints selected. Page 2 Greed "Greed is good. Greed is right. Greed works. Greed cuts through, clarifies, and captures the essence of the evolutionary spirit." Gordon Gecko (Michael Douglas) 2 Greedy Algorithms Some possibly familiar examples: ¦ Gale-Shapley stable matching algorithm. ¦ Dijkstra’s shortest path algorithm. ¦ Prim and Kruskal MST algorithms. ¦ Huffman codes. ¦ . . . 3 Selecting Breakpoints Minimizing breakpoints. ¦ Truck driver going from Princeton to Palo Alto along predetermined route. ¦ Refueling stations at certain points along the way. ¦ Truck fuel capacity = C. Greedy algorithm. ¦ Go as far as you can before refueling. Princeton Palo Alto 1 C C 2 C 3 C 4 C 5 C 6 C 7 4 Sort breakpoints by increasing value: 0 = b 0 < b 1 < b 2 < ... < b n . S ‹ {0} x = 0 while (x „ b n ) let p be largest integer such that b p £ x + C if (b p = x) return "no solution" x ‹ b p S ‹ S ¨ {p} return S Greedy Breakpoint Selection Algorithm Selecting Breakpoints: Greedy Algorithm S = breakpoints selected. 5 Selecting Breakpoints Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let 0 = g 0 < g 1 < . . . < g p = L denote set of breakpoints chosen by greedy and assume it is not optimal. ¦ Let 0 = f 0 < f 1 < . . . < f q = L denote set of breakpoints in optimal solution with f 0 = g 0 , f 1 = g 1 , . . . , f r =g r for largest possible value of r. ¦ Note: q < p. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 9 8 r = 4 Greedy: OPT: g 0 g 1 g 2 f 0 f 1 f 2 g p f q g r f r 6 Selecting Breakpoints Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let 0 = g 0 < g 1 < . . . < g p = L denote set of breakpoints chosen by greedy and assume it is not optimal. ¦ Let 0 = f 0 < f 1 < . . . < f q = L denote set of breakpoints in optimal solution with f 0 = g 0 , f 1 = g 1 , . . . , f r = g r for largest possible value of r. ¦ Note: q < p. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 9 8 Greedy: OPT: 5 5 5 r = 5 g 0 g 1 g 2 f 0 f 1 f 2 g p f q r = 4 7 Selecting Breakpoints Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let 0 = g 0 < g 1 < . . . < g p = L denote set of breakpoints chosen by greedy and assume it is not optimal. ¦ Let 0 = f 0 < f 1 < . . . < f q = L denote set of breakpoints in optimal solution with f 0 = g 0 , f 1 = g 1 , . . . , f r = g r for largest possible value of r. ¦ Note: q < p. ¦ Thus, f 0 = g 0 , f 1 = g 1 , . . . , f q = g q 1 2 3 4 1 2 3 4 6 7 Greedy: OPT: 5 5 r = q = 5 g 0 g 1 g 2 f 0 f 1 f 2 g q f q g p 8 Activity Selection Activity selection problem (CLR 17.1). ¦ Job requests 1, 2, … , n. ¦ Job j starts at s j and finishes at f j . ¦ Two jobs compatible if they don't overlap. ¦ Goal: find maximum subset of mutually compatible jobs. Time 0 A C F B D G E 123456789 10 11 H Page 3 Greed "Greed is good. Greed is right. Greed works. Greed cuts through, clarifies, and captures the essence of the evolutionary spirit." Gordon Gecko (Michael Douglas) 2 Greedy Algorithms Some possibly familiar examples: ¦ Gale-Shapley stable matching algorithm. ¦ Dijkstra’s shortest path algorithm. ¦ Prim and Kruskal MST algorithms. ¦ Huffman codes. ¦ . . . 3 Selecting Breakpoints Minimizing breakpoints. ¦ Truck driver going from Princeton to Palo Alto along predetermined route. ¦ Refueling stations at certain points along the way. ¦ Truck fuel capacity = C. Greedy algorithm. ¦ Go as far as you can before refueling. Princeton Palo Alto 1 C C 2 C 3 C 4 C 5 C 6 C 7 4 Sort breakpoints by increasing value: 0 = b 0 < b 1 < b 2 < ... < b n . S ‹ {0} x = 0 while (x „ b n ) let p be largest integer such that b p £ x + C if (b p = x) return "no solution" x ‹ b p S ‹ S ¨ {p} return S Greedy Breakpoint Selection Algorithm Selecting Breakpoints: Greedy Algorithm S = breakpoints selected. 5 Selecting Breakpoints Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let 0 = g 0 < g 1 < . . . < g p = L denote set of breakpoints chosen by greedy and assume it is not optimal. ¦ Let 0 = f 0 < f 1 < . . . < f q = L denote set of breakpoints in optimal solution with f 0 = g 0 , f 1 = g 1 , . . . , f r =g r for largest possible value of r. ¦ Note: q < p. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 9 8 r = 4 Greedy: OPT: g 0 g 1 g 2 f 0 f 1 f 2 g p f q g r f r 6 Selecting Breakpoints Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let 0 = g 0 < g 1 < . . . < g p = L denote set of breakpoints chosen by greedy and assume it is not optimal. ¦ Let 0 = f 0 < f 1 < . . . < f q = L denote set of breakpoints in optimal solution with f 0 = g 0 , f 1 = g 1 , . . . , f r = g r for largest possible value of r. ¦ Note: q < p. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 9 8 Greedy: OPT: 5 5 5 r = 5 g 0 g 1 g 2 f 0 f 1 f 2 g p f q r = 4 7 Selecting Breakpoints Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let 0 = g 0 < g 1 < . . . < g p = L denote set of breakpoints chosen by greedy and assume it is not optimal. ¦ Let 0 = f 0 < f 1 < . . . < f q = L denote set of breakpoints in optimal solution with f 0 = g 0 , f 1 = g 1 , . . . , f r = g r for largest possible value of r. ¦ Note: q < p. ¦ Thus, f 0 = g 0 , f 1 = g 1 , . . . , f q = g q 1 2 3 4 1 2 3 4 6 7 Greedy: OPT: 5 5 r = q = 5 g 0 g 1 g 2 f 0 f 1 f 2 g q f q g p 8 Activity Selection Activity selection problem (CLR 17.1). ¦ Job requests 1, 2, … , n. ¦ Job j starts at s j and finishes at f j . ¦ Two jobs compatible if they don't overlap. ¦ Goal: find maximum subset of mutually compatible jobs. Time 0 A C F B D G E 123456789 10 11 H 9 Activity Selection: Greedy Algorithm Sort jobs by increasing finish times so that f 1 £ f 2 £ ... £ f n . S = f for j = 1 to n if (job j compatible with A) S ‹ S ¨ {j} return S Greedy Activity Selection Algorithm S = jobs selected. 10 Activity Selection Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let g 1 , g 2 , . . . g p denote set of jobs selected by greedy and assume it is not optimal. ¦ Let f 1 , f 2 , . . . f q denote set of jobs selected by optimal solution with f 1 = g 1 , f 2 = g 2 , . . . , f r = g r for largest possible value of r. ¦ Note: r < q. 1 5 8 1 5 8 9 13 15 21 17 r = 3 p = 6 q = 7 Greedy: OPT: f 1 = g 1 21 f 2 = g 2 f 3 = g 3 11 11 9 Activity Selection Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let g 1 , g 2 , . . . g p denote set of jobs selected by greedy and assume it is not optimal. ¦ Let f 1 , f 2 , . . . f q denote set of jobs selected by optimal solution with f 1 = g 1 , f 2 = g 2 , . . . , f r = g r for largest possible value of r. ¦ Note: r < q. 1 5 8 11 1 5 8 9 13 15 21 17 r = 3 p = 6 q = 7 Greedy: OPT: f 1 = g 1 21 f 2 = g 2 f 3 = g 3 Replace 11 with 9 12 9 Activity Selection Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let g 1 , g 2 , . . . g p denote set of jobs selected by greedy and assume it is not optimal. ¦ Let f 1 , f 2 , . . . f q denote set of jobs selected by optimal solution with f 1 = g 1 , f 2 = g 2 , . . . , f r = g r for largest possible value of r. ¦ Note: r < q. 1 5 8 1 5 8 9 13 15 21 17 r = 3 p = 6 q = 7 Greedy: OPT: f 1 = g 1 21 f 2 = g 2 f 3 = g 3 Replace 11 with 9 Page 4 Greed "Greed is good. Greed is right. Greed works. Greed cuts through, clarifies, and captures the essence of the evolutionary spirit." Gordon Gecko (Michael Douglas) 2 Greedy Algorithms Some possibly familiar examples: ¦ Gale-Shapley stable matching algorithm. ¦ Dijkstra’s shortest path algorithm. ¦ Prim and Kruskal MST algorithms. ¦ Huffman codes. ¦ . . . 3 Selecting Breakpoints Minimizing breakpoints. ¦ Truck driver going from Princeton to Palo Alto along predetermined route. ¦ Refueling stations at certain points along the way. ¦ Truck fuel capacity = C. Greedy algorithm. ¦ Go as far as you can before refueling. Princeton Palo Alto 1 C C 2 C 3 C 4 C 5 C 6 C 7 4 Sort breakpoints by increasing value: 0 = b 0 < b 1 < b 2 < ... < b n . S ‹ {0} x = 0 while (x „ b n ) let p be largest integer such that b p £ x + C if (b p = x) return "no solution" x ‹ b p S ‹ S ¨ {p} return S Greedy Breakpoint Selection Algorithm Selecting Breakpoints: Greedy Algorithm S = breakpoints selected. 5 Selecting Breakpoints Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let 0 = g 0 < g 1 < . . . < g p = L denote set of breakpoints chosen by greedy and assume it is not optimal. ¦ Let 0 = f 0 < f 1 < . . . < f q = L denote set of breakpoints in optimal solution with f 0 = g 0 , f 1 = g 1 , . . . , f r =g r for largest possible value of r. ¦ Note: q < p. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 9 8 r = 4 Greedy: OPT: g 0 g 1 g 2 f 0 f 1 f 2 g p f q g r f r 6 Selecting Breakpoints Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let 0 = g 0 < g 1 < . . . < g p = L denote set of breakpoints chosen by greedy and assume it is not optimal. ¦ Let 0 = f 0 < f 1 < . . . < f q = L denote set of breakpoints in optimal solution with f 0 = g 0 , f 1 = g 1 , . . . , f r = g r for largest possible value of r. ¦ Note: q < p. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 9 8 Greedy: OPT: 5 5 5 r = 5 g 0 g 1 g 2 f 0 f 1 f 2 g p f q r = 4 7 Selecting Breakpoints Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let 0 = g 0 < g 1 < . . . < g p = L denote set of breakpoints chosen by greedy and assume it is not optimal. ¦ Let 0 = f 0 < f 1 < . . . < f q = L denote set of breakpoints in optimal solution with f 0 = g 0 , f 1 = g 1 , . . . , f r = g r for largest possible value of r. ¦ Note: q < p. ¦ Thus, f 0 = g 0 , f 1 = g 1 , . . . , f q = g q 1 2 3 4 1 2 3 4 6 7 Greedy: OPT: 5 5 r = q = 5 g 0 g 1 g 2 f 0 f 1 f 2 g q f q g p 8 Activity Selection Activity selection problem (CLR 17.1). ¦ Job requests 1, 2, … , n. ¦ Job j starts at s j and finishes at f j . ¦ Two jobs compatible if they don't overlap. ¦ Goal: find maximum subset of mutually compatible jobs. Time 0 A C F B D G E 123456789 10 11 H 9 Activity Selection: Greedy Algorithm Sort jobs by increasing finish times so that f 1 £ f 2 £ ... £ f n . S = f for j = 1 to n if (job j compatible with A) S ‹ S ¨ {j} return S Greedy Activity Selection Algorithm S = jobs selected. 10 Activity Selection Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let g 1 , g 2 , . . . g p denote set of jobs selected by greedy and assume it is not optimal. ¦ Let f 1 , f 2 , . . . f q denote set of jobs selected by optimal solution with f 1 = g 1 , f 2 = g 2 , . . . , f r = g r for largest possible value of r. ¦ Note: r < q. 1 5 8 1 5 8 9 13 15 21 17 r = 3 p = 6 q = 7 Greedy: OPT: f 1 = g 1 21 f 2 = g 2 f 3 = g 3 11 11 9 Activity Selection Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let g 1 , g 2 , . . . g p denote set of jobs selected by greedy and assume it is not optimal. ¦ Let f 1 , f 2 , . . . f q denote set of jobs selected by optimal solution with f 1 = g 1 , f 2 = g 2 , . . . , f r = g r for largest possible value of r. ¦ Note: r < q. 1 5 8 11 1 5 8 9 13 15 21 17 r = 3 p = 6 q = 7 Greedy: OPT: f 1 = g 1 21 f 2 = g 2 f 3 = g 3 Replace 11 with 9 12 9 Activity Selection Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let g 1 , g 2 , . . . g p denote set of jobs selected by greedy and assume it is not optimal. ¦ Let f 1 , f 2 , . . . f q denote set of jobs selected by optimal solution with f 1 = g 1 , f 2 = g 2 , . . . , f r = g r for largest possible value of r. ¦ Note: r < q. 1 5 8 1 5 8 9 13 15 21 17 r = 3 p = 6 q = 7 Greedy: OPT: f 1 = g 1 21 f 2 = g 2 f 3 = g 3 Replace 11 with 9 13 9 Activity Selection Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let g 1 , g 2 , . . . g p denote set of jobs selected by greedy and assume it is not optimal. ¦ Let f 1 , f 2 , . . . f q denote set of jobs selected by optimal solution with f 1 = g 1 , f 2 = g 2 , . . . , f r = g r for largest possible value of r. ¦ Note: r < q. 1 5 8 1 5 8 9 13 15 21 17 r = 3 p = 6 q = 7 Greedy: OPT: f 1 = g 1 21 f 2 = g 2 f 3 = g 3 r = 4 9 9 14 Making Change Given currency denominations: 1, 5, 10, 25, 100, devise a method to pay amount to customer using fewest number of coins. ¦ Ex. 34¢. Greedy algorithm. ¦ At each iteration, add coin of the largest value that does not take us past the amount to be paid. ¦ Ex. $2.89. 15 Coin-Changing: Greedy Algorithm Sort coins denominations by increasing value: c 1 < c 2 < ... < c n . S ‹f while (x „ 0) let p be largest integer such that c p £ x if (p = 0) return "no solution found" x ‹ x - c p S ‹ S ¨ {p} return S Greedy Coin-Changing Algorithm S = coins selected. 16 Is Greedy Optimal for Coin-Changing Problem? Yes, for U.S. coinage: {c 1 , c 2 , c 3 , c 4 , c 5 } = {1, 5, 10, 25, 100}. Ad hoc proof. ¦ Consider optimal way to change amount c k £ x < c k+1 . ¦ Greedy takes coin k. ¦ Suppose optimal solution does not take coin k. – it must take enough coins of type c 1 , c 2 , . . . , c k-1 to add up to x. 1 c k 10 25 100 4 Max # taken by optimal solution 2 3 5 1 no limit k 1 3 4 5 2 4 Max value of coins 1, 2, . . . , k in any OPT 20 + 4 = 24 75 + 24 = 99 4 + 5 = 9 no limit 2 dimes no nickels Page 5 Greed "Greed is good. Greed is right. Greed works. Greed cuts through, clarifies, and captures the essence of the evolutionary spirit." Gordon Gecko (Michael Douglas) 2 Greedy Algorithms Some possibly familiar examples: ¦ Gale-Shapley stable matching algorithm. ¦ Dijkstra’s shortest path algorithm. ¦ Prim and Kruskal MST algorithms. ¦ Huffman codes. ¦ . . . 3 Selecting Breakpoints Minimizing breakpoints. ¦ Truck driver going from Princeton to Palo Alto along predetermined route. ¦ Refueling stations at certain points along the way. ¦ Truck fuel capacity = C. Greedy algorithm. ¦ Go as far as you can before refueling. Princeton Palo Alto 1 C C 2 C 3 C 4 C 5 C 6 C 7 4 Sort breakpoints by increasing value: 0 = b 0 < b 1 < b 2 < ... < b n . S ‹ {0} x = 0 while (x „ b n ) let p be largest integer such that b p £ x + C if (b p = x) return "no solution" x ‹ b p S ‹ S ¨ {p} return S Greedy Breakpoint Selection Algorithm Selecting Breakpoints: Greedy Algorithm S = breakpoints selected. 5 Selecting Breakpoints Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let 0 = g 0 < g 1 < . . . < g p = L denote set of breakpoints chosen by greedy and assume it is not optimal. ¦ Let 0 = f 0 < f 1 < . . . < f q = L denote set of breakpoints in optimal solution with f 0 = g 0 , f 1 = g 1 , . . . , f r =g r for largest possible value of r. ¦ Note: q < p. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 9 8 r = 4 Greedy: OPT: g 0 g 1 g 2 f 0 f 1 f 2 g p f q g r f r 6 Selecting Breakpoints Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let 0 = g 0 < g 1 < . . . < g p = L denote set of breakpoints chosen by greedy and assume it is not optimal. ¦ Let 0 = f 0 < f 1 < . . . < f q = L denote set of breakpoints in optimal solution with f 0 = g 0 , f 1 = g 1 , . . . , f r = g r for largest possible value of r. ¦ Note: q < p. 1 2 3 4 5 6 7 1 2 3 4 5 6 7 9 8 Greedy: OPT: 5 5 5 r = 5 g 0 g 1 g 2 f 0 f 1 f 2 g p f q r = 4 7 Selecting Breakpoints Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let 0 = g 0 < g 1 < . . . < g p = L denote set of breakpoints chosen by greedy and assume it is not optimal. ¦ Let 0 = f 0 < f 1 < . . . < f q = L denote set of breakpoints in optimal solution with f 0 = g 0 , f 1 = g 1 , . . . , f r = g r for largest possible value of r. ¦ Note: q < p. ¦ Thus, f 0 = g 0 , f 1 = g 1 , . . . , f q = g q 1 2 3 4 1 2 3 4 6 7 Greedy: OPT: 5 5 r = q = 5 g 0 g 1 g 2 f 0 f 1 f 2 g q f q g p 8 Activity Selection Activity selection problem (CLR 17.1). ¦ Job requests 1, 2, … , n. ¦ Job j starts at s j and finishes at f j . ¦ Two jobs compatible if they don't overlap. ¦ Goal: find maximum subset of mutually compatible jobs. Time 0 A C F B D G E 123456789 10 11 H 9 Activity Selection: Greedy Algorithm Sort jobs by increasing finish times so that f 1 £ f 2 £ ... £ f n . S = f for j = 1 to n if (job j compatible with A) S ‹ S ¨ {j} return S Greedy Activity Selection Algorithm S = jobs selected. 10 Activity Selection Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let g 1 , g 2 , . . . g p denote set of jobs selected by greedy and assume it is not optimal. ¦ Let f 1 , f 2 , . . . f q denote set of jobs selected by optimal solution with f 1 = g 1 , f 2 = g 2 , . . . , f r = g r for largest possible value of r. ¦ Note: r < q. 1 5 8 1 5 8 9 13 15 21 17 r = 3 p = 6 q = 7 Greedy: OPT: f 1 = g 1 21 f 2 = g 2 f 3 = g 3 11 11 9 Activity Selection Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let g 1 , g 2 , . . . g p denote set of jobs selected by greedy and assume it is not optimal. ¦ Let f 1 , f 2 , . . . f q denote set of jobs selected by optimal solution with f 1 = g 1 , f 2 = g 2 , . . . , f r = g r for largest possible value of r. ¦ Note: r < q. 1 5 8 11 1 5 8 9 13 15 21 17 r = 3 p = 6 q = 7 Greedy: OPT: f 1 = g 1 21 f 2 = g 2 f 3 = g 3 Replace 11 with 9 12 9 Activity Selection Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let g 1 , g 2 , . . . g p denote set of jobs selected by greedy and assume it is not optimal. ¦ Let f 1 , f 2 , . . . f q denote set of jobs selected by optimal solution with f 1 = g 1 , f 2 = g 2 , . . . , f r = g r for largest possible value of r. ¦ Note: r < q. 1 5 8 1 5 8 9 13 15 21 17 r = 3 p = 6 q = 7 Greedy: OPT: f 1 = g 1 21 f 2 = g 2 f 3 = g 3 Replace 11 with 9 13 9 Activity Selection Theorem: greedy algorithm is optimal. Proof (by contradiction): ¦ Let g 1 , g 2 , . . . g p denote set of jobs selected by greedy and assume it is not optimal. ¦ Let f 1 , f 2 , . . . f q denote set of jobs selected by optimal solution with f 1 = g 1 , f 2 = g 2 , . . . , f r = g r for largest possible value of r. ¦ Note: r < q. 1 5 8 1 5 8 9 13 15 21 17 r = 3 p = 6 q = 7 Greedy: OPT: f 1 = g 1 21 f 2 = g 2 f 3 = g 3 r = 4 9 9 14 Making Change Given currency denominations: 1, 5, 10, 25, 100, devise a method to pay amount to customer using fewest number of coins. ¦ Ex. 34¢. Greedy algorithm. ¦ At each iteration, add coin of the largest value that does not take us past the amount to be paid. ¦ Ex. $2.89. 15 Coin-Changing: Greedy Algorithm Sort coins denominations by increasing value: c 1 < c 2 < ... < c n . S ‹f while (x „ 0) let p be largest integer such that c p £ x if (p = 0) return "no solution found" x ‹ x - c p S ‹ S ¨ {p} return S Greedy Coin-Changing Algorithm S = coins selected. 16 Is Greedy Optimal for Coin-Changing Problem? Yes, for U.S. coinage: {c 1 , c 2 , c 3 , c 4 , c 5 } = {1, 5, 10, 25, 100}. Ad hoc proof. ¦ Consider optimal way to change amount c k £ x < c k+1 . ¦ Greedy takes coin k. ¦ Suppose optimal solution does not take coin k. – it must take enough coins of type c 1 , c 2 , . . . , c k-1 to add up to x. 1 c k 10 25 100 4 Max # taken by optimal solution 2 3 5 1 no limit k 1 3 4 5 2 4 Max value of coins 1, 2, . . . , k in any OPT 20 + 4 = 24 75 + 24 = 99 4 + 5 = 9 no limit 2 dimes no nickels 17 Does Greedy Always Work? US postal denominations: 1, 10, 21, 34, 70, 100, 350, 1225, 1500. ¦ Ex. 140¢. ¦ Greedy: 100, 34, 1, 1, 1, 1, 1, 1. ¦ Optimal: 70, 70. 18 Characteristics of Greedy Algorithms Greedy choice property. ¦ Globally optimal solution can be arrived at by making locally optimal (greedy) choice. ¦ At each step, choose most "promising" candidate, without worrying whether it will prove to be a sound decision in long run. Optimal substructure property. ¦ Optimal solution to the problem contains optimal solutions to sub- problems. – if best way to change 34¢ is {25, 5, 1, 1, 1, 1} then best way to change 29¢ is {25, 1, 1, 1, 1}. Objective function does not explicitly appear in greedy algorithm! Hard, if not impossible, to precisely define "greedy algorithm." ¦ See matroids (CLR 17.4), greedoids for very general frameworks. 19 Minimizing Lateness Minimizing lateness problem. ¦ Single resource can process one job at a time. ¦ n jobs to be processed. – job j requires p j units of processing time. – job j has due date d j . ¦ If we assign job j to start at time s j , it finishes at time f j = s j + p j . ¦ Lateness: l j = max { 0, f j -d j }. ¦ Goal: schedule all jobs to minimize maximum lateness L = max l j . 0 123456789 10 11 12 13 14 15 d = 11 d = 8 d = 15 d = 6 d = 9 d = 9 d = 11 d = 8 d = 2 d = 6 d = 9 d = 9 Lateness = 3 20 Minimizing Lateness: Greedy Algorithm Sort jobs by increasing deadline so that d 1 £ d 2 £ … £ d n . t = 0 for j = 1 to n Assign job j to interval [t, t + p j ] s j ‹ t, f j ‹ t + p j t ‹ t + p j output intervals [s j ,f j ] Greedy Activity Selection Algorithm max lateness = 2 0 123456789 10 11 12 13 14 15 d 5 = 11 d 2 = 8 d 6 = 15 d 1 = 6 d 4 = 9 d 3 = 9Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!