20CS472001  Design and Analysis of Algorithms II  Winter 2011 


P(1) P(2) P(3) P(4) P(5) ... P(n) ooooo ... owhere 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(j1) 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) oo+++++o+++++o+++++o ... oNow suppose our 1mesh 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,...,n1 (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 nnode 1mesh where the first node is not connected and let Y(n) denote the number of maximal configurations possible for an nnode 1mesh where the first node is connected to another node. Then T(n) and Y(n) may be found from
T(n) = Y(n1), n > 1; Y(n) = T(n2)+Y(n2) + T(n3)+Y(n3) + ... 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(n1) = ?
This gives a very easy way to get Y(n), right? So, what is Y(40)?
T(n) = Y(n1) n > 1; Y(n) = T(n2)+Y(n2) + T(n3)+Y(n3) + ... 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).
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?