Fall 2004, Midterm 1 Answers ---------------------------- = [malloc masters] - solution int **malloc_masters() { int **p; p = (int **) malloc(1*sizeof(int *)); *p = (int *) malloc(1*sizeof(int)); **p = 4; return p; } - solution explained - you need to allocate space in the heap for the 2 boxes in the right (the one in the left is passed as the return value) - the left-most box points to something that points to an int (i.e., an int*). Therefore, it's an int** (2st line) - the box in the middle points to an int. Therefore, it's an int*. To allocate it, we use malloc (2nd line) - the right-most box contains an int. To allocate it, we use malloc (3rd line) - we need to set the contents of the right-most box to 4 - note that the order of lines 2, 3, and 4 can't be different - grading standard: - 1 point for specifying the return type to be int ** - body of the function was worth 5 points with the following deductions: - -1 point for declaring an extra variable - -1 point for other minor errors (e.g. making the second line p = (int *) malloc(1*sizeof(int *)); ) - -4 for having only 1 call to malloc(). - -4 for other major errors (e.g. switching lines 2 and 3) - -5 for having no calls to malloc - -5 for interpreting the problem as asking for a single dimensional array of size 3 = [bit encoding] - solution a: 127 b: - white: 2 gibithings (64 - 14-19 = 31 bits. 2^31 = 2 * 2 ^ 30 = 2 gibithings) - pink: 4 gibithings (64 - 14-18 = 32 bits. 2^32 = 2^2 * 2 ^ 30 = 4 gibithings) - purple: 8 mebithings (64 - 14-27 = 23 bits. 2^23 = 2^3 * 2 ^ 20 = 8 mebithings) - solution explained - part a: - the first 6 bits of an instruction determine whether it's R, I, or J. - an instruction is R iff its first 6 bits are zero - in that case, the final 6 bits define unique instructions => there are (2^6) R instructions - for any other value for the first 6 bits, we have I and J instructions - I, J instructions are different iff their code (first 6 bits is different) => there are (2^6 - 1) I, J instructions (2 are J, rest are I) - total - (2^6) + (2^6 - 1) = 2^7 - 1 = 127 - part b: [consult the IEC] - grading standard - part a: 2 points for the correct answer and 1 point if you were off by one (you put either 128 or 126). There were a few ways you could be off by one. The most common was writing 128 instead of 127 because they forgot that there are only 2^6 - 1 R-types since there is no R-type instruction with opcode 00000, because this implies an I or J type instruction. Other people seemed to way overcount for unknown reasons, writing something like: 2^6 + 2^6 + 2^6 - part b: 3 points for the correct answer. I gave 2 points if they had their IEC wrong (gigithings instead of gibithings). They also got 2 points if they showed work and had a single minor arithmetic error that caused them to have a wrong answer. I gave one point to anyone who seemed to understand that they had about 64 bits to work with and that the two numbers that had to be represented would take up about 14 and (18,19,27) bits. The common problem on this was people doing some calculation like: 2^64 - 2^14 - 2^19 i.e. subtracting the amount of numbers that can be represented rather than subtracting bits. = [circular lists, parts a and b] - solution 1) struct pair *tmp = (struct pair *)malloc(sizeof(struct pair)); 2) tmp->cdr = head->cdr; 3) head->cdr = tmp; 4) tmp->cdr = head->cdr->cdr; 5) head->cdr->cdr = tmp; 6) Box six should have been left blank - solution explained - 1) must allocate the new node in the heap (not in global storage!) - 2,3) to link (tmp) between (head) and (head->cdr) we need to - a) point 5 to 2: ->next = ,,, tmp->cdr = head->cdr; - a) point 1 to 5: ->next = ,,, head->cdr = tmp; - 4,5) to link (tmp) between (head->cdr) and (head->cdr->cdr) we need to - a) point 5 to 3: ->next = ,,, tmp->cdr = head->cdr->cdr; - a) point 2 to 5: ->next = ,,, head->cdr->cdr = tmp; - grading standard - 5 boxes, 1 point per box (all or nothing) - box 6 not blank loses 2 points - subtracted 1 point from a few answers where the student added extra comments to the effect that in the 1 element case the code could potentially segfault or would be incorrect. This displayed an ignorance of what the code was actually doing, so even though their answers to 4 and 5 were correct, I subtracted a point for demostrating their lack of full understanding. = [circular lists, part c] - solution if (p->cdr != head) delete_recursive(p->cdr); free(p); - solution explained - remember that when writing recursive functions your first task should be to ensure it eventually ends (otherwise the program goes into an infinite loop) - the list is circular, so comparing (p == NULL) is useless - the only way to ensure we have run through all the nodes is when we're back at the first element. We know the first element is pointed by head, so we end up when (p == head) - we must access to p->cdr before deleting p (otherwise the contents of the pointer are filled with garbage) - after we have deleted all the right-most elements, we must free the current pointer p - grading standard: - 5 points total - -1 point for working, 3-semicolon solution if (p->cdr == head) { free(p); } else { delete_recursive(p->cdr); free(p); } - -2 points for working, 4-or-more-semicolon solution - not-working solution <= 2: - +1 for at least a call to "free" - +1 for at least a call to "delete_recursive (p->cdr)" = [circular lists, parts d, e] - solution reset_numbers: addi $sp, $sp, -4 sw $ra, 0($sp) beq $a0, $0, end sw $a1, 0($a0) lw $a0, 4($a0) addi $a1, $a1, 1 jal reset_numbers end: lw $ra, 0($sp) addi $sp, $sp, 4 jr $ra - the C program goes into an infinite loop (p is nevern NULL), and as it uses the stack (recursive procedure), the stack will overflow, and the program will crash - solution explained - this is vanilla C->MIPS translation. Some notes - you need both epilog and prolog, as the function is recursive, and therefore calls (jal) itself - p is $a0, so the branch must compare $a0 and $0 - i is $a1 - to write into p->car, we must write into what p points to (remember that car is the first field in the struct p points to). In other words, we store $a1 into 0($a0) - to access p->cdr, we must dereference p using an offset of 4 (the size of the first field in the struct p points to, int car, is 4 bytes). In other words, we load the word in 4($a0). We must use such value as the first argument when calling ourselves, so the value must be stored in $a0 - ++i implies that you must first add 1 to $a1, then call jal - grading standards - d. 9 points - 1pt - prologue - 1pt - branch - 2pts - p->car = i - 2pts - p->cdr - 1pt - ++i - 1pt - epilogue - 1pt - jr $ra - converting the recursive function into a loop (changing "jal reset_numbers" into "j body") takes out 2 points - e. 3 points - 1pt for saying that there'll be an infinite loop - 3pts for saying that there'll be a stack overflow or that the program will crash. = [raw bits] - solution - white STX, O, h, $ and $t5, $s2, $t7 - pink STX, U, c, ! addu $t4, $s2, $s5 - purple STX, O, t, ' ' add $t6, $s2, $t7 - solution explained - [not really needed] - grading standard - character encoding: 0.5 points per box. - instruction: 1 point for correct instruction, 1 point for correct operands in correct order = [FP debate] - solution - int, not float - NICT0: - (2^{24} + 1) - PICT0: 2^{24} + 1 - float, not int - NICT0: - (2^{31} + 2^8) 0xcf000001 - PICT0: 2^{31} 0x4f000000 - solution explained - generic - int (signed) can represent values in the interval [-2^{31}, +2^{31}) (note that the interval is closed in the left and open in the right) - FP 754 has only 24 significant bits (the implicit bit plus the mantissa) - int, not float - we need an integer that int can represent and FP can't - FP can represent any integer of the form: 1 xxxx xxxx xxxx xxxx xxxx xxx, or 1. 2^{23} - when going to the next exponent (24), FP can only represent integers whose last binary digit is zero (i.e., even numbers). This is equivalent to any integer of the form: 1 xxxx xxxx xxxx xxxx xxxx xxx0, or 1.0 2^{24} - in particular, 1 0000 0000 0000 0000 0000 0001 cannot be represented, and there are no smaller integers that can't be represented => PICT0 = 1 0000 0000 0000 0000 0000 0001 = 2^{24} + 1 - float is a symmetric format (can represent the same negative than positive numbers) => NICT0 = -PICT0 - float, not int - we need an integer that FP can represent and int can't - PICT0 is the smallest integer that int can't represent, which is 2^{31} (encoded in FP as 0x4f000000) - NICT0 is the smallest (in absolute value) integer that int can't represent. Note that -2^{31} is representable by both (int is asymmetric) - (-2^{31} - 1) is not representable by FP, as it would require a 32-bit long mantissa -1000 0000 0000 0000 0000 0000 0000 0000 - instead of that, the smallest integer that FP can represent is -1000 0000 0000 0000 0000 0001 0000 0000 (note that a 23-bit long mantissa can cover this number) => NICT0 is -2^{31} - 2^8 (encoded in FP as 0xcf000001) - grading standard - old standard - 2 points per NICT0, PICT0 in the (int, not float) case - 1 point per NICT0, PICT0 in the (float, not int) case - 1 point for the right 754 representation of the (float, not int) NICT0 and PICT0 - no credit for incorrect answers - new standard - (int, not float) case - +2 for the exponent (24), +1 if off by one (23 or 25) - +1 for the symmetry (NICT0 and PICT0 have the same exponent), and form is 2^{xx} - +1 for the {+1,-1} - (float, not int) case - +2 for the exponent (31), +1 if off by one (30 or 32) - +1 for the -2^{8} (no approximations) - +1 for both hex correct - grade = maximum (old grade, new grade) = [reverse engineering, part a] - solution /* unsigned */ int foo(unsigned int n) { return bar(n,0) ; } /* unsigned */ int bar(unsigned int n , /* unsigned */ int ctr) { return ((n==0) ? 0 : bar(n>>1 , ctr+1)) ; // acceptable variations: // return (n ? bar(n/2 , ++ctr) : ctr) ; } - accepted variations: - in bar, parameter n could have been declared as type [signed] int if the shift variation was used; but NOT if the division variation was used, since, for example, 0xFFFFFFFF (treated signed) when divided by 2 yields 0x00000000, and not 0x7FFFFFFF as desired. - head recursion: /* unsigned */ int foo(unsigned int n) { return bar(n) ; } /* unsigned */ int bar(unsigned int n) { return ((n==0) ? 0 : bar(n>>1) + 1) ; // accepted variations: // return (n ? bar(n/2) + 1 : 0) ; } - solution explained - foo just sets $a1 (the second argument) to zero and then falls through bar - bar checks the value of the first parameter ($a0). If zero, it sets the return value ($v0) to $a1 and returns - if $a0 is not zero - the first argument ($a0) is SRL'ed one position, which is equivalent to divide by 2 - the second argument ($a1) is ++'ed - bad calls itself - note that you can write bar in just one line by using the handy conditional expression (page 51 of K&R) - common mistakes: - recursive call: ctr++ was NOT accepted in lieu of ++ctr, since the value of ctr++ is the value of ctr *before* the increment, effectively calling bar with the same value, 0. - trying to optimize bar to one statement, and ending up either with an awful and cryptic return statement [*heavily* frowned upon], or turning it into something that did not work [costing you more points!]. learn the ?: operator. - grading standard [10 points]: - +1 : return types of foo and bar, and correct type for parameter n. - +1 : call to bar within foo, with correct arguments. - +2 : test case. - +2 : base case. - +2 : recursive call to bar with shifted argument. - +2 : incrementing of a counter variable. - -1 : having more than one statement within bar. = [reverse engineering, part b] - solution foo(n) = { [log_2(n)] + 1 , for n > 0 // floor(log_2(n)) + 1 0 , for n == 0 // log_2(0) is undefined } - accepted variations: - floor(log_2(n) + 1) - ceiling(log_2(n+1)) - log_2(n) + 1 // under the assumption that this was an integer logarithm. omitting the case for n==0 - solution explained - bar divides the first argument by 2 and adds 1 to the second argument. This is equivalent to looking for the left-most 1 digit in a 32-bit value. This function is equivalent to a base 2 logarithm. ($a0 == 0) ? 0 : ceiling(log_2($a0)) + 1 - you may think about it this way: log_10() is the number of digits a decimal number has. For example, log_10(1) = 0 log_10(1 <-> 9) = 0 <-> 1 1 digit log_10(10) = 1 log_10(10 <-> 99) = 1 <-> 2 2 digits log_10(100) = 2 log_10(100 <-> 999) = 2 <-> 3 3 digits log_10(1000) = 3 - grading standard [2 points]: - 2/2 : correct [or accepted variation]. - 1/2 : had a logarithm function, or mentioned something about counting bits. - 0/2 : otherwise. = [reverse engineering, part c] - solution - the largest value returned is 32 - solution explained - the biggest number that foo can return is 32 (the number of digits in a large number) - grading standard [2 points]: - 2/2 : 32. - 1/2 : off by one. - 0/2 : otherwise. = [reverse engineering, part c] - solution the value returned by foo((unsigned int) -x), when x was in the range of 0 to 9 (inclusive), is 32 - solution explained - if x is a single-digit integer, -x is 11111......111xxxx, and when casting it to (unsigned int), it gets transformed into a very large number => foo() returns 32 - grading standard [2 points]: - 2/2 : 32. - 1/2 : off by one. - 0/2 : otherwise. = [numerical representation] - solution - white - "-" ,,, "can't tell" - 1001 1111, -31, 0x9f ,,, 1111 1111, -127, 0xff - 1001 0000, -144, 0x90 ,,, 0000 1111, 15, 0x0f - 1001 0000, -112, 0x90 ,,, 1000 1111, -113, 0x8f - 1001 0000, -111, 0x90 ,,, 1000 1111, -112, 0x8f - pink - "can't tell" ,,, "-" - 1111 1111, -127, 0xff ,,, 1001 1111, -31, 0x9f - 0000 1111, 15, 0x0f ,,, 1001 0000, 144, 0x90 - 1000 1111, -113, 0x8f ,,, 1001 0000, -112, 0x90 - 1000 1111, -112, 0x8f ,,, 1001 0000, -111, 0x90 - purple - "-" ,,, "can't tell" - 1100 1111, -79, 0xcf ,,, 1111 1110, -126, 0xfe - 1100 0000, 192, 0xc0 ,,, 0000 1110, 14, 0x0e - 1100 0000, -64, 0xc0 ,,, 1000 1110, -114, 0x8e - 1100 0000, -63, 0xc0 ,,, 1000 1110, -115, 0x8e - solution explained - "-" ,,, "can't tell",,, "+" - in 2's complement, a number is positive iff its 7th (left-most) bit is 0 - sign-magnitude - we're looking for the number closest to -\inf - if the 4 left-most bits are set, and the left-most bit is 1, the number is negative. To make is as negative as possible, we must set the right-most bits to 1111 - if the 4 right-most bits are set, we need to make the number negative (left-most bit set to 1). To make the number as negative as possible, we must set the other 3 bits to 111 - unsigned - we're looking for the number closest to -\inf, which in this case is closest to 0 (there are no negative numbers in unsigned) - if the 4 left-most bits are set, to make the number as small as possible, we must set the right-most bits to 0000 - if the 4 right-most bits are set, we need to make the number as small as possible (left-most bits set to 0000) - 1's and 2's complement - we're looking for the number closest to -\inf - if the 4 left-most bits are set, and the left-most bit is 1, the number is negative. To make is as negative as possible, we must set the right-most bits to 0000 - if the 4 right-most bits are set, we need to make the number negative (left-most bit set to 1). To make the number as negative as possible, we must set the other 3 bits to 000 - grading standard: - 1 point per box - if you missed either the decimal or hex representation, no credit at all = [call] - solution - advantages: - less disk space for executable - smaller memory footprint for process (shared dll in mem) - new libraries do not require recompile - portability - faster exec for already linked code - disadvantage: - executable is not self-contained - runtime speed slower at startup - must keep all dlls on runtime as well as dev system - grading standard: - 3 points total, 1 point per question - vague answers like, "slower", "faster", "better code", "worse code", "independence", "simpler", "more complex", "modular", "less resources", "more resources", "more work for linker", "less space", and "more space" were not given points