CS19002 Programming and Data Structures Laboratory Spring 2009, Section 2

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 x0 of A. Subsequently, for i = 1,2,3,..., we generate xi = f(xi-1), where f(x) = (x2+1) % M. Since the elements of the sequence x0, x1, x2, ... are from the finite set A, there must be a match xi = xj 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 x0, x1, x2, ... 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.

Your task is to use a singly linked list to represent such a rho. Start with the following standard type definition.
   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 x0. 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)));

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

Submission site | Lab home | Course home | My home