Carnegie Mellon University, Computer Science Department
 Graduate Algorithms 15-750, Spring 2004,  Instructor Manuel Blum
  
 Homework Assignment #1 

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


 
1. The median of a vector of n numbers can be computed in O(n) time by
the algorithm described in the paper "Time Bounds for Selection" 
(M. Blum, R. Floyd, V. Pratt, R. Rivest, R.Tarjan. Journal of Computer
and System Sciences 7, 448-461, 1973).

   Using this algorithm, show that a vector of n numbers can be partitioned
in O(n log p) time (where p is a positive integer) into its "p-quantiles", 
(i.e. into p vectors S_1, S_2, ..., S_p, each of them having a number of
elements equal either to the lower integer part, or to the upper integer 
part of n/p), such that for any A in S_i and B in S_j, if i<j then A<=B.


2. Consider a finite, non-empty set V. Show how to maintain a partition 
C = {V_1, V_2, ..., V_k} of V, such that:

 a. for each v in V, we can identify in _one_step_ the (index j of the
unique) set V_j which contains v.
 b. we can merge any two sets V_i, V_j (1<=i<j<=k) in O(min(|V_i|,|V_j|)) 

 We want you to precisely describe the data structures you choose to solve 
this problem, as well as to concisely prove achieving the specified time for 
each operation ("find", and respectively "merge").


3. a. Let G=(V, E) be an undirected graph. Let I(G) be defined as

I(G) = { F | F is the edge set of an acyclic subgraph (or a "forest") of G}

  Prove that:
   
      i)  For all A in I(G) and B included in A, we have B in I(G)
      ii) For all A and B in I(G), if |A| < |B|, then there exists x in B\A
         such that A U {x} also belongs to I(G).

(We say that (E,I(G)) has a structure of GRAPHIC MATROID.)

   b. Let M be a matrix with entries over a field. Let I(M) be the set of 
linearly independent columns sets of M. That is, 

      I(M) = {S | S is a set of linearly independent columns of M}

Prove that:
   
      i)  For all A in I(M) and B included in A, we have B in I(M)
      ii) For all A and B in I(M), if |A| < |B|, then there exists x in B\A
         such that A U {x} also belongs to I(M).

(If we denote by C(M) the set of M's columns, we say that (C(M),I(M)) has 
a structure of MATRIC MATROID,)

   c. Extra credit. 
   True or False: Is any graphic matroid isomorphic to a matric matroid? 
That is, you should answer whether for any graph G=(V,E), there exists a 
matrix M and a function b:E-->C(M), such that:

   i.  b is bijective
   ii. for any A in I(G), b(A) belongs to I(M) 

(here, b(A)={b(x)|x belongs to A})
   Whether your answer is 'YES' or 'NO', give a valid justification, or 
otherwise it won't be taken into consideration.
   
   

4. Let G = (V, E, w) be a connected undirected graph, where w:E-->N is a 
weight function on its edges. We assume that every two different edges have
different weights associated to them. You are asked to design an algorithm for 
constructing a minimum spanning tree for G, in the following incremental 
manner: 


         Algorithm MST

 Start with a collection C formed by |V| sets, each of these containing a 
(different) vertex of G, and with T a subgraph of G, whose edge set is empty.
  
  (Comment: Throughout the algorithm, T shall denote the partially constructed 
            solution, while C shall denote the set of connected components of 
            T. Moreover, we will - unambiguously - use T to denote T's edge 
            set,) 
            
 At each "stage" of the algorithm, do the following: 
   - for every connected component V_i in C, find the smallest edge e that 
     "leaves" the component (i.e., find e = (u,v) in E such u belongs to 
     V_i, v doesn't belong to V_i, and w(e) is minimum over all edges with 
     this property) and add e to T;
   - let C be the new set of connected components of T
   - if |C| = 1, output T and stop; else, reiterate
   
   
 What you should do:
 1. Describe the data structures that would help you implement this algorithm. 
 2. Prove that the algorithm terminates and that it indeed finds a minimum 
      spanning tree of G.
 3. Prove that there are at most log_2 |V| stages.
 4. Prove that the above algorithm has O(|E| log |V|) complexity.