Your friends want to break into the lucrative coffee shop market by opening (m,1)(m,2)- a new chain called The Coffee Pot. They have a map of the street corners in a neighbourhood of Toronto (shown on the right), and estimates pi.j of the: profits they can make if they open a shop on corner (i,j), for each corner. | However, municipal regulations forbid them from opening shops on corners (2,1)(2,2) (m, n) (2,n) 1,j), (i + 1,j), (i,j -1), and (i,j +1) (for those corners that exist) if they open a shop on corner (i,j). As you can guess, they would like to select street corners where to open shops in order to maximize their profits! (a) [5 marks] Consider the following greedy algorithm to try and select street corners. C : {(i, j) : 1 m, 1 j n} # C is the set of every available corner S : 0 # S is the current selection of corners while C #0: pick (i,j)e C with the maximum value of pi,j # Add (j) to the selection and remove it (as well as all corners adjacent to it) from C. S:= S U {(i,j)} C := C-(i,j), (i-1,j), (it 1,j),(j-1), (i,j+1)} return S Give a precise counter-example to show that this greedy algorithm does not always find an optimal solution. State clearly the solution found by the greedy algorithm, and show that it is not optimal by giving another selection with larger profit. [15 marks] Prove that the greedy algorithm from part (a) has an approximation ratio of 4. (Hint: Let S be the selection returned by the greedy algorithm and let T be any other valid selection of street corners. Show that for all (i,j) e T, either (i,j) e S or there is an adjacent (i',j')e S with py,j' 2 pij. What does this means for all (i,j) e S and their adjacent corners?)