# Homework 7

*Due by 11:59pm on Saturday, 7/25*

## 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 1 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:

## Required questions

### Question 1

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'
>>> s.rest.rest is Link.empty
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).
>>> s = Link(1, Link(2, Link(3, Link(4))))
>>> every_other(s)
>>> s
Link(1, Link(3))
>>> odd_length = Link(5, Link(3, Link(1)))
>>> every_other(odd_length)
>>> odd_length
Link(5, Link(1))
>>> singleton = Link(4)
>>> every_other(singleton)
>>> singleton
Link(4)
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q every_other`

### Question 2

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(s):
"""Return whether Link s 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
"""
"*** YOUR CODE HERE ***"
```

Use OK to test your code:

`python3 ok -q has_cycle`

### Question 3

The `ordered_sequence_to_tree`

function takes a sorted linked list and converts
it into a balanced `BinaryTree`

. A `BinaryTree`

is balanced if

- the number of entries in its left branch differs from the number of entries in its right branch by at most 1, and
- its non-empty branches are also balanced trees.

In order to write `ordered_sequence_to_tree`

, implement `partial_tree(s, n)`

,
which converts the first `n`

elements of the sorted linked list `s`

into a
balanced `BinaryTree`

. The return value is a two-element tuple: the resulting
balanced tree; and the rest of the linked list.

Hint: This function requires two recursive calls. The first call builds a left branch out of the first`left_size`

elements of s; Then, the next element is used as the entry of the returned tree. Finally, the second recursive call builds the right branch out of the next`right_size`

elements. In total,`(left_size + 1 + right_size) = n`

, where 1 is for the entry:

```
def partial_tree(s, n):
"""Return a balanced tree of the first n elements of Link s, along with
the rest of s. A tree is balanced if
(a) the number of entries in its left branch differs from the number
of entries in its right branch by at most 1, and
(b) its non-empty branches are also balanced trees.
Examples of balanced trees:
BinaryTree(1) # branch difference 0 - 0 = 0
BinaryTree(1, BinaryTree(2), None) # branch difference 1 - 0 = 1
BinaryTree(1, None, BinaryTree(2)) # branch difference 0 - 1 = -1
BinaryTree(1, BinaryTree(2), BinaryTree(3)) # branch difference 1 - 1 = 0
Examples of unbalanced trees:
# branch difference 2 - 0 = 2
BinaryTree(1, BinaryTree(2, BinaryTree(3)), None)
# Unbalanced right branch
BinaryTree(1, BinaryTree(2, BinaryTree(3), None),
BinaryTree(4, BinaryTree(5, BinaryTree(6), None), None))
>>> s = Link(1, Link(2, Link(3, Link(4, Link(5)))))
>>> partial_tree(s, 3)
(BinaryTree(2, BinaryTree(1), BinaryTree(3)), Link(4, Link(5)))
>>> t = Link(-2, Link(-1, Link(0, s)))
>>> partial_tree(t, 7)[0]
BinaryTree(1, BinaryTree(-1, BinaryTree(-2), BinaryTree(0)), BinaryTree(3, BinaryTree(2), BinaryTree(4)))
>>> partial_tree(t, 7)[1]
Link(5)
"""
if n == 0:
return BinaryTree.empty, s
left_size = (n-1)//2
right_size = n - left_size - 1
"*** YOUR CODE HERE ***"
def ordered_sequence_to_tree(s):
"""Return a balanced tree containing the elements of ordered Link s.
Note: this implementation is complete, but the definition of partial_tree
above is not complete.
>>> ordered_sequence_to_tree(Link(1, Link(2, Link(3))))
BinaryTree(2, BinaryTree(1), BinaryTree(3))
>>> elements = Link(1, Link(2, Link(3, Link(4, Link(5, Link(6, Link(7)))))))
>>> ordered_sequence_to_tree(elements)
BinaryTree(4, BinaryTree(2, BinaryTree(1), BinaryTree(3)), BinaryTree(6, BinaryTree(5), BinaryTree(7)))
"""
return partial_tree(s, len(s))[0]
```

Use OK to test your code:

```
python3 ok -q partial_tree
python3 ok -q ordered_sequence_to_tree
```

## Extra question

Extra questions are not worth extra credit and are entirely optional. They are designed to challenge you to think creatively!

### Question 4

Implement `has_cycle_constant`

, which has the same behavior as `has_cycle`

but
requires only constant 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(s):
"""Return whether Link s 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`