Homework #5Homework 5 is due for all groups on Thursday 3/28/02. Each group is required to hand in atypewritten report (see “More information about homework”) and must be prepared to presentand discuss your report in class (Note: each homework-related presentation in class is worthabout 20% of a homework grade).For the following programs you are to:1 Draw its control graph.2. Compute its complexity V(G).3. Compute its actual complexity, AC4. Reduce the complexity to its minimum if possible. If the complexity was reduced then:a. redraw the graphb. compute the new complexity V(G’)c. show the new program.Bill1 (int a){if (a == 5)c == 15;elsec == 5;k = 4;if (c < 10)g = 65;elseg = 42;}Bill2 (int a, int b, int d, int e, int r1, int r2, int, r3){if (a == 1){if ( b == 1)c == 15;else if (b == 2)c == 20;elsec == 25;}else if (a == 2)x = 2;elsex = 1;if (a == 1){if (c == 15)z = r1;else if (c == 20)z = r2;elsez = r3;}else if ( d == 1){if (e == 1)w = 37;elsew = 38;}else if (d == 2){if ( e == 1)w = 56;elsew = 72;}}Bill3 (int b){printf(“enter multiplier \n”);scanf(“ %d “, &ans)if (ans == 1)x == r1;else if (ans == 2)x == r2;elsex = r3if (b == 1)y = q1 * x;else if (b == 2)y = q2 * x;elsey = q3 * x;printf(“Enter next value \n”);scanf(“ %d “, &ans)if (ans == 1)x == r1;else if (ans == 2)x == r2;elsex = r3}Bill4 (int a, int b, int r1, int r2, int r3){if (a == 1)c == r1;else if (a == 2)c == r2;elsec = r3;if (b == 1){printf(“Hello”);x = 3;}else if (b == 2){printf(“Hi”);y = 82;}elseprintf(Bye”);if (c == r1)g = 65;else if (c == r2)g = 42;elseg = 103;}For the following function compute its essential complexity and prove that it is not structure byusing result 7 from the McCabe paper.search (int item, int table[100] ){x = 0;quit = FALSE;While (!quit){if (Table[x++] == item)return x – 1;if (x > 100)quit == TRUE;}return –1;}In page 319 of the McCabe paper in the lower right corner is a binary search program. In thefollowing page is its control graph. Does this control graph represent the binary search function.Explain.In the McCabe paper result 1 give 4 conditions that if any exists then the program is notstructured. Later in result 5 and 6 they give 2 conditions each. Can we change result 1 from“A structures program can be written by not branching into or out of a loop or into or out of adecision.”To“A structures program can be written by not branching into or out of a decision.”Based on the fact that a loop is in fact a decision. Except for infinite loops, a loop must have astopping condition. Comment and justify your
View Full Document