Computer Science 111  
version of Septmber 26, 2001 227PM

Problem Set 2:

Due by 5PM Tuesday October 9.
You can hand this in at class or leave it in the folder on
the 2nd floor of the CS building (near the student mailboxes).


(1) [Representation]

    In class we saw how strings of bits could be used to represent 
    sets of information.  In some situations, we want to make the
    representation as efficient as possible (i.e. to use the minimum
    number of bits).  

    Consider here the representation of the alphabet.  Suppose you
    wanted to represent all upper and lower case letters 
    (i.e., a, b, ... z, A, B, ... Z).  Suggest a representation and
    tell how many bits it requires.

    How does your answer change if you are only representing the
    capital letters?  


(2) [Carry ripple adder]

    (A) When we built the carry-ripple adder in class, we used 
    a building block that took 3 inputs and generated 2 outputs.

    The inputs were one bit from each addend as well as a carry bit.

    The outputs are a bit from the sum and a carry bit.	

    The carry bits move from one building block to the next -- we think
    of them as ripple-ing down the circuit -- hence the name.

    Build a circuit for this building block from AND, OR and NOT gates.  


    (B) We could build a carry-ripple adder using a black box that took 
    as input two bit chunks from each of the inputs along with a carry bit 
    and generated as output a 2 bit chunk of the output along with a
    carry bit.  So this box would take 5 inputs and generate 3 outputs.

    The black box essentially performs the addition

           Cin
       X2   X1
       Y2   Y1
==============
Cout   Z2   Z1

    where X2 and X1 are the bits of the first number, Y2 and Y1 are the
    bits of the second number and Cin is the carry left over from the
    previous addition.  Z2 and Z1 are the output bits of the sum and 
    Cout is the carry in the output.  

    If you were to build truth tables to describe this box, how many
    would you need and how big would they be?

    If someone gave you such a black box, how would you build an adder
    that worked for adding 4 bit numbers?  for adding 16 bit numbers?

    (C) (extra credit) Use the universal method to give a design in
    terms of AND, OR and NOT gates of the black box described in part 
    B of this problem.

(3) (Hexadecimal representation)

    (A) How do we write the decimal number 10 in hexadecimal?  How do 
    we write the decimal number 100 in hexadecimal?

    (B) When we write the hexadecimal number 10, what is the corresponding
    decimal number?  What decimal number corresponds to the hexadecimal
    number 100?

    (C) What is the sum of the hexadecimal numbers 1C and 2D?  What is
    their product?

(4) (Numeracy)  

     In the last assignment, you determined that your computer could do an
     incredibly large number of instructions during a COS 111 lecture.  You
     calculated ths number by counting the number of times your computer's
     clock ticks during the 75 minutes of a lecture.  In this assignment,
     we will extend this analysis to trying to solve a real problem.

     Imagine that you are using your computer to try and determine my
     password.  You do so, by taking a guess at my password and then 
     performing a test to see if you have guessed correctly.  The test 
     you do is very complicated for reasons you will (hopefully) understand
     by the end of the semester.  Testing one password takes about 
     1 million instructions or 1 million ticks of your computer's clock.

     How many passwords can you check during a COS 111 lecture?

     If you don't have an answer to problem 4 of the first assignment,
     you will not be able to do this problem.  In this case, send mail
     to cs111@cs.princeton.edu and someone will give you a number to use.