Carnegie Mellon University, Computer Science Department
Graduate Algorithms 15-750, Spring 2004  
Instructor: Manuel Blum
TA: Doru Balcan
  
Homework Assignment #2

Important Note: Each problem is worth 10 points. The solutions are expected 
by Friday, Jan 30, at the beginning of the class (IN CLASS). Any hand-ins 
after this deadline shall not be taken into consideration.



1. Consider the system of seven points and seven lines (six line segments and
a circle) shown below. 


                           a
                           o
                          /|\
                         / | \
                        / _|_ \
                     f o/  |  \o e
                      /| \ | / |\
                     / | / X \ | \
                    /  X   |g  X  \
                   / /  \  |  /   \ \
                b o--------o--------o c
                           d

(to understand the figure better, print this page, and then join with a pen 
the following items: lines a-f-b, a-e-c, b-d-c, a-g-d, b-g-e, c-g-f, and 
the circle that passes through d,e,f and has the center in g.)


Define the independence system M = (E, I) where E = {a,b,c,d,e,f,g} and a 
subset S of E is in I iff one of the following is true:

 i)  |S| < 3
 ii) |S| = 3 and none of the seven lines passes through all three points
         in S.
         
  a. Show that M is a matroid. What are its circuits?
 
  b-1. Let K be a field of characteristic different from 2.
     Show that M is NOT (isomorphic to) a(ny) K-matric matroid. That is, 
     there is no system of seven vectors over field K, such that that 
     the independent sets have exactly the same structure as I.
  b-2. Can you give an example of a matric matroid M' over a field of 
     characteristic 2, such that M and M' are isomorphic?
  
(You may alternatively solve b-1, or b-2. It's not necessary to solve both.)
  
  
2. (Note. In solving this problem, you will need to recall and employ the 
results and methods in Problems 1, 2, and 4, from the previous homework.)

  Let G = (V, E, w) be a connected undirected graph, where w is an injective
weight function on the edges (i.e. w:E-->N and for all distinct e1, e2 in E,
w(e1) and w(e2) are distinct). Let n:=|V|, m:=|E|.
  Assume now that the adjacency list of each vertex v has been subdivided 
into its "p-quantiles" (for some p to be determined later). For a vertex v, 
let's denote the set of the all these p-quantiles by 

             P(v,p) = {S_1(v), S_2(v),...,S_p(v)},

such that for all S_i(v), S_j(v) in P(v,p), i<j, for all e' in S_i(v), for 
all e'' in S_j(v), we have w(e') < w(e''). (By a language abuse, we will say
that S_i(v) is "smaller" than S_j(v). Note that "smaller" doesn't refer to 
the size of the sets involved!)
  In the following, we shall modify the algorithm MST in HW1, Pb.4. First 
of all, for maintaining the set of connected components of G at each stage, 
we shall employ our favorite method for solving Pb2 in HW1. Let C denote 
the set of all connected components V_i (1<=i<=k_s) of V, at stage s. 
  To search for the minimum edge that "leaves" such a connected component 
V_i, we proceed by inspecting the adjacency lists of all vertices v in V_i, 
IN BATCHES. More exactly, instead of searching through all of the adjacency 
list of V_i for a minimum edge (v,u) that leaves V_i, we first look into 
the "smallest" p-quantile in P(v,p). If such a search into a quantile results 
in finding at least one edge (v,u) with u in another component, then the 
search is a "success"; otherwise it's a "failure".

  a. Show how, using the procedure described above, we can find all the 
minimum edges that leave the current connected aomponents, such that:
  
     i) the total time due to successes is O(m/p) _per_stage_, and
    ii) the total time due to failures is O(m) altogether.
    
  b. Show that the algorithm described above operates in 
O(log(n)*(m/p + n) + m*log(p)) time. By choosing p accordingly, conclude 
(i.e. prove) that the MST of a graph with m >= n*log(n), can be found in 
O(m*log(log(n))) time.
 
 
 Extra credit: 
   Generalize this result (i.e. algorithm), so that the same running time can 
be achieved for graphs with m < n*log(n). Hint: First apply the algorithm in 
Pb4, HW1 for log(log(n)) stages.




3. Suppose that P = {p1, p2, ..., pn} is a set of n points in the plane, 
no three of which are colinear, and no two have the same x coordinate. 
If we further assume that they are already ordered by their x coordinate, 
then give a linear time algorithm for computing the convex hull of P.
More specifically, this algorithm has to return the smallest convex 
polygon that encloses all n points, by producing its vertices in clockwise 
order (or counter-clockwise order, whichever you prefer). Your algorithm 
should simply incrementally look at the points one at a time, from left 
to right, and if a point pi isn't contained in the interior of the polygon
representing the partially constructed solution up to that moment, this 
partial solution has to be modified.