Base code:

Exercise 2. (30 points) The tortoise and the hare. A popular interview question is to describe an algorithm for testing if a singly linked list contains a cycle. Note that you cannot simply set a pointer to the first node of the list and then repeatedly advance it using next links while checking whether you've reached the end of the list or returned to the first node. It is possible that the list contains a cycle not including the first node (as in the next diagram) and in that case this algorithm would loop forever! An elegant solution for detecting a cycle is Floyd's "tortoise and hare" algorithm. This approach still uses only a constant amount of memory besides the nodes of the list. More precisely, Floyd's algorithm uses two pointer variables, both initially pointing to the first node of the list. In each iteration, one of the pointers (the "hare) is advanced by two nodes. The other pointer (the "tortoise") is advanced by only one node in 1 each iteration. If it is not possible to advance the hare by two nodes because we reach a null pointer this means that we have reached the end of the list, and therefore the list does not have a cycle. If the tortoise and the hare point to the same node at the end of any iteration then we have determined that the list is cyclic. Your task is to implement the function cycle_length() in the provided C program cycle.c, without modifying the main function. This function receives as argument a pointer to the head node of a singly- linked list and returns the number of nodes in the cycle, if a cycle exists, and 0 otherwise. You may only use a constant amount of additional memory in cycle_length(). After you have implemented this function, compiling and running the program with a command line argument between 1 and 6 will call your function against some predefined linked lists, and should print the following cycle lengths: % make cycle cc -g -Wall -std=c99 cycle.c -o cycle % ./cycle 1 Cycle length: 0 % ./cycle 2 Cycle length: 7 % ./cycle 3 Cycle length: 4 % ./cycle 4 Cycle length: 1 % ./cycle 5 Cycle length: 0 % ./cycle 6 Cycle length: 0 Erercise 3 (40 points) Sparse polynomials #include 2 #include 4-typedef struct node { int value; struct node *next; } node; 8 10 * If the singly-linked list headed by 'head' has a cycle 11 * return the length (number of nodes) of the cycle. 12 * Otherwise return e. Use Floyd's tortoise 13 * and hare algorithm described in the lab document to 14 * determine if the list has a cycle. 15 16 - int cycle_length(node *head) { 17 /* TODO: add your code here */ 18 19 200 21 22 23 /* do not modify the main function */ 24 int main(int argc, char* argv[]) 25 { 26 node nodes [25]; //enough to run our tests 27 - for(int i=0; i ", argv[@]); 34 return 1; 35 } 36 37 // convert the first argument from a string to a number 38 int testcase_number = atoi(argv[1]); 39 40 - switch( testcase_number ) { 41 case 1: 42 nodes[0].next = &nodes[1]; 43 nodes[1] .next = &nodes[2]; nodes [2] .next = &nodes[3]; printf("Cycle length: %d ", cycle_length(&nodes[0])); 46 break; 47 48 case 2: nodes [4] .next = &nodes[5]; nodes [5] .next = &nodes [6]; nodes [6] -next = &nodes [7]; 52 nodes [7] .next = &nodes[8]; 53 nodes [8] .next = &nodes[9]; 54 nodes[9].next = &nodes [10]; 55 nodes[10] .next = &nodes[4]; printf("Cycle length: %d ", cycle_length(&nodes [4])); break; 59 60 61 case 3: nodes[11] .next = &nodes[12]; nodes[12] .next = &nodes [13]; nodes [13] .next = &nodes [14]; nodes [14] .next = &nodes [15]; nodes [15] .next = &nodes[16]; nodes [16] .next = &nodes [17]; nodes [17] .next = &nodes[14]; printf("Cycle length: %d ", cycle_length(&nodes[11])); break; case 4: nodes[18] .next = &nodes[18]; printf("Cycle length: %d ", cycle_length(&nodes[18])); break; 72 73 74 75 76 78 79 case 5: nodes [19] .next = &nodes [20]; nodes [20] .next = &nodes [21]; nodes [21] .next = &nodes [22]; nodes[22].next = &nodes [23]; printf("Cycle length: %d ", cycle_length(&nodes[19])); break; case 6: printf("Cycle length: %d ", cycle_length(NULL)); break; 82 83 84 85 86 87 88 89} 90 91 } return; Exercise 2. (30 points) The tortoise and the hare. A popular interview question is to describe an algorithm for testing if a singly linked list contains a cycle. Note that you cannot simply set a pointer to the first node of the list and then repeatedly advance it using next links while checking whether you've reached the end of the list or returned to the first node. It is possible that the list contains a cycle not including the first node (as in the next diagram) and in that case this algorithm would loop forever! An elegant solution for detecting a cycle is Floyd's "tortoise and hare" algorithm. This approach still uses only a constant amount of memory besides the nodes of the list. More precisely, Floyd's algorithm uses two pointer variables, both initially pointing to the first node of the list. In each iteration, one of the pointers (the "hare) is advanced by two nodes. The other pointer (the "tortoise") is advanced by only one node in 1 each iteration. If it is not possible to advance the hare by two nodes because we reach a null pointer this means that we have reached the end of the list, and therefore the list does not have a cycle. If the tortoise and the hare point to the same node at the end of any iteration then we have determined that the list is cyclic. Your task is to implement the function cycle_length() in the provided C program cycle.c, without modifying the main function. This function receives as argument a pointer to the head node of a singly- linked list and returns the number of nodes in the cycle, if a cycle exists, and 0 otherwise. You may only use a constant amount of additional memory in cycle_length(). After you have implemented this function, compiling and running the program with a command line argument between 1 and 6 will call your function against some predefined linked lists, and should print the following cycle lengths: % make cycle cc -g -Wall -std=c99 cycle.c -o cycle % ./cycle 1 Cycle length: 0 % ./cycle 2 Cycle length: 7 % ./cycle 3 Cycle length: 4 % ./cycle 4 Cycle length: 1 % ./cycle 5 Cycle length: 0 % ./cycle 6 Cycle length: 0 Erercise 3 (40 points) Sparse polynomials #include 2 #include 4-typedef struct node { int value; struct node *next; } node; 8 10 * If the singly-linked list headed by 'head' has a cycle 11 * return the length (number of nodes) of the cycle. 12 * Otherwise return e. Use Floyd's tortoise 13 * and hare algorithm described in the lab document to 14 * determine if the list has a cycle. 15 16 - int cycle_length(node *head) { 17 /* TODO: add your code here */ 18 19 200 21 22 23 /* do not modify the main function */ 24 int main(int argc, char* argv[]) 25 { 26 node nodes [25]; //enough to run our tests 27 - for(int i=0; i ", argv[@]); 34 return 1; 35 } 36 37 // convert the first argument from a string to a number 38 int testcase_number = atoi(argv[1]); 39 40 - switch( testcase_number ) { 41 case 1: 42 nodes[0].next = &nodes[1]; 43 nodes[1] .next = &nodes[2]; nodes [2] .next = &nodes[3]; printf("Cycle length: %d ", cycle_length(&nodes[0])); 46 break; 47 48 case 2: nodes [4] .next = &nodes[5]; nodes [5] .next = &nodes [6]; nodes [6] -next = &nodes [7]; 52 nodes [7] .next = &nodes[8]; 53 nodes [8] .next = &nodes[9]; 54 nodes[9].next = &nodes [10]; 55 nodes[10] .next = &nodes[4]; printf("Cycle length: %d ", cycle_length(&nodes [4])); break; 59 60 61 case 3: nodes[11] .next = &nodes[12]; nodes[12] .next = &nodes [13]; nodes [13] .next = &nodes [14]; nodes [14] .next = &nodes [15]; nodes [15] .next = &nodes[16]; nodes [16] .next = &nodes [17]; nodes [17] .next = &nodes[14]; printf("Cycle length: %d ", cycle_length(&nodes[11])); break; case 4: nodes[18] .next = &nodes[18]; printf("Cycle length: %d ", cycle_length(&nodes[18])); break; 72 73 74 75 76 78 79 case 5: nodes [19] .next = &nodes [20]; nodes [20] .next = &nodes [21]; nodes [21] .next = &nodes [22]; nodes[22].next = &nodes [23]; printf("Cycle length: %d ", cycle_length(&nodes[19])); break; case 6: printf("Cycle length: %d ", cycle_length(NULL)); break; 82 83 84 85 86 87 88 89} 90 91 } return