Due by 11:59pm on Wednesday, July 29

Instructions

Download hw05.zip. Inside the archive, you will find a file called hw05.py, along with a copy of the ok autograder.

Submission: When you are done, submit the assignment to Gradescope. You may submit more than once before the deadline; only the final submission will be scored. Check that you have successfully submitted your code on Gradescope. See Lab 0 for more instructions on submitting assignments.

Using Ok: If you have any questions about using Ok, please refer to this guide.

Readings: You might find the following references useful:

• Scheme Specification
• Scheme Built-in Procedure Reference

Grading: Homework is graded based on correctness. Each incorrect problem will decrease the total score by one point. This homework is out of 2 points.

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

Recommended VS Code Extensions

We recommend that you install the vscode-scheme extension so that parentheses are highlighted.

Before:

After:

In addition, the 61a-bot (installation instructions) VS Code extension is available for Scheme homeworks. The bot is also integrated into ok.

Required Questions

Linked Lists

class Link:
    """A linked list is either a Link object or Link.empty

    >>> s = Link(3, Link(4, Link(5)))
    >>> s.rest
    Link(4, Link(5))
    >>> s.rest.rest.rest is Link.empty
    True
    >>> s.rest.first * 2
    8
    >>> print(s)
    (3 4 5)
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '('
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + ')'

>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> s
Link(1, Link(2, Link(3, Link(4))))
>>> s.first = 9
>>> s
Link(9, Link(2, Link(3, Link(4))))

>>> s = link(1, link(2, link(3, link(4))))
>>> s
[1, [2, [3, [4, 'empty']]]]
>>> first(s) = 9
  File "", line 1
SyntaxError: can't assign to function call

Q1: Add Links

Write a function add_link that takes in two linked lists, link1 and link2, and returns a new linked list that concatenates link2 to the end of link1.

You may assume that the input list is shallow; none of its elements are themselves another linked list.

Note: You may not assume that the input lists are of the same length.

Challenge (Optional): Do NOT assume that the input list is shallow (i.e. your input can be a nested linked list). Hint: use the built-in type function.

def add_links(link1: Link, link2: Link) -> Link:
    """Adds two Links, returning a new Link

    >>> l1 = Link(1, Link(2))
    >>> l2 = Link(3, Link(4, Link(5)))
    >>> new = add_links(l1, l2)
    >>> print(new)
    (1 2 3 4 5)
    >>> new2 = add_links(l2,l1)
    >>> print(new2)
    (3 4 5 1 2)
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q add_links
Copy
✂️

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: Link) -> None:
    """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))))
    >>> square = lambda x: x * x
    >>> print(link1)
    (3 (4) 5 6)
    >>> link2 = Link(1, Link(Link(Link(2, Link(3))), Link(4)))
    >>> double = lambda x: x * 2
    >>> print(link2)
    (1 ((2 3)) 4)
    >>> # 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(square, link1)
    ...     deep_map_mut(double, link2)
    ... finally:
    ...     Link.__init__ = hold
    >>> print(link1)
    (9 (16) 25 36)
    >>> print(link2)
    (2 ((4 6)) 8)
    """
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q deep_map_mut
Copy
✂️

Efficiency

def bar(n):
    for a in range(n):
        for b in range(n):
            print(a,b)

def rec(n):
    if n == 0:
        return 1
    else:
        return rec(n - 1) + rec(n - 1)

Q3: Prime

Write a function that returns whether a number is prime or not in O(sqrt(n)) time, where sqrt means square root. You can assume n >= 2.

Hint: you don't need to check whether every single number that is smaller than n divides n

from math import sqrt
def is_prime_sqrt(n: int) -> bool:
    """Tests whether a number N is prime or not. Implement this function
    in O(sqrt(n)) time. You can assume n >= 2

    >>> is_prime_sqrt(2)
    True
    >>> is_prime_sqrt(67092481)
    False
    >>> is_prime_sqrt(524287)
    True
    >>> is_prime_sqrt(2251748274470911)
    False
    >>> is_prime_sqrt(6700417)
    True
    >>> is_prime_sqrt(44895587973889)
    False
    >>> is_prime_sqrt(2147483647)
    True
    >>> is_prime_sqrt(67280421310721)
    True
    """
    # sqrt(k) will give the square root of k as a floating point (decimal)
    "*** YOUR CODE HERE ***"

Use Ok to test your code:

python3 ok -q is_prime_sqrt
Copy
✂️

Scheme

scm> (* 3 (+ 4 2))
18

scm> (+ 1 2)
3
scm> (- 10 (/ 6 2))
7
scm> (modulo 35 4)
3
scm> (even? (quotient 45 2))
#t

(define <symbol> <expression>)

scm> (define pi (+ 3 0.14))
pi
scm> pi
3.14

(cond
    (<p1> <e1>)
    (<p2> <e2>)
    ...
    (<pn> <en>)
    (else <else-expression>))

scm> (define x 5)
x
scm> (cond ((= (modulo x 3) 0) x)
            ((= (modulo x 3) 1) (- x 1))
            ((= (modulo x 3) 2) (+ x 1)))
6

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:

1. x^2y = (x^y)²
2. 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)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q pow
Copy
✂️

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

(define (repeatedly-cube n x)
    (if (zero? n)
        x
        (begin
            (define y ___)
            ___)))

Use Ok to test your code:

python3 ok -q repeatedly-cube
Copy
✂️

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)
  'YOUR-CODE-HERE
)

(define (caddr s)
  'YOUR-CODE-HERE
)

Use Ok to test your code:

python3 ok -q cadr-caddr
Copy
✂️

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!

1. Fall 2019 Final Q7b: Mull It Over
2. Spring 2018 Midterm 2 Q4(a): Sequences