COS 111, Fall 1998 - Solutions for Second In-Class Exam

The exam had a median score of 48 points out of 100, so obviously people found it difficult. Here is a more detailed histogram of scores: 

< 20       xx
20-24      xxx
25-29      xxx
30-34      xxxxxx
35-39      xxxxxxxxxxxx
40-44      xxxxxxx
45-49      xxxxxxxxx
50-54      xxxxxxxxxx
55-59      xxxxxxx
60-64      xxx
65-69      xxxxx
70-74      xx
75-79      xxxxx
80-84      xxxxxx
85-89      xx
90-94      
95-99      x

Please see Professor LaPaugh with any grading questions.

Problem 1

Multitasking can be achieved without time slices by taking advantage of the time that processes wait for peripheral devices (disks, keyboard input, etc.). When a process that is running has to wait for input or output from one of these devices, the operating system puts it on the waiting queue and chooses another ready process to run. The new process will run to completion or until it needs to wait, at which point another process (possibly the first) will get a turn. In this way several processes will be part-way through execution at the same time, just as in multitasking with time slices. In fact, changing the running process when a process needs to wait is already done when time slices are used. Using time slices just adds a timer so that no process runs too long without another process getting a turn. Thus, using time slices make multitasking fairer, but is not required for it.

Problem 2

There are many correct answers. Here is one. Variable k selects an entry of B and variable i selects an entry of A to copy into the selected entry of B. Variable k works its way forward starting with the first entry of B, and variable i works its way backwards from the last entry of A. 
i = n;
k = 1;
while (i >= 1)
  {
     B[k] = A[i] ;
     i = i - 1;
     k = k + 1;
  }

Problem 3

To successfully complete this problem, you had to meticulously follow through each recursive application of the function and the return to the calling function after each recursive application finishes. 
execute PrintsWhat(A, 7, 1) -- length=7, start=1:
   if (2*start <= length) true, so:
   temp = 2*start = 2
   PrintsWhat(A, 7, 2) ==> execute PrintsWhat on A with length=7, start=2:
         NEW RECURSIVE EXECUTION
         if (2*start <= length) true so:
         temp = 2*start = 4
         PrintsWhat(A, 7, 4) ==> execute PrintsWhat on A with length=7, start=4:
               NEW RECURSIVE EXECUTION
               if (2*start <= length) false
               if ((2*start)+1 <= length) false
               print A[start]   ==> PRINT A[4], i.e.  PRINT 8
               RETURN FROM EXECUTION OF PrintsWhat(A, 7, 4)  ==>
         RETURNS TO second conditional statement of PrintsWhat(A, 7, 2):
         if ((2*start)+1 <= length) true, so:
         temptoo = (2*start)+1 = 5
         PrintsWhat(A, 7, 5) ==> execute PrintsWhat on A with length=7, start=5:
               NEW RECURSIVE EXECUTION
               if (2*start) <= length) false
               if ((2*start)+1 <= length) false
               print A[start]   ==> PRINT A[5], i.e.  PRINT 5
               RETURN FROM EXECUTION OF PrintsWhat(A, 7, 5) 
         RETURNS TO print statement of PrintsWhat(A, 7, 2):      
         print A[start]  ==> PRINT A[2], i.e. PRINT 13
         RETURN FROM EXECUTION OF PrintsWhat(A, 7, 2)  ==>
   RETURNS TO second conditional statement of PrintsWhat(A, 7, 1):
   if ((2*start)+1 <= length) true, so:
   temptoo = (2*start)+1 = 3
   PrintsWhat(A, 7, 3) ==> execute PrintsWhat on A with length=7, start=3:
         NEW RECURSIVE EXECUTION
         if (2*start <= length) true so:
         temp = 2*start = 6
         PrintsWhat(A, 7, 6) ==> execute PrintsWhat on A with length=7, start=6:
               NEW RECURSIVE EXECUTION
               if (2*start <= length) false
               if ((2*start)+1 <= length) false
               print A[start]   ==> PRINT A[6], i.e.  PRINT 3
               RETURN FROM EXECUTION OF PrintsWhat(A, 7, 6)  ==>
         RETURNS TO second conditional statement of PrintsWhat(A, 7, 3):
         if ((2*start)+1 <= length) true, so:
         temptoo = (2*start)+1 = 7
         PrintsWhat(A, 7, 7) ==> execute PrintsWhat on A with length=7, start=7:
               NEW RECURSIVE EXECUTION
               if (2*start) <= length) false
               if ((2*start)+1 <= length) false
               print A[start]   ==> PRINT A[7], i.e.  PRINT 6
               RETURN FROM EXECUTION OF PrintsWhat(A, 7, 7) 
         RETURNS TO print statement of PrintsWhat(A, 7, 3):      
         print A[start]  ==> PRINT A[3], i.e. PRINT 9
         RETURN FROM EXECUTION OF PrintsWhat(A, 7, 3)  ==>
   RETURNS TO print statement of PrintsWhat(A, 7, 1):  
   print A[start]  ==> PRINT A[1], i.e. PRINT 22

Notes on the grading of this problem. (by A. LaPaugh)
You may see the sum of 6 to 10 small numbers on your paper -- this was to assist me in assigning partial credit. You should not try to interpret those numbers, but here are the criteria I used (NOT in the order of the numbers in the sum).
I looked for evidence that you knew:

Problem 4

PowerB is more efficient. One must ask how many steps each function is going to take to do the calculation. PowerA iterates a multiplication and an addition k times. So the number of steps it takes is proportional to k. PowerB solves a problem half the size (with respect to k) recursively and then does one or two multiplications. This halving can only happen log k times, so the number of steps PowerB takes is proportional to log k. If one compares the number of steps in one iteration of PowerA to the number of steps in one recursive application of PowerB, PowerA looks like it has fewer step (say 3 versus 6 if you count the tests in the conditional statements). However, the fact that PowerB does so many fewer recursive calls completely overshadows this. For example, for k=10, 3k = 30 but 6 * log k < 24, and for k=20, 3k = 60 but 6 * log k < 30. The superiority in efficiency of PowerB over PowerA is analogous to the superiority in efficiency of binary search over sequential search.

Problem 5

The two variables in the program must be declared: 
int result;
int i;