Graph/Divide and Conquer: Assignment

  1. Let G = (V, E) represent a graph. G is bipartite if V can be partitioned into two sets S1 and S2 such that for all (i,j) E, i S1 and j S2 or vise versa. (I.E., there is no edge whose end points are both in S1 or both in S2.)

    Write an algorithm BIPAR to determine if a given graph is bipartite. At each call to BIPAR a new edge (i,j) is given in no particular order. BIPAR must accept or reject (i, j) depending on whether the graph so far constructed (including (i, j)) is bipartite or not. Assume n = |V| is initialized before the first call to BIPAR. BIPAR must test m edges in time O(m+n) plus the time required to execute a sequence of no more than 2m FIND's and max(m, n-2) UNION's.

  2. (Double maxima and minima) We are given n>1 elements: x1 , x 2 , . . . , x n. Write an algorithm to find the two largest and the two smallest elements. Assume n is a multiple if 4. Show that your algorithm requires no more than (9/4)n - 4 comparisons between elements.