Homework 8 | CS 88 Spring 2020

Due at 11:59:59 pm on Sunday, 4/5/2020.

Instructions

Download hw08.zip. Inside the archive, you will find starter files for the questions in this homework, along with a copy of the OK autograder.

Submission: When you are done, submit with python3 ok --submit. 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 okpy.org. See this article for more instructions on okpy and submitting assignments.

Readings: This homework relies on following references:

Section 2.9

Practice with Linked Lists!

Question 1: List to Link

Write a function list_to_link that converts a Python list to a Link.

def list_to_link(lst):
    """Takes a Python list and returns a Link with the same elements.

    >>> link = list_to_link([1, 2, 3])
    >>> print_link(link)
    <1 2 3>
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q list_to_link

Question 2: Mutable Mapping

Implement deep_map_mut(fn, link), which applies a function fn onto all elements in the given linked list link. If an element is itself a linked list, apply fn to each of its elements, and so on.

Your implementation should mutate the original linked list. Do not create any new linked lists.

Hint: The built-in isinstance function may be useful.
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> isinstance(s, Link)
True
>>> isinstance(s, int)
False

def deep_map_mut(fn, link):
    """Mutates a deep link by replacing each item found with the
    result of calling fn 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))))
    >>> deep_map_mut(lambda x: x * x, link1)
    >>> print_link(link1)
    <9 <16> 25 36>
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q deep_map_mut

Question 3: Reverse

Implement reverse, which takes a linked list link and returns a linked list containing the elements of link in reverse order. The original link should be unchanged.

def reverse(link):
    """Returns a Link that is the reverse of the original.

    >>> print_link(reverse(Link(1)))
    <1>
    >>> link = Link(1, Link(2, Link(3)))
    >>> new = reverse(link)
    >>> print_link(new)
    <3 2 1>
    >>> print_link(link)
    <1 2 3>
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q reverse

Question 4: Mutate Reverse

Implement mutate_reverse, which takes a linked list instance and mutates it so that its values appear in reverse order. For an extra challenge, find an implementation that requires only linear time in the length of the list (big-Theta n).

def mutate_reverse(link):
    """Mutates the Link so that its elements are reversed.

    >>> link = Link(1)
    >>> mutate_reverse(link)
    >>> link
    Link(1)

    >>> link = Link(1, Link(2, Link(3)))
    >>> mutate_reverse(link)
    >>> link
    Link(3, Link(2, Link(1)))
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q mutate_reverse

Question 5: Insert

Implement a function insert that takes a Link, a value, and an index, and inserts the value into the Link at the given index. You can assume the linked list already has at least one element. Do not return anything — insert should mutate the linked list.

Note: If the index is out of bounds, you can raise an IndexError with:
raise IndexError

def insert(link, value, index):
    """Insert a value into a Link at the given index.

    >>> link = Link(1, Link(2, Link(3)))
    >>> print_link(link)
    <1 2 3>
    >>> insert(link, 9001, 0)
    >>> print_link(link)
    <9001 1 2 3>
    >>> insert(link, 100, 2)
    >>> print_link(link)
    <9001 1 100 2 3>
    >>> insert(link, 4, 5)
    IndexError
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q insert

Question 6: Slice

Implement a function slice_link that slices a given link. slice_link should slice the link starting at start and ending one element before end, as with a normal Python list.

def slice_link(link, start, end):
    """Slices a Link from start to end (as with a normal Python list).

    >>> link = Link(3, Link(1, Link(4, Link(1, Link(5, Link(9))))))
    >>> new = slice_link(link, 1, 4)
    >>> print_link(new)
    <1 4 1>
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q slice_link

Optional Questions

Question 7: Rotate

Implement rotate, which takes a linked list link and a number n, and returns a linked list containing the elements of link shifted to the right n times.

def rotate(link, n):
    """Rotates the Link so that its elements are shifted to the right n times.

    >>> link = Link(1, Link(2, Link(3)))
    >>> link = rotate(link, 0)
    >>> link
    Link(1, Link(2, Link(3)))
    >>> link = rotate(link, 1)
    >>> link
    Link(3, Link(1, Link(2)))
    >>> link = rotate(link, 2)
    >>> link
    Link(1, Link(2, Link(3)))
    >>> rotate(link, 5)
    Link(2, Link(3, Link(1)))
    >>> link = Link(1, Link(2, Link(3, Link(4, Link(5, Link(6))))))
    >>> rotate(link, 4)
    Link(3, Link(4, Link(5, Link(6, Link(1, Link(2))))))
    """
    "*** YOUR CODE HERE ***"

Use OK to test your code:

python3 ok -q rotate