Due at 11:59:59 pm on 4/3/2020.

## Starter Files

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

## Submission

By the end of this lab, you should have submitted the lab with `python3 ok --submit`. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

• To receive credit for this lab, you must complete Questions 1, 2, 3, 4, and 5 in lab08.py and submit through OK.
• Questions 6 and 7 are extra practice. They can be found in the lab08_extra.py file. It is recommended that you complete these problems on your own time for extra practice.

## Midsemester Survey

We have posted an optional survey that you can complete to give us feedback and help us make the course even better! Completing this survey will yield 1 Extra Credit Point that will be added at the end of the semester.

A linked list is either an empty linked list (`Link.empty`) or a first value and the rest of the linked list.

``````class Link:
"""
>>> s
"""
empty = ()

def __init__(self, first, rest=empty):
self.first = first
self.rest = rest

def __repr__(self):
rest_str = ', ' + repr(self.rest)
else:
rest_str = ''

To check if a `Link` is empty, compare it against the class attribute `Link.empty`. For example, the below function prints out whether or not the link it is handed is empty:

``````def test_empty(link):
else:
print('This linked list is not empty!')``````

Note: Linked lists are recursive data structures! A linked list contains the first element of the list (`first`) and a reference to another linked list (`rest`) which contains the rest of the values in the list.

### Question 1: WWPP: Linked Lists

Use OK to test your knowledge with the following "What Would Python Print?" questions:

``python3 ok -q link -u``

If you get stuck, try loading lab09.py into an interpreter or drawing out the diagram for the linked list on a piece of paper.

``````>>> from lab09 import *
______1
______2
______True
______9001
______3
______1
______1
______2
______<1 2 3 4>``````

### Question 2: Link to List

Write a function `link_to_list` that converts a given `Link` to a Python list.

``````def link_to_list(link):
"""Takes a Link and returns a Python list with the same elements.

[1, 2, 3, 4]
[]
"""
# Recursive solution
return []

# Iterative solution
result = []
return result``````

Use OK to test your code:

``python3 ok -q link_to_list``

### Question 3: Deep Map

Implement `deep_map`, which takes a function `f` and a `link`. It returns a new linked list with the same structure as `link`, but with `f` applied to any element within `link` or any `Link` instance contained in `link`.

The `deep_map` function should recursively apply `fn` to each of that `Link`'s elements rather than to that `Link` itself.

Hint: You may find the built-in `isinstance` function useful.

``````def deep_map(f, link):
"""Return a Link with the same structure as link but with fn mapped over
its elements. If an element is an instance of a linked list, recursively
apply f inside that linked list as well.

>>> print_link(deep_map(lambda x: x * x, s))
<1 <4 9> 16>
<1 <2 3> 4>
<<2 <4 6> 8> <<10>>>
"""
else:

Use OK to test your code:

``python3 ok -q deep_map``

Let's implement a method in order to add together items of `link1` and `link2`. Do not assume that the links are the same length.

``````def add_links(link1, link2):

<1 2 3 4 5>
"""
else:

# Iterative version (using reverse)
return reverse(result)``````

Use OK to test your code:

``python3 ok -q add_links``

### Question 5: Every Other

Implement `every_other`, which takes a linked list `s`. It mutates `s` such that all of the odd-indexed elements (using 0-based indexing) are removed from the list. For example:

``````>>> s = Link('a', Link('b', Link('c', Link('d'))))
>>> every_other(s)
>>> s.first
'a'
>>> s.rest.first
'c'
True``````

If `s` contains fewer than two elements, `s` remains unchanged.

Do not return anything! `every_other` should mutate the original list.

``````def every_other(s):
"""Mutates a linked list so that all the odd-indiced elements are removed
(using 0-based indexing).

>>> every_other(s)
>>> s
>>> every_other(odd_length)
>>> odd_length
>>> every_other(singleton)
>>> singleton
"""
return
else:
s.rest = s.rest.rest
every_other(s.rest)``````

Use OK to test your code:

``python3 ok -q every_other``

## Extra Questions

The following questions are for extra practice — they can be found in the the lab08_extra.py file. It is recommended that you complete these problems on your own time.

### Question 6: Find Intersection

Implement `intersection`, which takes two linked lists, `xs` and `ys`, and finds the `Link` at which the two linked list begin to intersect (or overlap). Remember that all `Link`s end with `Link.empty`, so there will always be some overlap.

For the two linked lists below, `z1` should be the start of the linked list that you return. Note that you should be comparing with identity, rather than equality; an intersection means that some part of the `Link` is shared between `xs` and `ys`, not just that they have the same elements.

Try to aim for `θ(n)` runtime (where `n` is the sum of the lengths of `xs` and `ys`), and even `θ(1)` additional space.

``````xs:  x1 -> x2 -> z1 -> z2 -> z3 -> ...
^
|
ys:        y1 ---+``````
``````def intersection(xs, ys):
"""
True

>>> b = a
>>> intersection(a, b).first # intersection begins at a
1

>>> intersection(a, looks_like_a) is Link.empty # no intersection! (identity vs value)
True

>>> a.first = 5
>>> intersection(a, b).first # intersection begins at a
5

>>> intersection(b, c).first # intersection begins at b
1
>>> intersection(c, b).first # intersection begins at b
1

>>> intersection(a, c).first # intersection begins at a
5
"""

# make xs and ys the same size
if len(xs) < len(ys):
return intersection(xs, ys.rest)
elif len(xs) > len(ys):
return intersection(xs.rest, ys)

# comparison
while xs is not ys:
xs, ys = xs.rest, ys.rest
return xs``````

Use OK to test your code:

``python3 ok -q intersection``

### Question 7: Cycles

The `Link` class can represent lists with cycles. That is, a list may contain itself as a sublist.

``````>>> s = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> s.rest.rest.rest.rest.rest.first
3``````

Implement `has_cycle` that returns whether its argument, a `Link` instance, contains a cycle.

Hint: Iterate through the linked list and try keeping track of which `Link` objects you've already seen.

``````def has_cycle(link):
"""Return whether link contains a cycle.

>>> s.rest.rest.rest = s
>>> has_cycle(s)
True
>>> has_cycle(t)
False
>>> has_cycle(u)
False
"""
lists = set()
return True
return False``````

Use OK to test your code:

``python3 ok -q has_cycle``

Extra for experts: Implement `has_cycle` with only constant space. (If you followed the hint above, you will use linear space.) The solution is short (less than 20 lines of code), but requires a clever idea. Try to discover the solution yourself before asking around:

``````def has_cycle_constant(link):
"""Return whether link contains a cycle.

>>> s.rest.rest.rest = s
>>> has_cycle_constant(s)
True
>>> has_cycle_constant(t)
False
"""
return False
return False
elif fast == slow or fast.rest == slow:
return True
else:
slow, fast = slow.rest, fast.rest.rest
return False``````

Use OK to test your code:

``python3 ok -q has_cycle_constant``

## Submit

Make sure to submit this assignment by running:

``python3 ok --submit``

## Extra Credit Practice

These questions are new this semester. They're a mix of Parsons Problems, Code Tracing questions, and Code Writing questions.

Confused about how to use the tool? Check out https://codestyle.herokuapp.com/cs88-lab01 for some problems designed to demonstrate how to solve these types of problems.

These cover some similar material to lab, so can be helpful to further review or try to learn the material. Unlike lab and homework, after you've worked for long enough and tested your code enough times on any of these questions, you'll have the option to view an instructor solution. You'll unlock each question one at a time, either by correctly answering the previous question or by viewing an instructor solution.

Starting from lab 2 onward, each set of questions are worth half (0.5) a point per lab, for a total opportunity of 4-5 points throughout the semester.

Use OK to test your code:

``python3 ok -q extra_credit``