CS150: Problem Set Comments

Problem Set 4: Creating Colossi - Comments

Question 1: For each g and f pair below, argue convincingly whether or not g is (1) O(f), (2) Ω(f), and (3) Θ(f) as explained above. For all questions, assume n is a non-negative integer.

g: n + 3, f: n
(1) n + 3 is in O (n). Choose c = 2 and n₀ = 3. Then, we have (n + 3) ≤ 2n which simplicies to 3 ≤ n which is true for all n ≥ 3.
(2) n + 3 is in Ω (n). Choose c = 1 and n₀ = 0. Then, we have n + 3 ≥ n which is for all n.
(3) n + 3 is in Θ(n) since we showed it was in O(n) and in Ω(n).
g: n² + n, f: n²
(1) n² + n is in O (n²). Choose c = 2 and n₀ = 1. Then, we have (n² + n) ≤ 2n² which simplifies to n ≤ n² and 1 ≤ n, which is true for all n > 1.
(2) n² + n is in Ω(n²). Choose c = 1 and n₀ = 0. Then we have (n² + n) > n² which is true for all n > 0.
(3) n² + n is in Θ(n²) since we showed it was in O(n²) and in Ω(n²).
g: 2ⁿ, f: 3ⁿ
(1) 2ⁿ is in O (3 ⁿ). Choose c = 1 and n₀ = 0. Then we have 2ⁿ ≤ 3ⁿ which is true for all n > 0.
(2) 2ⁿ is not in Ω (3 ⁿ). Since 3ⁿ grows faster than 2ⁿ for any choice of c, we can always find a value m such that 2ⁿ < c * 3ⁿ for all n > m. Recall that 2ⁿ is 2 * 2 * 2 * ... (n times) and 3ⁿ is 3 * 3 * 3 ... (n times). So, we need to choose n such that c * 3 * 3 * 3 ... (n times) is greater than 2 * 2 * ... (n times). Each time we increase the value of n by one, the value of c3ⁿ / 2ⁿ is multiplied by 1.5. After some number of multiplications, it must be greater than 1.
(3) 2ⁿ is not in Θ (3 ⁿ) since in (2) we argued it is not in Ω (3 ⁿ).
g: 2ⁿ, f: nⁿ
(1) 2ⁿ is in O (nⁿ). Choose c = 1 and n₀ = 2. Then, we have 2ⁿ ≤ nⁿ for all n ≥ 2.
(2) 2ⁿ is not in Ω (n ⁿ). Since nⁿ grows faster than 2ⁿ for any choice of c, we can always find a value m such that 2ⁿ < cnⁿ for all n > m. For example, we can choose n = 1/c + 1. Then, cnⁿ = c1/c^{1/c + 1} = 1/c^1/c. Since c must be less than 1/2 (otherwise n = 3 would work), we know 1/c > 2, and 1/c^1/c ≥ 2^1/c.
(3) 2ⁿ is not in Θ (n ⁿ) since in (2) we argued it is not in Ω (3 ⁿ).
g: the federal debt n years from today, f: the US population n years from today (this one requires a more informal argument)
This one merits a longer discussion that will be in a future lecture (probably Lecture 18).

Question 2: Define the xor function that takes two bits as parameters and evaluates to 1 if exactly one of the parameters is 1 and evaluates to 0 otherwise.

A simple way to define xor is:

(define (xor a b) (if (eq? a b) 0 1))

Question 3:
a. Write a function string-to-baudot that takes a string and transforms it into a list of Baudot codes.
b. Write the inverse function, baudot-to-string, that takes a list of lists of baudot codes and transforms it back into a string.
c. Describe the running time of your baudot-to-string procedure using Θ notation. Make sure to explain carefully what any variable you use means.

A good way to define them is to use map:

(define (string-to-baudot string) 
  (map char-to-baudot (string->list string)))

(define (baudot-to-string baudot-list)
  (list->string (map baudot-to-char baudot-list)))

The running time of baudot-to-string depends on the length of the list passed in as baudot-list. We use n to refer to the number of elements in the input list. The map application evaluates an application of baudot-to-char on every element of the list. Since baudot-to-char has constant running time, and is evaluated once for each element, the total running time for the map expression is in Θ(n). Then, baudot-to-string applies list->string to the result of the map. We don't have the code for list->string since it is built in to DrScheme, but it is reasonable to guess it is in Θ(l) where l is the number of elements in the input list, since it has to look at each element to convert it to a string. In this case, the length of the input list to list->string is the length of the output of map which is the length of the input baudot-list, n. This means the list->string application is in Θ(n) work. So, the total running time for baudot-to-string involves Θ(n) work for the map plus Θ(n) work for the list->string application. n + n = 2n, but within Θ the factor doesn't matter, so the total running time is in Θ(n).

Question 4: To rotate our wheels, we will take the number at the front of the list and move it to the back. The first number in the list will represent the current position of the wheel.

a. Define a function rotate-wheel that takes one of the wheels as a parameter. It should return the wheel rotated once. For example, (rotate-wheel (list 1 0 0 1 0)) should evaluate to (0 0 1 0 1). Although all the wheels in our simulated Lorenz cipher machine have five bits, your rotate-wheel procedure should work for any length list.

b. Define a function rotate-wheel-by that takes a wheel as the first parameter and a number as the second. The function should return the wheel list rotated by the number passed in. For example, (rotate-wheel-by (list 1 0 0 1 0) 2) should evaluate to (0 1 0 1 0) and (rotate-wheel-by wheel 5) should evaluate to wheel.

Here's a straightforward answer:

(define (rotate-wheel wheel)
  (append (cdr wheel) (list (car wheel))))

(define (rotate-wheel-by wheel n)
  (if (= n 0) wheel
      (rotate-wheel-by (rotate-wheel wheel) (- n 1))))

Another approach is to remember the n-times procedure we used in PS3:

(define (rotate-wheel-by wheel n)
  ((n-times rotate-wheel n) wheel))

Question 5:
a. Define a function rotate-wheel-list that takes a list of wheels (like K-wheels) as a parameter and evaluates to a list of wheels where each of the wheels in the parameter list of wheels has rotated once. For example, (rotate-wheel-list K-wheels) should evaluate to ((1 0 1 0 1) (1 0 0 1 0) (0 0 1 0 1) (1 1 0 1 1) (0 0 0 1 1)).

b. Define a function rotate-wheel-list-by that takes a list of wheels and a number as parameters, and evaluates to a list where each of the wheels in the parameter list of wheels has rotated the number parameter times. For example, (rotate-wheel-list-by K-wheels 5) should evaluate to the same list as K-wheels.

c. Describe the running time of your rotate-wheel-list-by procedure using Θ notation. Be sure to explain what all variables you use mean.

One way is to use map and ntimes:

(define (rotate-wheel-list wheellist) 
   (map rotate-wheel wheellist))

(define (rotate-wheel-list-by wheellist n)
  ((n-times rotate-wheel-list n) wheellist))

Another approach:

(define (rotate-wheel-list-by wheels n)
  (map (lambda (wheel) (rotate-wheel-by wheel n) wheels))

We'll analyze the second definition (although the result would be the same for the first definition). The running time of rotate-wheel-list-by depends on both inputs — the wheels passed in and the number of rotates, n. To avoid confusion we will use w to represent the number of wheels, p to represent the number of positions in each wheel (fixed as 5 in the problem set, but the procedure we defined would work for any length), and r as the number of rotates to do (the value passed in as n.

Applying the procedure rotate-wheel-list-by evalutes map on the list of wheels. This means the procedure passed as the first parameter to map is evaluated w times.

That map procedure is (lambda (wheel) (rotate-wheel-by wheel n)) so we are evaluating (rotate-wheel-by wheel n) w times. The body of rotate-wheel-by is ((n-times rotate-wheel n) wheel)), so we are evaluating rotate-wheel r times (note that n corresponds to the r variable we introduced) for each wheel. The amount of work done by rotate-wheel depends on the length of the wheel. We defined it as (append (cdr wheel) (list (car wheel))), and append has running time in Θ(l) where l is the number of elements in the first list passed to append (probably, we don't know how DrScheme actually defines it, but do know it has to look at every element in the first list). In this case l is the number of positions in each wheel, p.

So, we are doing Θ(p * r) work for each wheel, and there are w wheels, so the total running time is in Θ(prw).

If you assumed the number of positions and number of wheels is fixed, as it is in the problem set problem, then the only input that varies is the value of r. In this case p and w would be constant, so the total running time is in Θ(r).

Question 6: Define a function wheel-encrypt that takes a Baudot-encoded letter (a list of 5 bits) and a list of wheels as parameters. The function should xor each bit of the Baudot list with the first value of its respective wheel and return the resulting list. For example, (wheel-encrypt (list 0 0 0 1 1) K-wheels) should produce (1 0 1 0 0). Your wheel-encrypt procedure should be Θ(n) where n is the length of the list passed as the first parameter to wheel-encrypt. Argue convincingly why your wheel-encrypt procedure is Θ(n).

(define (wheel-encrypt baudot-letter wheel-list)
  (map xor baudot-letter (map car wheel-list)))

Question 7:
a. Define a function called do-lorenz that takes a list of Baudot values, the K wheels, S wheels and M wheel. The function should encrypt the first Baudot code with the K and S wheels, then recursively encrypt the rest of the Baudot codes with the wheels rotated. The function should return the encrypted values in the form of a list of Baudot values.

b. Define a function lorenz that takes four parameters: a string and three integers. The integers represent the starting positions of the three wheels, respectively. The function should call do-lorenz with the string converted to Baudot and the wheels rotated to the correct starting positions. The function should return the ciphertext in the form of a string.

(define (do-lorenz code k-wheels s-wheels m-wheel)
  (if (null? code) code
      (cons 
       (wheel-encrypt (wheel-encrypt (car code) k-wheels) s-wheels)
       (do-lorenz 
          (cdr code)
          (rotate-wheel-list k-wheels)
          (if (= (car m-wheel) 1) (rotate-wheel-list s-wheels) s-wheels)
              (rotate-wheel m-wheel)))))

(define (lorenz string n1 n2 n3)
  (if (null? string) string
      (baudot-to-string
       (do-lorenz (string-to-baudot string)
                  (rotate-wheel-list-by k-wheels n1)
                  (rotate-wheel-list-by s-wheels n2)
                  (rotate-wheel-by m-wheels n3)))))

Question 8: Define a procedure that takes a ciphertext and evaluates lorenz on the ciphertext for all 125 possible starting positions. It may be helpful to use the function printf that will print out a string to the interactions window.

There are many different ways to do this. Here's one:

(define (solve-lorenz string position1 position2 position3)
  (if (<= position1 5)
      (if (<= position2 5)
	  (if (<= position3 5)
	      (begin ; need begin to do evaluate both expressions
		(printf (lorenz string position1 position2 position3))
		(solve-lorenz string position1 position2 (+ 1 position 3)))
	      (solve-lorenz string position1 (+ 1 position2) 1))
	  (solve-lorenz string (+ 1 position1) 1 1))))

Here's another way:

(define (solve-lorenz ctext)
  (map 
   (lambda (k-step)
     (map
      (lambda (s-step)
	(map
	 (lambda (m-step)
	   (printf (lorenz ctext k-step s-step m-step)))
	 (intsto 5)))
      (intsto 5)))
   (intsto 5)))

The encrypted message: AT THE TIME, I HAD NO THOUGHT OR KNOWLEDGE OF COMPUTERS IN THE MODERN SENSE, AND HAD NEVER HEARD THE TERM USED EXCEPT TO DESCRIBE SOMEBODY WHO DID CALCULATIONS. - THOMAS FLOWERS.

An interesting book about human computers is, When Computers Were Human by David Alan Grier. The human computers of the day followed algorithms similar to those followed by (non-human) computers, just doing the steps by hand and mind.

Question 9:

a. The actual Lorenz cipher operated similarly to the one in this problem set except instead of only having 5 positions in each wheel, each wheel had many more positions (up to 61). Suppose n is the number of possible positions for each Lorenz cipher wheel, and the procedure used to cryptanalyze the cipher is the same as your code (except extended as necessary to handle the extra wheel positions). Describe how the amount of work needed to break a Lorenz-encrypted message grows as a function of the number of wheel positions, n, using Θ notation. Assume the message length and number of wheels are fixed.

If we scale the number of positions, is increases the number of different starting positions for each wheel. In solve-lorenz we fixed the number of positions as 5. A more general solve-lorenz would make that a parameter (we use p):

(define (solve-lorenz p ctext)
  (map 
   (lambda (k-step)
     (map
      (lambda (s-step)
	(map
	 (lambda (m-step)
	   (printf (lorenz ctext k-step s-step m-step)))
	 (intsto p)))
      (intsto p)))
   (intsto p)))

The length of the list passed to the outer map is n since (intsto p) evaluates to a list of length p which we have define as n, the number of wheel positions. For each, element the inner map produces a length of length n, so the length of the list to the innermost map is n². The innermost map evaluates lorenz n times for each element of that list, so there are n * n² total evaluations of lorenz which is in Θ(n³).

The time each lorenz evaluation takes is not constant, though, since it scales with the length of the message (fixed here), and the number of rotations to do (not fixed here - it depends on the number of wheel positions). The average number of rotations will scale as Θ(n) so, the actual work done will scale as Θ(n⁴) in the number of wheel positions. (This was a tough question — is your assumed lorenz was constant time and got Θ(n³) that is a very good (but not quite correct) answer to this question.)

b. Suppose instead that it was possible to add S and K wheels to the Lorenz cipher, and w represents the number of S and K wheels (for example, for the cipher machine in the problem set, w is 5). Describe how the amount of work needed to break a Lorenz-encrypted message grows as a function of w, using Θ notation. Assume the message length and number of wheel positions are fixed.

Here we are fixing the number of wheel positions and varying the number of wheels. From question 5c, we know the work of rotate-wheel-list-by scales with the number of wheels, Θ(w), and solve-lorenz evaluates this a constant number of times. Hence, the work scales as Θ(w).

Note that this assumes all the wheels in a group must start at the same position (this is not the case for the actual machine), and all the wheel pins are known to the code breakers (also not the case in reality most times). Without those assumptions, the analysis becomes much more complicated, and the running time increases as Θ(p^w) where p is the number of possible starting positions for each wheel.

c. If the Nazis learned of Bletchley Park's success in breaking the Lorenz cipher during the war, what changes that could be done without building and redistributing completly new cipher machines, would be most likely to prevent further successful cryptanalysis?

This one needs a longer discussion and some more information on how the Allies actually broke the cipher. We will cover this in a later class (probably Class 18).