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