Homework 6 Solutions

Solution Files

You can find the solutions in hw06.scm.

You may find it useful to try code.cs61a.org/scheme when working through problems, as it can draw environment and box-and-pointer diagrams and it lets you walk your code step-by-step (similar to Python Tutor). Don't forget to submit your code through Ok though!

Scheme Editor

As you're writing your code, you can debug using the Scheme Editor. In your scheme folder you will find a new editor. To run this editor, run python3 editor. This should pop up a window in your browser; if it does not, please navigate to localhost:31415 and you should see it.

Make sure to run python3 ok in a separate tab or window so that the editor keeps running.

If you find that your code works in the online editor but not in your own interpreter, it's possible you have a bug in code from an earlier part that you'll have to track down. Every once in a while there's a bug that our tests don't catch, and if you find one you should let us know!

Required Questions

Q1: Survey

Please fill out the survey at this link and fill in hw06.py with the token. The link might not work if you are logged into some google account other than your Berkeley account, so either log out from all other accounts or open the link in a private/incognito window and sign in to your Berkeley account there.

To check that you got the correct token run

Use Ok to test your code:

python3 ok -q survey

Scheme

Getting Started Video

Q2: Thane of Cadr

Define the procedures cadr and caddr, which return the second and third elements of a list, respectively:

(define (cddr s)
  (cdr (cdr s)))

(define (cadr s)

  (car (cdr s))
)

(define (caddr s)

  (car (cddr s))
)

Following the given example of cddr, defining cadr and caddr should be fairly straightforward.

Just for fun, if this were a Python linked list question instead, the solution might look something like this:

cadr = lambda l: l.rest.first
caddr = lambda l: l.rest.rest.first

Use Ok to unlock and test your code:

python3 ok -q cadr-caddr -u
python3 ok -q cadr-caddr

Q3: Sign

Using a cond expression, define a procedure sign that takes in one parameter val and returns -1 if val is negative, 0 if val is zero, and 1 if val is positive.

(define (sign val)

  (cond ((> val 0) 1)
        ((= val 0) 0)
        ((< val 0) -1))
)

The order of the cases doesn't really matter, and we could also use an else clause in the place of one of the conditions.

The condition looks something like this in Python:

if val > 0:
    return 1
elif val == 0:
    return 0
elif val < 0:
    return -1

Opinions differ on which is better, but hopefully you can see that the Scheme cond is quite readable and compact once you get used to it.

Use Ok to unlock and test your code:

python3 ok -q sign -u
python3 ok -q sign

Q4: Pow

Implement a procedure pow for raising the number base to the power of a nonnegative integer exp for which the number of operations grows logarithmically, rather than linearly (the number of recursive calls should be much smaller than the input exp). For example, for (pow 2 32) should take 5 recursive calls rather than 32 recursive calls. Similarly, (pow 2 64) should take 6 recursive calls.

Hint: Consider the following observations:

  1. x2y = (xy)2
  2. x2y+1 = x(xy)2

You may use the built-in predicates even? and odd?. Scheme doesn't support iteration in the same manner as Python, so consider another way to solve this problem.

(define (square x) (* x x))

(define (pow base exp)

  (cond ((= exp 0) 1)
        ((even? exp) (square (pow base (/ exp 2))))
        (else (* base (pow base (- exp 1)))))
)

Use Ok to unlock and test your code:

python3 ok -q pow -u
python3 ok -q pow

The else clause shows the basic recursive version of pow that we've seen before in class.

We save time in computation by avoiding an extra n/2 multiplications of the base. Instead, we just square the result of base^(exp/2).

Video walkthrough:

Submit

Make sure to submit this assignment by running:

python3 ok --submit