Computer Science 111  
version of October 13, 2001 400PM

Problem Set 3:

Due by 5PM Tuesday October 16.
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).


In this problem, you will design a digital system from beginning
to end.  You will do so by building a State Machine and then
implementing the parts of the state machine as we did in class.

The system you will design is a system to recognize patterns
that might arise in a string of bits.

Suppose that your machine is designed to recognize the pattern
"0110" and "1111".  

Your machine will operate by having a clock that provides one
bit of input every second.  That is, the machine operates at
1 Hz. As each input bit is received, you will have time to 
change state and to update memory.  

You can think of your machine as being the electronics in a
computer operated lock.  Here, the inputs are entered by the
user who wishes to open/close the lock.  The value of output 
indicates the current status of the lock ( 0: closed; 1: open ). 

When the lock is closed, it looks for the pattern "0110" in the
input string. If the pattern "0110" has been read, you will output 1,
indicating that the lock is open. 

Once the lock has been opened, it will stay open until the 
sequence "1111" is received. In reponse to this sequence, 
the lock will close (i.e. the output will be set back to 0). 

Your machine has to be able to operate on arbitrarily long
sequences of inputs.  For example, if the input is 1010110, the
lock will open because the final sequence was correct.

(Part 1) Carefully write down what the inputs and outputs of the
system are, and draw the state diagram describing the State Machine
for the lock (just as we did in class for the traffic light).
Clearly indicate on the arrows between states what the inputs need to
be in order to change from one state to the other.  Don't forget to
include arrows from a state back to itself if it should stay in the same
state.


(Part 2) How many bits do you need to represent your states?
Write down your representation for each state.


(Part 3) Write down the multiple-output truth table corresponding to
the next state and output, given the current state and inputs to it.


(Part 4) Finally, draw the final structure of the circuit for the
 lock.  You can use memory and the Universal Method as
"black boxes" -- you don't need to draw every gate.  Be sure to
specify where the system clock figures in to your circuit.

------
(Numeracy exercise)  

In the last assignment, you determined how many possible
passwords your computer can check during a single COS 111 lecture.
In this problem, we will extend that effort to see how long it would
take to determine my password if I don't choose wisely.

Case A:
The spelling dictionary on my computer has 45424 words.  If you knew
that my password was one of these words, how long would it take you
to ``crack'' my password.  You can either give your answer in
time units (hours, minutes, seconds) or in units of COS 111 lectures.

Case B:
Imagine that my password is an 8 digit number (eg perhaps it is
the last 8 digits of my social security number).  How many
such passwords are possible?  For how many COS 111 lectures would
your computer have to work on the task of ``cracking'' my password
before you had succeeded.?

Case C:
Suppose that you used not only your computer, but the computers of all
of your COS 111 classmates to crack passwords.  There are about 40
students in the class and about 25 class periods.  How large a
set of passwords could you test during the semester?

If you don't have an answer to problem 4 of the second 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.