# Homework 7

*Due by 11:59pm on Sunday, 7/24*

## Instructions

Download hw07.zip. Inside the archive, you will find a file called hw07.py, 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. See Lab 0 for 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:

## Linked Lists

### Question 1: 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.
>>> link = Link(1, Link(2, Link(3, Link(4))))
>>> link_to_list(link)
[1, 2, 3, 4]
>>> link_to_list(Link.empty)
[]
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q link_to_list`

### Question 2: 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 = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> has_cycle(s)
True
>>> t = Link(1, Link(2, Link(3)))
>>> has_cycle(t)
False
>>> u = Link(2, Link(2, Link(2)))
>>> has_cycle(u)
False
"""
"*** YOUR CODE HERE ***"
```

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!* **The questions
after this are still required.**

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 = Link(1, Link(2, Link(3)))
>>> s.rest.rest.rest = s
>>> has_cycle_constant(s)
True
>>> t = Link(1, Link(2, Link(3)))
>>> has_cycle_constant(t)
False
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q has_cycle_constant`

## Trees

### Question 3: Cumulative Sum

Write a function `cumulative_sum`

that mutates the Tree `t`

, where each node's
entry becomes the sum of all entries in the subtree rooted at the node.

```
def cumulative_sum(t):
"""Mutates t where each node's entry 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)])
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q cumulative_sum`

### Question 4: Is BST

Write a function `is_bst`

, which takes a Tree `t`

and returns `True`

if, and
only if, `t`

is a valid binary search tree, which means that:

- Each node has at most two children (a leaf is automatically a valid binary search tree)
- The children are valid binary search trees
- For every node, the entries in that node's left child are less than or equal to the entry of the node
- For every node, the entries in that node's right child are greater than the entry of the node

Note that, if a node has only one child, that child could be considered either
the left or right child. You should take this into consideration. **Do not use
the** `BST`

**constructor or anything from the** `BST`

**class.**

*Hint:* It may be helpful to write helper functions `bst_min`

and `bst_max`

that
return the minimum and maximum, respectively, of a Tree if it is a valid binary
search tree.

```
def is_bst(t):
"""Returns True if the Tree t has the structure of a valid BST.
>>> t1 = Tree(6, [Tree(2, [Tree(1), Tree(4)]), Tree(7, [Tree(7), Tree(8)])])
>>> is_bst(t1)
True
>>> t2 = Tree(8, [Tree(2, [Tree(9), Tree(1)]), Tree(3, [Tree(6)]), Tree(5)])
>>> is_bst(t2)
False
>>> t3 = Tree(6, [Tree(2, [Tree(4), Tree(1)]), Tree(7, [Tree(7), Tree(8)])])
>>> is_bst(t3)
False
>>> t4 = Tree(1, [Tree(2, [Tree(3, [Tree(4)])])])
>>> is_bst(t4)
True
>>> t5 = Tree(1, [Tree(0, [Tree(-1, [Tree(-2)])])])
>>> is_bst(t5)
True
>>> t6 = Tree(1, [Tree(4, [Tree(2, [Tree(3)])])])
>>> is_bst(t6)
True
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q is_bst`

## Python Sets

A set is an **unordered** collection of **distinct** objects that supports
membership testing, union, intersection, and adjunction. The main differences
between sets and lists are that sets are unordered and contain no duplicates.
Other than that, almost everything is the same.

```
>>> a = [1, 1, 2, 2, 3, 3]
>>> a = set(a)
>>> a # No duplicates
{1, 2, 3}
>>> a = {3, 1, 2}
>>> a # Not necessarily in same order
{1, 2, 3}
```

The Python documentation on
sets has more
details. The main things you will use with sets include: `in`

, `union`

(`|`

),
`intersection`

(`&`

), and `difference`

(`-`

).

One really convenient thing about Python sets is that many operations on sets (adding elements, removing elements, checking membership) run in θ(1) (constant) time (usually).

Some of the problems use a utility method called `timeit`

, which takes a
parameterless function as argument, executes it, and returns the time required
to do so. It's a variation on the function `timeit.timeit`

function in the
Python3 library.

The following problem will be used as part of the AutoStyle study, which you can find more information about on Piazza. Participation in this study will be rewarded with extra credit.

### Question 5: Add Up

Write the following function so it (usually) runs in θ(m) time, where m is
the length of `lst`

.

```
def add_up(n, lst):
"""Returns True if any two non identical elements in lst add up to n.
>>> add_up(100, [1, 2, 3, 4, 5])
False
>>> add_up(7, [1, 2, 3, 4, 2])
True
>>> add_up(10, [5, 5])
False
>>> add_up(151, range(0, 200000, 2))
False
>>> timeit(lambda: add_up(151, range(0, 200000, 2))) < 1.0
True
>>> add_up(50002, range(0, 200000, 2))
True
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q add_up`

Now you have the chance to improve your coding style for this question. Once you have passed all the tests, invoke AutoStyle by running the command

`python3 ok --style -q add_up`

. AutoStyle will provide to you hints that improve the style of your code.

### Question 6: Missing Value

Write the following function so it (usually) runs in θ(n) time, where n is
the length of `lst0`

.

```
def missing_val(lst0, lst1):
"""Assuming that lst0 contains all the values in lst1, but lst1 is missing
one value in lst0, return the missing value. The values need not be
numbers.
>>> from random import shuffle
>>> missing_val(range(10), [1, 0, 4, 5, 7, 9, 2, 6, 3])
8
>>> big0 = [str(k) for k in range(15000)]
>>> big1 = [str(k) for k in range(15000) if k != 293 ]
>>> shuffle(big0)
>>> shuffle(big1)
>>> missing_val(big0, big1)
'293'
>>> timeit(lambda: missing_val(big0, big1)) < 1.0
True
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q missing_val`