1 ) Use the algorithm(i-e Horn-sat) for Horn formulas to determine if the following formula is satisable. State every step of the algorithm.

= ( ( x y ) z ) u ( w u ) ( u ( ( y w ) ( w z ) ) x) x

2 ) Compute the convex hull of the following set of points in two dimensions by dividing in to upper hull and lower hull.

(6,3), (0,2), (7,1), (2,6), (0,2), (5,7), (10,1), (5,4), (7,2).

Algorithm : We maintain a list L. The entries of L are vertices pi on the partial upper hull as we move from left to right, along with the slope i = ski, where pk immediately precedes pi in the list. 1: Initially L contains only one entry: p1 (the leftmost point), 1 = + 2: for j = 2 to n do 3: while sij i, where pi, i is the last entry in L do 4: delete pi, ifrom L 5: add pj, j sij to L This algorithm computes the upper hull correctly, since it ensures the slopes are decreasing from left to right, and every point is considered for being in the hull.