Sample Midterm, Fall 2020 NAME: __________________________________ CPSC 323a First In-Class Examination Do all work on the exam. Each problem is worth the number of points noted, which may not be proportional to its level of difficulty. 1. Describe two's complement and excess notation with offset 128 on a computer with 8-bit words. For each scheme your description should specify - the range of representable integers X; - an expression for rep(X), the representation of the integer X; and - an algorithm to compute rep(-X) from rep(X) (without subtracting from 0). What property of excess notation makes it preferable for the exponent of a floating-point number? 2. a. Construct a Huffman tree for the letters A, C, D, E, N, U, R, and Y whose relative frequencies are as follows: A C D E N U R Y 8 3 4 13 7 3 6 2 Give the Huffman code for each of the letters. To what extent is this code unique? Explain. Give the code for the word REDUNDANCY. b. Is there any set of relative frequencies of the letters A, B, C, D, E, F, G, and H for which A 1 C 001 E 00001 G 0000001 B 01 D 0001 F 000001 H 0000000 is a Huffman code? Justify your answer. 3. a. Describe a coding scheme for 4-bit bytes that can detect and correct single-bit errors. Explain how the code detects and corrects such errors. b. Why is the Lempel-Ziv-Welch encoding of a file likely to be more sensitive to a single-bit error than the file itself? Can such an error cause changes throughout the file once the encoding is decoded? Justify your answers. For simplicity you may assume that the string table never fills up. 4. Describe how a cache works on a read from memory (i.e., the next higher level in the memory hierarchy) in sufficient detail that you have described each of the following terms: memory block cache line cache miss hit ratio direct-mapped set associative fully associative Circle each term at the point it is defined. CS-323-10/04/20