COS111 FALL 1999 FINAL EXAM INFORMATION AND SOLUTIONS The median score on this exam was 162/200; the mean was 147/200. Below are brief solutions for each question. The grader of each question is indicated. Please contact the grader for any specific questions. Problem 1 (grader Mao Chen) (a) 53 (b) 11001110 (c) There is an overflow. (d) May (e) bat AND (ball OR hit) AND (NOT sonar) Problem 2 (grader Mao Chen) (a) If we user a 10-bit representation with the same structure, the range of numbers that can be represented are greater than using 8-bit reoresentation. The exponent can range between -16 and 15, so the range of numbers which can be represented using 10-bit is -15/16 * 2^15 to 15/16 * 2^15. (b) 0100001111 Problem 3 (grader Mao Chen) (a) Instruction Execution Register/Memory change 207F Load register 0 with the value 7F R0 = 7F 2101 Load register 1 with the value 1 R1 = 1 2200 Load register 2 with the value 0 R2 = 0 1314 Load register 3 with the content at memory location 14 R3 = 7E B310 If the R3 = R0 jump to 10 (False, continue) 5212 Add R1 and R2 and store the result to R2 R2 = 1 5313 Add R1 and R3 and store the result to R3 R3 = 7F B008 If R0 = R0 jump to 08 (unconditional jump) B310 If the R3 = R0 jump to 10 (True, jump) 3215 Store the value in R2 in memory cell 15 (15)= 1 C000 halt (b) At the end of the execution, the value in the memory cell 15 is the difference between 7F and the value in the memory cell 14. Problem 4 (grader Andrea LaPaugh) Part a) running: ready(in order of priority-- waiting on I/O: top of the list first): process 4 process 1 process 2 process 5 process 3 process 6 Part b) running: ready(in order of priority-- waiting on I/O: top of the list first): process 1 process 5 process 2 process 3 process 4 process 6 Some people thought that more I/O had finished, rather than that process 4 was starting I/O. This mis-interpretation, if done correctly, received substantial partial credit. Part c) No change, process 3 is run some more: running: ready(in order of priority-- waiting on I/O: top of the list first): process 3 (empty) process 2 process 6 process 1 process 4 process 5 Problem 5 (grader Andrea LaPaugh) one possible solution in pseudocode: answer = "yes" // start out by anticipating WILL see palindrome i=1; j=n; while (i <= j) { if (WORD[i] does not equal WORD[j]) {answer = "no"} i = i+1 j = j-1 } return answer Problem 6 (grader Andrea LaPaugh) One possible solution in pseudocode: function DECODE(string) returns decoded string IF the string to be decoded contains no triples in parentheses, then RETURN the string unchanged. It is already decoded. (This is the BASE CASE) ELSE do the following: Find the leftmost triple (p, q, u) so that the string to be decoded is x(p,q,u)T, where x is a string with no triples and T is the sequence of triples beyond the leftmost triple (T could be empty) Count p characters back from the right end of x. Copy from this point in x q characters and call this length-q suffix y Let z be the string resulting from calling DECODE on string xyuT (i.e. the string returned by the RECURSIVE call to DECODE) Return z END Problem 7 (grader Elena Oranskaya) Note: correct analysis of either the worst case or the average case runtime of the algorithm was accepted for full credit. Below we analyze the worst case scenario. Starting at X (X < Y), the algorithm tries to find the greatest commom divisor of X and Y. Clearly the worst case occurs if the GCD is 1, thereby forcing the algorithm to check every number between 1 and X. When this happens the loop is executed X-1 times, and in each iteration 2 divisions are performed. So the total number of unit operations equals 2*(X-1), which belongs to O(X). Problem 8 (grader Elena Oranskaya) a. The hash function constructs a 9-bit binary number, since each ASCII character of the SS# is mapped to its parity bit. It is certainly possible for either a 0 or 1 to occur in any position of the 9-bit pattern, so the total number of unique hash table entries equals 2^9 = 512. b. To find two conflicting SS#s, we can keep 8 of the digits the same, and change just one digit, making sure the the two differing digits map to the same parity. 011 11 1111 and 311 11 1111 certainly work Of course, there are many correct solutions to this question. Problem 9 (grader Elena Oranskaya) a. If player 'o' would not make a mistake, the outcome of the game is a draw. Therefore, player 'x' can make any of the possible moves from the starting position without being able to affect the outcome. If player 'o' might make a 'bad' move, then player 'x' should take either of the two left branches, since each of them can lead to a winning configuration. b. o-x xxo o-- || ---------------- | / | / | oxx o-x xxo xxo o-- ox- | | | | oxx oox xxo xxo oo- ox- | | oxx xxo oox The first move of 'x' follows the Improving Position Rule. The third branch is eliminated since it violates that rule. 'o' must respond following the Blocking Opponent rule. 'x' responds in the left branch by folloing the Blocking Opponent rule. Note that 'x' does not make a move in the middle branch since there is no blocking to be done, and the position can no longer be improved.