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

 
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.

Solution:

 One approach to solve this problem, could be the following. 
 Let V be the vector of elements (which now is a proper set), and let 
VS be the sorted version of VS. (Although we're not going to explicitly
sort V at all, we can refer to VS as a reference for the "true" order
statistics of V).
 Obviously, if p = 1, then the problem is solved already (*:-)). 
Assume now p>=2.
 First, let's assume our elements are different. (If they aren't, we 
can break ties by employing some sufficiently small \epsilon, in a 
pretty obvious fashion).
 We will use a generalization of the median selection algorithm that 
uses the median selection to quickly find (i.e. in O(n)) the k-th 
element of VS, whatever this (fixed) k index may be (see for instance, 
see section 9.3 in Cormen, Leiserson & Rivest's book).
 The next step is to specify what are the positions (in sorted order) 
of the smallest elements of each set S_i. More precisely, let's call
these indices left(i), 1<=i<=p. Once again, their significance is
that VS(left(i)) = min(S_i) for any 1<=i<=p. Additionally, let 
left(p+1) = n+1.
 Assuming n=pq+r (0<=r<p), we have floor(n/p) = q; if r=0, then 
ceil(n/p)=q, else ceil(n/p)=q+1. As we can easily prove, the number 
of sets S_i having |S_i|=q+1 is exactly r.
 If we impose that |S_i|=q+1 for 1<=i<=r, and |S_i|=q otherwise,
then all left(i)'s are uniquely determined. Namely (as you can 
easily verify),

left(i) = q*(i-1) + min(i,r+1)      1<=i<=p

 Obviously, the time needed to compute all these numbers is O(p).
Since p<=n<=n*log_2(p) we observe that this step doesn't jeopardize
our desired time bound.
 Let's give now an algorithm that produces the output we want. 

PART(i,j, U_i_j)
begin
(1)  if i+1 = j 
(2)     return S_i = U_i_j
     else
(3)     k = ceil((i+j)/2)
(4)     F = select(U_i_j, left(k)-left(i)+1)
(5)     U_i_k = {x| x in U_i_j and x < F}
(6)     U_k_j = U_i_j \ U_i_k
(7)     concatenate (PART(i,k,U_i_k), PART(k,j,U_k_j))
     end
end     

 To use this procedure, we shall call PART(1,p+1,V). Let's see now that
it correctly solves our problem, and it does that in the required time.
 At any moment, the procedure takes as input the indices i and j (i<j)
and set U_i_j, of elements larger or equal to VS(left(i)), and strictly 
smaller than VS(left(j)) (we may assume VS(n+1)=VS(left(p+1))=+oo ). The
output is the set {S_t| i<=t<j}.
 It's obvious that the number of elements in S_t's is determined by the
choice of the indices left(i), left(j). Because of the separation in 
subsets U_i_k and U_k_j, we observe that the condition "i<j => elements 
of S_i are smaller than the elements of S_j" is also satisfied.
 The "select" in Line (4) is the median selection generalization 
algorithm. Instead of calling it with left(k) as "position" argument,
we used the fact that only elements between left(i) and left(j)-1 are 
present in U_i_j. So, the index (in the sorted version of U_i_j) of 
the minimum element in the "middle set" of U_i_j's partition is 
left(k)-left(i)+1.
 Let's analyze the cost (i.e. running time) of the procedure. Instead
of doing this for each call separately, we'll do it in a more "global"
fashion.
 The easiest to count is the number of times Line (2) is executed: p 
times precisely (one for each S_i).
 The number of times Line (1) is executed, is equal to the number of calls 
to PART. We can prove that this number is 1 for the "recursion level 0", 
2 for "recursion level 1", and so on. In total, this number does not exceed
1+2+2^2+...+2^ceil(log_2(p)) which is O(p).
 Obviously, the total time spent on Line (3) is the number of times 
the test in Line (1) was false, that is O(p)-p = O(p).
 Lines (4),(5),(6) require O(|U_i_j|), which is O(n) for recursion level 0,
O(n) for recursion level 1 (because the sum of the length of the 2 vectors
is exactly n), and so on. Overall, it will not exceed O(n) * (log_2(p)+1), 
which is O(n log p).
 Line (7) will account for O(min(k-i,j-k)), at each recursion step. Since 
we already decided to count the 2 calls separately (in "global" fashion), 
all we have to do is measure concatenation of 2 lists. Again, this can't 
be more than O(n) for each recursion level, so O(n log p) overall.
 As we observed earlier p <= n*log2(p), which means that the total time
required is O(n log p), which concludes our proof.




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").


Solution:

  There's obviously no unique solution to the problem, but we can 
certainly imagine something like this. Let the elements of V be 
indexed by numbers in {1,2,..., |V|}.
  Let's represent every V_i as a slightly modified doubly-linked 
circular list: every node, besides its "forward" and "backward" 
pointers, has also a pointer to the head of the list (call this 
"list-head"). Denote by L_i the "list" corresponding to V_i, for 
all i, 1<=i<=|V|.
  For direct access to each particular node, we may assume that, 
in memory, the nodes corresponding to the numbers are stored in 
consecutive locations. As a consequence, when we want to find the
node corresponding to number k, we access the k-th location assigned 
to the |V| nodes.
  We'll consider that the "head" of each list is enough to identify
the set represented by that list. Thus, if we are given a number k,
we find its corresponding node by accessing the k-th location, and 
then we follow the "list-head" link to the head of the list. Shortly, 
we can identify each node's list in O(1).
  When we merge two sets V_i, V_j, we only need to merge the two 
corresponding data structures. More exactly, we need to "glue" the 
lists together (which, due to the doubly-linked structure can be done
in O(1)) and then change the pointers of nodes in the smaller list
to the head of the larger list. Obviously, this node will be the head 
of the resulting structure, and moreover this is going to take
O(min(|V_i|,|V_j|)) time.
  
  

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
         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.
   

Solution
a. i) If A is in I(G), then it represents a set of edges that form an
acyclic subgraph of G. Obviously, if we take out edges from A (even
if we take none), the resulting subgraph isn't going to have any cycles
either.

   ii) Suppose A and B are in I(G), |A|<|B|, and for all edges e in B\A, 
the graph induced by AU{e} contains a cycle. But this is equivalent with 
saying that all edges in B are joining two vertices in the same connected 
component of G(A) (the subgraph of G induced by A).
   Let V_1 U V_2 U ... U V_k , the partition of V such that V_i (1<=i<=k)
are the vertex sets corresponding to G(A)'s connected components. Let 
A_1 U A_2 U ... A_k the partition of edges in A, such that A_i (1<=i<=k)
are (all) the edges of the i-th connected component of G(A). It follows 
that edges in each A_i form a tree, and so |A_i| = |V_i| - 1. Moreover, 
any acyclic graph with vertex set V_i will have at most |V_i|-1 = |A_i| 
edges (due to the acyclic-maximality property of trees).
   By our assumption and by the observation above, B can be partitioned 
into B_1 U B_2 U ... U B_k such that B_i are the sets of edges in B joining 
vertices of V_i (1<=i<=k). Since edges in B don't form any cycle, neither 
will edges in each of the B_i's. This implies |B_i| <= |A_i| (due to the 
property above).
   But then |B|=|B_1|+|B_2|+...+|B_k| <= |A_1|+|A_2|+...+|A_k|=|A|, which 
contradicts the condition |A|<|B|.
   So, there has to exist an edge in B such that it joins 2 connected 
components of G(A), or equivalently, there exists e in B\A such that 
AU{e} belongs to I(G).


b. i)  Obviously, any subset of a set of linearly independent vectors
is still a set of linearly independent vectors.
   ii) Let A, B in I(M) with |A| < |B|. Then dim(sp(A))=|A|<|B|=dim(sp(B)).
(here, sp(A) is the space spanned by the vectors in A; we define sp(B) 
analogously).
   If for every column x in B, AU{x} is not linear independent, then it 
means all the vectors in B can be written as linear combinations of 
vectors in A. But, since sp(B) is spanned (i.e. generated) by vectors 
in B, it follows that sp(B) is included in sp(A), and therefore 
dim(sp(B)) <= dim(sp(A)). From this contradiction, we deduce that the
assumption we made is false, and so there has to exist a vector in B
(and obviously not in A) which, if added to A, still gives us a set
of vectors that are linearly independent.

c. The statement is true. For instance, for a graph G = (V,E), consider 
M as the vertex-edge incidence matrix: for all v in V, for all e in E,
m_v_e = 1 if v is an endpoint of e, and 0 otherwise. We consider that 
the entries - 0's and 1's- are elements of the field Z_2). Obviously, 
every column of M corresponds to exactly one edge of G, and viceversa. 
  To check the second condition, we can prove that each dependent set 
of I(M) corresponds to a unique dependent set of I(G).
  Let's consider a set S of linearly dependent columns of M. That means
there exists a set S' = {c1, c2, ..., ck}, included in S, such that
c1 + c2 + ... ck = 0 (that's because we're in Z_2, and all the 
coefficients can be either 0 or 1). But that means that the number of 
entries equal to 1, in any fixed position v (1<=v<=|V|), in all these 
columns is even. This further means that the subgraph of G determined by
the edges corresponding to ci (1<=i<=|E|) has only vertices with even
degrees (of course, not all of them zero). But it's easy to prove that
such a graph must contain a cycle (otherwise it's acyclic, and so one 
of its connected components is a non-trivial tree; but any such tree 
has at least on leaf!). So, the sub graph determined by S' contains a 
cycle, and naturally, the graph determined by S contains a cycle (since 
it has more edges), and so the set of edges corresponding to columns in 
S is not an independent set in (E, I(G)). By reciprocity, if the graph
determined by a column set S contains a (simple) cycle, then the subset 
of S, formed by the columns that correspond to the (simple) cycle edges, 
is not linearly independent, and so S is not linearly independent.

  This concludes that any graphic matroid is a matric matroid.

   

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.

Solution:

1. We shall employ the data structure described and analyzed in Problem 2.
More over, we maintain a queue containing pointers to the heads of 
the lists (i.e. data structures representing the sets).

2. First of all, we can see that the number of connected components in C
decreases strictly at every stage, so the algorithm is bound to terminate. 

It is easy to see that what the algorithm is doing, basically, is to apply
the "Blue Rule" repeatedly. Yes, it's not clear at first that we don't get
cycles! But, under the assumption that all the weights are different, we can
prove that, in any stage, the new edges that are added to T will not  
generate any cycles. Indeed, assume we have such a cycle. More precisely,
assume (w.l.o.g.) e_1_2, e_2_3, ... e_{t-1}_{t}, e_{t}_1 are edges newly
found at a certain stage of the algorithm, such that for all i, 1<=i<=t,
e_i_{i+1} is the shortest edge that leaves V_i, and the component of its 
second endpoint is V_{i+1}. (We consider V_{t+1} = V_1, for the ease of
notation).

 Note: The above discussion doesn't imply that e_i_{i+1} is just the 
minimum weight edge that joins V_i and V_{i+1}! We just assumed 
(w.l.o.g.) that the second endpoint of the minimum edge that leaves 
V_i, lies in V_{i+1}. (To avoid all this cofusion, we could just number 
the connected components V_{i_1}, V_{i_2},... but that's probably more 
difficult to follow.)
 From the way we chose these edges, we get:

         w(e_1_2) < w(e_2_3) < ... < w(e_{t}_1) < w(e_1_2),

which is clearly absurd. So, we just apply the Blue Rule, with no fear, 
and what we'll get is (obviously, now) a MST!

3. We first start with |V| (singleton) connected components. At each 
stage, the number of connected components decreases by AT LEAST a 
factor of two. As a direct consequence, the number of stages isn't 
going to be more than log_2 |V|.

4. It's enough to show that each stage needs at most O(|E|) time for 
its completion. Since there are at most log_2 |V| stages the 
O(|E| log |V|) time bound follows immediately.
   To find the minimum weight edges that leave all |C| components, 
we could examine (once) the adjacency lists of all vertices in each 
component, that is, the adjacency lists of all vertices in the graph. 
But the number of elements in all these lists is 2*|E| (since the edge 
connecting nodes i and j belongs to the adjacency lists of both i and j).

 Note: In the described procedure, we scan through ALL edges, although
only those that join two different connected components are in fact of 
interest to our purpose. It's clear that we can decide in O(1) if an 
edge actually joins two different connected components, by the 
properties of our data structure. Moreover, we don't need to update 
the adjacency lists, or anything.

  Therefore, finding the edges that we'll add to T, requires no more 
than O(|E|). What about finding the new connected components? For 
instance, by DFS-traversing T, we'll do that in O(|V|+|T|). But since 
our graph is connected, we have |V| <= |E|; obviously, since T is 
included in E, we also have |T| <= |E|.

  Finally, we get that the time spent at every stage is O(|E|), and so the
total time of the algorithm is O(|E|log|V|).