Consider the following C switch statement: switch (i) { case 15: week = 3; day =

Question

Consider the following C switch statement:

switch (i) {

case 15: week = 3; day = 1; break;

case 16: week = 3; day = 2; break;

case 17: week = 3; day = 3; break;

case 18: week = 3; day = 4; break;

case 19: week = 3; day = 5; break;

case 20: week = 3; day = 6; break;

case 21: week = 3; day = 7; break;

case 22: week = 4; day = 1; break;

case 23: week = 4; day = 2; break;

case 24: week = 4; day = 3; break;

case 25: week = 4; day = 4; break;

case 26: week = 4; day = 5; break;

case 27: week = 4; day = 6; break;

case 28: week = 4; day = 7; break;

case 29: week = 5; day = 1; break;

case 30: week = 5; day = 2; break;

case 31: week = 5; day = 3; break;

}

(a) How many comparisons would be performed, on average, if linear search were used to implement this switch statement? (Assume that i always matches one of the case values listed and that each value is equally likely.) A “comparison” involves testing whether the value of i matches one of the case values.

(b) Repeat part (a) using binary search instead of linear search. Assume that a single comparison can test whether i is less than, equal to, or greater than a particular case value.

(c) Would it make sense to use a jump table to implement this switch statement? Why or why not?

Explanation / Answer

a. On a linear search, the average number of comparisons required is: the number of elements divided by 2. Here we have a total of 17 cases, starting from 15 till 31. Therefore the average number of comparisons is 8.5. The reason is:

For case 15: the number of comparisons required is 1.

For case 16: the number of comparisons required is 2.

For case 17: the number of comparisons required is 3.

.....

.....

.....

For case 31: the number of comparisons required is 17.

And to calculate the average number of comparisons is: (1 + 2 + 3 + ..... + 17) / 17 = ((17 * 18) / 2 ) / 17 = 153 / 17 = 9.

b. On binary search the average number of comparisons required is: logarithm of the number of number of elements to the base 2. Here we have a total of 17 cases, starting from 15 till 31. Therefore the average number of comparisons is 4.08. The reason is, everytime, you search for an element, the size of the list is divided by 2. Assume there are 16 elements(for simplicity), therefore, the mid value is (0+15)/2 = 7.

Means to search for element at index 7 the number of comparisons required is 1.

At this point, if we are not search for element at 7th position, there are 2 possibilities, either the element is in the left side list, or in the rightside list. Please not that, we can apply the binary search only on sorted list. Therefore, now, we will search for the left side list of 7 elements, or in the right side list of 8 elements. The search proceeds like this, by subsiding the list by half after each comparison. Therefore the average number of comparisons required on a binary search is slightly more than 4.

c. The jump table means an array of relative addresses where the program execution control can be moved to. Its pretty much similar to the switch statement. Instead of maintaining a switch case block, we can simply divide the blocks, and give the names to every block and store the block addresses in the array(jump table). Based on the choice, we can move on to that address, and execute that block of code. Therefore to conclude, we can implement this switch case using jump table.

If you have any further queries, just get back to me.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.