(1). [5 points] (a). Let S be the set of points {(3,1), (4,4), (5,-1), (2,-1), (2,2), (2,1), (4,-1), (6,1), (8,1), (8,5), (7,4), (3,3)}. When the Graham code of Section 3.5 is run on this data, what is the sorting (as in Table 3.1 of [ORourke]) and what is the history of the stack (as in the example on page 86 of [ORourke])? Plot the points and the resulting convex hull. (b). Give a specific example of a set S of points in the plane, having integer coordinates (give them!) so that, when Grahams algorithm the history of the stack, and the value of i at the top of the while loop is as follows (as on page 86 of [ORourke]):

i = 2 : 4, 6 i = 3 : 2, 4, 6 i = 4 : 1, 2, 4, 6 i = 4 : 2, 4, 6 i = 4 : 4, 6 i = 5 : 0, 4, 6 i = 6 : 5, 0, 4, 6

Draw your example clearly (in addition to giving the integer coordinates of the 7 points of S).

(2). [5 points] Let S = {p1, . . . , pn} be a set of n points in the plane. We say that a point pi S sees to the southwest if there are no points of S having both their x-coordinate strictly less than that of pi and their y-coordinate strictly less than that of pi (i.e., there are no points of S strictly to the southwest of pi). The southwest fence of S is the polygonal chain whose vertices are the points pi S of S that see to the southwest, given in order from left to right (i.e., increasing x-coordinate). (a). Draw the set of points S = {(3, 2),(1, 1),(2, 1), 5, 2),(0, 3),(2, 2),(1, 4)} and highlight (circle) those points that see to the southwest. Show also the southwest fence for S. (b). Describe how to apply the divide and conquer method to give an algorithm to compute the southwest fence of a set S of n points in the plane. What is the efficiency of the algorithm, in big-Oh? (You do not need to write code or pseudocode for this problem, but try to describe the algorithm as clearly as you can, in reasonable length.)