Homework 6
Due by 11:59pm on Wednesday, 10/21
Instructions
Download hw06.zip. Inside the archive, you will find a file called hw06.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 Survey
Complete the mid-semester survey to receive full credit for this homework.
Review Questions (Optional)
All of these questions are optional, but should serve as useful review.
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
Implement mutate_reverse
, which takes a linked list instance and mutates it
so that its values appear in reverse order. For an extra challenge, find an
implementation that requires only linear time in the length of the list
(big-Theta n).
def mutate_reverse(link):
"""Mutates the Link so that its elements are reversed.
>>> link = Link(1)
>>> mutate_reverse(link)
>>> link
Link(1)
>>> link = Link(1, Link(2, Link(3)))
>>> mutate_reverse(link)
>>> link
Link(3, Link(2, Link(1)))
"""
"*** YOUR CODE HERE ***"
Use OK to test your code:
python3 ok -q mutate_reverse
Question 3
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
branch 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 branch order i.e. 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)
...
Link(0, Link(1, Link(2)))
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(5))))
Link(0, Link(6, Link(7, Link(8))))
Link(0, Link(6, Link(9)))
Link(0, Link(11, Link(12)))
>>> for path in long_paths(whole, 3):
... print(path)
...
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(4))))
Link(0, Link(1, Link(3, Link(5))))
Link(0, Link(6, Link(7, Link(8))))
>>> long_paths(whole, 4)
[]
"""
"*** YOUR CODE HERE ***"
Question 4
The sequence_to_tree
function takes a sorted linked list and converts it into
a balanced Tree
in which every sub-tree has at most two branches. For every
subtree with 2 branches, all nodes in the left branch are smaller than the root
of the subtree and all nodes in the right branch are larger.
A Tree
is balanced if
- It is a leaf, or
- It has exactly one branch that is a leaf, or
- It has two branches and the number of nodes in its first branch differs from the number of nodes in its second branch by at most 1, and both branches are also balanced.
In order to write sequence_to_tree
, implement partial_tree(s, n)
,
which converts the first n
elements of the sorted linked list s
into a
balanced Tree
. 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 nextright_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.
Examples of balanced trees:
Tree(1) # leaf
Tree(1, [Tree(2)]) # one branch is a leaf
Tree(1, [Tree(2), Tree(3)]) # two branches with one node each
Examples of unbalanced trees:
Tree(1, [Tree(2, [Tree(3)])]) # one branch not a leaf
Tree(1, [Tree(2), # Mismatch: branch with 1 node
Tree(3, [Tree(4, [Tree(5)])])]) # vs branch with 3 nodes
>>> s = Link(1, Link(2, Link(3, Link(4, Link(5)))))
>>> partial_tree(s, 3)
(Tree(2, [Tree(1), Tree(3)]), Link(4, Link(5)))
>>> t = Link(-2, Link(-1, Link(0, s)))
>>> partial_tree(t, 7)[0]
Tree(1, [Tree(-1, [Tree(-2), Tree(0)]), Tree(3, [Tree(2), Tree(4)])])
>>> partial_tree(t, 7)[1]
Link(5)
"""
if n == 1:
return (Tree(s.first), s.rest)
elif n == 2:
return (Tree(s.first, [Tree(s.rest.first)]), s.rest.rest)
else:
left_size = (n-1)//2
right_size = n - left_size - 1
"*** YOUR CODE HERE ***"
def sequence_to_tree(s):
"""Return a balanced tree containing the elements of sorted Link s.
Note: this implementation is complete, but the definition of partial_tree
above is not complete.
>>> sequence_to_tree(Link(1, Link(2, Link(3))))
Tree(2, [Tree(1), Tree(3)])
>>> elements = Link(1, Link(2, Link(3, Link(4, Link(5, Link(6, Link(7)))))))
>>> sequence_to_tree(elements)
Tree(4, [Tree(2, [Tree(1), Tree(3)]), Tree(6, [Tree(5), Tree(7)])])
"""
return partial_tree(s, len(s))[0]
Use OK to test your code:
python3 ok -q partial_tree
python3 ok -q sequence_to_tree