Computer Science 111  

Problem Set 1:

Due by 5PM Tuesday October 2.
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) (Boolean Algebra)
    a) Show the truth table for  "NOT ( (NOT X) OR (NOT Y) )" ?
    b) What function this truth table represent?



(2) (Truth tables)
    Draw a circuit using AND, OR, and NOT gates for the 
    truth table below.  Use the method we saw in class.

    Note, when drawing, don't worry too much about making your pictures
    look good.  Just be sure to write inside each gate what type of gate
    it is (like in the lecture).

    W X Y || Z
----------------
    0 0 0 || 1
    0 0 1 || 0
    0 1 0 || 0
    0 1 1 || 1
    1 0 0 || 1
    1 0 1 || 0
    1 1 0 || 0
    1 1 1 || 1

    (For extra credit): Can you give a simple description of what this circuit computes?



(3) (Universality)
    A "transistor" (the building block of computing) is just a gate with the 
    following truth table:

     X Y || T(X,Y)
------------------
     0 0 || 0  
     0 1 || 1
     1 0 || 0
     1 1 || 0

     Note that the transistor is a little different from the gates
     we've seen so far, because it is "asymmetric."  It treats
     its two inputs differently, unlike AND, OR, and NAND gates.

     In what follows, it is worthwhile to have some intuition into
     transistors.  The output of the transistor is just equal to Y,
     unless it is "blocked" by X:  that is, if X is 1, then the output 
     is always zero.  Otherwise, the output is just Y.


	a) Show how to build a NOT gate just from transistors.

	b) Show how to build an AND gate just from transistors.


	Hints: 
	i)  You may need more than 1 transistor.
	ii) You are allowed to use inputs that are always fixed at either 0 or 1.

(4) (Numeracy)  
     A computer's CPU has a clock that synchronizes all circuitry.  Each gate
     of the circuit executes once each time the clock ticks.  These gate
     executions taken together enable the CPU to perform one instruction
     (e.g. adding or multiplying 2 numbers) with each tick of the clock.

     The rate of clock ticking is given as a frequency.  For example, 
     a CPU with a frequency of 800 MHz has a clock that ticks 800
     million times per second.

     How many instructions could your computer be carrying out during the
     75 minutes of a COS 111 lecture?

     If you know the clock rate of your computer, tell us and use this
     number in your computation.  If you don't, assume that it has a
     clock rate of 800 MHz.