Lab 7: Generators, Linked Lists, and Trees
Due by 11:59pm on Friday, October 18.
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.
Check that you have successfully submitted your code on
okpy.org.
Required Questions
What Would Python Display?
Q1: WWPD: Linked Lists
Read over the Link
class in lab07.py
. Make sure you understand the
doctests.
Use Ok to test your knowledge with the following "What Would Python Display?" questions:
python3 ok -q link -u
Enter
Function
if you believe the answer is<function ...>
,Error
if it errors, andNothing
if nothing is displayed.If you get stuck, try drawing out the box-and-pointer diagram for the linked list on a piece of paper or loading the
Link
class into the interpreter withpython3 -i lab07.py
.
>>> from lab07 import *
>>> link = Link(1000)
>>> link.first
______1000
>>> link.rest is Link.empty
______True
>>> link = Link(1000, 2000)
______AssertionError
>>> link = Link(1000, Link())
______TypeError
>>> from lab07 import *
>>> link = Link(1, Link(2, Link(3)))
>>> link.first
______1
>>> link.rest.first
______2
>>> link.rest.rest.rest is Link.empty
______True
>>> link.first = 9001
>>> link.first
______9001
>>> link.rest = link.rest.rest
>>> link.rest.first
______3
>>> link = Link(1)
>>> link.rest = link
>>> link.rest.rest.rest.rest.first
______1
>>> link = Link(2, Link(3, Link(4)))
>>> link2 = Link(1, link)
>>> link2.first
______1
>>> link2.rest.first
______2
Q2: WWPD: Trees
Use Ok to test your knowledge with the following "What Would Python Display?" questions:
python3 ok -q trees-wwpd -u
Enter
Function
if you believe the answer is<function ...>
,Error
if it errors, andNothing
if nothing is displayed. Recall thatTree
instances will be displayed the same way they are constructed.
>>> from lab07 import *
>>> t = Tree(1, Tree(2))
______Error
>>> t = Tree(1, [Tree(2)])
>>> t.label
______1
>>> t.branches[0]
______Tree(2)
>>> t.branches[0].label
______2
>>> t.label = t.branches[0].label
>>> t
______Tree(2, [Tree(2)])
>>> t.branches.append(Tree(4, [Tree(8)]))
>>> len(t.branches)
______2
>>> t.branches[0]
______Tree(2)
>>> t.branches[1]
______Tree(4, [Tree(8)])
Generators
Iterators also allow us to represent infinite sequences, such as the sequence of natural numbers (1, 2, ...).
class Naturals:
"""
>>> m = Naturals()
>>> [next(m) for _ in range(5)]
[1, 2, 3, 4, 5]
"""
def __init__(self):
self.current = 0
def __iter__(self):
return self
def __next__(self):
self.current += 1
return self.current
Q3: Scale
Implement the generator function scale(s, k)
, which yields elements of the
given iterable s
, scaled by k
. As an extra challenge, try writing this
function using a yield from
statement!
def scale(s, k):
"""Yield elements of the iterable s scaled by a number k.
>>> s = scale([1, 5, 2], 5)
>>> type(s)
<class 'generator'>
>>> list(s)
[5, 25, 10]
>>> m = scale(naturals(), 2)
>>> [next(m) for _ in range(5)]
[2, 4, 6, 8, 10]
"""
"*** YOUR CODE HERE ***"
for elem in s:
yield elem * k
# Alternate solution
def scale(s, k):
yield from map(lambda x: x*k, s)
Use Ok to test your code:
python3 ok -q scale
Linked Lists
Q4: Link to List
Write a function link_to_list
that takes in a linked list and returns the
sequence as a Python list. You may assume that the input list is shallow; none
of the elements is another linked list.
Try to find both an iterative and recursive solution for this problem!
def link_to_list(link):
"""Takes a linked list 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 ***"
# Recursive solution
if link is Link.empty:
return []
return [link.first] + link_to_list(link.rest)
# Iterative solution
def link_to_list(link):
result = []
while link is not Link.empty:
result.append(link.first)
link = link.rest
return result
# Video Walkthrough: https://youtu.be/hdO9Ry8d5FU?t=25m6s
Use Ok to test your code:
python3 ok -q link_to_list
Trees
Q5: Cumulative Sum
Write a function cumulative_sum
that mutates the Tree t
so that each node's
label becomes the sum of all labels in the subtree rooted at the node.
def cumulative_sum(t):
"""Mutates t so that each node's label becomes the sum of all labels 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 ***"
for b in t.branches:
cumulative_sum(b)
t.label = sum([b.label for b in t.branches]) + t.label
Use Ok to test your code:
python3 ok -q cumulative_sum
Q6: 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 label of the node
- For every node, the entries in that node's right child are greater than the label 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.
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
>>> t7 = Tree(2, [Tree(1, [Tree(5)]), Tree(4)])
>>> is_bst(t7)
False
"""
"*** YOUR CODE HERE ***"
def bst_min(t):
"""Returns the min of t, if t has the structure of a valid BST."""
if t.is_leaf():
return t.label
return min(t.label, bst_min(t.branches[0]))
def bst_max(t):
"""Returns the max of t, if t has the structure of a valid BST."""
if t.is_leaf():
return t.label
return max(t.label, bst_max(t.branches[-1]))
if t.is_leaf():
return True
if len(t.branches) == 1:
c = t.branches[0]
return is_bst(c) and (bst_max(c) <= t.label or bst_min(c) > t.label)
elif len(t.branches) == 2:
c1, c2 = t.branches
valid_branches = is_bst(c1) and is_bst(c2)
return valid_branches and bst_max(c1) <= t.label and bst_min(c2) > t.label
else:
return False
Use Ok to test your code:
python3 ok -q is_bst