CS19002 Programming and Data Structures Laboratory |
Spring 2009, Section 2 |

(Linked lists)

In this exercise, you are supposed to create and work with rho-like linked lists.

Let *M* be a positive integer and *A* = {0,1,2,3,`...`,*M*-1}
the set of all remainders modulo *M*. We start with a random element *x*_{0} of
*A*. Subsequently, for *i* = 1,2,3,`...`, we generate
*x*_{i} = *f*(*x*_{i-1}), where
*f*(*x*) = (*x*^{2}+1) % *M*.
Since the elements of the sequence *x*_{0}, *x*_{1},
*x*_{2}, `...` are from the finite set *A*, there must
be a match *x*_{i} = *x*_{j}
after finitely many iterations. After that, the sequence is periodic, since every
element of the sequence is uniquely determined only by the previous element. To sum up,
the sequence *x*_{0}, *x*_{1}, *x*_{2},
`...` looks like the Greek letter rho. The following figure gives an
example. The first three elements (11, 22 and 35) constitute the tail of the
rho. After that, there is a cycle of length 6.

typedef struct _node { int data; /* value stored in a node */ struct _node *next; /* pointer to the next node */ } node;

**Part 1 [Credit: 50%]**

Write a function `genrho()` with the following prototype:

node *genrho ( int M , int x );

The function accepts the modulus *M* and the initial value
*x*_{0}. It creates a rho-like list using the function
*f*(*x*) described above, and returns a pointer to the
header node of the list. Do not use a dummy node at the beginning
of the list.

**Part 2 [Credit: 50%]**

Write a function `cyclelen()` with the following prototype:

int cyclelen ( node *head );

The function accepts, as its only parameter, a pointer to the header of a rho-like list and returns the length of the cycle of the rho.

It is important to mention that the number of nodes or any such
auxiliary information must **not** be generated during the creation
of the list. The function `cyclelen` only assumes that the
header pointer points to a valid rho-like list.

In order to detect the cycle length, use the following algorithm.
Initialize two pointers `p` and `q` to the header
pointer. Subsequently, enter a loop in which `p` advances
by one node in the list and `q` by two nodes. Evenually,
the two pointers must meet at some node in the cyclic part of
the rho. Once a node in the cycle is detected, make a complete
traversal along the cycle in order to determine its length.

Report the output of your program on the following parameters.

M = 100, x = 5. M = 6543, x = 3456. M = 35791, x = 13579;

You may use the following `main()` function. For simplicity, you
are **not required** to free the memory allocated to a list, before
creating the next list with different parameter values.

int main () { printf("Run 1: M = 100, x = 5, cycle length = %d\n\n", cyclelen(genrho(100,5))); printf("Run 2: M = 6543, x = 3456, cycle length = %d\n\n", cyclelen(genrho(6543,3456))); printf("Run 3: M = 35791, x = 13579, cycle length = %d\n\n", cyclelen(genrho(35791,13579))); exit(0); }

Here is a sample output for *M* = 50 and *x* = 11.

11: Inserted... continuing... 22: Inserted... continuing... 35: Inserted... continuing... 26: Inserted... continuing... 27: Inserted... continuing... 30: Inserted... continuing... 1: Inserted... continuing... 2: Inserted... continuing... 5: Inserted... continuing... 26: Cycle detected... breaking... M = 50, x = 11, cycle length = 6