Computer Science 111  
version of October 9, 2001 645PM

Problem Set 4:

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


(Problem 1) In class, we defined a machine language and showed its
instruction set.  We were then able to write programs for a few 
Simple tasks.  In this problem, you are asked to make some modifications 
to those programs.

a) Create a machine language program that will add the N numbers
starting at the number K.  These would be the numbers K, K+1, K+2, ... K+N-1.

b) Create a machine language program that will compute 6! (that is, 6 factorial
which is defined as 1x2x3x4x5x6).

c) Create a machine language program that will let you put a value
N in a register and then compute N! (N factorial which is the product
of the first N integers).  (Hint: this will be a modification of one
of the programs for adding the first N integers.

d) The quantity N! grows very quickly.  On our machine where memory stores
values that are no more than 16 bits long, we can not store N! for values
of N that are greater than 8.  If your program from part c) were to try and
compute 9!, it  could cause the toy machine to crash or would cause an
error to occur.  To fix this, modify your program from part c) so that
it checks whether the value of N is more than 8.  If it is, it should
reset the value to 8 and compute 8!.


(Problem 2)  In this problem, you will use compression schemes 
like the ones discussed in class to find a shorter representation
for the phrase

	They saw the theater when the terminator game came.  They
	played the game in the theater.

a) If we were to represent this phrase as it stands (i.e. no compression), 
how many units of memory would it require?

b) Identify duplicate words and tell how you would build a
dictionary to reduce the amount of memory required.  Show the
way the string would be respresented with your dictionary and 
text intermingled. Tell how much memory is saved by your scheme.

c) Use the technique we saw in class to build strings of letters,
not necessarily words, to build a dictionary to further reduce the 
memory required.  Show how your representation would look.  Tell how
much memory is saved in your scheme.

d) (Extra credit)  Devise a scheme of your own to produce a representation
of this particular phrase that requires even less memory.


------
(Numeracy exercise)  

In assignment 2, you determined how many possible
passwords your computer can check during a single COS 111 lecture.
In assignment 3, you determined that it would be fairly easy to
crack a password from the dictionary or made up of 8 digits.
In this assignment, we'll build on those results.

(Part a) If I chose a password made up of letters of the alphabet,
all lower case, and having exactly 6 characters.  How many such words
are there?  How many COS111 lectures will it take your computer
to crack my password?  You may assume that your computer can
check 3.6 million passwords during a COS111 lecture.

(Part b) Suppose that you use your computer to just crack passwords.
So, instead of working at it for 75 minutes twice a week, it tests 
passwords 24 hours a day.  How many passwords can your computer check 
in a day?  You may assume that your computer runs at 800 megahertz (cycles 
per second) and can test one password in a million cycles.

(Part c)  Using the result of part b, how long would it take to crack
my password if it was constructed as in Part a.  Assume that you are 
running your computer to try and crack passwords 24 hours a day. 

(Part d)  How does your answer to part c change if my password has
7 letters?