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