20-CS-472-001 Design and Analysis of Algorithms II Winter 2011

Recursion

Due: xxx, 2011

  1. Consider a 1-mesh of size n as shown:
             P(1)  P(2)  P(3)  P(4)  P(5)  ...  P(n)
              o-----o-----o-----o-----o--  ... --o
    
    where the circles represent processors (labeled P(*)) and the lines represent communication paths betwen adjacent processors. We assume that any communicating processor can communicate with only one other processor. Also, P(i) is allowed to communicate with P(j) by using links provided for P(i+1), P(i+2), ... and P(j-1) as shown below for a cummunication link between P(2) and P(5) (o+++++o means a link that is in use).
             P(1)  P(2)  P(3)  P(4)  P(5)  ...  P(n)
              o-----o+++++o+++++o+++++o--  ... --o
    
    Now suppose our 1-mesh is designed so that if P(i) is communicating with P(j), i < j, then P(k), for all i < k < j, cannot be linked with any other processor. In the example above, no communication from P(3) or P(4) is possible since there is a communication path spanning them. At any one moment in time it is possible to make P(i) communicate with P(i+1) for all i=1,3,5,...,n-1 (if n is even). However, if P(1) is communicating with P(n) then no other processors may communicate.

    Let a pair (a,b) denote a communication path between a processor a and a processor b. A configuration is a set of possible paths that are feasible (satisfies the design constraint of the previous paragraph). A maximal configuration is a configuration to which no more pairs can be added without losing feasibility. For the case n=2 the only maximal configuration is {(P(1),P(2))}. For n=4 the maximal configurations are

        {(P(1),P(2)) (P(3),P(4))},
        {(P(1),P(3))},
        {(P(2),P(4))},
        {(P(1),P(4))},
        {(P(2),P(3))}.
    
    For n=6 the maximal configurations are
        {(P(1),P(2)) (P(3),P(4)) (P(5),P(6))},
        {(P(1),P(2)) (P(3),P(5))},
        {(P(1),P(2)) (P(4),P(6))},
        {(P(1),P(2)) (P(4),P(5))}, 
        {(P(1),P(2)) (P(3),P(6))},
        {(P(1),P(3)) (P(4),P(5))},
        {(P(1),P(3)) (P(4),P(6))},
        {(P(1),P(3)) (P(5),P(6))},
        {(P(1),P(4)) (P(5),P(6))},
        {(P(1),P(5))},
        {(P(1),P(6))}, 
        {(P(2),P(3)) (P(4),P(5))},
        {(P(2),P(3)) (P(4),P(6))}, 
        {(P(2),P(3)) (P(5),P(6))},
        {(P(2),P(4)) (P(5),P(6))},
        {(P(2),P(5))},
        {(P(2),P(6))}.
    
    What is the average number of pairs of processors connected in the cases n=2, n=4, and n=6 assuming all maximal configurations are equally likely?

    Let T(n) denote the number of maximal configurations possible for an n-node 1-mesh where the first node is not connected and let Y(n) denote the number of maximal configurations possible for an n-node 1-mesh where the first node is connected to another node. Then T(n) and Y(n) may be found from

          T(n) = Y(n-1),  n > 1;  
          Y(n) = T(n-2)+Y(n-2) + T(n-3)+Y(n-3) + ... T(1)+Y(1) + 1;
          T(1) = 1;
          Y(1) = 0; 
          Y(2) = 1;
    
    Why? (that is, clearly express the meaning of all the terms in the recurrence relation).

    Note that:

          Y(3) = Y(1) + T(1) + 1 = 2;
          T(3) = Y(2) = 1;
          Y(4) = Y(2) + Y(1) + T(2) + T(1) + 1 = 3;
          T(4) = Y(3) = 2;
          Y(5) = Y(3) + Y(2) + Y(1) + T(3) + T(2) + T(1) + 1
               = 2 + 1 + 1 + 1 + 1 = 6;
          T(5) = Y(4) = 3;
          Y(6) = 6 + 5 = 11;
          T(6) = Y(5) = 6;
    
    Compare with the number of maximal configurations listed above for n=2,4,6 (on your own).

    From the equation for Y(n) above find Y(n) - Y(n-1) = ?

    This gives a very easy way to get Y(n), right? So, what is Y(40)?

  2. Find a recurrence relation expressing the average number of connections (communication links) in a 1-mesh of size n.

  3. You derived a recurrence relation for communication connections over maximal configurations of a 1-mesh. The relation was:
          T(n) = Y(n-1) n > 1;
          Y(n) = T(n-2)+Y(n-2) + T(n-3)+Y(n-3) + ... T(1)+Y(1) + 1;
          T(1) = 1;
          Y(1) = 0; 
          Y(2) = 1;
    
    Now use the method of generating functions to actually get a closed form expression for T(n) and Y(n).

  4. State a recursive algorithm for producing sequence X of n bits. A sequence X of n bits is a list of all possible n-bit binary numbers such that each adjacent pair of numbers differs in exactly one bit. Example:
    n=     2         3          4            5
          00       000        0000        00000
          01       001        0001        00001
          11       011        0011        00011
          10       010        0010        00010
                   110        0110        00110
                   111        0111        00111
                   101        0101        00101
                   100        0100        00100
                              1100        01100
                              1101        01101
                              1111        01111
                              1110        01110
                              1010        01010
                              1011        01011
                              1001        01001
                              1000        01000
                                          11000
                                          11001
                                          11011
                                            ...
                                         get it?
    
    What is the complexity of your algorithm?