COMP 3711H – Fall 2016Tutorial 61. (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 mapgives the distance between gas stations on his route. The professor wishes to make as fewgas stops as possible along the way. Give an efficient method by which Professor Midascan determine at which gas stations he should stop and prove that your algorithm yieldsan optimal solution.The simple greedy algorithm is optimal. It is to drive to the furthest possible city that onecan reach with the current gas in the car and then fill 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 optimalityof greedy by induction on n. Let O be any optimal solution and assume that Greedy isoptimal on all problems on set size < n (for the basis this is obviously true on sets of size1 and 2). We may also assume that, whenever O adds gas, O fills the gas tank completely(since this can not make the solution worse). We use |O| and |G| to denote the numbersof stops each solution makes.Now consider the input on n points. Let g1be the first stop that Greedy makes and o1bethe first stop that OPT makes. By the definition of Greedy, o1≤ g1. WriteG = g1, g2, . . . , gkO = o1, o2, . . . , ok0By definition, k0≤ k, where the giand oiare the stops the algorithms make. Let i be thefirst index for which gi6= oi.Now let t = maxioi≤ g1. From the observations above we know that t ≥ 1.SetO0= g1, ot+1, ot+2, . . . , ok0.Since g1≥ otthis is a legal tour. Thus t = 1, otherwise O was not optimal. SoO0= g1, o2, o3, . . . , ok0.Now note that o2, o3, . . . , ok0must be an optimal stopping pattern for the problem xg1, xg1+1, . . . , xnbecause otherwise we could replace it in O with a smaller set of gas fills, getting a smalleroptimal solution (which is imposisble).From the induction hypothesis we know that g2, . . . , gkis an optimal stopping pattern forthe problem xg1, xg1+1, . . . , xn.Thus k = k0and 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 optimalsolution.1(b) Suppose that the available coins are in denominations that are powers of c. i.e. thedenominations are c0, c1, ..., ckfor some integers c > 1 and k ≥ 1. Show that thegreedy algorithm always yields an optimal solution.(c) Give a set of coin denominations for which the greedy algorithm does not yield anoptimal solution. Your set should include a penny so that there is a solution forevery value of n.(a) Set cq= bn/25c,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 cqquartersSet cd= bnq/10c (largest number of dimes that can be used)Set nd= nq− 10cd(amount remaining)Set cn= bnd/5cSet cp= np= nd− 5cn.Solution uses cqquarters, cddimes, cnnickles and cppennies.Proof of optimality: Assume Greedy solution G is not optimal.Let O be an optimal solution using oqquarters, oddimes, onnickels and oppennies.First note that if op≥ 5 we can replace every 5 pennies with one nickle, reducing thenumber of coins used, so we can assume op< 5.If od≥ 3 replace every three dimes with 1 quarter and 1 nickle without increasingthe 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 ifod= 2 and on= 1. In this case we can replace the two dimes and one nickle withone quarter, reducing the number of coins used, contradicting optimality of O. Sothis is impossible.This means that 10od+ 5on+ op< 25. Sincen = 25oq+ 10od+ 5on+ opwe have just shown that cq= bn/25c = oq.After greedy takes off the cq= oqquarters what remains isn0= n − 25oq= 10od+ 5on+ op.From the facts that on≤ 1 and op≤ 4 we see that 5on+ op< 10 so Greedy choosescd= oddimes and then cnonnickles and then cp= oppennies, so we are done.(b) Recall that there is a unique way to write n in base c, i.e.,n =Xiaicisuch that ∀i, 0 ≤ ai< c.First consider the greedy solutions. Suppose it chooses gicoins of type ci. If, for somei, gi≥ c then the greedy solution could have chosen one more coin of denomination2ci+1. So, for all i, gi< c, and by the uniqueness of such a representation, for all i,gi= ai.Now let oidenote the number of cicoins used in an optimal solution for makingchange of n cents. Note that, ∀i, oi< c; if this was not true then we could replacethe oicoins of size ciwith one coin of size ci+1and (oi− c) coins of size ci, reducingthe 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, E0) such thatfor all u 6= v, {u, v} ∈ E0if 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 haveno 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; otherwiseboth of them are in E which would have connected u, v.• Then every other vertex w is connected to u (and v) in G since such a w must containan edge to at least one of u, v and is connected to the other via the edge {u, v}.• Then every pair w, w0are connected in G since they are both connected to u.4. An (undirected) graph G = (V, E) is bipartate if there exists some S ⊂ V such that, forevery edge {u, v} ∈ E, either (i) u ∈ S, v ∈ V − S or (ii) v ∈ S, u ∈ V − S.Let G = (V, E) be a connected graph. Design an O(n + e) algorithm that checks whetherG is bipartite. Hint: Run BFS.Run BFS. Recall that d[v] will store the shortest distance from …