Assignment 9
(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₀ of A. Subsequently, for i = 1,2,3,..., we generate x_i = f(x_i-1), where f(x) = (x²+1) % M. Since the elements of the sequence x₀, x₁, x₂, ... 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₀, x₁, x₂, ... 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₀. 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