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?