Final Exam Solutions CS 213 Fall 2001 ********* Problem 1 ********* Expression Always True? 1. (x-y) N: Let x = Tmin, y = 0 2. ((x+y)<<4) + y-x == 17*y+15*x Y: Associative, commutative, distributes 3. ~x+~y+1 == ~(x+y) Y: (-x-1)+(-y-1)+1 == -(x+y)-1 4. ux-uy == -(y-x) Y 5. (x >= 0) || (x < ux) N: x = -1. Comparison x < ux is never true. 6. ((x >> 1) << 1) <= x Y: x>>1 rounds toward minus infinity. 7. (double)(float) x == (double) x N: Try x = Tmax. 8. dx + dy == (double) (y+x) N: Try x=y=Tmin. 9. dx + dy + dz == dz + dy + dx Y: Within range of exact representation by double's. 10. dx * dy * dz == dz * dy * dx N: Try dx=Tmax, dy=Tmax-1, dz=Tmax-2 ********* Problem 2 ********* int looper(int n, int *a) { int i; int x = 0; // 2 points for(i = 0; i < n; i++) { // 2points if (a[i] > x) or if (!(a[i] <= x)) // 2 points x = a[i]; // 2 points x++; // 2 points } return x; } ********* Problem 3 ********* typedef struct node { double x; unsigned short; struct node *next; struct node *prev; } node_t; node_t n; void func() { node_t *m; m = n.next->prev; m->y /= 16; return; } ********* Problem 4 ********* M = 5 N = 7 ********* Problem 5 ********* A. 0xbffff5b0 B. char *, int, file_spec *, l_node, int * C. descriptor, len, file, root, &result or B. int, struct file_spec *, int, struct l_node *, int C. len, file, root.tag, root.next, &result ********* Problem 6 ********* Cache m C B E S t s b 1. 32 1024 4 4 64 24 6 2 2. 32 1024 4 256 1 30 0 2 3. 32 1024 8 1 128 22 7 3 4. 32 1024 8 128 1 29 0 3 5. 32 1024 32 1 32 22 5 5 6. 32 1024 32 4 8 24 3 5 ********* Problem 7 ********* copy_matrix(): a. ROWS=128, COLS=128: 100% b. ROWS=128, COLS=192: 25% c. ROWS=128, COLS=256: 100% copy_n_flip_matrix(): a. ROWS=128, COLS=128: 25% b. ROWS=128, COLS=192: 25% copy_n_flip_matrix2() a. ROWS=128, COLS=128: 25% b. ROWS=192, COLS=128: 75% ********* Problem 8 ********* Version Measured CPE Theoretical CPE A1 4.00 4/1 = 4.00 A2 2.67 8/3 = 2.67 A3 1.67 4/3 = 1.33 A4 1.67 4/3 = 1.33 A5 2.67 8/3 = 2.67 ********* Problem 9 ********* A. printed 10 times counter==1 in first line counter==2 in last line B. Output is: counter = 1 counter = 3 counter = 3 C. Because signals are not queued, the program does NOT print the same value of counter each time. The possible values are counter == {1,2,3,4,5} depending on the scheduling of the child processes. ********** Problem 10 ********** First Fit: 40a 40a, 24a 40a, 24a, 24a 40a, 24a, 24a, 48a 40a, 24a, 24f, 48a 40f, 24a, 24f, 48a 24a, 16f, 24a, 24f, 48a 24a, 16f, 24a, 72f 24a, 16f, 24a, 56a, 16f 24a, 40f, 56a, 16f Best Fit: 40a 40a, 24a 40a, 24a, 24a 40a, 24a, 24a, 48a 40a, 24a, 24f, 48a 40f, 24a, 24f, 48a 40f, 24a, 24a, 48a 40f, 24a, 24a, 48f 40f, 24a, 24a, 56a 64f, 24a, 56a make_header: B. header = (size & ~0x7) | (alloc & 0x1) | ((palloc & 0x1) << 1); set_palloc_in_header: A. *(long *)block = (curr & ~0x2) | ((palloc & 0x1) << 1);