Due by 11:59pm on Monday, 7/24

## Instructions

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 Lab 0 for more instructions on submitting assignments.

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

# Homework Questions

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

Use OK to test your code:

``python3 ok -q every_other``

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

Hint: The built-in `isinstance` function may be useful.

``````>>> s = Link(1, Link(2, Link(3, Link(4))))
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

Does not return the modified Link object.

>>> deep_map_mut(lambda x: x * x, link1)
<9 <16> 25 36>
"""
``````

Use OK to test your code:

``python3 ok -q deep_map_mut``

### Question 3: Two List

Implement a function `two_list` that takes in two lists and returns a linked list. The first list contains the values that we want to put in the linked list, and the second list contains the number of each corresponding value. Assume both lists are the same size and have a length of 1 or greater. Assume all elements in the second list are greater than 0.

``````def two_list(lst1, lst2):
"""
Returns a linked list according to the two lists that were passed in. Assume
lst1 and lst2 are the same size. Elements in lst1 represent the value, and the
corresponding element in lst2 represents the number of this value is desired in the
final linked list. Assume all elements in lst2 are greater than 0. Assume both
lists have at least one element.

>>> a = [1, 3, 2]
>>> b = [1, 1, 1]
>>> c = two_list(a, b)
>>> c
>>> a = [1, 3, 2]
>>> b = [2, 2, 1]
>>> c = two_list(a, b)
>>> c
"""
``````

Use OK to test your code:

``python3 ok -q two_list``

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

Use OK to test your code:

``python3 ok -q has_cycle``

Extra question: This question is not worth extra credit and is entirely optional. It is designed to challenge you to think creatively!

Implement `has_cycle_constant` 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
"""
``````

Use OK to test your code:

``python3 ok -q has_cycle_constant``

## Trees

### Question 5: Cumulative Sum

Write a function `cumulative_sum` that mutates the Tree `t`, where each node's root becomes the sum of all entries in the subtree rooted at the node.

``````def cumulative_sum(t):
"""Mutates t where each node's root becomes the sum of all entries in the
corresponding subtree rooted at t.

>>> t = Tree(1, [Tree(3, [Tree(5)]), Tree(7)])
>>> cumulative_sum(t)
>>> t
Tree(16, [Tree(8, [Tree(5)]), Tree(7)])
"""
``````

Use OK to test your code:

``python3 ok -q cumulative_sum``

### Question 6: Prune Min

Write a function that prunes a tree t mutatively. Tree t and its branches always have zero branches or two branches. For the trees with two branches, reduce the number of branches from two to one by keeping the branch that has the smaller root value. Do nothing with trees with zero branches. Prune the tree from the bottom up. The result should be a linear tree.

``````def prune_min(t):
"""Prune the tree mutatively from the bottom up. Assume the tree and its branches always have either two branches or none. Prune the tree by
reducing the number of branches from two to one, choosing the branch with the smaller root value. Assume branches have differing root values.
Do nothing with trees with zero branches.

>>> t1 = Tree(6)
>>> prune_min(t1)
>>> t1
Tree(6)
>>> t2 = Tree(6, [Tree(3), Tree(4)])
>>> prune_min(t2)
>>> t2
Tree(6, [Tree(3)])
>>> t3 = Tree(6, [Tree(3, [Tree(1), Tree(2)]), Tree(5, [Tree(3), Tree(4)])])
>>> prune_min(t3)
>>> t3
Tree(6, [Tree(3, [Tree(1)])])
"""
``````

Use OK to test your code:

``python3 ok -q prune_min``

### Question 7: Long Paths

Implement `long_paths`, which returns a list of all paths in a tree with length at least `n`. A path in a tree is a linked list of node values that starts with the root and ends at a leaf. Each subsequent element must be from a child of the previous value's node. The length of a path is the number of edges in the path (i.e. one less than the number of nodes in the path). Paths are listed in order from left to right.

``````def long_paths(tree, n):
"""Return a list all paths in tree with length at least n.

>>> t = Tree(3, [Tree(4), Tree(4), Tree(5)])
>>> left = Tree(1, [Tree(2), t])
>>> mid = Tree(6, [Tree(7, [Tree(8)]), Tree(9)])
>>> right = Tree(11, [Tree(12)])
>>> whole = Tree(0, [left, Tree(13), mid, right])
>>> for path in long_paths(whole, 2):
...     print(path)
...
>>> for path in long_paths(whole, 3):
...     print(path)
...
``python3 ok -q long_paths``