The median score on the exam was 154/200 points (77 %). Histogram:

  < 100 xxxxx
100-119 xxxxxxx
120-139 xxxxxxxxx
140-159 xxxxxxxxxxxxxxxxxxxxxxxxxxx
160-179 xxxxxxxxxxxxxxxxxxxxxxx
180-200 xxxxxxxxxxxx

Problem 1:

2's complement notation is used to represent both negative and positive numbers. 7-bit 2's complement, in particular, represents numbers from -2^6 to +2^6-1 ( negative 64 to positive 63. )

If a number is written in 2's complement, you can tell if it is negative by looking at the first bit: if it is 1, it is negative and must be "converted" for you to see what its magnitude is. In this case, the first bit is zero, meaning that we just treat this like an ordinary number:

Part b:(5 points) What is the fewest number of bits that can be used for a 2's complement representation of the decimal value -27? Give the 2's complement representation of -27 in that number of bits.

Well, twenty-seven normally takes 5 bits to write down (27 is 11011) so we'll need one more bit: 5 bits are used to store the values between 0 through 31. If we want to store the values 0 through 31 and their negatives, then we have twice as many values to store; we need 6 bits instead of 5.

To convert -27 to 2's complement, we flip the bits and add one. Flipping the bits in 011011 gives 100100. Adding one gives us 100100 + 000001 == 100101.

Part c:(5 points) Give the addition of the following two 4-bit 2's complement numbers: 0101 and 1001. Is there overflow error?

The reason we use 2's complement representation for numbers is that we can perform arithmetic on them normally. In other words, to add together these two 2's complement numbers, we just add them the normal way:

0101	( 4 + 1 == 5 )
1001	( negative 111 == -7 )
-------
1110	( negative 010 == -2 )

We know no overflow occurred, because the results are correct: 5 + -7 = -2.

Part d:(4 points) What is the decimal representation of the value whose eight-bit floating point representation as presented in Brookshear is 11101101?

Given 1 110 1101, we have the sign bit on, indicating that the number is negative. The exponent, 110, is an excess-4 representation of a number. In this case it represents +2, because 110 in binary is 6, or 4 plus 2.

So, we take the mantissa of 1101, representing the binary fraction .1101, and shift the point two to the right. In other words, we're multiplying it by 2^(positive 2) = 4. Not forgetting the sign bit, we get:
 

Part e:(3 points) The bit sequence 011011010110001101100101 represents an English word in ASCII code. What is that word?

We have 24 bits, or 3 8-bit ASCII bytes. Looking them up in Brookshear:

01101001	01100011	01100101
I	C	E

Problem 2:

Part b: (10 points)Give a Boolean equation using AND OR and NOT for the function whose truth table is:

x	y	f(x,y)
0	0	1
0	1	0
1	0	1
1	1	1

Each row where f(x,y)==1 can be singled out by an expression using nothing but ands:

x	y	f(x,y)	expression
0	0	1	!x AND !y
0	1	0
1	0	1	x AND !y
1	1	1	x AND y

The whole expression can be written (!x and !y) OR (x and !y) OR (x and y).

Further simplification shows that we can turn this into x OR (!x and !y), which becomes x OR !y. But any of the above expressions are correct.

Problem 3:

Executing the program means actually performing the steps in the algorithm. It was not enough to merely describe the algorithm, as it is described above.

When the program is started, we load the value in location 0c into register 2. What is the value of the location 0c? It's 0, as it says in the last line of the listing. Then we load the number 1 (not the contents of the address 1) into register 0.

So, when we get to the jump instruction, do we jump to 0A or don't we? We don't, because register 2 and register 0 contain different values. We compute register 3 = 1, and store this in 0c. In other words:

PC	register 0	register 2	register 3	Memory location 0C
00	??	0	??	0
02	1	0	??	0
04	1	0	??	0
06	1	0	1	0
08	1	0	1	1
0A	1	0	1	1

Many students just described what the instructions meant, but did not perform them --- that is, did not describe what explicit values the registers obtained, or whether the branch in address 04 would or would not be taken. Some said that the value of address 0C was not known, so there was no way to determine if the branch should be taken.

Problem 4:

Part a:  (8 points) How much virtual memory does the system have?

Part b: (12 points) Describe what the memory manager must do when the operating system tries to start a 5th process by loading its machine code into memory.  Assume that none of the original 4 processes have completed.

Problem 5:

int largest_divisor(int I)

{

    int divisor, remain;

    int i;

     for (i = I/2; i >= 1; i--) {        // the largest divisor of I cannot be larger than one half of I.

        if ( (remain = I - I /i) == 0)  // if the remainder of I divided by i is zero, then this means that I is divisible by i.

            divisor = i;                // since we count in descending order, the first divisor we find will be the

            return divisor;             // largest one.

    }

    if (i == 1) return 1;                 // if we reach here, that means no divisor other than 1 can be found. return 1.

}

Problem 6:

int ArrayCompare (array A, array B, int n)

{

    int i;

    int answer;

    for (i=0; i < n; i++) {

        if (A[i] == B[i]) {

            answer++;

        }

    }

    return answer;

}

Problem 7:

Part a:

First execution, k=1, after first cycle of moving top and bottom pointers:

start     top pointer ->    1010
                            0111
                            0010    exchange
                            0101
                            1000
end      bottom pointer ->  0000  

First execution, k=1, after second cycle of moving top and bottom pointers:

start                       0000
                            0111
                            0010    
top and bottom pointers ->  0101  
                            1000
end                         1010  

First execution, k=1, after adjust pointers:

start                       0000  
                            0111  
                            0010   
            top pointer ->  0101  apply recursively to top four items
                            ---------------
         bottom pointer ->  1000  apply recursively to bottom two items  
end                         1010  AFTER application to top four finishes
                  

Second execution, k=2, after first cycle of moving top and bottom pointers:

start                       0000  
            top pointer ->  0111  
         bottom pointer ->  0010    exchange 
end                         0101

Second execution, k=2, after second cycle of moving top and bottom pointers:

start                       0000  
top and bottom pointers ->  0010  
                            0111   
end                         0101

Second execution, k=2, after adjust pointers:

start                       0000  
            top pointer ->  0010 apply recursively to top two items
                           -----------  
         bottom pointer ->  0111  apply recursively to bottom two items  
end                         0101  AFTER application to top two finishes

Third execution, k=3, after first cycle of moving top and bottom pointers:

top and bottom pointers ->  0000  
                            0010 

Third execution, k=3, after adjust pointers:

start      top pointer ->   0000  top pointer=start;, do NOT apply recursively
end      bottom pointer ->  0010  bottom pointer=start;, do NOT apply recursively 

Fourth execution, k=3, after first cycle of moving top and bottom pointers:

start       top pointer ->  0111  
end      bottom pointer ->  0101    exchange 

Fourth execution, k=3, after second cycle of moving top and bottom pointers:

top and bottom pointers ->  0101  
                            0111

Fourth execution, k=3, after adjust pointers:

start       top pointer ->  0101  top pointer=start; do NOT apply recursively
end      bottom pointer ->  0111  bottom pointer=start; do NOT apply recursively 

Fifth execution, k=2, after first cycle of moving top and bottom pointers:

start                       1000  
top and bottom pointers ->  1010  
                  
Fifth execution, k=2, after adjust pointers:

start                       1000  
end         top pointer ->  1010 apply recursively to top two items
                            ---------- 
bottom pointer off bottom of list (bottom pointer > end ); do NOT apply recursively

Sixth execution, k=3, after first cycle of moving top and bottom pointers:

top and bottom pointers ->  1000  
                            1010 

Sixth execution, k=3, after adjust pointers:

start      top pointer ->   1000  top pointer=start;, do NOT apply recursively
end      bottom pointer ->  1010  bottom pointer=start;, do NOT apply recursively 

EXECUTION COMPLETED.  FINAL LIST:
                            0000
                            0010
                            0101   
                            0111
                            1000
                            1010 

Part b:

The full story on the efficiency of BitByBitSort is complicated, just as it is for quick sort. However, the important observation is that BitByBitSort does not call itself recursively for lists of size less than 2 and on average, list lengths are halved from one application to the next recursive application (0's and 1's are equally likely in a bit position). Therefore, on average BitByBitSort is as efficient as quick sort, both executing in time O(n*logn).

Now, turning to worst case time: the worst case for BitByBitSort is if the list contains n identical items. Then BitByBitSort goes through the list once for each bit, b times in all, trying to separate 1's from 0's unsuccessfully. The execution time is then proportional to b*n. In comparison, quick sort at worst only strips the pivot off the list and executes again with a list of length one less, so it executes in time proportional to n + (n-1) + (n-2) + ... + 1 = (n+1)*n/2 = O(n^2). If b is less than n/2, BitByBitSort is more efficient in the worst case. Typically, b is much smaller than n, since having n/2 bits means having magnitudes up to 2^(n/2). For example, if one has a list of 1000 numbers between 0 and 1,000,000, n=1000 and k=20.

Finally, some students raised the issue of how many bits of each number quick sort examines. Quick sort looks at all bits to compare two values. One could conclude that quick sort really has an execution time of O(b*n*logn) on average and O(b*(n^2)) worst case. However, comparisons are usually done by machine instructions in hardware and many bits are compared at the same time (in parallel). In contrast, BitByBitSort explicitly examines one bit at a time so the parameter b must be considered.

Problem 8

if (LastA == nil)                   //if linked list A is empty 
    {FirstA = FirstB;               // reset so FirstA and LastA refer
     LastA = LastB;                 // to linked list B
    }
else                                //otherwise
   { if (LastB != nil)                 //if linked list B is not empty
          {                               // link the first item in B as
            LastA.next = FirstB           // following the last item in A
            LastA = LastB                 // and make LastA refer to the 
          }                              // last item in B
   }
LastB = nil;               // change LastB and FirstB to indicate
FirstB = nil;              // that B is now empty

Problem 9

Part a:

The values examined are 100, 25, 18, and 20 in that order.

Part b:

Following the procedure in Brookshear for inserting an entry in a binary search tree, 99 would be added below and to the right of 87:

    .
     .
      .
       \
       87
         \
         99

Problem 10

Part a:

To look up 20, one divides it by 11 and gets a remainder of 9. Therefore entry 9 of the array is examined. Entry 9 contains a linked list of values. The first value examined is 130. This is not the correct value, so the second value is examined. This is 20 as desired.

Part b:

To add value 99, again one divides by 11. The remainder is 0, so 99 should be added to Entry 0 of the array. This entry is empty, so 99 becomes the only (at present) value stored at Entry 0.