Due at 11:59pm on 10/15/2015.

## Starter Files

Download lab07.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.

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

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
>>> len(s)
3
>>> s
3
>>> len(s)
0
"""
empty = ()

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

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 lab07.py into an interpreter or drawing out the diagram for the linked list on a piece of paper.

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

### Question 2: 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.

<1 2 3>
<9001 1 2 3>
<9001 1 100 2 3>
IndexError
"""
if index == 0:
raise IndexError
else:

# iterative solution
index -= 1
if index == 0:
else:
raise IndexError``````

Use OK to test your code:

``python3 ok -q insert``

## Trees (Again)

As we saw in lecture, we can also represent trees as objects.

``````class Tree:
def __init__(self, entry, branches=()):
self.entry = entry
for branch in branches:
assert isinstance(branch, Tree)
self.branches = list(branches)

def __repr__(self):
if self.branches:
branches_str = ', ' + repr(self.branches)
else:
branches_str = ''
return 'Tree({0}{1})'.format(self.entry, branches_str)

def is_leaf(self):
return not self.branches``````

### Question 3: WWPP: Trees

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

``python3 ok -q trees -u``

Hint: Remember for all WWPP questions, enter `Function` if you believe the answer is `<function ...>` and `Error` if it errors.

``````>>> from lab07 import *
>>> t = Tree(1, Tree(2))
______Error
>>> t = Tree(1, [Tree(2)])
>>> t.entry
______1
>>> t.branches
______Tree(2)
>>> t.branches.entry
______2
>>> t.entry = t.branches.entry
>>> t
______Tree(2, [Tree(2)])
>>> t.branches.append(Tree(4, [Tree(8)]))
>>> len(t.branches)
______2
>>> t.branches
______Tree(2)
>>> t.branches
______Tree(4, [Tree(8)])``````

### Question 4: Same Shape

Write a function `same_shape` that returns `True` if two `Tree`s have the same shape. Two trees have the same shape if they have the same number of children and each of their children have the same shape.

``````def same_shape(t1, t2):
"""Returns whether two Trees t1, t2 have the same shape. Two trees have the
same shape if they have the same number of branches and each of their
children have the same shape.

>>> t, s = Tree(1), Tree(3)
>>> same_shape(t, t)
True
>>> same_shape(t, s)
True
>>> t = Tree(1, [Tree(2), Tree(3)])
>>> same_shape(t, s)
False
>>> s = Tree(4, [Tree(7)])
>>> same_shape(t, s)
False
"""
return len(t1.branches) == len(t2.branches) and \
all(same_shape(st1, st2) for st1, st2 in zip(t1.branches, t2.branches))``````

Use OK to test your code:

``python3 ok -q same_shape``

## Extra Questions

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

### Question 5: Cumulative Sum

Write a function `cumulative_sum` that returns a new `Tree`, where each entry is the sum of all entries in the corresponding subtree of the old `Tree`.

``````def cumulative_sum(t):
"""Return a new Tree, where each entry is the sum of all entries in the
corresponding subtree of t.

>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> cumulative = cumulative_sum(t)
>>> t
Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> cumulative
Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
>>> cumulative_sum(Tree(1))
Tree(1)
"""
subtrees = [cumulative_sum(st) for st in t.branches]
new_entry = sum(st.entry for st in subtrees) + t.entry
return Tree(new_entry, subtrees)``````

Use OK to test your code:

``python3 ok -q cumulative_sum``

### Question 6: 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.

<1 2 3>
"""
if not lst:
else:

Use OK to test your code:

``python3 ok -q list_to_link``

### Question 7: 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 8: 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.

<1>
<3 2 1>
<1 2 3>
"""
return new

# Recursive solution
return t
else:

Use OK to test your code:

``python3 ok -q reverse``

### Question 9: 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``

### Question 10: 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``

### Motivation

Since you are already familiar with Python's built-in lists, you might be wondering why we are teaching you another list representation. There are historical reasons, along with practical reasons. Later in the term, you'll be programming in Scheme, which is a programming language that uses linked lists for almost everything. But let's not worry about that for now. The real reason, is that certain operations are faster with linked lists.

Python's built-in list is like a sequence of containers with indices on them: Linked lists are a list of items pointing to their neighbors. Notice that there's no explicit index for each item. Suppose we want to add an item at the head of the list.

• With Python's built-in list, if you want to put an item into the container labeled with index 0, you must move all the items in the list into its neighbor containers to make room for the first item; • With a linked list, you tell Python that the neighbor of the new item is the old beginning of the list. To test this, in your terminal, enter the following command: ```python3 timing.py insert 100000```, which inserts 100,000 items into the beginning of both a linked list and a Python built-in list to compare the speed.

Now, say we want the item at index 3.

• In the built-in list, you can simply grab the item from the container with 3 labeled on it;
• In the linked list, you need to start at the first item, and go to its neighbor's neighbor's neighbor to finally reach the item at index 3.

To test this, enter the following command in your terminal: ```python3 timing.py index 10000```. This program compares the speed of randomly accessing 10,000 items from both a linked list and a built-in Python list (each with length 10,000).

You'll learn more about orders of growth this week, which will provide mathematical rigor when comparing the runtime of the same operations with different data structures.