Grading Key: CS 231, Lab 3 (Spring 2000)
----------------------------------------

1. Bits and alternatives

    1. 6 bits are needed to distinguish between 52 alternatives
    
    2. 14 bits will allow us to distinguish between 2^14 = 16,384 alternatives
    
    3. Adding 4 bits to a binary representation increases the number of alternatives
       we can represent by a factor of 16

2. Conversion from decimal

     Base 10      Base 2      Base 8          Base 16
      173       1010 1101       255             AD
      152       1001 1000       230             98
      111        110 1111       157             6F
       63         11 1111        77             3F  
       64        100 0000       100             40  

3. Conversion from other bases

      Base 10      Base 2         Base 8          Base 16 
        127        111 1111         177              7F
        169       1010 1001         251              A9
        511     1 1111 1111         777             1FF

4. Fractions

    1.  0.1101 binary is 0.8125 decimal (or 13/16 as a fraction).
    
    2.  A.A in hex represents 10.625 in decimal or 1010.1010 in binary (also 1010.101)

    3.  1/3 is represented by the repeating binary number 0.01010101 (etc.)

5. Floating point numbers

    1. The largest (positive) number representable is:  + 9.9999999  E +99
       The smallest (i.e., largest negative) numberis:  - 9.9999999  E +99
       The difference between the two is                + 1.99999998 E +100   
                                                    OR  +19.9999998  E +99
       (note that the latter is *not* representable in this scheme)

    2. Using this scheme we can represent 2 to the 16th or 65,536 different numbers.
       (Fewer if you recognize that some codes actually represent the same number,
        but I advised people not to worry about this detail.)

6. Addition in other bases

    1. 234 in binary = 11101010
       172 in binary = 10101100
       
       Adding them together (with carries showing, as requested), looks like this:
       
         1 1 1   1
           1 1 1 0 1 0 1 0
       +   1 0 1 0 1 1 0 0
       -------------------
         1 1 0 0 1 0 1 1 0

    2. In binary,      1 is the largest carry
       In decimal,     1 is the largest carry
       In hexadecimal, 1 is the largest carry
       
       In fact, 1 is always the largest carry if we are only adding two numbers.

7. Relative logarithms

    1. 5 decimal digits should be equivalent to about 17 binary digits (or bits),
       since 5 * 3.321928 = 16.60964 or about 17 (rounding up).
    
    2. The ratio of log base 16 and log base 2 of any number will be 1/4, since 
       every hex digit corresponds exactly to 4 binary digits (2 to the 4th = 16).


8. 38 = 100110 in binary
   51 = 110011 in binary
   
   multiplying using 51 as control:
   
               1 0 0 1 1 0
             1 0 0 1 1 0
       1 0 0 1 1 0
   + 1 0 0 1 1 0
   -----------------------
     1 1 1 1 0 0 1 0 0 1 0
     
   multiplying using 38 as control:
   
             1 1 0 0 1 1
           1 1 0 0 1 1
   + 1 1 0 0 1 1
   -----------------------
     1 1 1 1 0 0 1 0 0 1 0

   In both cases we have 11110010010 (bin) = 1938 (dec) = 51 * 38.


9. Textual representation
   
   Since there are 33 symbols listed (note that there are *two* parentheses, 
   left and right), we will need 6 bits per symbol (5 bits would only allow 
   for 32 symbols, since 2^5 = 32). Given 200 symbols in the message, we would
   therefore need a total of 1200 bits (since 6 * 200 = 1200). If you made
   different assumptions based on the typical representations of ASCII, you
   would get slightly larger values:
   
       assuming 7 bits per char (ASCII), 1400 bits;
       assuming 1 byte per char (ASCII), 1600 bits.