Computer Science 111: 

Problem Set 2: Solution

(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? 

Answer:

With N bits, we can represent 2^N letters. 

a) upper and lower letters: that's 52 letters in total. since 2^6 = 64 > 52 > 32 = 2^5, we need 6 bits 

b) only capital letters: that's 26 letters in total. since 2^5 = 32 > 26 > 16 = 2^4, we need 5 bits. 

Below is an example for representing all the 52 upper and lower letters. For capital letters only, you can 

omit the leftmost '0' and thus need 5 bits. 

(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. 

Answer:

                        Truth Table:

We can see from the truth table that: 

 Z     =     ( (NOT X) AND (NOT Y) AND (Cin) ) OR   ( (NOT X) AND (Y) AND (NOT Cin) ) OR

               ( (X) AND (NOT Y) AND (NOT Cin) ) OR    ( (X) AND (Y) AND (Cin) )

 Cout =    ( (NOT X) AND (Y) AND (Cin) ) OR  ( (X) AND (NOT Y) AND (Cin) ) OR

                ( (X) AND (Y) AND (NOT Cin) ) OR ( (X) AND (Y) AND (Cin) )

We can then build the circuit:

(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?

Answer: 

One "easy" way is to build a truth table that has 5 inputs ( X1, Y1, X2, Y2, Cin ) and 

3 outputs ( Z1, Z2, Cout), so the table will have 2^5 = 32 rows. 

However, like what we did in class,  we can rewrite the addition as:

                C                            Cin

                X2                          X1

                Y2                          Y1

==========            =========

    Cout     Z2                    C    Z1

Thus, we need only two truth tables with 2^3 = 8 rows each:

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?

Answer:

We  are going to build Carry-Ripple Adders using the black box:

4-bit adder: 

                  a3    a2    a1    a0

                  b3    b2    b1    b0

          ================

          c3    d3    d2    d1    d0

16-bit adder:

              a15    a14    a13    a12    a11    a10    a9    a8    a7    a6    a5    a4    a3    a2    a1    a0

              b15    b14    b13   b12    b11    a10    b9    b8   b7    b6    b5   b4    b3    b2    b1    b0

     ===============================================================    

     c15   d15    d14    d13    d12    d11    d10   d9    d8   d7    d6    d5    d4    d3   d2    d1    d0

(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.

Answer:

From the two truth tables in part B), we can see that:

 Z1     =     ( (NOT X1) AND (NOT Y1) AND (Cin) ) OR   ( (NOT X1) AND (Y1) AND (NOT Cin) ) OR

                 ( (X1) AND (NOT Y1) AND (NOT Cin) ) OR    ( (X1) AND (Y1) AND (Cin) )

 C      =    ( (NOT X1) AND (Y1) AND (Cin) ) OR  ( (X1) AND (NOT Y1) AND (Cin) ) OR

                ( (X1) AND (Y1) AND (NOT Cin) ) OR ( (X1) AND (Y1) AND (Cin) )

 Z2    =    ( (NOT X2) AND (NOT Y2) AND (C) ) OR   ( (NOT X2) AND (Y2) AND (NOT C) ) OR

                ( (X2) AND (NOT Y2) AND (NOT C) ) OR    ( (X2) AND (Y2) AND (C) )

 Cout =    ( (NOT X2) AND (Y2) AND (C) ) OR  ( (X2) AND (NOT Y2) AND (C) ) OR

                ( (X2) AND (Y2) AND (NOT C) ) OR ( (X2) AND (Y2) AND (C) )

Thus the circuit: 

(3) (Hexadecimal representation)

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

100 in hexadecimal?

Answer:

(10)₁₀ = (A)₁₆        

(100)₁₀ = (6 x 16^1 + 4 x 16^0) ₁₀ = (60)₁₆ + (4)₁₆ = (64)₁₆

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

decimal number corresponds to the hexadecimal number 100?

Answer:

(10)₁₆ = (1 x 16^1 + 0 x 16^0)₁₀ = (16)₁₀

(100)₁₆ = (1 x 16^2 + 0 x 16^1 + 0 x 16^0) ₁₀ = (256 + 0 + 0)₁₀  = (256)₁₀

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

Answer:

(1C)₁₆ = (1 x 16^1 + 12)₁₀ = (28)₁₀ 

(2D)₁₆ = (2 x 16^1 + 13)₁₀ = (45)₁₀

(1C)₁₆ + (2D)₁₆ = (28 + 45)₁₀ = (73)₁₀ = (4 x 16^1 + 9 x 16^0)₁₀ = (40)₁₆ + (9)₁₆ = (49)₁₆

(1C)₁₆ x (2D)₁₆ = (28 x 45) ₁₀ = (1260)₁₀ = (4 x 16^2 + 14 x 16^1 + 12 x 16^0)₁₀

                           = (400)₁₆ + (E0)₁₆ + (C)₁₆ = (4EC)₁₆

(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?

Answer:

Suppose your computer has a clock rate of 900 MHz, then the result from problem 4 of Problem Set 1

is 4,050,000,000,000 ( or 4.05 x 10^12 ), which means your computer can execute 4.05 x 10^12

instructions during the 75 minutes of a COS 111 lecture.

Given the fact that testing one password takes about 1 million ( 10^6 ) instructions, the number of

passwords you can test during the 75 minutes of a COS 111 lecture is

        4.05 x 10^12 / 10^6 = 4.05 x 10^6   (4.05 million)

Comments? Questions? ----- contact us at cs111@cs.princeton.edu