Homework 5 Solutions

hw05.zip

Solution Files

You can find the solutions in hw05.py.

Scheme Introduction

The 61A Scheme interpreter is included in each Scheme assignment. To start it, type python3 scheme in a terminal. To load a Scheme file called f.scm, type python3 scheme -i f.scm. To exit the Scheme interpreter, type (exit).

Scheme Editor

All Scheme assignments include a web-based editor that makes it easy to run ok tests and visualize environments. Type python3 editor in a terminal, and the editor will open in a browser window (at http://127.0.0.1:31415/). Whatever changes you make here will also save to the original file on your computer! To stop running the editor and return to the command line, type Ctrl-C in the terminal where you started the editor.

The Run button loads the current assignment's .scm file and opens a Scheme interpreter, allowing you to try evaluating different Scheme expressions.

The Test button runs all ok tests for the assignment. Click View Case for a failed test, then click Debug to step through its evaluation.

Remember to run python ok commands (to unlock or submit tests) in a separate terminal window, so that you don't have to stop the editor process.

Recommended VS Code Extensions

If you choose to use VS Code as your text editor (instead of the web-based editor), install the vscode-scheme extension so that parentheses are highlighted.

Before:

After:

Required Questions

Getting Started Videos

These videos may provide some helpful direction for tackling the coding problems on this assignment.

To see these videos, you should be logged into your berkeley.edu email.

YouTube link

Linked Lists

Important: For the Linked List and Efficiency questions, you will make changes to hw05.py.

Q1: Store Digits

Write a function store_digits that takes in an integer n and returns a linked list containing the digits of n in the same order (from left to right).

Important: Do not use any string manipulation functions, such as str or reversed.

def store_digits(n):
    """Stores the digits of a positive number n in a linked list.

    >>> s = store_digits(1)
    >>> s
    Link(1)
    >>> store_digits(2345)
    Link(2, Link(3, Link(4, Link(5))))
    >>> store_digits(876)
    Link(8, Link(7, Link(6)))
    >>> store_digits(2450)
    Link(2, Link(4, Link(5, Link(0))))
    >>> store_digits(20105)
    Link(2, Link(0, Link(1, Link(0, Link(5)))))
    >>> # a check for restricted functions
    >>> import inspect, re
    >>> cleaned = re.sub(r"#.*\\n", '', re.sub(r'"{3}[\s\S]*?"{3}', '', inspect.getsource(store_digits)))
    >>> print("Do not use str or reversed!") if any([r in cleaned for r in ["str", "reversed"]]) else None
    """
    result = Link.empty
    while n > 0:
        result = Link(n % 10, result)
        n //= 10
    return result

Use Ok to test your code:

python3 ok -q store_digits

Q2: Mutable Mapping

Implement deep_map_mut(func, s), which applies the function func to each element in the linked list s. If an element is itself a linked list, recursively apply func to its elements as well.

Your implementation should mutate the original linked list. Do not create any new linked lists. The function returns None.

Hint: You can use the built-in isinstance function to determine if an element is a linked list.
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> isinstance(s, Link)
True
>>> isinstance(s, int)
False

Construct Check: The final test case for this problem checks that your function does not create any new linked lists. If you are failing this doctest, make sure that you are not creating link lists by calling the constructor, i.e.
s = Link(1)

def deep_map_mut(func, s):
    """Mutates a deep link s by replacing each item found with the
    result of calling func on the item. Does NOT create new Links (so
    no use of Link's constructor).

    Does not return the modified Link object.

    >>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
    >>> print(link1)
    <3 <4> 5 6>
    >>> # Disallow the use of making new Links before calling deep_map_mut
    >>> Link.__init__, hold = lambda *args: print("Do not create any new Links."), Link.__init__
    >>> try:
    ...     deep_map_mut(lambda x: x * x, link1)
    ... finally:
    ...     Link.__init__ = hold
    >>> print(link1)
    <9 <16> 25 36>
    """
    if s is Link.empty:
        return None
    elif isinstance(s.first, Link):
        deep_map_mut(func, s.first)
    else:
        s.first = func(s.first)
    deep_map_mut(func, s.rest)

Use Ok to test your code:

python3 ok -q deep_map_mut

Efficiency

Q3: Log k Pow

Write the following function so it runs in ϴ(log k) time.

Hint: this can be done using a procedure called repeated squaring.

def lgk_pow(n,k):
    """Computes n^k.

    >>> lgk_pow(2, 3)
    8
    >>> lgk_pow(4, 2)
    16
    >>> a = lgk_pow(2, 100000000) # make sure you have log time
    """
    if k == 1:
        return n
    if k % 2 == 0:
        return lgk_pow(n*n,k//2)
    else:
        return n * lgk_pow(n*n, k//2)

Use Ok to test your code:

python3 ok -q lgk_pow

Scheme

Important: For the Scheme questions in this next section, you will make changes to hw05.scm.

Q4: Pow

Implement a procedure pow that raises a number base to the power of a nonnegative integer exp. The number of recursive pow calls should grow logarithmically with respect to exp, rather than linearly. For example, (pow 2 32) should result in 5 recursive pow calls rather than 32 recursive pow calls.

Hint:

x^2y = (x^y)²

x^2y+1 = x(x^y)²

For example, 2¹⁶ = (2⁸)² and 2¹⁷ = 2 * (2⁸)².

You may use the built-in predicates even? and odd?. Also, the square procedure is defined for you.

Scheme doesn't have while or for statements, so use recursion to solve this problem.

(define (square n) (* n n))

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

Use Ok to test your code:

python3 ok -q pow

We avoid unnecessary pow calls by squaring the result of base^(exp/2) when exp is even.

The else clause, which is for odd values of exp, multiplies the result of base^(exp-1) by base.

When exp is even, computing base^exp requires one more call than computing base^(exp/2). When exp is odd, computing base^exp requires two more calls than computing base^((exp-1)/2).

So we have a logarithmic runtime for pow with respect to exp.

Q5: Repeatedly Cube

Implement repeatedly-cube, which receives a number x and cubes it n times.

Here are some examples of how repeatedly-cube should behave:

scm> (repeatedly-cube 100 1) ; 1 cubed 100 times is still 1
1
scm> (repeatedly-cube 2 2) ; (2^3)^3
512
scm> (repeatedly-cube 3 2) ; ((2^3)^3)^3
134217728

For information on let, see the Scheme spec.

(define (repeatedly-cube n x)
    (if (zero? n)
        x
        (let
            ((y (repeatedly-cube (- n 1) x)))
            (* y y y))))

Use Ok to test your code:

python3 ok -q repeatedly-cube

We know our solution must be recursive because Scheme handles recursion much better than it handles iteration.

The provided code returns x when n is zero. This is the correct base case for repeatedly-cube; we just need to write the recursive case.

In the recursive case, the provided code returns (* y y y), which is the cube of y. We use recursion to set y to the result of cubing x n - 1 times. Then the cube of y is the result of cubing x n times, as desired.

Q6: Cadr and Caddr

Define the procedure cadr, which returns the second element of a list. Also define caddr, which returns the third element of a list. Try writing cadr and caddr in terms of car and cdr.

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

(define (cadr s)
  (car (cdr s)))

(define (caddr s)
  (car (cddr s))
)

The second element of a list s is the first element of the rest of s. So we define (cadr s) as the car of the cdr of s.

The provided cddr procedure takes a list s and returns a list that starts at the third element of s. So we define (caddr s) as the car of the cddr of s.

Use Ok to test your code:

python3 ok -q cadr-caddr

Check Your Score Locally

You can locally check your score on each question of this assignment by running

python3 ok --score

This does NOT submit the assignment! When you are satisfied with your score, submit the assignment to Gradescope to receive credit for it.

Submit Assignment

Submit this assignment by uploading any files you've edited to the appropriate Gradescope assignment. Lab 00 has detailed instructions.

Exam Practice

Homework assignments will also contain prior exam questions for you to try. These questions have no submission component; feel free to attempt them if you'd like some practice!

Linked Lists

Fall 2020 Final Q3: College Party
Fall 2018 MT2 Q6: Dr. Frankenlink
Spring 2017 MT1 Q5: Insert