CS150: Problem Set 4: Hints

Problem Set 4: Hints

You are on your honor to make a good-faith effort to solve problems on your own, or with your partners, before using these hints. This typically means at least 10 minutes of brainstorming, attacking the problem with pencil and paper, drawing small diagrams, and so on. The hints are provided with the intention of reducing frustration when course staff support is not available.

If you use the hints, you should indicate them in your sources list. Using the hints will not influence your grade in any way. However, telling us which hints you used will allow us to know which problems were considered difficult. Example: (define sources (list "I used the hints for problems 3 and 7. The hint for problem 3 was helpful, the hint for problem 7 did not help at all."))

In Python:

sources = ["first source", "second source"]

The hints are written in white text on a white background. On most browsers you make the hint visible by moving your mouse over it. If that doesn't work, click your mouse on the screen and drag it over the box: the text will become visible. Try it out on the apparently-empty box below:

If you can read these words, you are doing it correctly.

Question 3

string-to-baudot Hint 1:

Use map.

string-to-baudot Hint 2:

Use string->list to convert your argument to a list, and then use map on it.

Question 4

Running Time Hint 1:

Check out example 8.2 (list length) in the course book.

Question 5

rotate-wheel Hint:

Use append to place the cdr of the wheel at the front of your answer. Remember that append takes two lists as arguments. To turn X into a one-element list containing X, use (list X).

rotate-wheel-by Hint:

Copy over the n-times code from PS3.

Question 6

rotate-wheel-list Hint:

Use map to apply rotate-wheel to every wheel in the list.

rotate-wheel-list-by Hint:

Copy over the n-times code from PS3.

Question 7

Running Time Hint 1:

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, 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). Express your answer in terms of those three variables.

How much work are we doing per wheel? How many wheels are there?

Running Time Hint 2:

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

Running Time Hint 3:

We are doing Θ(p * r) work for each wheel, and there are w wheels.

Question 8

wheel-encrypt Hint:

Use map to apply xor to two lists: the Baudot letter (which is just a list of bits) and the list consisting of the first part of each wheel. How can you get the first part of each wheel? map again!

Question 10

do-lorenz Hint 1:

This is a recursive procedure in which the base case is (null? list-of-baudots), the results are combined by (cons ...), and the recursive call is to do-lorenz with each of the four arguments modified as per the text.

do-lorenz Hint 2:

This works as the heart of the recursive call:

 (do-lorenz (cdr list-of-baudots)
             (rotate-wheel-list kwheels)
             (if (= (car mwheel) 1) (rotate-wheel-list swheels) swheels)
             (rotate-wheel mwheel))

... but you'll still need two calls to wheel-encrypt to make things work.

Question 11

brute Hint 1:

To call something on all of the numbers between 1 and 5, we might do:

(map (lambda (i) (something i)) (list 1 2 3 4 5))

brute Hint 2:

To consider all pairs of numbers between 1 and 5, we might do:

(map (lambda (i) 
  (map (lambda (j)
          (something i j)
        ) (list 1 2 3 4 5)
  )) (list 1 2 3 4 5)
)

[an error occurred while processing this directive]