St and S2, where Sl contains elements of S less than
p and Sacontains elements of S greater than p.

3. If I 81 1 = k-1l, then output ந.

If I I > 1-1, then output QuickSelect(S1l, k).

If I 31 I ಆ 1-1, then output wickSelect(S, ‏ہم‎ 1 3 | -1).
Prove that the expected number of comparisons made
by QuickSelect on a set S of size n is at most 4n.

b. Consider the following problem "Given n line segments, find

if any two 6 segments intersect". Give a D(n*log(m)) time
algorithm that solves the given problem.

a. Consider tossing m pebbles onto the n nodes of a k-regular
undirected graph 6 (a graph is k-regular if every node has
degree k). Each pebble lands on a node selected uniformly at
random. A pair of pebbles is said to "collide" if they fall
on the same node or on two nodes that are neighbors. What is
the expected number of pairs of pebbles that collide? About
how large must m be before you would expect at least 1 pair
of pebbles to collide?

മ. Consider the following problem "'We are given an array
of n points in the 6 plane, find out the closest pair
of points in the plan". Give a O(n*log(n)) time
algorithm that solves the given problem.

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