b.

Consider the following problem "We are given an array of n points in the 6 plane, find
whether three points are collinear". Give a O(n?*log(x)) time algorithm that solves the
given problem.

9. a. Define RP, co-RP, ZPP and BPP randomized complexity classes. Give at least 6 an
example for each.

b.

Suppose you are given the convex hull of a set of n points in the plane, and 6 one
additional point (x, y). The convex hull is represented by an array of vertices in
counterclockwise order, starting from the leftmost vertex. Describe an algorithm to test
in O(log n) time whether or not the additional point (x, y) is inside the convex hull.