COMP 3711H Fall 2016 Tutorial 6 1 CLRS 16 2 4 Professor Midas drives an automobile from Newark to Reno along Inter state 80 His car s gas tank when full holds enough gas to travel m miles and his map gives the distance between gas stations on his route The professor wishes to make as few gas stops as possible along the way Give an e cient method by which Professor Midas can determine at which gas stations he should stop and prove that your algorithm yields an optimal solution The simple greedy algorithm is optimal It is to drive to the furthest possible city that one can reach with the current gas in the car and then ll up the tank and then continue Suppose that the cities are at locations 0 x0 x1 xn Let GREEDY be the greedy solution which we will denote by G We will prove optimality of greedy by induction on n Let O be any optimal solution and assume that Greedy is optimal on all problems on set size n for the basis this is obviously true on sets of size 1 and 2 We may also assume that whenever O adds gas O lls the gas tank completely since this can not make the solution worse We use O and G to denote the numbers of stops each solution makes Now consider the input on n points Let g1 be the rst stop that Greedy makes and o1 be the rst stop that OPT makes By the de nition of Greedy o1 g1 Write By de nition k cid 48 k where the gi and oi are the stops the algorithms make Let i be the rst index for which gi cid 54 oi Now let t maxi oi g1 From the observations above we know that t 1 Set Since g1 ot this is a legal tour Thus t 1 otherwise O was not optimal So G g1 g2 gk O o1 o2 ok cid 48 O cid 48 g1 ot 1 ot 2 ok cid 48 O cid 48 g1 o2 o3 ok cid 48 Now note that o2 o3 ok cid 48 must be an optimal stopping pattern for the problem xg1 xg1 1 xn because otherwise we could replace it in O with a smaller set of gas lls getting a smaller optimal solution which is imposisble From the induction hypothesis we know that g2 gk is an optimal stopping pattern for the problem xg1 xg1 1 xn Thus k k cid 48 and greedy is optimal for our original set 2 Consider the problem of making change for n cents using the fewest number of coins Assume that each coin s value is an integer a Describe a greedy algorithm to make change consisting of quarters 25 cents dimes 10 nickels 5 and pennies 1 Prove that your algorithm yields an optimal solution 1 b Suppose that the available coins are in denominations that are powers of c i e the denominations are c0 c1 ck for some integers c 1 and k 1 Show that the greedy algorithm always yields an optimal solution c Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution Your set should include a penny so that there is a solution for every value of n a Set cq cid 98 n 25 cid 99 This is the largest number of quarters that can be used to make change for n cents Set nq n 25cq This is the amount remaining after using cq quarters Set cd cid 98 nq 10 cid 99 largest number of dimes that can be used Set nd nq 10cd amount remaining Set cn cid 98 nd 5 cid 99 Set cp np nd 5cn Solution uses cq quarters cd dimes cn nickles and cp pennies Proof of optimality Assume Greedy solution G is not optimal Let O be an optimal solution using oq quarters od dimes on nickels and op pennies First note that if op 5 we can replace every 5 pennies with one nickle reducing the number of coins used so we can assume op 5 If od 3 replace every three dimes with 1 quarter and 1 nickle without increasing the number of coins So we can assume od 2 If on 2 replace every 2 nickels with one dime reducing the number of coins used so we can assume on 1 Now suppose that 10od 5on op 25 The only way that this can happen is if od 2 and on 1 In this case we can replace the two dimes and one nickle with one quarter reducing the number of coins used contradicting optimality of O So this is impossible This means that 10od 5on op 25 Since n 25oq 10od 5on op we have just shown that cq cid 98 n 25 cid 99 oq After greedy takes o the cq oq quarters what remains is n cid 48 n 25oq 10od 5on op From the facts that on 1 and op 4 we see that 5on op 10 so Greedy chooses cd od dimes and then cnon nickles and then cp op pennies so we are done b Recall that there is a unique way to write n in base c i e n cid 88 aici i such that i 0 ai c First consider the greedy solutions Suppose it chooses gi coins of type ci If for some i gi c then the greedy solution could have chosen one more coin of denomination 2 ci 1 So for all i gi c and by the uniqueness of such a representation for all i gi ai Now let oi denote the number of ci coins used in an optimal solution for making change of n cents Note that i oi c if this was not true then we could replace the oi coins of size ci with one coin of size ci 1 and oi c coins of size ci reducing the number of coins used contradicting optimality of O This for all i oi c which means that for all i oi ai Since for all i gi ai oi greedy IS optimal c Let 1 4 6 be the set of coin denominations Suppose we make change for n 8 cents The greedy solution uses one 6 cent coin and two 1 cent coins i e it uses 3 coins However the optimal solution would only use two 4 cents coins 3 Given an undirected graph G V E its complement G is the graph V E cid 48 such that for all u cid 54 v u v E cid 48 if and only if u v E Prove that either G or G is connected Let E be the edges in G If G is not connected thene there exists some pair u v that have no path in G connecting them u v E so u v are connected in G For all other vertices w at least one of u w and u w must be in E otherwise both of them are …