# Problem Set 4: Solution

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

Answer:

10:    Load    R1 <--- K        (K)

11:    Load    R2 <--- 0000   (running total)

12:    Load    R3 <--- N        (N)

13:    Load    R4 <--- 0001   (always 1)

14:    Add    R2 <--- R2 + R1        (add K to the running total)

15:    Add    R1 <--- R1 + R4        (K = K + 1)

16:    Subtract    R3 <--- R3 - R4   (N = N - 1)

17:    Jump to 14 if (R3 > 0)            (if N isn't 0 yet, continue to add)

18:    Halt        (N is now 0, and R2 = K + (K+1) + ... + (K+N-1) )

Or, if you prefer to use "Jump & Count", here is a solution:

10:    Load    R1 <--- K                    (K)

11:    Load    R2 <--- 0000               (running total)

12:    Load    R3 <--- N                    (N)

13:    Load    R4 <--- 0001               (always 1)

14:    Subtract    R3 <--- R3 - R4    (N = N - 1)

15:    Add    R2 <--- R2 + R1            (add K to the running total)

16:    Add    R1 <--- R1 + R4            (K = K + 1)

17:    Jump to 15 and decrease R3 if  (R3 > 0)

(if N isn't 0 yet, decrease R3 by 1 and continue to add)

18:    Halt        (N is now 0, and R2 = K + (K+1) + ... + (K+N-1) )

Note: without line 14, you'll end up doing one more addition than needed

(i.e. the final result will be R2 = K + (K+1) + ... + (K+N-1) + (K+N) )

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

1 x 2 x 3 x 4 x 5 x 6).

Answer:

10:     Load    R1 <--- 0006    (N)

11:     Load    R2 <--- 0001    (running product)

12:     Load    R3 <--- 0001    (always 1)

13:     Multiply    R2 <--- R2 x R1    (multiply N to the running product)

14:     Subtract    R1 <--- R1 - R3    (N = N - 1)

15:     Jump to 13 if (R1 > 0)            (if N isn't 0 yet, continue to multiply)

16:     Halt     (N is now 0, and R2 = 1 x 2 x 3 x 4 x 5 x 6)

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.

Answer:

10:     Load    R1 <--- N         (N)

11:     Load    R2 <--- 0001    (running product)

12:     Load    R3 <--- 0001    (always 1)

13:     Multiply    R2 <--- R2 x R1    (multiply N to the running product)

14:     Subtract    R1 <--- R1 - R3    (N = N - 1)

15:     Jump to 13 if (R1 > 0)            (if N isn't 0 yet, continue to multiply)

16:     Halt     (N is now 0, and R2 = 1 x 2 x 3 x 4 x 5 x ... x N)

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

Answer:

Here, we need to check the value of N before we calculate the factorial. To do that, we load N and

8 into two different registers, then calculate the value of 8 - N.

If (8 - N > 0), which means N < 8, we do not need to reset the value and can continue to

calculate the factorial;

Otherwise, (8 - N <= 0), which means N >= 8, we need to reset the value to 8 before we

continue to calculate the factorial.

10:    Load    R1 <--- N         (N)

11:    Load    R2 <--- 0001    (running product)

12:    Load    R3 <--- 0001    (always 1)

13:    Load    R4 <--- 0008            (8)

14:    Subtract   R5 <--- R4 - R1    (R5 = 8 - N)

15:    Jump to 17 if (R5 > 0)           (if N < 8, then we needn't reset the value)

16:    Load    R1 <--- 0008            (otherwise, reset N to 8)

17:    Multiply    R2 <--- R2 x R1    (multiply N to the running product)

18:    Subtract    R1 <--- R1 - R3    (N = N - 1)

19:    Jump to 17 if (R1 > 0)            (if N isn't 0 yet, continue to multiply)

1A:     Halt     (N is now 0, and R2 = 1 x 2 x 3 x 4 x 5 x ... N        if N <   8)

or R2 = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8  if N >= 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?

Answer:

The quote has 16 words, made up of 71 letters, 15 spaces, and 2 periods. To store it, we need

71 + 15 + 2 = 88 units of memory

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 represented with your dictionary and text

intermingled. Tell how much memory is saved by your scheme.

Answer:

Notice that the word "the" appears 4 times, "They", "theater" and "game" appear 2 times.

We then build our dictionary:

1 => They    2 => the    3 => theater    4 => game

The quote now reads:

"1 saw 2 3 when 2 terminator 4 came. 1 played 2 4 in 2 3."

They the theater game*1 saw 2 3 when 2 terminator 4 came. 1 played 2 4 in 2 3.

Note: we need a symbol (*) to tell when the dictionary ends; and we need to make sure there aren't

numbers or * in the text we want to compress.

We need 56 unites for the new quote above, and another 22 units for the dictionary. That is

56 + 22 = 78 units in total. We save 88 - 78 = 10 units.

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.

Answer:

Using patterns in the quote, we can build our new dictionary:

1 => They_    2 => _the    3 => ater    4 => _game_

The quote now reads:

"1saw223_when2_terminator4came._1played24in223."

They_#_the#ater#_game_*1saw223_when2_terminator4came._1played24in223.

Note: we use (#) to separated the patterns, we need a symbol (*) to tell when the dictionary ends;

and we need to make sure there aren't numbers or * or # in the text we want to compress.

We need 46 units for the new quote above, and another 23 units for the dictionary. That is

46 + 23 = 69 units in total. We save 88 - 69 = 19 units.

d) (Extra credit) Devise a scheme of your own to produce a representation of this particular

phrase that requires even less memory.

Answer:

Well, there can be many approaches. One common way is to break the representation into bits.

Say, if you have 4 numbers ( 0,1,2,3 ), you can use 2 bits (instead of 8 bits) to represent each

number. Or, in our quote, only 20 different symbols (letters, space, period) have appeared. You

can give a different encoding which requires only 5 bits (less than ASCII, which has 8 bits).

If you know about Haffman coding, you can give a pretty good solution :)

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

Answer:

The password has exactly 6 characters, and each of them can be one of  the 26 lower case letters,

so there can be 26 x 26 x 26 x 26 x 26 x 26 = 26 ^ 6 = 308,915,776 different passwords.

Assume we can check 3.6 million passwords during a COS111 lecture, we need

308,915,776

-------------------    =    85.81 lectures

3,600,000

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

Answer:

800 x 10^6 cycles    60 seconds      60 minutes     24 hours        1 password

-------------------- x ------------ x ------------ x ---------- x ----------------

second                    minute            hour                day             10^6 cycles

= 69,120,000 passwords per day

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

Answer:

From Part a, we know that there can be 308,915,776 different passwords;

from Part b, we know that we can check 69,120,000 passwords per day,

so we need

308,915,776

------------------ = 4.47 days

69,120,000

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

Answer:

If the password has 7 letters, there can be 26^7 = 8,031,810,176 passwords.

We'll need

8,031,810,176

------------------- = 116.2 days

69,120,000

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